Faktoruhr

Die Faktoruhr zeigt die Uhrzeit in der Form $\mathrm{Stunden:Minuten:Sekunden}$ an, also als $\mathrm{hh:mm:ss}$ , und zerlegt dann die Zahl $\mathrm{hhmmss}$ in Primfaktoren. Beispielsweise wird eine Viertelstunde nach elf Uhr, also um 11:15:00, folgendes angezeigt: $111500=2\cdot 2\cdot 5\cdot 5\cdot 5\cdot 223$ . 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:

Abbildung 1: Der ausschlaggebende xkcd Comic (Linzenz xkcd, Creative Commons)

Und nun … die Mathematik dazu:

Teil 1: Fakten

Weil $\mathrm{hh}<24$ , $\mathrm{mm}<60$ und $\mathrm{ss}<60$ 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 $\mathrm{hh:mm:00}$ bis $\mathrm{hh:mm:59}$ . 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 $x^2$ und $y^2$ , die die Gleichung $x^2-n=y^2$ (mit $n$ eine natürliche Zahl) erfüllen. Auf Grund der 3. Binomischen Formel ist dann

$n=x^2-y^2=(x+y)(x-y)$

und $a=x+y$ und $b=x-y$ sind die gesuchten Teiler von $n$ . Das Fermatsche Verfahren findet dabei genau diejenigen Teiler $a$ und $b$ , die am nächsten zur Wurzel von $n$ 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 $x$ beginnend bei $\lceil\sqrt{n}\rceil$ (also bei der kleinsten ganzen Zahl, die größer als die Quadratwurzel aus $n$ ist) $Q(x)\coloneqq x^2-n$ . Sobald eine dieser Zahlen eine Quadratzahl ist, z.B. $x^2-n=y^2$ , kann man eine multiplikative Zerlegung von $n$ angeben, deren beide Faktoren dann erneut der Prozedur zu unterwerfen sind. Es ist nämlich nach der 3. Binomischen Formel $n=x^2-y^2=(x-y)(x+y)$ . Die Suche kann man beenden, wenn $x$ den Wert $\frac{n+9}{6}$ überschreitet, da dann bereits sicher ist, dass $n$ eine Primzahl ist. Diese Abbruchbedingung gilt allerdings nur für ungerade Zahlen $n$ , 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 $24806$ (also der Zeitpunkt 2:48 Uhr und 6 Sekunden). Dann ist zunächst der Faktor 2 multiplikativ abzuspalten und man erhält $24806=2\cdot 12403$ und kann die Prozedur auf $n=12403$ anwenden. Da die Quadratwurzel von 12403 ungefähr 111,368 ist, beginnt man mit der Bestimmung von $Q(x)$ für $x=112$ . In diesem Falle ergibt sich

$Q(112)=1122-12403=141$
$Q(113)=366$
$Q(114)=593$
$Q(115)=822$
$Q(116)=1053$
$Q(117)=1286$
$Q(118)=1521=39^2\quad\text{(!)}$ .

Man erhält folglich $x=118$ und $y=39$ , also $x+y=157$ und $x=79$ als Primfaktoren, d.h. $12403=79\cdot 157$ oder $24806=2\cdot 79\cdot 157$ auf der Anzeige der Faktoruhr im ERLEBNISLAND MATHEMATIK zur Zeit 2:48 Uhr und 6 Sekunden.