Elementare Zahlentheorie: Blatt 1

Wie versprochen gibt es hier meine Sage-Programme zum 1. Übungsblatt. Das Skript findet ihr unter http://data.countnumber.de/ENTH/.

Aufgabe 1

Eine einfache Implementierung des Sieb des Eratosthenes ist die folgende Funktion sieve:

def sieve(n):
    """Berechne die Liste aller Primzahlen 2 <= p < n.
    Die gleiche Funktionalität steht in Sage auch als Funktion primes_first_n
    zur Verfügung.
    """
    candidates = [True] * n
    candidates[0] = candidates[1] = False
    # Da wir nur Vielfache von i ab i² streichen, können wir aufhören, sobald
    # i²>n ist.  Die Funktion range erwartet ganze Zahlen als Argument, so dass
    # wir die Gleitkommazahl, die sqrt(n) zurückgibt runden müssen.  Zudem
    # liefert range(a,b) die Liste
    #   a, a+1, a+2, …, b-2, b-1,
    # weshalb wir noch 1 addieren müssen um auch für Quadratzahlen n das
    # richtige Ergebnis zu bekommen.
    for i in range(2, int(sqrt(n))+1):
        if not candidates[i]:
            # Vielfache von zusammengesetzten Zahlen werden schon vorher als
            # Vielfache der Primteiler gestrichen, mache also mit dem nächsten
            # i weiter.
            continue
        # Streiche alle Vielfachen ab i², die durch i teilbaren Zahlen zwischen
        # i und i² haben einen Primfaktor p < i und wurden somit bereits
        # gestrichen.
        for j in range(i*i, n, i):
            candidates[j] = False
    # 
    return [p for (p, is_prime) in enumerate(candidates) if is_prime]

Nun liefert diese Funktion alle Primzahlen unterhalb einer gegebenen Schranke, gefragt war aber eine Liste der ersten 10 000 Primzahlen.

Das Problem können wir lösen, indem wir sieve mit einem großzügig gewählten n aufrufen, etwa n = 1000000, durch ausprobieren (einfach n größer machen, bis die Liste lang genug ist).

# Berechne die Liste der Primzahlen <10⁶ und wähle mit [:10000] die ersten 10000
# aus dieser Liste aus.
first_10000_primes = sieve(1000000)[:10000]

Wir können auch ein bisschen mogeln und uns von Sage die 10 000. Primzahl p angeben lassen und dann sieve(p) aufrufen:

p = nth_prime(10000)
first_10000_primes = sieve(p)

Aufgabe 2

Für diese Aufgabe war eine Funktion zu implementieren, die die Anzahl der Primzahlen unterhalb einer gegebenen Schranke zählt. Dazu können wir unsere Funktion sieve wiederverwenden.

# Die in Aufgabe 1 erzeugte Liste first_10000_primes enthält alle Informationen,
# die wir nun brauchen.  Wir müssen lediglich Zählen, wie viele der Primzahlen
# unter einer gegebenen Schranke liegen.

# Die vielleicht einfachste Möglichkeit ist die folgende:
def num_primes_below(n):
    """Ermittle, wie viele Primzahlen ≤ n es gibt."""
    if n > first_10000_primes[-1]:
        # Wenn die Grenze größer ist, als die 10000. Primzahl, so können wir
        # nicht sicher sein, ob wir wirklich alle Primzahlen < n kennen.  In
        # diesem Fall beenden wir die Funktion einfach mit einer Fehlermeldung.
        print "Grenze zu groß: %d" % n
        return
    counter = 0
    for p in first_10000_primes:
        if p > n:
            # Wir haben alle Primzahlen < n gezählt, sind also fertig.
            return counter
        counter += 1
    return counter

Aufgabe 4.1

def is_valid_isbn10(n):
    # Zunächst wandeln wir die Zahl n in eine Liste ihrer Ziffern um.  Wie
    # Freitag erwähnt geht das, indem wir zunächst n in eine Zeichenkette
    # umwandeln und anschließend die einzelnen Zeichen wieder in Zahlen:
    #   digits = map(int, str(n))
    # Sage beinhaltet jedoch bereits eine passende Funktion, die jedoch nur
    # für den Sage-Ganzzahltyp Integer, nicht den Python-Ganzzahltyp int zur
    # Verfügung steht:
    digits = Integer(n).digits()
    # Diese Funktion liefert jedoch die Ziffern in in umgekehrter Reihenfolge,
    # weshalb wir anschließend die Liste umdrehen, oder das restliche Programm
    # anpassen müssen.  Der Einfachheit halber drehen wir die Liste um:
    digits.reverse()
    # Reduzieren modulo m kann man in Sage mittels des % Operators:
    return sum([(i+1)*d for (i, d) in enumerate(digits)]) % 11 == 0

def find_16_divisor_isbns(low, high):
    """Bestimme die Liste aller gültigen ISBN-Nummern n mit genau 16 Teilern,
    wobei low ≤ n ≤ high ist.
    """
    result = []
    for n in range(low, high+1):
        if is_valid_isbn10(n) and len(divisors(n)) == 16:
            # An dieser Stelle haben wir eine Lösung gefunden und fügen sie
            # hinten an die Liste an.
            result.append(n)
    return result

lst = find_16_divisor_isbns(1441926535, 1441928509)
# Eigentlich sollte lst[11] das richtige Ergebnis sein (die Indizes starten bei
# 0), aber aus irgendeinem Grund ist bei mir die richtige ISBN-10 die 14.
lst[13]