Project Euler Nr. 37

Der Wikipedia-Artikel „Truncatable prime“ bietet die Lösung für die, die nicht selbst rechnen wollen. Ferner sei auf den Artikel „Truncatable Prime“ auf mathworld.wolfram.com verwiesen.

Beim Problem Nr. 37 vom Project Euler sind die 11 Primzahlen gesucht, bei denen man sowohl von rechts nach links, als auch von links nach rechts jeweils eine Ziffer wegnehmen kann und dennoch jeweils eine Primzahl erhält. Die Zahlen 2, 3, 5 und 7 sind ausgenommen. Als Beispiel wird die Zahl 3797 genannt.

Meine Vorüberlegung betrifft die Primzahlen im Zahlenraum von 1 bis 100:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.

Jede Primzahl, auf die das zutrifft, muss mindestens zweistellig sein und die äußersten Ziffern rechts und links müssen jeweils Primzahlen sein, d. h. die Primzahl muss - falls sie mindestens dreistellig ist - mit 23, 29, 31, 37, 53, 59, 71, 73 oder 79 beginnen.

2 - 23 - 29
3 - 31- 37
5 - 53 - 59
7 - 71 - 73 - 79

Im Zahlenbereich von 1 bis 100 können schon einmal 4 Primzahlen gefunden werden, die zur gesuchten Menge gehören:

23, 37, 53, 73.

Ausschließen kann ich alle Primzahlen, die mit einer 1, 4, 6, 8 oder 9 beginnen sowie alle, die mit einer 1 oder 9 (alle Zahlen, die auf 0, 2, 4, 6 oder 8 enden, sind durch 2 teilbar und somit keine Primzahlen) enden, direkt ausschließen und muss sie nicht näher prüfen.

Ich kann ferner alle Primzahlen ausschließen, die eine 4, 6, 8 oder 0 enthalten, weil dann bei der Trunkierung unweigerlich eine gerade Zahl herauskommen muss. Ein Sonderfall ist die 2, weil sie zwar an erster Stelle auftauchen darf, nicht aber an einer anderen Stelle.

3547 - 354 - 35 - 3

3547 - 547 - 47 - 7

In diesem Fall wäre auch 35 keine Primzahl (7 * 5).

Wie kann ein Algorithmus aussehen, der das Problem löst?

• Zunächst einmal muss ich Primzahlen ermitteln, die in eine Prüfliste aufgenommen werden.
• Dann muss ich die Primzahlen durchlaufen, um sie zu prüfen. Auslassen kann ich alle Zahlen, die eine 4, 6, 8 oder 0 enthalten oder mit 1 oder 9 enden oder beginnen.
• Schließlich muss ich für jede "Form" der Primzahl prüfen, ob sie wiederum in der Liste der Primzahlen enthalten ist. Dazu müssen die verschiedenen trunkierten Zahlen erstellt werden.
• Wenn ich 11 Primzahlen gefunden habe, dann kann ich die Prüfung abbrechen.

Schauen wir mal. Zunächst einmal die Funktion, die von rechts bzw. links jeweils eine Ziffer trunkiert - hier ein Beispiel für die Zahl 12345:

zahl = 12345

zahl = str(zahl)
for i in range(1,len(zahl)):
    print(zahl[:len(zahl)-i]," - ",zahl[len(zahl)-i:])

Das ergibt in der Konsole dann:

1234  -  5
123  -  45
12  -  345
1  -  2345

Das funktioniert schon einmal.

Am Ende muss man die Summe für die Liste [23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797, ...] bilden.