Counting Ones

Das Problem Nr. 9 „Counting Ones“ wird bereis als Spaßproblem („This program is a fun math problem!“) beschrieben. Es sind in einem Zahlenbereich von 1 bis einschließlich einer Zahl n alle Einser gezählt werden. Im Bereich bis 10 finden sich so z. B. zwei Einser und zwar bei 1 und einmal bei 10. Die Lösung des Problems, wenn man die Dateneingabe außen vor lässt, ist knapp zu formulieren:

def counting_ones(n):
    """ Soll alle Einser zwischen
    1 bis einschließlich n ermitteln

    """
    zahlen = [str(n) for n in range(1,n + 1)]
    zahlenreihe = "".join(zahlen)
    return zahlenreihe.count("1")


for i in [13,1,999,23,1111,9997,511]:
    print(counting_ones(i))

Schöne, einfache Probleme, zumindest die, die ich mir jetzt angesehen habe.

Die (3n+1)-Vermutung

Die (3n+1)-Vermutung bzw. das Collatz-Problem ist ein ungelöstes mathematisches Problem, welches erstmals 1937 vom Mathematiker Lothar Collatz formuliert wurde.

Die zu erzeugende Zahlenfolge folgt folgendem Bildungsgesetz:

• Beginne mit irgendeiner natürlichen Zahl n > 0.
• Ist n gerade, dann nimm n/2.
• Ist n ungerade, dann nimm 3n + 1.
• Wiederhole die Vorgehensweise mit der erhaltenen Zahl.

Konkret wird vermutet, dass jede so konstruierte Zahlenfolge in den Zyklus 4, 2, 1 mündet, dabei ist der Startwert bei n > 0 nicht relevant.

Der Algorithmus lässt sich mit Python implementieren:

# collatz_problem.py

from random import randint


def collatz_folge_erzeugen(n):
    ''' Erzeugt die Zahlenfolge entsprechend dem
    Algorithmus nach Collatz.

    '''
    while n != 1:
        if n % 2 == 0:
            n //= 2
        else:
            n = 3 * n + 1
        print(n, end=", ")
    print("...")

for i in range(0,1):

    n = randint(1,100)
    print("\n\nFolge für {}!".format(n))
    collatz_folge_erzeugen(n)

Man sollte beachten, dass die Bedingung bei while bewirkt, dass die Collatz-Folge nicht in den Zyklus 4, 2, 1 mündet, sondern beim ersten Auftreten endet.

Primzahlen

Ich habe das Sieb des Eratosthenes schon vor einiger Zeit mal programmiert.

(1) Ein Ansatz mit Listen und list comprehensions

Der Algorithmus wirkt in dieser Form bereits sehr schnell.

def sieben(zahl):
    ''' Eine erste Implementierung des
    Sieb des Eratosthenes mit Listen
    '''
    liste = [2]
    liste.extend([i for i in range(3,zahl+1,2)])
 
    for z in range(2,zahl+1):
        if z in liste:
            exliste = [e * z for e in range(z,zahl+1) if e * z <= zahl]
            # print(z, exliste)
            if len(exliste) == 0:
                break
            else:
                for e in exliste:
                    if e in liste:
                        liste.remove(e)
    return liste
 
 
ergebnis = sieben(10000)
 
print(", ".join(map(str,ergebnis)),end=".\n")

Das Skript nutzt str.join(iterable) und map. Das Skript macht sich zunutze, dass nur die ungeraden Zahlen geprüft werden müssen, weil alle geraden Zahlen außer 2 keine Primzahlen sind. Sobald die exliste leer ist, wird die Löschung abgebrochen, weil angenommen wird, dass alle weiteren Listen auch leer sein werden.

(2) Ein Ansatz mit einem Wörterbuch

Mit dem Wörterbuch wirkt der Algorithmus noch etwas schneller:

