Wie Fermat-Zahlen Lila herausgefordert haben

Jenny besucht Lila in ihrem Zimmer in Berlin. Jenny ist zwar Mathestudentin, hat aber wenige Programmierkenntnisse. Und Lila interessiert sich sehr fürs Programmieren. Sie hat schon ein paar Programme geschrieben. Beide überlegen, wie man wohl weitere Fermat-Primzahlen findet.

Lila Diese Fermat-Zahlen kann ich gut berechnen. Jenny, wie war die Formel?

Jenny

Fermat-Zahlen

Lila Oh, das klappt ganz gut:

Pepin-Test

Jenny Danke, Lila, gut, gut, gut! Jetzt gibt es den bekannten Pépin-Test. Dazu musst Du prüfen, ob

gilt. Dann ist Primzahl.

Lila Was bedeutet das?

Jenny Die Formel bedeutet, dass

bei der Division durch den Rest -1 lässt.

Lila Aha! Also muss ich diese tolle Pépin-Zahl

durch teilen?

Numerische Berechnung der Pépin-Zahlen

Jenny Ja!

Lila Okay, bis

klappt das,

aber für

macht mein TigerJython nicht mehr mit! Schau mal hier!

Ich habe extra Alles für große Zahlen eingerichtet, long int! Ich schätze, das geht auch nicht mit anderen Anwendungen wie Excel oder dem wissenschaftlichen Taschenrechner. Weißt Du, was wir nun tun sollen?

Jenny Ich habe noch nie sowas ausgerechnet. Hmm.

Lila Habt Ihr denn gar kein Rechnerpraktikum?

Jenny Nö! Wir haben mit unseren Mathe-Fächern schon genug zu tun. Wir rechnen Alles mit Zettel und Stift aus. Weißt Du, die meisten Profs finden praktische oder Näherungsrechnung unter ihrer Würde. Als wäre das schmutzig!

Lila Ehrlich? Bei uns in Indien fangen die Kinder schon in der Schule mit dem Programmieren an. Und viele von meinen Freunden wollen Programmierer werden. Ich hatte eigentlich gehofft, hier in Deutschland sehr viel darüber zu lernen und nicht ganz so – wie sagt man?

Jenny … hemdsärmlig?

Lila Was ist das?

Jenny Es heißt so viel wie Aus dem Bauch heraus, frei…

Lila Okay, ... nicht ganz so frei, ich dachte, ich lerne hier eher systematisch und klug die Welt zu berechnen.

Jenny Na, an meiner Uni nicht.

Lilas Primzahltest Prime Prime Program

Lila Hmm. Schade! Jetzt lass uns weitermachen. Weißt Du, dieser Pépin-Test ist echter Mist! Diese blöden Pépin-Zahlen

werden viel zu groß! Ich weiß was, wir nehmen einen anderen Test! Ich habe schon ein Programm geschrieben, um Primzahlen zu testen. Es heißt Prime Prime Program. Hier, ist Primzahl.

Jenny Zeig mal!

Lila Hier!

Jenny Hey, Glückwunsch!

Lila Danke! Und jetzt gebe ich mal unser ein!

Jenny Hey, ist keine Primzahl! Schade! Fermat hätte sich gewundert, wie schnell das geht, meinst Du nicht auch?

Lila I hope so.

***

Übungsaufgabe

Ist Lilas Test auch für größere Fermat-Zahlen geeignet?

Lösung

Für die nächste Fermatzahl funktioniert Lilas Programm Prim Prim Prim nicht, weil es nur auf Primzahlteiler bis 10⁶ testet – notwendig wäre jedoch bis 10⁹.