Perfect Number

Q: Wie hoch ist die Zeitkomplexität beim Überprüfen, ob eine Zahl eine vollkommene Zahl ist?

Das Sammeln von Teilerpaaren bis √n benötigt O(√n) Zeit und O(1) Speicherplatz. Für n = 10^8 sind das etwa 10^4 Schritte. Das Testen jedes Kandidaten bis n / 2 hat eine Komplexität von O(n) und benötigt bei derselben Eingabe etwa 5 × 10^7 Schritte.

Q: Wie viele vollkommene Zahlen gibt es unter 10^8?

Fünf: 6 , 28 , 496 , 8128 und 33550336 . Sie werden schnell rar. Die nächste Zahl, 8589869056 , passt nicht einmal in eine 32-Bit-Ganzzahl.

Q: Gibt es ungerade vollkommene Zahlen?

Niemand weiß es. Jede bislang gefundene vollkommene Zahl ist gerade. Bei Suchen wurden ungerade vollkommene Zahlen unter 10^1500 ausgeschlossen, aber kein Beweis besagt, dass sie nicht existieren können. Deine Funktion muss anhand der Definition arbeiten und darf nicht einfach annehmen, dass die Eingabe gerade ist.

Q: Was ist der Unterschied zwischen vollkommenen, überreichlichen und defizienten Zahlen?

Vergleiche die Summe der echten Teiler mit der Zahl. Sind sie gleich, ist die Zahl vollkommen, wie 28 . Ist die Summe größer, ist die Zahl abundant, wie 12 , dessen Teiler sich zu 16 addieren. Ist die Summe kleiner, ist die Zahl defizient, wie jede Primzahl, deren einziger echter Teiler 1 ist.

EinsteigerMathe und Simulation

+10

Ein echter Teiler von n ist ein positiver Teiler, der kleiner als n selbst ist. Eine vollkommene Zahl ist gleich der Summe ihrer echten Teiler: 6 = 1 + 2 + 3. Du erhältst eine positive ganze Zahl n. Gib true zurück, wenn n vollkommen ist, andernfalls false.

Funktion

isPerfect(n: integer) → boolean

ninteger: die positive Ganzzahl, die getestet werden soll
Gibt zurückboolean: wahr, wenn n der Summe seiner echten Teiler entspricht, andernfalls falsch

Einschränkungen

1 ≤ n ≤ 10⁸

Beispiele

Eingabe: n = 28
Ausgabe: true
Erklärung: Die echten Teiler von 28 sind 1, 2, 4, 7 und 14. Sie ergeben zusammen 28, also ist 28 vollkommen.

Eingabe: n = 12
Ausgabe: false
Erklärung: Die echten Teiler von 12 sind 1, 2, 3, 4 und 6. Sie ergeben zusammen 16, was 12 übersteigt.

Eingabe: n = 1
Ausgabe: false
Erklärung: 1 hat überhaupt keinen echten Teiler, daher ist die Summe 0 und nicht 1.

+16 versteckte Tests beim Einreichen

Weiterführende Frage

Jede gerade vollkommene Zahl hat die Form 2^(p-1) × (2^p-1), wobei 2^p-1 prim ist. Kannst du mit dieser Formel alle vollkommenen Zahlen unterhalb von 10^8 auflisten, ohne jede Zahl zu testen?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Die Definition verlangt eine Summe von Teilern, und eine naheliegende Schleife probiert jeden möglichen Kandidaten bis n / 2 aus. Für n = 10^8 sind das 5 × 10^7 Divisionen. Teiler treten paarweise auf und multiplizieren sich zu n, sodass du beide Mitglieder jedes Paars sammeln kannst, während du nur bis √n suchst – etwa 10^4 Schritte.

Alle echten Teiler addieren

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Folge der Definition. Probiere jedes d ab 1 aufwärts aus und addiere, wenn n % d == 0 gilt, d zu einer laufenden Summe. Vergleiche am Ende die Summe mit n. Bei 28 nimmt die Schleife 1, 2, 4, 7 und 14 auf, und 1 + 2 + 4 + 7 + 14 = 28.

Du kannst bei n / 2 aufhören. Ein Teiler außer n ergibt einen Quotienten von mindestens 2 und ist daher nie größer als die Hälfte von n. Die Grenze gilt auch für n = 1: Die Schleife wird nullmal ausgeführt, die Summe bleibt 0, und das Ergebnis ist false.

Die Halbierung des Bereichs ändert das Wachstum nicht. Für n = 10^8 wird die Schleife weiterhin 5 × 10^7 Mal ausgeführt, und zwar bei jeder Eingabe dieser Größe, unabhängig davon, ob sie einen Teiler hat oder nicht.

Algorithmus

Setze total auf 0.
Durchlaufe d von 1 bis n / 2.
Wenn n % d == 0, addiere d zu total.
Gib zurück, ob total == n.