def sieben(zahl):
    ''' Eine erste Implementierung des
    Sieb des Eratosthenes mit einem Woerterbuch
    '''
    keys = [2]
    keys.extend([i for i in range(3,zahl,2)])

    woerterbuch = {}

    for key in keys:
        woerterbuch[key] = True  # True = prime (!)
          
    for key in keys:
        if woerterbuch[key] == True:
            vielfache = [i * key for i in range(key,zahl+1) if i * key <= zahl]
            # print(key,vielfache)
            if len(vielfache) == 0:
                break
            else:
                for item in vielfache:
                    if item in woerterbuch:
                        woerterbuch[item] = False
    return [i for i in keys if woerterbuch[i] == True]

ergebnis = sieben(1000)

print(", ".join(map(str,ergebnis)),end=".\n")

Gefühlt ist das auch für größere Zahlen sehr zügig. Ich verzichte hier auf eine mitlaufende Ausgabe, was sich leicht durch einen weiteren print-Befehl nach der Zeile

if woerterbuch[key] == True:

realisieren ließe. In diesem Fall könnte der Aufbau einer weiteren Liste und die return-Anweisung entfallen.

Performanz-Test

Mit dem Modul profiler - entsprechend den Hinweisen von Michael Weigend (4. Aufl.) 2010 - ergab sich folgendes Bild:

Ich hätte nicht erwartet, dass die Umsetzung mit dem Wörterbuch so viel performanter ist. Inzwischen habe ich weiter am Code geschraubt, so dass beide Skripte eigentlich noch etwas performanter geworden sein müssten. Das zweite Skript schafft die Prüfung des Zahlenraums bis 1.000.000 jetzt in ca. 38,34 Sekunden statt ursprünglich etwa 42,18 Sekunden.

Feedback aus dem Python-Forum

Hier der Link zum Thread. Offensichtlich gibt es bei beiden Implementierungen noch deutliches Optimierungspotential.

Teilbarkeit

Manchmal ist es sinnvoll alle Teiler einer Zahl zu ermitteln, etwa um sich an dieser Aufgabe zu versuchen. Ein ganz erster Versuch, eine Funktion zu schreiben, die alle Teiler einer Zahl liefert, ist:

def teiler_ermitteln(zahl):
    ''' Soll alle Teiler einer ganzen Zahl ermitteln
    und als Liste zurueckgeben.
    
    '''
    liste = []
    liste.extend([1,zahl])
    
    ende = zahl
    i = 1
    
    while i < ende:
        
        i += 1

        if i == ende:
            break
        
        if (zahl / i) % 1 == 0.0:
            
            liste.append(i)
            
            if int(zahl/i) != i:
                liste.append(int(zahl/i))
                
            ende = int(zahl/i)

    return liste 


ergebnis = teiler_ermitteln(72)

ergebnis.sort()

print(ergebnis)

Das Skript arbeitet so nur für natürliche Zahlen größer 0. Da aber  gilt, so gilt auch  und . Man kann sich also bei der Untersuchung des Teilbarkeitsbegriffs auf natürliche Zahlen beschränken.

Um die Programmieraufgabe allerdings zu lösen, reicht diese Version vollkommen aus:

def teiler_ermitteln(zahl):
    ''' Soll alle Teiler einer ganzen Zahl ermitteln
    und als Liste zurueckgeben.
     
    '''
    liste = []
    liste.extend([1,zahl])
     
    ende = zahl
    i = 1
     
    while i < ende:
         
        i += 1
 
        if i == ende:
            break
         
        if (zahl / i) % 1 == 0.0:
             
            liste.append(i)
             
            if int(zahl/i) != i:
                liste.append(int(zahl/i))
                 
            ende = int(zahl/i)
            
    liste.sort()
    return liste 
 

for i in range(1,10000):

    teiler = teiler_ermitteln(i)
    teiler.pop()
    summe = sum(teiler)
    
    if summe > i and i % 2 != 0:
        print("{} ist abundant.".format(i))
    elif summe == i:
        print("{} ist vollkommen.".format(i))

Ich denke allerdings, dass in der eigentlichen Funktion noch deutliches Optimierungspotential steckt.