In langsamen Schritten mehren sich die Lösungsvorschläge zu den projecteuler.net Problemen in dieser Serie. Nun sind es fünf an der Zahl. Zur Feier des Tages werden heute eine ganz simple, handschriftliche Lösung vorgestellt und die dazu äquivalente Implementierung in Python gezeigt.

Problemvorstellung

Die Probleme von projecteuler.net sind aufgrund des meist recht hohen Rechenaufwands nicht nur durch Überlegen mit Bleistift und Papier zu lösen. Zumindest nicht in einem vertretbaren zeitlichen Rahmen. Ebenso häufig, wie die Probleme nicht ohne weiteres mit Bleistift und Papier lösbar sind, helfen diese Mittel das Problem besser zu verstehen und eine elegante Lösung zu erarbeiten.

Wie bereits bei der Lösung des vierten Problems, lassen sich auch hier einige Gedanken machen, die schnell zur Lösung führen. Diesmal geht es sogar soweit, dass eine rein schriftliche Lösung ohne großen Aufwand eingereicht werden kann.

Obwohl das Problem an sich keine Herausforderung mehr darstellt, wenn die Probleme 1 bis 4 gelöst sind, habe von derzeit 1802789 Projecteuler-Mitgliedern nur 64072 es auch gelöst.

Doch worum handelt das Problem, welches spätestens auf den zweiten Blick einfach erscheint?

Finde die kleinste Zahl, welche durch alle Zahlen von 1 bis 20 gerade teilbar ist!

Als Beispiel zu dieser Fragestellung haben die Macher hinter Projecteuler.net das gleiche Problem mit den Zahlen von 1 bis 10 gelöst. Hiernach ergibt sich als Lösung: 2520.

Problemeingrenzung

Spätestens seit der Lösung des dritten Projecteuler-Problems wissen wir, dass alle Zahlen eine eindeutige Primfaktorenzerlegung besitzen. Ebenfalls aus dem dritten Problem ist bekannt, wie wir eine Primfaktorenzerlegung durchführen können, dieses Wissen hilft uns an dieser Stelle weiter.

Wie können wir das bereits erworbene Wissen auf dieses Problem übertragen?

Gesucht ist eine Zahl, die durch alle Zahlen von 1 bis 20 ohne Rest teilbar ist. Gleichwertig kann auch eine Zahl gefunden werden, welche durch alle Primfaktoren der Zahlen 1 bis 20 ohne Rest teilbar ist. Also suchen wir erst einmal eine Menge an Primzahlen, welche die Zahlen 1 bis 20 abbilden kann. Dabei ist es nicht wichtig, dass alle 21 Zahlen gleichzeitig aus der Menge heraus gebildet werden können.

In Kürze ergibt sich aus den Überlegungen und dem bereits vorhandenen Wissen folgendes Vorgehen:

1. Suchen aller Primzahlen bis 20 entweder im Kopf oder mit dem Sieb des Eratosthenes.
2. Suchen der Primfaktorenzerlegung aller Zahlen von 1 bis 20 und zusammenfassen aller Primfaktoren mit ihren Häufigkeiten in einer Menge.
3. Reduzieren der Häufigkeiten, damit jede Zahl mindestens ein Mal aus den Primfaktoren gebildet werden kann.

Also beschränkt sich die Herausforderung der Aufgabe lediglich auf eine Primfaktorenzerlegung und etwas Abzählen der Häufigkeiten. Gehen wir es an!

Problemlösung

Wie bereits in der Einleitung angedroht, versuche ich mich zum ersten Mal in dieser Serie mit einer einfachen, handschriftlichen Rechnung. Dazu gehe ich zielführenden nach den Punkten 1-3 aus dem vorangegangenen Abschnitt vor:

1. Die Primzahlen bis 20 inkl. der 1:1 2 3 5 7 11 13 17 19
2. Primfaktoren aller Zahlen außer der Primzahlen von 1 bis 20:
   4: 2 2
