Faktoruhr
Die Faktoruhr zeigt die Uhrzeit in der Form an, also als
, und zerlegt dann die Zahl
in Primfaktoren. Beispielsweise wird eine Viertelstunde nach elf Uhr, also um 11:15:00, folgendes angezeigt:
. Die etwas seltsame Idee, die Uhrzeit (einschließlich der Sekunden) als Dezimalzahl zu lesen und dann zu faktorisieren, geht auf die Internet-Comicserie xkcd zurück, siehe nachfolgende Abbildung 1:
Und nun … die Mathematik dazu:
Teil 1: Fakten
Weil ,
und
gelten muss, kommen nicht alle der 1000000 sechsstelligen Zahlen vor, sondern nur soviele, wie der Tag Sekunden hat, nämlich 86400. Darunter sind 7669 Primzahlen. Die letzte Primzahl-Zeit vor Mitternacht ist 23:59:51. Die Zahl 235951 ist Nummer 20903 unter allen Primzahlen, aber nur Nummer 7669 unter den Faktoruhr-Primzahlen. Die Mehrzahl der 7669 Primzahlen, die die Faktoruhr anzeigen kann, bekommen die Besucher des ERLEBNISLANDs MATHEMATIK allerdings nicht zu sehen, weil sie außerhalb der Öffnungszeiten des Museums liegen:
- Zwischen 9:00 und 18:00 Uhr sind es 2731 Faktoruhr-Primzahlen.
- Davon liegen 2440 in der Werktags-Öffnungszeit 9:00–17:00 und 2407 in der Wochenend-Öffnungszeit 10:00–18:00.
- Pro Minute sind etwa fünf Primzahlen zu erwarten, wobei die Häufigkeit morgens etwas höher ist als abends.
- Maximal sind es neun Primzahlen in einer Minute (also von
bis
. Das kommt zehnmal vor, nämlich um 9:00, 10:05, 11:09, 11:31, 11:53, 12:13, 12:20,13:06, 14:04 und 15:28.)
- Zwischen 11:52:49 und 11:53:43 liegen 11 Primzahlen innerhalb von 54 Sekunden.
- Mehr als eine Minute auf die nächste Primzahl warten muss man ab 10:12:21 (62 Sekunden), 10:27:01 (70 Sekunden), 12:17:27 (76 Sekunden) und 14:29:49 (64 Sekunden).
- Unter den Faktoruhr-Primzahlen sind 859 Primzahlzwillinge.
- Zwischen 9:00 und 18:00 Uhr sind es 278 Zwillinge, davon liegen 255 in der Öffnungszeit 9:00–17:00 und 242 in der Öffnungszeit 10:00–18:00.
- Etwa alle zwei Minuten ist ein Primzahlzwilling zu erwarten, wobei die Häufigkeit morgens etwas höher ist als abends.
- Besonders häufig sind Primzahlzwillinge gegen 9:40, 12:20 und 15:20.
- Besonders lang auf einen Primzahlzwilling warten muss man ab 10:55:29 (7:52), 12:27:43 (8:08), 15:02:23 (7:24), 16:34:11 (7:36) und 17:49:31 (7:00).
- Es gibt kurioserweise sogar einen „Faktoruhr-Primzahldrilling“: 11:52:59, 11:53:01, 11:53:03.
Teil 2: Der Algorithmus von Fermat
Die grundlegende Methode zur Zerlegung einer gegebenen natürlichen Zahl in Primzahlfaktoren beruht auf einem Algorithmus, der von Pierre de Fermat (um 1608–1668) erstmalig angegeben wurde.
Die Faktorisierungsmethode von Fermat sucht nach zwei Quadratzahlen und
, die die Gleichung
(mit
eine natürliche Zahl) erfüllen. Auf Grund der 3. Binomischen Formel ist dann
und und
sind die gesuchten Teiler von
. Das Fermatsche Verfahren findet dabei genau diejenigen Teiler
und
, die am nächsten zur Wurzel von
liegen.
Obwohl das Verfahren eines der langsamsten bekannten Verfahren ist, die dieses leisten, so besitzt diese Methode doch eine gewisse Bedeutung in der Mathematik, da nahezu alle schnellen heute bekannten Faktorisierungsverfahren auf die Methode von Fermat zurückgehen.
Im Einzelnen ist nun die folgende Prozedur durchzuführen:
Um eine natürliche Zahlnzu faktorisieren, berechnet man für beginnend bei
(also bei der kleinsten ganzen Zahl, die größer als die Quadratwurzel aus
ist)
. Sobald eine dieser Zahlen eine Quadratzahl ist, z.B.
, kann man eine multiplikative Zerlegung von
angeben, deren beide Faktoren dann erneut der Prozedur zu unterwerfen sind. Es ist nämlich nach der 3. Binomischen Formel
. Die Suche kann man beenden, wenn
den Wert
überschreitet, da dann bereits sicher ist, dass
eine Primzahl ist. Diese Abbruchbedingung gilt allerdings nur für ungerade Zahlen
, was man aber stets dadurch erreichen kann, dass man vor Beginn dieser Prozedur die höchste Potenz von 2 multiplikativ abspaltet.
Ein Beispiel soll dies abschließend illustrieren:
Zu faktorisieren ist die Zahl (also der Zeitpunkt 2:48 Uhr und 6 Sekunden). Dann ist zunächst der Faktor 2 multiplikativ abzuspalten und man erhält
und kann die Prozedur auf
anwenden. Da die Quadratwurzel von 12403 ungefähr 111,368 ist, beginnt man mit der Bestimmung von
für
. In diesem Falle ergibt sich
.
Man erhält folglich und
, also
und
als Primfaktoren, d.h.
oder
auf der Anzeige der Faktoruhr im ERLEBNISLAND MATHEMATIK zur Zeit 2:48 Uhr und 6 Sekunden.
Literatur
[1] Bundschuh, P.: Einführung in die Zahlentheorie, 6. Auflage, Berlin, 2008.
[2] Du Sautoy, M.: Die Musik der Primzahlen. Auf den Spuren des größten Rätsels der Mathematik, München, 2004.
[3] Padberg, F.: Elementare Zahlentheorie, 3. Auflage, Heidelberg, 2008.
[4] Wolfart, J.: Einführung in die Algebra und Zahlentheorie, Braunschweig / Wiesbaden, 1996.