- Da es unmöglich ist, gleichverteilt aus allen natürlichen Zahlen zu wählen, wird eine „zufällige ganze Zahl“ definiert, indem man zunächst gleichverteilt aus 1 bis N wählt und dann den Grenzwert für N → ∞ betrachtet
- In Those Fascinating Numbers steht, dass die Wahrscheinlichkeit, dass der zweite Primfaktor einer zufälligen ganzen Zahl kleiner als 37 ist, ungefähr 1/2 beträgt; dies wird durch Dichteberechnungen und Experimente bestätigt
- Kleine Primzahlen treten häufig als kleine Primfaktoren ganzer Zahlen auf, wodurch intuitiv plausibel wird, dass eine kleine Zahl wie 37 der Median sein kann
- Die Methode von De Koninck und Tenenbaum berechnet λ₂(p), indem sie wie beim Sieb des Eratosthenes Bedingungen kombiniert, ob eine Zahl durch bestimmte Primzahlen teilbar ist
- Addiert man λ₂(p) über die Primzahlen, erreicht die kumulative Dichte bei 37 etwa 0,5002 und liegt damit sehr nahe am direkt berechneten Wert 0,5002501 für N=10⁷
Woher die Zahl 37 stammt
- Im Vorwort von Those Fascinating Numbers steht der Satz, dass 37 der Median des zweiten Primfaktors einer ganzen Zahl ist
- Gemeint ist, dass die Wahrscheinlichkeit, dass der zweite Primfaktor einer zufällig gewählten ganzen Zahl kleiner als 37 ist, ungefähr 1/2 beträgt
- Anfangs wirkt 37 viel zu klein und schwer zu glauben, aber es wird plausibel, wenn man bedenkt, dass kleine Primzahlen häufig als kleine Primfaktoren ganzer Zahlen auftreten
- Zum Beispiel hat etwa die Hälfte aller ganzen Zahlen 2 als kleinsten Primfaktor
- Ziel ist es, diese Tatsache direkt experimentell zu prüfen und auf Grundlage des Papers von De Koninck und Tenenbaum zu berechnen, warum gerade 37 herauskommt
Wie man eine „zufällige ganze Zahl“ definiert
- Auf der Menge aller natürlichen Zahlen gibt es keine Gleichverteilung, daher fixiert man zunächst eine große Zahl N
- Dann wählt man zufällig eine der ganzen Zahlen von 1 bis N und betrachtet den Grenzwert der Wahrscheinlichkeit für N → ∞
- Für kleine N kann man den zweiten Primfaktor jeder ganzen Zahl direkt bestimmen und den Median überprüfen
- Bei N=10⁷ ergibt sich als Näherung für die kumulative Wahrscheinlichkeit 0,5002501
- In Online-SageCell kann eine Faktorisierung dieser Größenordnung lange dauern und in ein Timeout laufen; eine lokale Ausführung ist daher nötig
λ₂(p): die Dichte dafür, dass p der zweite Primfaktor ist
- Das Paper Sur la loi de répartition du k-ième facteur premier d’un entier von De Koninck und Tenenbaum bezeichnet die Dichte der ganzen Zahlen, für die p der zweite Primfaktor ist, als λ₂(p)
- Der Kern der Berechnung besteht darin, ähnlich wie beim Sieb des Eratosthenes durch Kombination der Frage, ob eine Zahl durch bestimmte Primzahlen teilbar ist, die Dichte zu zählen
- Für den Fall, dass der zweite Primfaktor 5 ist, gibt es nur zwei Möglichkeiten
2^a 3^0 5^b ...: Zahlen, die Vielfache von 2 und 5, aber keine Vielfachen von 3 sind2^0 3^a 5^b ...: Zahlen, die Vielfache von 3 und 5, aber keine Vielfachen von 2 sind
- Die Dichte des ersten Falls ist
1/2 × 2/3 × 1/5 = 1/15 - Die Dichte des zweiten Falls ist
(1 - 1/2) × 1/3 × 1/5 = 1/30 - Da sich die beiden Mengen nicht überschneiden, kann man sie addieren; die Dichte der ganzen Zahlen, deren zweiter Primfaktor 5 ist, beträgt damit 1/10
Formel für eine allgemeine Primzahl p
- Damit p der zweitkleinste Primfaktor ist, muss unter den Primzahlen kleiner als p genau eine Primzahl q enthalten sein, während alle übrigen Primzahlen r kleiner als p, außer q und p, nicht enthalten sein dürfen
- Diese Bedingung lässt sich als Primfaktorzerlegung der folgenden Form ausdrücken
[ p^b q^a \prod_{q \neq r \lt p} r^0 ]
- Berechnet man für jedes q < p die Dichte und addiert sie, erhält man folgende Formel
[ \lambda_2(p) = \sum_{q \lt p} \frac{1}{p} \frac{1}{q} \prod_{q \neq r \lt p} \left ( 1 - \frac{1}{r} \right ) ]
- Dieselbe Gleichung lässt sich wie folgt umformen
[ \lambda_2(p) = \frac{1}{p} \left[ \prod_{q \lt p} \left(1 - \frac{1}{q}\right) \right] \sum_{q \lt p} \frac{1}{q} \left(1 - \frac{1}{q}\right)^{-1} ]
Die Berechnung, durch die 37 zum Median wird
- Die gesuchte Primzahl (p^) ist der Punkt, an dem die Summe der Dichten dafür, dass der zweite Primfaktor höchstens (p^) ist, ungefähr 1/2 wird
[ \lambda_2(2) + \lambda_2(3) + \lambda_2(5) + \ldots + \lambda_2(p^*) \approx \frac{1}{2} ]
- Implementiert man λ₂(p) und addiert die Werte über die Primzahlen, erreicht die kumulative Dichte bei 37 ungefähr 1/2
- Die berechnete erwartete Dichte beträgt etwa 0,5002
- Auch der Wert 0,5002501, der im direkten Faktorisierungs-Experiment für N=10⁷ herauskam, liegt sehr nahe daran
Erweiterung auf den k-ten Primfaktor
- Die allgemeine Formel für die Dichte λₖ(p), dass der k-te Primfaktor p ist, lautet wie folgt
[ \lambda_k(p) = \frac{1}{p} \left[ \prod_{q \lt p} \left(1 - \frac{1}{q}\right) \right] s_{k-1}(p) ]
- Dabei ist (s_j(p) = \sum \frac{1}{m}), wobei die Summe über m läuft, die genau j Primfaktoren haben und deren Primfaktoren alle kleiner als p sind
- Die asymptotische Formel für den Median (p_k^*) des k-ten Primfaktors lautet
[ \log \log p_k^* = k - b + O\left(\frac{1}{\sqrt{k}}\right) ]
- Dabei ist b der folgende Wert
[ b = \frac{1}{3} + \gamma - \sum_p \left( \log((1-1/p)^{-1}) - 1/p \right) ]
- (\gamma) ist die Euler-Mascheroni-Konstante
1 Kommentare
Hacker-News-Kommentare
Das heißt nicht, dass 37 an sich hier besonders interessant wäre.
Interessant ist vielmehr die Tatsache, dass hier überhaupt ein endlicher Median existiert. Wenn das gilt, muss es ein Primzahlwert sein, weil der Median als Element der Liste definiert wurde. In dieser Liste ist es zufällig 37, es hätte auch ein anderer Wert sein können.
Damit 37 wirklich interessant würde, müsste die Definition so gelockert werden, dass der Median auch ein Wert außerhalb der Menge sein kann, und der Grenzwert trotzdem gegen 37 konvergiert. Das wäre ziemlich überraschend gewesen.
Werte kleiner als 37 machen nur etwa 49,061 % aus, Werte größer als 37 nur etwa 49,975 %. Ab einem gewissen Punkt liegen bei geradem N immer zwei 37er auf beiden Seiten der 50%-Marke, daher ist der Median exakt 37 und kein anderer Wert. Eine längere Erklärung habe ich in einem anderen Kommentar geschrieben [0].
[0] https://news.ycombinator.com/item?id=38245162
Die Existenz des Medians legt nahe, dass es auch für alle anderen Perzentile Grenzwerte geben könnte. Mehr noch: Für jede Zahl könnte der Grenzanteil der ganzen Zahlen existieren, deren zweiter Primfaktor größer als diese Zahl ist; bei 37 ist dieser Anteil eben zufällig 0,5.
Mir hat gefallen, wie klar der Artikel die Frage beantwortet hat, die einem zuerst in den Sinn kommt: „Wie zum Teufel beweist man das?“
Interessanterweise taucht 37 auch beim Optimal-Stopping-Problem / Sekretärinnenproblem auf.
Zufällig ist 37 auch die erste irreguläre Primzahl. Das hängt damit zusammen, warum der Große Satz von Fermat schwierig ist.
https://en.wikipedia.org/wiki/Regular_prime
Es wurde gesagt: „Zahlen, deren zweite Primzahl 2 ist, sind 0,000000000000000“. Ist der Titel des Artikels auch ohne den ausdrücklichen Zusatz ohne Wiederholungen korrekt?
Wenn man die Notation auf Englisch vollständig ausschreibt, wird sie meist weitschweifig. Hätte man „zweite Primzahl ohne Wiederholungen“ geschrieben, könnte jemand fragen, ob man nicht auch „zweitkleinste“ oder „in aufsteigender Reihenfolge“ dazuschreiben müsste. In Papers werden solche Begriffe in der Regel formal zusammen mit präziserer, aber immer noch nicht vollständig exakter mathematischer Notation definiert.
Das ist nicht als Haarspalterei gemeint, sondern weil es die Nutzbarkeit von Theorembeweisern stark erhöht, wenn Menschen die „unsichtbaren“ Teile der Mathematik erschließen können, statt alles einzeln explizit angeben zu müssen. Dazu gibt es einen guten Vortrag von Andrej Bauer: https://www.youtube.com/watch?v=wZSvuCJBaFU
Ich frage mich, ob es in der Richtung der L-Funktionen oder Modulformen interessante Sätze oder Resultate gibt, die dieses Ergebnis umfassen.
Ich lerne das gerade, und das Thema ist faszinierend.
Ich bin über das Video https://www.peakmath.org/quest-for-f1 darauf gestoßen, und http://lmfdb.org lohnt sich ebenfalls zum Stöbern.
Ich finde, diese Tatsache macht 37 ziemlich interessant.
Zumindest ist sie definitiv interessanter als 31.
31 ist zwar auch eine Primzahl und damit bis zu einem gewissen Grad interessant, aber nicht so interessant wie 37, die, wie wir gerade gelernt haben, der Median des zweiten Primfaktors ganzer Zahlen ist.
Gibt es Kandidaten für noch interessantere ganze Zahlen? Und gibt es eine Zahl, die man als interessanteste ganze Zahl bezeichnen könnte?
Das sind jeweils die Big-Endian- und Little-Endian-Versionen des ASCII-Strings „the most interesting“.
Interessant ist, dass irreguläre Primzahlen etwa 41 % aller Primzahlen ausmachen und trotzdem erst so spät erstmals auftreten. Siehe: https://encyclopediaofmath.org/wiki/Irregular_prime_number#:~:text=An%20odd%20prime%20number%20p,prime%20numbers%20are%20called%20regular
Welche Primzahl die interessanteste ist, hängt davon ab, was man interessanter findet. Wenn man den Median des zweiten Primfaktors mag, ist 37 die beste; wenn man die erste irreguläre Primzahl mag, ist 37 ebenfalls die beste. Am Ende ist es eine Frage der Perspektive.
Ein weiterer Grund, warum 37 gut ist: Sie endet auf 7 und klingt daher „zufällig“, wenn jemand einen bittet, eine Zahl zu nennen; außerdem ist sie besser als 27, weil sie prim ist. 7 ist zu niedrig, und 17 hat eine unglückliche Konnotation. Allerdings ist auch 37 eine ziemlich unheimliche Zahl. Schon als Primzahl ist sie recht unregelmäßig, und dann ist sie auch noch eine irreguläre Primzahl.
Deshalb beruhen unser Zeitsystem und die Trigonometrie vermutlich auf 60. 360 = 6*60, und 360 hat 24 Teiler.
Erstaunlich, dass der Beweis so einfach ist. 37 ist meine neue Lieblingsprimzahl geworden.
Ich frage mich, wie die Wachstumsrate des Durchschnittswerts des zweiten Primfaktors aussieht. Ich vermute, er wächst unbegrenzt, aber vielleicht ziemlich langsam.
Ich war mein Leben lang auf diese Zahl fixiert. Immer wenn ich auf die Uhr schaue oder das Nummernschild des Autos vor mir sehe, fühlt es sich an, als würde ich 37 sehen.
Es gibt auch allerlei zufällige Bezüge wie Channel 37: https://en.wikipedia.org/wiki/Channel_37