Karl Schwalen
6.04
Version 9.15
Weitere Aufsätze des Verfassers unter http://www.primath.homepage.t-online.de
Primzahl-Lücken und Primzahl-Abstände
Teil II: Große Primzahllücken besonderer ’Bauart’
------------------------------------------------------------------------------------------------------------1. Das Thema
Eine Primzahllücke ist definiert als L = pk +1 – pk. Bezüglich der max. Lücken in Abhängigkeit
von k gibt es heute recht gute Abschätzungen (s. Anmerkungen am Schluss).
Vorliegend wird die Frage untersucht, wie die größtmöglichen Lücken sich entwickeln, wenn
man nur eine fest vorgegebene Folge von Primteilern – nämlich p1 bis pm – als Teiler der
Zahlen innerhalb der Lücken zulässt. Konkret:
Wie groß ist der Abstand dm = |na – ne| zweier nat. Zahlen na, ne höchstens, wenn gefordert wird,
dass alle zwischen na und ne liegenden Zahlen durch mindestens eine der Primzahlen 2,3,5,...,pm
teilbar sind?
Mit Πm =
m
∏ p i ist das gleichbedeutend mit
i =1
ggT(na, Πm ) = 1; ggT(ne, Πm ) = 1 und ggT(n, Πm ) > 1 für na < n < ne
(dm ist damit definitionsgemäß die größte Lücke zwischen zwei primen Restklassen im
kleinsten positiven Vertreter-System zum Modul Πm.)
na und ne müssen also nicht unbedingt Primzahlen sein; ihre etwaigen Teiler müssen nur alle
größer als pm sein. Der größte Abstand dm (die „maximale Lücke“) wird im Weiteren mit Dm
bezeichnet. Gesucht wird die Zahlenfolge {Dm} mit m ≥ 1.
Ansätze
Bzgl. {Dm} ist klar, dass
• die Folge nur aus geraden Zahlen besteht, da die Differenz zweier ungerader Zahlen
(na und ne) stets gerade ist ;
• Dm + 1 > Dm ; d.h. die Folge wächst streng monoton und
• für m → ∞ auch Dm über alle Grenzen wächst, denn das folgt aus der Monotonie in
Verbindung mit Dm+1 – Dm ≥ 2. (Das beinhaltet eine Erweiterung des Satzes, dass sich
für den maximalen Abstand zweier Primzahlen keine obere Schranke angeben lässt,
auf zum Modul Πm teilerfremde Zahlen.)
Die ersten Dm-Werte sind leicht zu bestimmen:
m = 1; p1 = 2
Nach Streichen der durch 2 teilbaren Zahlen bleiben die ungeraden Zahlen übrig. Bildet man
deren Differenzen ergibt sich 2, 2, 2, 2,.....; d.h. D1 = 2.
m = 2; p2 = 3
Streichen der durch 2 und/oder 3 teilbaren Zahlen ergibt die
Folge : 1, 5, 7, 11, 13, 17, 19, 23, 25,.... Daraus die Folge der
Differenzen: 4, 2, 4, 2, 4, 2,...... und somit: D2 = 4.
1
Hier zeigt sich bereits die bekannte Tatsache, dass wegen ggT(a, k) = ggT(a + k, k) die nicht
durch 2,3,....,pm teilbaren Zahlen eine periodische Differenzenfolge bilden (siehe
nachstehende Darstellung) und daher auch das gesuchte größte Folgenglied Dm in jeder
Periode enthalten ist.
2. Die Differenzenfolge
m = 3; p3 = 5
1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, .....
6, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 4, 6, 2, 6, 4, ....... D3 = 6
=
=
Die Darstellung macht den periodischen Aufbau der Zahlenfolge sichtbar.
Allgemein: Die Differenzen der Zahlen, die keinen Primteiler ≤ pm besitzen, bilden eine
Folge mit der Periodenlänge Πm und jede Periode umfasst
m
Πm)
∏ ( pi − 1) = ϕ(Π
i =1
=
Folgenglieder (ϕ (n): Euler-Funktion).
Je Periode gibt es zwei Symmetrieachsen: Die eine liegt auf dem Zahlenstrahl an den Stellen
2⋅k⋅Tm (an den „Nahtstellen“ zweier Perioden; Tm = Πm / 2 ; k = {0, 1, 2, 3, .......}) und teilt
immer ein Folgenglied mit Betrag 2 (siehe oben blaue Ziffern) während die andere sich an
den Stellen (2⋅k +1)⋅Tm (im „Zentrum“ der betr. Periode) befindet und ein Folgenglied vom
Betrag 4 mittig teilt (siehe oben rote Ziffern).
Die nachstehende Grafik veranschaulicht die Situation für den allgemeinen Fall.
Nahtstelle
2⋅k⋅Tm
2
Zentrum
(2⋅k +1)⋅Tm
4
Nahtstelle
2⋅(k +1)⋅Tm
2
Symmetrieachsen
Periode (Länge: Πm = 2⋅Tm)
3. Die Lücke an der Nahtstelle
Bildet man (mit Rechnerhilfe) die Differenzenfolgen für die nächstgrößeren m-Werte, findet
man folgende maximale Lücken:
D4 = 10
D5 = 14
D6 = 22
D7 = 26
D8 = 34
Möchte man sich ein Bild darüber verschaffen, wie das betr. Dm – ausgehend von kleineren
m-Werten – durch sukzessives Zusammenziehen von Folgengliedern entstanden ist, erstellt
man zweckmäßigerweise eine Liste, in der für alle ungeraden Zahlen zwischen na und ne der
2
jeweils kleinste Primteiler angegeben ist. (Für die geraden Zahlen kann man den Aufwand
sparen.)
Beispiel: D7 = 26 (p7 = 17)
na , 11, 3, 7, 5,
3,
17,
13,
3,
5,
7,
3,
11,
ne
Man erkennt unschwer, dass, wenn man die beiden mittig postierten Teiler 13 und 17 (die
jeweils nur einmal vorkommen) weglässt, D7 in die drei Folgenglieder/Abstände 12, 2, 12
zerfällt. Dies ist aber genau die Situation an den Nahtstellen der Perioden im Fall m = 5 (p5 =
11). Damit ist der Bildungsmechanismus klar: An einem Teil der (unendlich vielen)
Nahtstellen der Perioden im Fall m – 2 entsteht durch Hinzufügen der beiden weiteren Teiler
pm-1 und pm eine Lücke der Größe 2⋅pm–1, (die sich dann natürlich nicht mehr an der Nahtstelle
der betr. Periode befindet.)
Mit der Setzung p0 = 1 gilt für m ≤ 8 somit: Dm = 2⋅⋅pm –1.
4. Eine Suchstrategie
Bereits für m = 9 findet sich mit D9 = 40 eine Lücke, die den Wert 2⋅p9 – 1 (= 38) übersteigt.
Ab etwa m = 12 stößt die komplette Durchmusterung von Tm nach der größten Lücke auch
bei Verwendung eines schnellen Rechner an zeitliche Grenzen, so dass man andere Verfahren
anwenden muss.
Vorliegend wurde so vorgegangen, dass eine Lücke d vorgegeben wurde und diese mit den
Primteiler pi ’aufgefüllt’ wurde.
Da die erste Zahl der Lücke (das ist na + 1) stets gerade ist, liegt das Raster der Zahlen, die die
2 als kleinsten Primteiler aufweisen, von vornherein fest. Das Raster der durch 3 teilbaren
Zahlen besitzt genau 2 ’zulässige’ Startpositionen, denn entweder ist na + 1 oder na + 2 oder
na + 3 – also na - durch 3 teilbar. Analoges gilt für alle erforderlichen m Primteiler. Probiert
man alle Kombinationen der Startpositionen durch, ergibt das genau ϕ(Π
Πm) Möglichkeiten,
was wiederum einer vollständigen Durchmusterung von Tm entspricht. Das wird aber wie
gesagt schnell undurchführbar.
Eine erhebliche Beschleunigung dieses ’Konstruktionsverfahrens’ lässt sich erreichen, indem
für ein vorgegebenes d = ne – na zunächst die Startpositionen der ersten f (z.B. f = 8)
Primteiler ermittelt werden, bei denen die Anzahl der insgesamt durch diese f Primteiler in der
Lücke ’belegten’ Stellen maximal bzw. fast maximal (z.B. 2 weniger als die MaximalAnzahl) wird. (Es wird also unterstellt, dass nur diese wenigen optimalen Varianten als
Ausgangbasis für die Belegung mit den weiteren Primteilern pf +1 bis pm relevant sind.)
Die Start-Positionen dieser (fast-) optimalen Belegungen werden gespeichert und dienen je als
Ausgang für die Belegung mit dem nächsten ’Paket’ von s Primteilern. Vorliegend wurde s so
gewählt, dass je Paket nicht mehr als 5⋅107 Kombinationen zu überprüfen waren.
k +s
(Also
∏ (p i −1) ≤ 5⋅107 )
i=k
Das Verfahren wird solange fortgesetzt, bis der größte Primteiler po = pk + s < d / 2 ist, da alle
weiteren pi nur noch eine einzige ungerade Zahl n innerhalb des Intervalls d teilen können.
Wenn also nach Teilen durch alle Primteiler p1 bis po noch ao Zahlen im Intervall d keinen
Primteiler ≤ po haben, gilt m(d) = o + ao.
Nun wird die Lücke d + 2 u.s.w. analog behandelt. Für verschiedene d-Werte findet man
dabei häufig gleiche m-Werte; der max. d-Wert ist dann zumindest eine Untergrenze für Dm
und – eventuell – das gesuchte Dm.
3
5. Das „Dreieck-Verfahren“
Bei der vorstehend angegebenen Obergrenze von 5⋅107 Iterationen bestehen die jeweils
optimal einzufügenden ’Pakete’ ab k > 70 nur noch aus 2 Primteilern, was zu suboptimalen
Gesamtergebnissen führen muss. Dem kann man folgendermaßen begegnen:
Wie leicht einzusehen ist, kann ein Primteiler, für den d /6 < pi < d/2 gilt, höchstens 2
ungerade Zahlen in einem Intervall d teilen.
Alle möglichen Positionen innerhalb einer im Intervall d vorgegebenen Differenzenfolge,
(die z.B. nach dem vorstehend beschriebenen Verfahren mittels der Primteiler pi < d / 6
gebildet wurde), bei denen ein bestimmtes pi genau 2 ungerade Zahlen, die keinen Primteiler
kleiner d / 6 haben, teilen, erhält man wie an folgendem Beispiel gezeigt:
Vorgabe: d = 90
Nach Teilen durch 2, 3,..., 13 – also p1 bis p6 liege folgender Differenzenfolge-Ausschnitt der
Länge 90 vor:
12 8 4 2 16 8 4 2 4 2 4 8 16 → t-Tupel mit t = 13
Wegen 13 < 90 / 6 < 17 und 43 < 90 / 2 < 47 können die Primteiler 17 bis 43 je höchstens 2
ungerade Zahlen in einem Intervall der Länge d teilen, was gleichbedeutend mit der
Zusammenfassung von je 2 mal 2 benachbarten Elementen des 13-Tupels ist.
Zum bestmöglichen Einfügen dieser Primteiler in steigender Reihenfolge wird – ausgehend
von vorstehendem t-Tupel – das „Dreieck-Schema“ g ( j, v) gebildet:
12
20
24
26
42
50
54
56
60
62
66
74
90
8 4 2 16 8 4 2 4 2 4 8 16
12 6 18 24 12 6 6 6 6 12 24
14 22 26 28 14 10 8 10 14 28
30 30 30 30 18 12 12 18 30
38 34 32 34 20 16 20 34
42 36 36 36 24 24 36
Die 1. Zeile ist das Ausgangs-t-Tupel.
44 40 38 40 32 40
Die weiteren Einträge g(j, v) des Schema’s
48 42 42 48 48
(j: Zeilen-Index; 2 bis t; v: Spalten; 1 bis t – j +1)
lassen sich zeilenweise leicht rekursiv berechnen:
50 46 50 64
54 54 66
g(j, v) = g(j – 1, v) + g(1, v + j – 1)
62 70
78
Findet sich innerhalb des umrandeten (inneren) Zahlen-Dreiecks eine Zahl, die das Doppelte
oder das Vierfache einer Primzahl pi mit 17 ≤ pi ≤ 43 ist, bedeutet dies, dass innerhalb des
Intervalls zwei Zahlen mit dem angezeigten Abstand durch das betreffende pi teilbar sind.
Im vorstehenden Beispiel trifft das für die rot geschriebenen Einträge zu.
Entscheidend ist nun, dass man die betr. Zahlen innerhalb des t-Tupels (und somit innerhalb
des Intervalls d ) auch lokalisieren kann.
Z.B. ist oben g(5, 3) = 34 = 2⋅17. Das bedeutet: na +20 (20 = 12 + 8) und na + 20 + 34 (=54)
sind durch 17 teilbar; bzw. die t-Tupel-Elemente Nr. 2 (= v – 1) und 3 (= v) sowie Nr. 7
(= Elemente-Nr. vom rechten Rand der betr. Zeile aus gezählt) und 8 (= j + v) werden bei
dieser Positionierung der 17 zusammengefasst.
Fazit: Aus der Position (j, v) einer im Inneren des Dreieck-Schema befindlichen Zahl, die
durch pi teilbar ist, lässt sich zugleich ablesen, welche Elemente des t-Tupels durch pi
zusammengefasst werden; nämlich die Elemente-Paare (v–1, v) sowie (j + v –1, j + v).
4
Infolge dieser Eigenschaft des Dreieck-Schema ist nun die optimale Anordnung der einzelnen
pi mit d /6 < pi < d/2 leicht zu bestimmen:
Im Beispiel erkennt man als erstes, dass von den 8 in Frage kommenden Primteilern nur 4 die
gewünschte Eigenschaft (2-fach Belegung) besitzen. Für diese 4 liest man folgende
möglichen Positionen ab:
17: (3, 8); (5, 10)
19: (2, 7); (4, 11)
23: (3, 12)
29: --31: (2, 13)
37, 41 u. 43: ---Stimmen 2 der 4 Indices für 2 unterschiedliche Primteiler überein, so „blockieren“ diese
beiden Belegungen sich insofern, als bei dieser Anordnung nicht 4 sondern nur 3 ElementePaare des t-Tupels zusammengefasst werden.
Im Beispiel sieht man sofort, dass folgende Belegung optimal ist:
17: (5, 10); 19: (4, 11); 23: (3, 12); 31: (2, 13)
Alle 4 Primteiler können also so angeordnet werden, dass im Intervall d insgesamt 8 ungerade
Zahlen, die keinen Primteiler < 17 besitzen, durch einen der Primteiler ≥ 17 geteilt werden.
Damit lässt sich die erforderliche Primteiler-Anzahl m für d = 90 (1-Tupel) angeben:
Die ersten 6 Primteiler ergeben das oben angegebene 13-Tupel.
Nach Belegung durch die o.a. 4 Primteiler > 13 verbleibt ein 5-Tupel (= 13 – 8)
Also werden zur Darstellung eines 1-Tupels noch 4 weitere Primteiler benötigt (, die je nur
eine Zahl im Intervall teilen): 29, 37, 41, 43. → Für dm = 90 ist hier m = 14; bei der
Untersuchung weiterer Belegungen wurde kein kleineres m gefunden, so das (sehr
wahrscheinlich) gilt: D14 = 90.
Bei dem in Ziffer 4. beschriebenen Verfahren hätte man im Beispiel für die optimale
Belegung mit den Primteilern > 13 insgesamt 16⋅18⋅22⋅28⋅30 = 5.322.240 Anordnungen
prüfen müssen, gegenüber 4 Anordnungen (= 2⋅2⋅1⋅1) bei Benutzung des Dreieck-Schema;
der Vorteil ist also evident.
Insbesondere ist sofort ersichtlich, für welche Primteiler keine 2-fach Belegung existiert.
Für größere d-Werte (z.B. d = 1000) nimmt auch bei diesem Verfahren sowohl die Anzahl der
infrage kommenden Primteiler als auch die Anzahl der je Primteiler möglichen Positionen
stark zu, so dass Durchprobieren aller Möglichkeiten praktisch (Zeitbedarf) nicht mehr
möglich ist. In diesen Fällen kann man auf verschiedene Weise Abhilfe schaffen z.B. indem
man den Primteilern, für die nur eine mögliche Belegung existiert, „Vorrang“ einräumt und
bei den übrigen Primteilern die Belegungen, die damit „kollidieren“ (ein Index ist gleich)
löscht. Durch jede dieser Maßnahmen kann allerdings das Auffinden der optimalen Belegung
verfehlt werden.
Anmerkung: Wenn das Ausgangs-t-Tupel nur mit Primteilern pi < d / 8 gebildet wurde,
lassen sich nach dem gleichen Verfahren im Dreieck-Schema auch alle Zahlen lokalisieren,
die drei Zahlen im vorgegebenen Intervall teilen und optimal anordnen; usw. für pi < d / 12 .
Das wurde vorliegend aber nicht angewendet.
5
6. Die Lücke im Zentrum
Da die ersten Dm ihre „Basis“ an den Nahtstellen der Perioden hatten, liegt es nahe auch die
Verhältnisse im Zentrum näher zu untersuchen. Wie sich herausstellt, findet man mit diesem
Ansatz über einen weiten Bereich die maximalen Lücken.
Während an den Nahtstellen für alle pi gilt: 2k⋅Tm ≡ 0 mod pi, lautet das Kongruenzsystem der
das Zentrum darstellenden Zahlen (2⋅k + 1)⋅Tm ≡ 1 mod 2 und (2⋅k + 1)⋅Tm ≡ 0 mod pi mit
1 < i ≤ pm , so dass die Differenzenfolge um das Zentrum herum leicht zu konstruieren ist, da
die Startpositionen für alle pi feststehen.
m
2:
3:
4:
5:
6:
......, 4,
......, 4,
......, 4,
......, 4,
......, 4,
2,
2,
2,
2,
2,
Differenzenfolge ’rechts’ der Symmetrieachse im Zentrum
4, 2, 4, 2, 4,...........
4, 6, 2, 6, 4,...........
4, 8, 6, 4, 6,...........
4, 8, 10, 6, 2,...........
4, 8, 16, 2, 4,...........
10: ....., 4, 2, 4, 8, 16, 30, 2, 10,........
11: ....., 4, 2, 4, 8, 16, 32, 10, 8,.........
18: ......, 4, 2, 4, 8, 16, 32, 64, 6, 8,........
31: ......, 4, 2, 4, 8, 16, 32, 64,128, 6, 12,..........
Symmetrieachse
Wie man aus den obigen Sequenzen der Differenzenfolge ersieht, liegen beiderseits der
zentralen 4 die ersten Glieder der Zahlenfolge 2i, wobei ab einem bestimmten i ein weiteres
Glied hinzukommt. Die nähere Betrachtung zeigt des weiteren, dass die 2i –Folge genau dann
um ein weiteres Glied 2 n (siehe eingekreiste Zahlen) wächst, wenn pr < 2 n < pr +1; also
r = π( 2 n ).
(Dass die Zahlen (2k + 1)⋅Tm ± 2i durch keine Primzahl p1, .....,pm teilbar sind, beweist ein
Satz von Euklid:
Ist a durch c aber nicht durch d teilbar, und b durch d aber nicht durch c teilbar, dann
ist a + b weder durch c noch durch d teilbar.
Vorliegend ist a = (2k+1) ⋅Tm
b = ± 2i
c: beliebige Primzahl aus p2, .....,pm d = 2.)
Um die 2 i- Folge beiderseits der Symmetrieachse zu einer Lücke zusammenzufassen, werden
genau weitere 2n Primteiler benötigt; d.h. insgesamt genau π( 2 n ) + 2⋅n = m n Primzahlen.
k
Wegen 2 +
∑2 = 2
i
k +1
bilden die nicht durch p1 bis pm teilbaren Zahlen eine Lücke der
i =1
Größe 2⋅2n + 1 (, die sich dann natürlich nicht mehr im Zentrum einer Periode befindet).
Also: d m n = 4⋅⋅ 2 n = 2 n + 2
6
Die nachstehende Liste zeigt die m n-Werte, die zugehörigen n und r sowie die Größe von
d mn :
n
r
mn
2n+2
Dm
2
3
4
5
6
7
8
9
2
4
6
11
18
31
54
97
6
10
14
21
30
45
70
115
16
32
64
128
256
512
1024
2048
22
46
90
190
324
614
1126
2204
r = π( 2 n )
mn = r + 2⋅n
m n ist die Mindestzahl an Primteilern,
die ausreicht, eine 2i -Folge (mit letztem
Glied 2 n ) zu einer einzigen Lücke der
Größe d m n = 2 n + 2 zusammenzufassen.
Tabelle 1
Von den 2n Zahlen innerhalb der 2 i-Folge, die keinen Primteiler ≤ pr besitzen, ist gemäß dem
obigen Ansatz jede genau durch ein pi (pr+1 ≤ pi ≤ pm) teilbar. Können aber nicht mehrere der
in Rede stehenden Zahlen ein bestimmtes pi als kleinsten Teiler haben, so dass man mit
weniger als 2n (zusätzlichen) Primteilern auskäme? Das ist nicht der Fall.
Begründung (stichpunktartig):
Zwei durch pi teilbare Zahlen müssten im vorliegenden Fall den Abstand 2⋅pi (und nicht etwa
4⋅pi ,da zu groß) haben; d.h. es müsste gelten: 2⋅pi = 2x + 2y mit 1 ≤ x,y ≤ n. Das ist nicht
möglich, denn
1. x = 1: 2 + 2y < 2⋅pi (daher ist auch 2⋅pi = 2x – 2y ausgeschlossen)
2. für x,y ≥ 2 gilt: 4|(2x + 2y) aber 2⋅pi ist nicht durch 4 teilbar. •
Da also jeder der 2n Primteiler pi nur eine Zahl innerhalb der 2 i-Folge teilt, können die pi in
ihren Positionen beliebig gegeneinander vertauscht werden, so dass die nächste Frage ist, ob
es Anordnungen gibt, bei denen ein pi na oder nb teilt, was eine Vergrößerung von dm
bedeuten würde.
Diese Frage ist zu bejahen, wie das folgende Beispiel zeigt, und es handelt sich sogar um den
Regelfall.
Beispiel: m = 9; mit n = 3 und aus r = m – 2n ergibt sich r = 3. Die Differenzenfolge in der
Umgebung von Tr lautet:
Tr
......,4, 2, 4, 6, 2, * 6, 4, 2, 4, 2, 4, 6, * 2, 6, 4, * 2, 4,.......
32, 28, 26, 22, 16, 14, 8, 4, 2, 2, 4, 8, 14, 16, 22, 26, 28, 32
11 13 17 7 19 23 11 7
13
Die zweite Zeile des Beispiels gibt den Abstand der Zahlen, die keinen Primteiler aus p1 bis pr
haben, vom Zentrum Tr an. In der dritten Zeile sind die 2n Primteiler pr+1 bis pm positioniert.
Damit erhält man zwischen den beiden roten Sternchen eine Lücke vom Betrag 28 (= 4⋅pr+1).
Nun ist aber ne (gekennzeichnet durch das rechte rote Sternchen) – wegen 8 + 14 = 22 –
ebenfalls durch 11 teilbar ...u.s.w., so dass die Lücke insgesamt um drei Folgenglieder auf
dm = 40 erweitert wird (, was – wie oben bereits erwähnt – zugleich die max. Lücke für m = 9
ist).
7
Allgemein beobachtet man, dass die max. Lücken für m = π( 2 n ) + 2n entstehen, wenn
entweder das zentrale Tupel nicht mit allen Primteilern p1 bis pr gebildet wird, sondern nur
mit den ersten π( 2 n ) – c (1 ≤ c ≤ 5) und die verbleibenden 2n + c Primteiler optimal (z.B.
mittels des Dreieck-Verfahren) eingefügt werden oder das zentrale Tupel asymmetrisch
verlängert wird (siehe das oben ausführlich behandelte Beispiel d = 90).
Die für m = π( 2 n ) + 2n gefundenen max. Lücken Dm sind in der letzten Spalte von Tabelle 1
aufgeführt.
7. Bestimmung von na
Bei der in den vorstehenden Ziffern beschriebenen Konstruktion einer Lücke d wurde ein
Vektor e (Länge z.B. 2d) – ausgehend von geeigneten Startwerten si (0 ≤ si < pi ) – so mit
Vielfachen der m Primteiler belegt, dass eine beliebig vorgegebene Stelle (z.B. e(f)) von
keinem pi belegt wurde, daran anschließend jedoch eine Sequenz der Länge d von mindestens
einem pi.
Die Lage einer Lücke Dm auf dem Zahlenstrahl – also na – lässt sich mit Hilfe des
Chinesischen Restsatz bestimmen, wobei die m zu lösenden Kongruenzen
xi ≡ (si – f) mod pi lauten. (si – f ist im nachstehenden Programm mit ri bezeichnet).
(Das Kongruenz-System besitzt natürlich unendlich viele Lösungen; hier ist nur die kleinste
(1. Periode) interessant.)
Wegen der dabei auftretenden großen Zahlen, ist im allgemeinen eine Plattform mit LangzahlArithmetik einzusetzen. Nachstehend ein ’aribas’-Programm, das Ganzzahlen bis 101000
verarbeiten kann (Π350 < 101000).
Beispiel: Berechnung von na für d21 = 164
function rr(n: integer);
# Eingabe nach Start für m = 21: rr(21).
var
i,s,c,c1,c2,m,m1,m2: integer;
d,e,r,q,o,u1,u2,u3,v1,v2,v3: integer;
p:array[500] of integer;
a:array[500] of integer;
begin
#-------Kleine Primzahl-Liste pi ----------p[1]:= 2; p[2]:= 3; s:= 2; e:= 3;
while s <= 500 do
e:= e+2; c:= isqrt(e); i:= 2;
while e mod p[i]<>0 and p[i]<= c do; i:= i+1; end;
if e mod p[i]<>0 then s:= s+1; p[s]:= e; end;
end;
#-------Startwerte ri für die einzelnen pi--------------a[1]:=1;a[2]:=1;a[3]:=3;a[4]:=6;a[5]:=8;a[6]:=1;a[7]:=12;
a[8]:=15;a[9]:=10;a[10]:=2;a[11]:=24;a[12]:=5;a[13]:=3;
a[14]:=36;a[15]:=26;a[16]:=50;a[17]:=32;a[18]:=12;
a[19]:=54;a[20]:=13;a[21]:=6;
#-------Sukzessives Lösen der Kongruenzen xi ≡ ri mod pi mit EEA----c1:=1; m1:= 1; s:=0;
while s < n do
s:=s+1; c2:=a[s]; m2:=p[s];
d:= m1; e:= m2; u1:= 1; v1:= 0; u2:= 0; v2:= 1;
while e <> 0 do
q:= d div e; r:= d mod e; u3:= u1-q * u2; v3:=v1-q * v2;
d:= e; e:= r; u1:= u2; v1:= v2; u2:= u3; v2:= v3;
end;
if (c1 - c2) mod d <> 0 then writeln("Nicht lösbar"); break; end;
o:= (c1-c2) div d; m:=(m1 * m2) div d; c:=(c1-u1 * m1 * o) mod m;
8
#
if c < 0 then c:= c + m; end;
writeln (c," MOD ",m);
c1:=c; m1:= m;
end;
#---------Ergebnis-----------------writeln(“Modul:“,m); c:=m-c;
writeln(“na:
“,c);
#----------Probe-------------------for i:=0 to 164 do
e:=gcd(c+i,m);
write (i," ",e,"--");if e=1 then write ("!!!");end;
end;
end.
Nach dem Start (Eingabe: rr(21).) erscheint als Ergebnis:
Modul:4072_96805_99249_02415_06213_23470
na:
2770_57525_07467_21217_36968_76057
(= Π21)
0 1--!!! 1 78--2 29--3 410--4 3--5 74--6 511--7 6--8 55--9 2--10 69--11 2-12 1037--13 14910--14 13--15 38--16 3--17 2--18 5--19 66--20 7--21 2--22
3--23 10--24 31--25 6--26 47--27 182--28 15--29 34--30 11--31 174--32 59-33 230--34 399--35 2--36 43--37 6--38 5--39 2--40 39--41 154--42 37--43 30-44 41--45 2--46 51--47 2--48 35--49 6--50 53--51 2--52 33--53 2470--54 67-55 1302--56 23--57 2--58 15--59 2--60 29--61 6--62 7--63 1870--64 3--65 2-66 13--67 6--68 5--69 14--70 3--71 2--72 19--73 86010--74 11--75 2--76 21-77 2--78 5--79 208360542--80 17--81 2--82 3--83 70--84 71--85 2706--86 31-87 2--88 15--89 58--90 7--91 6726--92 13--93 10--94 3--95 2--96 11--97
714--98 5--99 2--100 3--101 2--102 23--103 1590--104 7--105 26--106 3--107
22--108 5--109 6--110 19--111 14--112 3--113 10--114 17--115 6--116 37--117
62--118 435435--119 2--120 47--121 402--122 43--123 10--124 3--125 322--126
41--127 6--128 5--129 418--130 3--131 442--132 7--133 30--134 61--135 2-136 3--137 2--138 5--139 42--140 11--141 2--142 3--143 10--144 13--145 6-146 7--147 58--148 3454485--149 2--150 59--151 66--152 73--153 2590--154 3-155 142--156 53--157 78--158 5--159 2--160 21--161 2--162 11--163 30--164
1--!!!
Die abschließende Zahlen-Kolonne stellt die Ergebnisse der Berechnung von ggT(c + i, m) in
der Form -- i ggT -- dar und bestätigt, dass nur für i = 0 und i = 164 ggT(c + i, m) = 1 gilt.
Wird im Programm unter „Ergebnis“ der Befehl c = m – c weggelassen, erhält man die –
wegen der Symmetrie immer existierende – komplementäre Lücke, wobei dann anstelle na
die obere Grenze ne berechnet wird; also ist unter „Probe“ e = gcd(c – i, m) zu berechnen.
Die Lücke d = 164 tritt aber nicht nur an zwei Stellen je Periode auf, denn, falls in einer
Lücke z.B. k Primteiler nur eine Zahl teilen (im Beispiel sind das 61, 67, 71 u. 73), können
diese Primteiler auf k! verschiedene Weisen angeordnet werden, die jeweils auf ein anderes na
führen (was der Chin. Restsatz garantiert).
9
8. Näherungsformel für Dm
Im Vorstehenden wurde vor allem auf die ’technischen’ Details der Bestimmung von dm
eingegangen. Das Ziel dabei war, die Bildungsmechanismen zu erkennen und eine Datenbasis
zu erhalten, die Aussagen über die zu erwartende Entwicklung von Dm für große m-Werte
ermöglichen.
Zunächst stellen sich noch zwei Fragen:
1.Wieso findet man ab m = 10 größere Lücken, wenn man gemäß Ziffer 6. (Lücke im
Zentrum) vorgeht, als gemäß Ziffer 4. (sukzessives Ermitteln der ’dichtesten
Packung’) ?
Ein Vergleich zeigt, dass bei der Lückenbildung im Zentrum die Belegung mittels der
kleinen (ersten) pi deutlich schlechter ist, als gemäß Ziffer 4.,; für die (relativ)
großen Primteiler ist es genau umgekehrt. Im Endergebnis ergibt sich (zunächst; siehe
Frage 2.) ein Vorteil zugunsten der zentralen Lücke.
2.Ist der Vorteil der zentralen Lückenbildung nachhaltig?
Für die ‚zentrale Lücke’ gilt: dm > 4⋅2n und m = π( 2 n ) + 2n und wegen p π ( 2n ) ≈ 2n
ist pm > 2n. Interessant ist die Entwicklung des Quotienten dm / pm.
Die nachstehende Tabelle zeigt dieses Verhältnis für n = 2 bis 11
n
2
3
4
5
6
7
8
9
10
11
m
dm
pm
dm / pm
6
10
14
21
30
45
70
115
192
336
22
46
90
190
324
614
1126
2204
4224
8412
13
29
43
73
113
197
349
631
1163
2267
1,69
1,58
2,09
2,60
2,86
3,11
3,22
3,49
3,78
3,71
Wie zu erwarten, wird der Betrag, um den dm das Minimum 4⋅2n übersteigt mit größer
werdendem m relativ immer unbedeutender und ebenso der Betrag, um den pm 2n
übersteigt, so dass der Quotient dm / pm den Wert 4 (wenn überhaupt) auch für m →∞
nur geringfügig überschreiten dürfte.
Wären die ‚zentralen Lücken’ zugleich die max. Lücken, würde also gelten: Dm ≈ 4⋅pm
für große m. Das wäre allerdings ein erstaunliches Resultat und es zeigt sich, dass es
sich auch nicht so verhält. Berechnet man nämlich die m-Werte für d = 4224 bzw.
d = 8412 mit dem Verfahren nach Ziffer 4. (dichte Packung) ((womit der Rechner schon
mal eine Nacht beschäftigt ist)) erhält man m = 183 bzw. 312 – d.h. eine deutlich
bessere Belegung als „im Zentrum“
(m = 192 bzw. 336).
Ab einem bestimmten d (das etwa bei 3000 liegen dürfte) reicht offenbar der Vorteil
durch die bessere Belegung durch die rel. großen Primteiler nicht mehr aus, den
Nachteil bei den kleineren Primteilern zu kompensieren.
Die Antwort auf Frage 2 ist also „Nein“.
Die vorliegend ermittelten größten dm-Werte (≤ Dm) sind in Tabelle 2 aufgeführt und in Bild 1
als Balkendiagramm dargestellt.
10
m
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
*
*
*
*
*
*
*
*
*
*
*
Dm
m
Dm
2
4
6
10
14
22
26
34
40
46
58
66
74
90
100
106
118
132
152
174
190
200
214
224
256
264
282
290
306
324
336
352
372
400
412
422
432
448
508
520
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
528
564
600
612
614
636
644
660
696
700
708
744
760
772
812
828
848
868
900
924
928
948
968
980
992
1060
1068
1076
1096
1126
1144
1146
1164
1188
1200
1220
1244
1284
1300
1312
m
81
1332
82
1368
83
1408
84
1420
85
1468
86
1496
87
1516
88
1536
89
1556
90
1580
91
1612
92
1632
93
1648
94
1660
95
1708
96
1728
97
1752
98
1768
99
1796
100
1820
101
1848
102
1872
103
1892
104
1904
105
1916
106
1946
107
1976
108
1998
109
2024
110
2040
111
2096
112
2128
113
2160
114
2180
115
2204
116
2216
117
2228
118
2244
..............
183
4222
..............
312
Tabelle 2: Vorliegend gefundene größte Lücken Dm
* : Dm = 2⋅pm–1
11
Dm
8412
2500
Dm
2000
1500
1000
500
0
1
Pm
Bild 1: Größtmögliche(?) Lücken Dm für 1 ≤ m ≤ 118 (Die Dm sind jeweils an der Position von pm auf dem Zahlenstrahl aufgetragen.)
12
Obwohl die vorliegenden Daten nicht ausreichen, eine „belastbare“ Aussage darüber zu
machen, wie Dm sich für große m-Werte entwickelt, wurde zumindest versucht, die
vorhandenen Werte durch eine Näherungsformel zu beschreiben.
Eine (und die einfachste) von mehreren untersuchten Varianten ist:
Dm ≈ 0,535⋅⋅pm⋅∆m
(∗
∗)
Darin ist ∆m der mittlere Abstand der Primzahlen an der Stelle pm. Für große Werte pm ist
dieser Abstand bekanntlich etwa gleich ln(pm); aber für kleine pm ist dieser Wert zu klein.
Vorliegend wurde ∆m mit Hilfe der „glatten“ Näherung Ri(x) aus Ri(x + w) – Ri(x) = 1
ermittelt. Wenn also für x = pm w ( mit Startwert w = ln(pm)) solange erhöht wird, bis die
Gleichung erfüllt wird, ist ∆m = w.
Die auf diese Weise erhaltenen ∆m-Werte können im hier interessierenden Bereich sehr gut
durch ∆m ≈ ln(pm + 5⋅ ln(pm⋅ m + 1 / m)) + 0,05 angenähert werden.
Der Vergleich zwischen den Dm-Werten und der Näherung ist in Bild 2 wiedergegeben.
(Eine „glatte“ Näherung erhält man, wenn in (∗
∗) pm durch das x ersetzt wird, dass sich aus
der iterativ zu lösenden Gleichung Ri(x) = m bestimmt.)
Fazit:
• Die Bestimmung der max. Lücken zwischen zwei zum Modul Πm teilerfremden Zahlen
bietet zugleich einen Einblick in das Wachstum der max. Primzahl-Lücken in Abhängigkeit
von der Anzahl m der für die Lückenbildung zur Verfügung stehenden Primteiler.
• Der Aufwand zur Berechnung der Dm-Werte ist recht hoch; er kann jedoch durch die (noch
zu erweiternde) Anwendung des Dreieck-Verfahren (im Vergleich zum „brute force“Verfahren) wesentlich reduziert werden. Dennoch dürfte die max. Lücke zwischen zwei
benachbarten Primzahlen auch heute noch nicht exakt anzugeben sein, selbst wenn die
Primzahlfolge bei m = 1000 abbrechen würde.
• Aus kombinatorischer Sicht ist das Dreieck-Verfahren bemerkenswert, da es ermöglicht, die
’sinnvollen’ Positionen der einzelnen Primteiler unmittelbar zu erkennen.
• Der mittlere Abstand dφ der zum Modul Πm teilerfremden Zahlen je Periode ist gleich
m
Πm / ϕ(Πm) = ∏ pip−i 1 . Gemäß einem Theorem von Mertens gilt für m → ∞:
i =1
m
∏ p p−1 =
i
i =1
i
eγ⋅ ln (pm) mit γ = 0,577215.. (Euler-Konstante) und eγ = 1,7810724...
Während dφ dementsprechend nur sehr langsam (prop. ln (pm)) zunimmt, wächst – wenn (∗
∗)
richtig ist – die max. Lücke Dm vergleichsweise schnell (prop. pm).
• Ein „schönes“ Ergebnis wäre für große m: Dm ≈ c⋅⋅ pm⋅ ln (pm) mit c =
13
1/ 2+ γ
2
(?)
2500
Dm
2000
1500
1000
Dm-Ist
Näherung: 0,535⋅pm⋅∆m
500
m
Bild 2: Vergleich Dm-Ist mit Näherungs-Formel
14
118
115
112
109
106
103
100
97
94
91
88
85
82
79
76
73
70
67
64
61
58
55
52
49
46
43
40
37
34
31
28
25
22
19
16
13
10
7
4
1
0
Anmerkungen:
• Zum Produkt ∏ p p−1
Die Euler’sche Produkt-Formel besagt: (ζ(s) =)
∞
n =1
Es ist z.B. ζ(2)–1 =
6
π2
∞
∑ n1 = ∏ p
s
i =1
pi s
s
i −1
für s > 1, reell
(Wahrscheinlichkeit, dass zwei zufällig ausgewählte nat. Zahlen
teilerfremd sind und Wahrscheinlichkeit, dass eine zufällig ausgewählte nat. Zahl quadratfrei
ist) und aus der Divergenz der harmonischen Reihe beim Grenzübergang s → 1 erkannte
Euler einen weiteren Beweis für die unendliche Anzahl der Primzahlen. Riemann dehnte die
Formel auf komplexe Werte von s aus – mit den bekannten Weiterungen.
m
Für s =1 ist
∑ 1i
= γ + ln(m) +
i =1
∞
1
2
(
1
m
–
B2 n
∑ n ⋅m
n =1
2n
) und die Reihe nähert sich mit wachsendem m
’von oben’ dem Wert γ + ln(m) an. (B2n: Bernoulli-Zahlen mit geradem Index)
Anders verhält es sich mit dem Produkt
∏ p p−1 : Eine Formel wie für die harmonische Reihe
p≤m
ist nicht bekannt; es ist aber bewiesen, dass der Wert des Produkts – als Folge der
schwankenden (lokalen) Dichte der Primzahlen – unendlich oft um den Wert eγ⋅ln(m)
oszilliert.
Hinsichtlich der max. Amplitude der Oszillationen gilt als z.Z. beste Abschätzung (Dusart):
eγ⋅ln(m)⋅(1 – ln 20,(2m ) ) < ∏ p p−1 < eγ⋅ln(m)⋅(1 + ln 20,(2m ) ) mit m > 2973
p≤m
Es ist nicht bekannt, bei welchem m das Produkt erstmalig kleiner als eγ⋅ln(m) ist. Im Bereich
bis m = 109 wurde vorliegend als kleinster Quotient für m = pi mit i = 46.254.156 der Wert
1,000.000.434.309.. ermittelt. Vermutlich ist die ’direkte’ Berechnung des Kreuzungspunktes
nicht möglich (vergleichbar mit der Frage, wann π(x) > li(x) ist).
• Zur max. Primzahl-Lücke (in Abhängigkeit von k bzw. x)
Die im Zusammenhang mit dem Thema „Große Primzahllücken“ meist behandelte Frage ist:
Wie groß ist die max. Primzahl-Lücke Lmax(x) im Intervall [2, x]?
Experimentell sind heute alle x-Werte (Primzahlen), nach denen eine bestimmte Lücke zum
ersten Mal auftritt, für alle L ≤ 2000 bestimmt worden. ‚Theoretisch’ ist das Problem aber
noch keinesfalls zufriedenstellend gelöst.
Nachstehend ein einfacher Ansatz:
Hinsichtlich des Intervall, in dem die k-te Primzahl zu finden ist, gilt (Dusart):
k⋅(ln k + ln(ln k) – 1 +
ln(ln k ) − 2 ,1
ln k
) ≤ pk ≤ k⋅(ln k + ln(ln k) – 1 +
ln(ln k ) − 2 , 0
ln k
) mit k > 683.383
Das ist ein erstaunlich präzises Resultat. Beispiel: k = 106. Aus der vorstehenden Ungleichung
folgt 15.479.360 ≤ pk ≤ 15.486.598 D.h. pk = 15479.360 + C mit 0 ≤ C ≤ 0ln,1⋅kk = 7238.
Tatsächlich ist pk = 15.485.863.
Wird die gleiche Rechnung mit k + 1 wiederholt, bedeutet das im Wesentlichen, dass das für
pk berechnete Intervall um etwas mehr als ln pk (mittlerer Abstand der Primzahlen an der
15
Stelle x = pk) „nach rechts“ verschoben wird.
≈ ln pk
*
*
Intervall für pk + 1
0,1 ⋅ k / ln k
Nimmt man an, die k-te Primzahl befände sich am linken Rand des für sie möglichen
Bereichs und die k+1-te am rechten Rand (siehe rote Punkte in der Skizze) wäre der Abstand
der beiden Primzahlen 0,1⋅k / ln k + ln pk. Also: Obergrenze für eine Primzahl-Lücke
zwischen der k-ten und der k+1-ten Primzahl:
Lk max ≤
0,1⋅k
ln k
+ ln(2k⋅ln k)
wobei pk mit 2k⋅ln k nach oben abgeschätzt wurde.
Im Beispiel ergibt das: Lk max ≤ 7256 für k = 106, was erwartungsgemäß noch viel ‚Luft’
enthält.
Es gibt natürlich eine Reihe wesentlich schärferer oberer Abschätzungen, die aber alle nicht
streng bewiesen sind. Die zur Zeit wohl beste – und bis 4⋅1018 bestätigte – geht von dem sehr
interessanten Postulat
1+ 1
pk + 1 < p k k aus (Firoozbakht) woraus folgt:
pk + 1 – pk < (ln pk)2 – ln pk für k > 3
Im Beispiel ergibt sich daraus mit pk = 15.485.863: Lk max < 257.
Tatsächlich ist im Bereich bis k = 106 die größte Lücke gleich 148 (k = 149689;
pk = 2010739; (ln pk)2 – ln pk = 196,14...).
(Genauere Herleitungen für Bereiche, in denen sich mindestens eine Primzahl befindet,
besagen (Rosser u. Schoenfeld):
Für x ≥ 2.010.760 gilt x < p < x + x / 16.597 und
für x > 1,1⋅1011 noch besser (Dusart): x < p < x + x / (25⋅ln2 x).
Diese Ergebnisse stellen wesentliche Verschärfungen gegenüber dem Bertrand’schen Postulat
dar, gemäß dem sich zwischen x und 2x mindestens eine Primzahl befindet.)
16
© Copyright 2024 ExpyDoc
