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…):

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.