Elementare Zahlentheorie: Blatt 12

Aufgabe 1

Der LLT ist schnell implementiert:

def is_prime_lucas_lehmer(p):
    """Check whether 2^p-1 is a Mersenne prime using the Lucas-Lehmer test."""
    s = Mod(4, 2^p - 1)
    for i in range(3, p+1): s = s^2 - 2
    return s == 0

Um eine Übersicht über die Laufzeite zu erhalten, lassen wir den Test mit Primzahlen verschiedener größe laufen. Zum Stoppen der Laufzeit benutzen wir die time()-Funktion.

from time import time
print "| \\(p\\)  | Prime (Yes/No) | Laufzeit des LLT (s) |"
print "|------|----------------|----------------------|"
for n in [1..10] + [100, 500, 1000, 1500, 2000, 3000, 4000, 5000]:
    p = nth_prime(n)
    print "| {} |".format(str(p).rjust(5, " ")),
    start = time()
    b = is_prime_lucas_lehmer(p)
    duration = time() - start
    if b:
        print "      Yes     ",
    else:
        print "      No      ",
    print "| {} |".format(str(duration).ljust(len("Laufzeit des LLT (s)"), " "))

Als Ergebnis erhalten wir die folgende Tabelle (die zweite Spalte \(M_p\) habe ich mal weggelassen, da die Zahl doch recht groß werden…):

\(p\) Prime (Yes/No) Laufzeit des LLT (s)
2 No 0.00597095489502
3 Yes 0.000696897506714
5 Yes 0.000622987747192
7 Yes 0.000731945037842
11 No 0.000629901885986
13 Yes 0.000751972198486
17 Yes 0.00091290473938
19 Yes 0.000904083251953
23 No 0.000869989395142
29 No 0.000170946121216
541 No 0.00384306907654
3571 No 0.133982896805
7919 No 0.841007947922
12553 No 1.47259402275
17389 No 3.35499310493
27449 No 10.6544179916
37813 No 23.6767170429
48611 No 42.8488218784

Aufgabe 2

def sum_of_proper_divisors(n):
    if n == 0:
        return 0

    # Zahlen vom Typ `int` (welche Python standardmäßig für ganze Zahlen
    # verwendet) haben keine Methode `divisors()`.  Daher müssen wir den
    # Sage-Typ `Integer` verwenden.
    # Summiere über alle Teiler bis auf den letzten (n selbst).
    return sum(Integer(n).divisors()[:-1])

for n in [1..1000]:
    f = sum_of_proper_divisors
    lst = [n]
    # Berechne nur die ersten 50 Folgenglieder
    for k in [1..50]:
        # Wenn die Folge ab jetzt nur noch Nullen enthält, oder eine
        # vollkommene Zahl, die sich dementsprechend unendlich oft wiederholt,
        # bringt es nichts, diesen Teil der Folge auszugeben.  Daher beenden
        # wir die Schleife in diesem Fall vorzeitig.
        if lst[-1] == 0 or len(lst) >= 2 and lst[-1] == lst[-2]:
            break

        # Ansonsten fügen wir das nächste Folgenglied hinzu.
        lst.append(f(lst[-1]))

    # Falls die Folge periodisch mit einer Periode der Länge 1 ist, dann geben
    # wir das an.
    if lst[-1] == lst[-2]:
        print lst, "und weiter mit Periode", lst[-1]
    else:
        print lst

Wenn eine Folge eine Periode größerer Länge hat, kann man dies natürlich auch leicht feststellen. Man überprüft einfach ob f(lst[-1]) schon in lst auftaucht.

Für diejenigen unter euch, die gerne ein bisschen tüfteln, gibt bei Project Euler unter anderem eine gut zu diesem Thema passende Aufgabe.