Project Euler: Problem 45

Bei Problem 45 des Projects Euler soll diejenige Zahl > 40755 gefunden werden, die sowohl eine Dreieckszahl als auch pentagonal und hexagonal ist.

Die Formeln zur Berechnung der Zahlenfolgen sind der Aufgabenstellung beigegeben.

T(n) = n (n + 1) / 2

P(n) = n (3 n -1) / 2

H(n) = n (2n - 1)

Die erste Zahl, für die diese Bedingung zutrifft ist 40755.

T(285) = P(165) = H(143) = 40755

Die nächste Zahl, die diese Bedingung erfüllt, wird gesucht.

Für die verschiedenen Zahlen ergeben sich folgende Zahlenfolgen:

T(n) → 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, ... 

P(n) → 1, 5, 12, 22, 35, 51, 70, 92, 117, 145, 176, 210, 247, 287, 330, 376, 425, 477, 532, ... 

H(n) → 1, 6, 15, 28, 45, 66, 91, 120, 153, 190, 231, 276, 325, 378, 435, 496, 561, 630, 703, ... 

Auffälligkeiten? Mir fällt auf, dass jedes zweite Element der Dreieckszahlen (T(n)) auch in der Zahlenfolge der hexagonalen Zahlen (H(n)) auftaucht:

1, 6, 15, 28, 45, 66, 91, 120, 153 usw.

Das heißt, dass ich die Dreieckszahlen nicht berechnen muss. Jede hexagonale Zahl ist zugleich immer eine Dreieckszahl. Mit einer Brute-Force-Methode lässt sich und ließ sich das Problem lösen (mir ist gerade aufgefallen, dass ich es schon einmal gelöst hatte):

pzahlen = [int(i * (3 * i - 1) / 2) for i in range(1,1000000)]

hzahlen = [int(i * (2 * i - 1)) for i in range(1,500000)]

print("Suche jetzt ein Element, das in allen drei Listen auftaucht.")

for i in pzahlen:

    if i in hzahlen:

        print(i)

Nachteil an diesem Verfahren ist sicherlich der Lärm, den der Lüfter produziert. Nicht sinnvoll. Ich habe hier beim MathBlog eine Lösung für das Problem gefunden, die ich nun implementieren will.

Der Lösungsweg erscheint recht einfach:

• Erzeuge hexagonale Zahlen und prüfe, ob es sich dabei um eine pentagonale Zahl handelt.

Verständnis: (1) Dieser Lösungsweg ist besser, weil nicht erst zwei Listen erzeugt werden müssen, sondern nur die Werte einer Liste hinsichtlich ihrer Eigenschaften zu prüfen sind. (2) Die hexagonalen Zahlen wurden ausgewählt, weil hier deutlich weniger Zahlen zu prüfen sind. (3) Ein weiteres, nicht ausgeschöpftes Potential zur Optimierung wäre es, erst die hexagonalen Zahlen ab 143 zu prüfen, weil 143 ja bereits ein Ergebnis (vgl. Aufgabenstellung) war.

In Python-Code könnte da so aussehen:

import math


def is_polygonal(n):
    ''' Pruefung auf Basis der Formel
    der Wikipedia, Rueckgabewerte True and False

    '''
    result = (math.sqrt(24 * n + 1) + 1) / 6
    if int(result) == result:
        return True
    else:
        return False


for i in range(1,100000):
    # Berechne eine hexagonale Zahl
    hexagonale_zahl = i * (2 * i - 1)
    # Pruefe das
    if is_polygonal(hexagonale_zahl):
        # Ausgabe
        print(hexagonale_zahl)

Die Lösung wird jetzt in wenigen Millisekunden ausgespuckt. Da ich die Prüfformel nicht selbst herleiten konnte, war ich auf die Formel in der Wikipedia angewiesen.