6: 2 3
8: 2 2 2
9: 3 3
10: 2 5
12: 2 2 3
14: 2 7
15: 3 5
16: 2 2 2 2
18: 2 3 3
20: 2 2 2 5
   Daraus ergibt sich die folgende Gesamtverteilung:
   
   

   Häufigkeitsverteilung der Primfaktoren

   
   Zur Lösung des Problems ist eine solche Darstellung nicht nötig. Um jedoch zu verdeutlichen, wie viel kleiner die gesuchte Zahl ist, wenn alle Faktoren, die zu viel sind, gestrichen werden, eignet sie sich hervorragend.
3. Jetzt bleibt nur noch die einzelnen Primfaktorzerlegungen durch zu gehen und die Häufigkeiten der Primfaktoren zu zählen. Daraus ergibt sich folgende Verteilung:
   
   

   reduzierte Häufigkeitsverteilung

   
   Das war es schon! Das Multiplizieren aller verbleibenden Faktoren führt zu der gesuchten Zahl:
   1*2*2*2*2*3*3*5*7*11*13*17*19 = 232792560

Alternative Lösung

Als alternative Lösung verkaufe ich heute einfach die Python-Implementierung des zuvor beschriebenen handschriftlichen Lösungswegs:

import numpy as np

def eratosthenes(N):
    """liefert alle Primzahlen bis N"""
    primes = np.arange(1,N+1,1)

    for i in np.arange(2,np.ceil(np.sqrt(N))+1,1):
        primes[i*i-1:N:i] = 0;

    return primes

def prime_fact_counter(N,testPrimes):
    nPrimes = np.size(testPrimes)
    countPrimes = np.zeros_like(testPrimes)

    for i in range(1,nPrimes,1):
        actPrime = testPrimes[i]
        while ((N%actPrime == 0) & (N >= actPrime)):
            N = N / actPrime;
            countPrimes[i] = countPrimes[i] + 1
        countPrimes[0] = 1
    return countPrimes

def solver(N):
    searchProduct = 1.0
    testPrimes = np.trim_zeros(np.sort(eratosthenes(N)))

    freq = np.zeros_like(testPrimes) # array of prime occurance for each factor 1..20
    totFreq = np.zeros_like(testPrimes) # array of total prime occurance

    print(testPrimes)

    for i in range(1,N+1,1):
        freq = prime_fact_counter(i,testPrimes)
        for j in range(0,freq.size,1):
            if (freq[j] > totFreq[j]):
                totFreq[j] = freq[j]

    print(totFreq)

    for j in range(0,totFreq.size,1):
        searchProduct = searchProduct * (testPrimes[j])**(totFreq[j])

    return searchProduct

N = 20

print(solver(N))

Insgesamt habe ich drei Funktionen definiert. Die erste Funktion ist der bereits bekannte Sieb des Eratosthenes. Sie berechnet alle Primzahlen bis zu einer Zahl N, oder anders ausgedrückt, alle in der Primfaktorenzerlegung vorkommenden Primzahlen der Zahl N.

Die zweite Funktion zählt die Anzahl der Primfaktoren einer bestimmten Zahl N. Das ist wichtig, um die maximale Häufigkeit eines Faktors in einer Zahl festzustellen. Zum Beispiel enthält die 16 genau vier mal die 2 als Faktor: 2*2*2*2 = 16

Die solver-Funktion durchläuft alle Zahlen von 1 bis 20, berechnet die Primfaktorenzerlegung und überprüft die Häufigkeiten. Am Ende wird aus der reduzierten Häufigkeitsverteilung die gesuchte Zahl errechnet.

Damit wäre das fünfte Problem von Projecteuler gelöst!

Schlusswort

Aufgrund des niedrigen Schwierigkeitsgrades des fünften Problems konnte zum ersten Mal in dieser Serie eine rein handschriftliche Lösung präsentiert werden. Alternativ dazu wurde auch eine Python-Implementierung aufgeführt, welche auch für Zahlen größer als N=20 geeignet ist.

In der Hoffnung, dass die simple Idee, die hinter dem Lösungsvorschlag steckt, klar geworden ist, freue ich mich wie immer auf Kommentare und Verbesserungsvorschläge.

Artikel aus der selben Kategorie:

• » Projecteuler: Lösung zu Problem 1
• » Projecteuler: Lösung zu Problem 9
• » Projecteuler: Lösung zu Problem 3
• » Projecteuler: Lösung zu Problem 2
• » Projecteuler: Lösungen in Serie