def isPerfect(n):
    total = 0
    # No proper divisor of n is larger than n / 2.
    for d in range(1, n // 2 + 1):
        if n % d == 0:
            total += d
    return total == n

Faktorenpaare bis zur Quadratwurzel sammeln

Idee

Wenn d n teilt, dann teilt auch n / d n. Für 28 sind die Paare 1 × 28, 2 × 14 und 4 × 7. In jedem Paar ist ein Element höchstens √n, denn zwei Zahlen, die größer als √n sind, ergeben multipliziert mehr als n. Eine Suche bis √n trifft also jedes Paar genau einmal, und du addierst dabei jeweils beide Elemente.

Bei zwei Elementen ist Vorsicht geboten. Das Paar 1 × n bringt n selbst ins Spiel, das kein echter Teiler ist: Beginne die Summe bei 1 und die Suche bei 2. Für n = 1 ist dieser Start jedoch falsch, denn der einzige Teiler ist die Zahl selbst. Gib deshalb vorher false zurück. Und wenn n eine Quadratzahl ist, wird die Wurzel mit sich selbst gepaart: Bei 36 muss 6 × 6 einmal 6 addieren, nicht zweimal.

Schreibe die Grenze als d * d ≤ n, sodass nur mit ganzen Zahlen gerechnet wird. Für n = 10^8 endet die Schleife bei d = 10^4; sie läuft also etwa 10^4 Mal statt 5 × 10^7 Mal.

Algorithmus

Wenn n == 1, gib false zurück.
Setze total auf 1 und d auf 2.
Solange d * d ≤ n gilt: Wenn d ein Teiler von n ist, addiere d und außerdem n / d, wenn dieser Wert von d abweicht.
Gehe zum nächsten d.
Gib zurück, ob total == n gilt.

def isPerfect(n):
    if n == 1:
        return False
    total = 1  # 1 divides every n > 1; n itself does not count
    d = 2
    while d * d <= n:
        if n % d == 0:
            total += d
            partner = n // d
            if partner != d:  # a square root pairs with itself: add it once
                total += partner
        d += 1
    return total == n

Stolperfallen und Grenzfälle

Der Paar-Trick ist kurz, und jeder seiner Fehler ändert die Summe um genau einen Teiler.

n selbst mitzählen. Das Paar 1 × n addiert n, und dann scheint jede Zahl eine Summe größer als n zu haben. Beginne die Gesamtsumme bei 1 und die Suche bei 2.
1 als vollkommen bezeichnen. Wenn die Gesamtsumme bei 1 beginnt, ergibt der Vergleich für die Eingabe 1 1 == 1. Die Summe ihrer echten Teiler ist 0, also behandle sie vor der Schleife.
Eine Quadratwurzel zweimal addieren. Für 16 sind die echten Teiler 1, 2, 4 und 8, deren Summe 15 ergibt. Addiert man 4 zweimal, erhält man 19.
Bei d * d < n aufhören. Dadurch wird die Quadratwurzel vollständig übersprungen, sodass 4 bei 16 nie gezählt wird.
Die Grenze aus einer Gleitkomma-Quadratwurzel ableiten. Bei einfacher Genauigkeit oder oberhalb von 2^53 bei doppelter Genauigkeit kann die Wurzel einer Quadratzahl um eins zu klein ausfallen und einen Teiler auslassen. Der Test d * d ≤ n bleibt bei ganzen Zahlen und hat dieses Problem nie.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität beim Überprüfen, ob eine Zahl eine vollkommene Zahl ist?

Das Sammeln von Teilerpaaren bis √n benötigt O(√n) Zeit und O(1) Speicherplatz. Für n = 10^8 sind das etwa 10^4 Schritte. Das Testen jedes Kandidaten bis n / 2 hat eine Komplexität von O(n) und benötigt bei derselben Eingabe etwa 5 × 10^7 Schritte.

Wie viele vollkommene Zahlen gibt es unter 10^8?

Fünf: 6, 28, 496, 8128 und 33550336. Sie werden schnell rar. Die nächste Zahl, 8589869056, passt nicht einmal in eine 32-Bit-Ganzzahl.

Gibt es ungerade vollkommene Zahlen?

Niemand weiß es. Jede bislang gefundene vollkommene Zahl ist gerade. Bei Suchen wurden ungerade vollkommene Zahlen unter 10^1500 ausgeschlossen, aber kein Beweis besagt, dass sie nicht existieren können. Deine Funktion muss anhand der Definition arbeiten und darf nicht einfach annehmen, dass die Eingabe gerade ist.

Was ist der Unterschied zwischen vollkommenen, überreichlichen und defizienten Zahlen?

Vergleiche die Summe der echten Teiler mit der Zahl. Sind sie gleich, ist die Zahl vollkommen, wie 28. Ist die Summe größer, ist die Zahl abundant, wie 12, dessen Teiler sich zu 16 addieren. Ist die Summe kleiner, ist die Zahl defizient, wie jede Primzahl, deren einziger echter Teiler 1 ist.

Python

def isPerfect(n):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

n = 28

Erwartet

true