| |
|
 Autor: |
|
Thema: Eine Beschreibung der Primzahlen über die Verteilung der zusammengesetzten Zahlen
|
|
|
dr.c.n
(offline)
Newbie
Beiträge: 9
Geschlecht: 
Mitglied seit: 12.10.2009
Deutschland
|
|
Eine Beschreibung der Primzahlen über die Verteilung der zusammengesetzten Zahlen #1
|
Datum: 12.10.2009, 15:08 
|
Eine Beschreibung der Verteilung der zusammengesetzten Zahlen: Gedanken zur Verteilung der Primzahlen
Zusammenfassung:
Im Folgenden soll gezeigt werden, wie sich unter Kenntnis des kleinsten Primteilers aller Zahlen bis n (der kleinste Primteiler einer Primzahl p ist p) sich die genaue Zahl aller Primzahlen bis 6n+1 berechnen lässt.
Hintergrund: Da es keine Formel gibt, welche sicher zu einer Primzahl führt, ich aber auch keine Hinweise zur Verteilung der zusammengesetzten Zahlen gefunden habe wird im folgenden der Frage nachgegangen, ob sich die Verteilung der zusammengesetzten Zahlen nach einem mathematisch fassbaren Algorithmus beschreiben lassen.
Vereinfachung: alle Primzahlen bis auf die 2 sind ungerade Zahlen. Es sollen daher nur die ungeraden zusammengesetzten Zahlen untersucht werden:
Alle zusammengesetzten ungeraden Zahlen 2n+1 lassen sich als Produkt von zwei ungeraden Zahlen beschreiben:
2n+1= (2a+1)(2b+1)
mit a,b element von N.
Das lässt sich vereinfachen zu
n=2ab+a+b.
Für jedes m nicht element der Verknüpfung(a,b): 2ab+a+b gilt:
2m+1=prim.
Nebenerkenntnis: jede gerade Zahl, welcher keiner Primzahl folgt, ist als Summe der Flächen von zwei Rechtecken mit der Form 2ab und 2(a+1)(b+1) darstellbar.
 
Betrachtung der Elemente der Verknüpfung (a,b): (2a+1)(2b+1)
Die Kenntnis der Zahl m der verschiedenen Elemente dieser Verknüpfung bis zu einer Zahl n wird als n-m die Zahl der Primzahlen bis zu einer Zahl n widerspiegeln.
Nachfolgende Tabelle zeigt die ersten Werte dieser Verknüpfung:
a= 1 2 3 4 5 6
b=
1 4 7 10 13 16 19
2 7 12 17 22 27 32
3 10 17 24 31 38 45
4 13 22 31 40 49 58
5 16 27 38 49 60 71
6 19 32 45 58 71 84
7 22 37 52 67 82 97
8 25 42 59 76 93 110
9 28 47 66 85 104 123
10 31 52 73 94 115 136
11 34 57 80 103 126 149
12 37 62 87 112 137 162
Feststellung 1: Die Verknüpfung ist spiegelsymmetrisch an der Diagonalen.
Feststellung 2: Die erste Reihe mit b=1 zeigt als Inkrement von Element zu Element die 3. In dem betrachteten System der ungeraden Zahlen steht ja auch die 1 für die reale 3.
Feststellung 3: Jede weitere 3. Reihe b=3n+1 enthält nur Elemente, welche auch in der ersten Reihe vorkommen. Begründung: Jedes b=3n+1 steht in der realen Zahlenwelt als 2b+1=2(3n+1)+1=6n+3 für eine durch 3 teilbare Zahl.
Gleiches gilt für die 2. Reihe (reale 5) und dann für jede weitere 5. Reihe etc.
Nur wenn b für eine Primzahl in der realen Welt steht, kommen also Elemente mit neuen Werten in dieser Tabelle hinzu. Ansonsten steht das Element bereits weiter oben in einer Reihe.
Feststellung 4: Wegen der Spiegelsymmetrie gilt die Feststellung 3 auch für alle a.
Programm zur Berechnung der Anzahl von verschiedenen Elementen der
Verknüpfung(a,b): (2a+1)(2b+1) unterhalb einer vorgegebenen Grenze
Beispiel: gesucht wird die Anzahl verschiedener Elemente mit einem Wert unter 50:
Farblich markiert sind die Zahlen kleiner 50.
a= 1 2 3 4 5
b=
1 4 7 10 13 16
2 7 12 17 22 27
3 10 17 24 31 38
4 13 22 31 40 49
5 16 27 38 49 60
6 19 32 45 58 71
7 22 37 52 67 82
8 25 42 59 76 93
9 28 47 66 85 104
10 31 52 73 94 115
11 34 57 80 103 126
12 37 62 87 112 137
13 40 67 94 121 148
14 43 72 101 130 159
15 46 77 108 139 170
16 49 82 115 148 181
17 52 87 122 157 192
18 55 92 129 166 203
Es folgt jetzt praktisch eine Quantifizierung des Sieb der Erastosthenes:
die Zahl 50 entspricht in der realen Welt der 101. Die Wurzel hieraus ist etwa 10 , die nächst kleinere ungerade Zahl 9 und damit beträgt das maximale a=4.
Jetzt gilt es zunächst die Elemente im Quadrat von (1,1) bis (4,4) zu zählen. Wegen der Symmetrie ist das nur ein Dreieck inclusive der Diagonale. Abzuziehen ist aber hier von jedes Element für a,wenn a nicht für eine ungerade Primzahl steht (im Beispiel die 40).
Weiterhin ist für jede weitere Reihe zu berechnen, wie viele Elemente kleiner gleich der untersuchten Zahl (im Beispiel die 50) die Reihe enthält. Es lässt sich ferner zeigen, dass wenn b für keine Primzahl in der realen Welt seht, in der Reihe maximal aber nur die Zahl der Primzahlen bis inklusive des kleinsten Primteilers dieser Zahl gezählt wird (siehe b=7, hier wird nur das Element 22 nicht aber die 37 gezählt).
Wie der Algorithmus funktioniert, ist dem nachfolgenden Basic-Programm zu entnehmen.
 
FreeBasic Programm zur Berechnung der Zahl der Primzahlen bis zu einer angegebenen Höchstgrenze:
dim a As ULongInt
dim b As ULongInt
dim bp As ULongInt
dim bc As ULongInt
dim ca As ULongInt
dim cb As ULongInt
dim ai As ULongInt
dim amax As ULongInt
dim bi As ULongInt
dim i As ULongInt
dim j As ULongInt
dim n As ULongInt
dim n1 As ULongInt
dim shared p (5000000,4) As integer
dim q As ULongInt
dim z As ULongInt
dim f As double
dim f1 As double
Z=0 rem wird die primzahlen zählen
n= 5000000
For i= 1 to n rem Schleife um die Primzahlen und die
Rem notwendigen Informationen zu erzeugen
If p(i,4)= 0 Then rem p(i,4)= 0 hat bisher keinen Primteiler
z=Z+1 rem primzahlzähler um 1 hochgesetzt
p(i,1)= 2*i+1 rem primzahl wird eingetragen
p(i,2)= 1 rem 1 = primzahl
P(i,4)=i rem odd#
For j = p(i,1)+i to n step p(i,1)
If p(j,4)=0 Then rem wenn bisher noch keinen Primteiler dann
rem jetzt setzen
p(j,4)=i rem nummer des kleinsten Primteiler als odd#
EndIf
Next j
EndIf
P(i,3)=z rem Zahl der primzahlen <=i
Rem Print i ,z
Next i
Rem JETZT KOMMT DIE BERECHNUNG
test:
input “bitte eine ungerade Zahl <=30.000.001 eingeben “, n1
n=(n1-1)/2
amax = int((n-1)/3)
bp=0
bc=0
For ai = 1 to amax
bi= int((n-ai)/(2*ai+1))
If p(ai,2)=0 Then rem wenn ai nicht prim
If bi>=p(ai,4) Then Rem wenn bi groesser = dem kleinsten Teiler
bc=bc+p(p(ai,4),3) Rem nur primzahlen bis zum kleinsten
rem Teiler addieren
Else
bc=bc+p(bi,3) Rem sonst Primzahlen bis bi addieren
EndIf
Else Rem wenn ai prim
If bi>ai Then Rem nur primzahlen bis max ai addieren
Bp=Bp+p(ai,3)
Else
bp=bp+p(bi,3) rem nur primzahlen bis max bi addieren
EndIf
EndIf
B=bc+bp
Next ai
Print “Dis Zahl der Primzahlen bis incl. “;n1; “ ist gleich “; n-b+1
goto test:
end
Ich hoffe auf Kritik
Carsten Neumann
|
|
|
dr.c.n
(offline)
Newbie
Beiträge: 9
Geschlecht:
Mitglied seit: 12.10.2009
Deutschland
|
|
|
Re: Eine Beschreibung der Primzahlen über die Verteilung der zusammengesetzten Zahlen #2
|
Datum: 12.10.2009, 15:10
|
Noch vergessen: die Schlüsse!
Überlegungen aus dem beschriebenen Algorithmus
Als Naturwissenschaftler (Medizin) bin ich Experimente gewohnt, d.h. Einflussgrößen werden verändert und man sieht wie sich das System verhält. Bei dem vorgegebenen und fixen System der Zahlen ist das natürlich nicht durchführbar.
Trotzdem sei eine einfache Überlegung erlaubt:
Wenn eine Reihe durch ein b definiert wird, welches für eine Primzahl steht, werden mehr Elemente erzeugt, die für eine zusammengesetzte Zahl stehen, als wenn b für eine Zahl steht, welche z.B. als kleinsten Primteiler die 3 hat (dann wird nur ein Element hinzugezählt).
Dieser Satz gilt für den Algorithmus auch in seiner Umkehrung.
Das heißt: gibt es an einem Ort relativ viele Primzahlen, wird es in der weiteren Folge mehr zusammengesetzte Zahlen und damit weniger Primzahlen geben und umgekehrt.
Das System der Primzahlen reguliert sich selbst!
Der Algorithmus kann auch als Primzahlentest dienen:
#p(n+2)-#p(n)=1 für n+2=prim
Die Verteilung der Primzahlen (bis zu einer Zahl n) bestimmt die Anzahl (und die Verteilung) der weiteren Primzahlen (und nicht nur bis 6n+1).
Oder ganz einfach ausgedrückt (da wir uns im ungeraden Zahlenbereich aufgehalten haben):
Die 3 bestimmt die Welt der Primzahlen
Primzahlen seien statistisch zufällig verteilt. Da es einen Algorithmus für die zusammengesetzten Zahlen gibt, scheint diese Zufälligkeit eher nur so auszusehen.
|
|
|
dr.c.n
(offline)
Newbie
Beiträge: 9
Geschlecht:
Mitglied seit: 12.10.2009
Deutschland
|
|
|
Re: Eine Beschreibung der Primzahlen über die Verteilung der zusammengesetzten Zahlen #3
|
Datum: 15.10.2009, 22:44
|
Ein Programm zu spielen:
Du bestimmst, ob eine Zahl prim ist und sehe die Auswirkungen
Im ersten Basic Programm wurde die Tabelle reihenweise untersucht und es brauchte viel Information zu den Zahlen bis n/6 wenn wir bis n die Anzahl der Primzahlen wissen wollten.
Das nachfolgende Programm untersucht die Tabelle spaltenweise. Es ist recursiv geschrieben und benötigt nur das Wissen um die Primzahlen bis √n. Es werden keine Primzahlen berechnet und auch die zusammengestzten Zahlen aufgrund der vorgegebenen Abhängigkeit mit der Verteilung der Primzahlen in ihrer Menge bestimmt.
Da das array a() die Information darüber enthält, ob eine Zahl prim ist oder nicht kann durch Veränderung der Verteilung der Primzahlen abgeschätzt werden, wie sich dies auf die weitere Verteilung der Primzahlen verhält.
Viel Spaß beim herumspielen….
Hintergrund: ich behaupte: im Unendlichen gibt es zwischen 2 Quadratahlen unendlich viele Primzahlen. Dabei ist die Goldbachsche Vermutung - zwischen zwei Quadratzahlen gibt es mindestens 2 Primzahlen - nicht einmal bewiesen.
Möglicherweise kann man ja mit einer Formel, die verständlicher ist als die Verteilung der Primzahlen und diese leicht überschätzt aufgrund der im Programm aufgezeigten Abhängigkeit diesen Satz beweisen……..
Freebasic Programm:
dim shared a(1000000) As byte Rem to look at number up to 10^12
dim shared t As ulongint
dim shared u As ulongint
dim shared s As double Rem not really needed just For timing
dim shared maxi As ulongint Rem not really needed just to check On highest prime used in table a(I)
Rem noofprod = number of products up to x with divisor <=i
Rem noofprim = number of primes <= x
Declare Function noofprod ( x As ulongint, i As ulongint ) As ulongint
Declare Function noofprim (x As ulongint )As ulongint
Function noofprod ( x As ulongint, i As ulongint ) As ulongint
dim m As ulongint
dim n As ulongint
dim k As ulongint
Rem If i is not prime search Next lower prime unless it is 3
Do while i*(2*i+2)> x And i>1
i=i-1
loop
Do while a(i)=0 Rem two statements For sqr(x) comes up with numbers much to high
i=i-1
loop
If maxi<i Then
maxi=i
EndIf
Rem If i=2 it is easy
If i=1 Then
x=int((x-1)/3)
return x
Else
n=int((x-1)/3) Rem all numbers For devisor 3
For k=2 to i
If a(k)=1 Then Rem If k is prime
m= int((x-k)/(2*k+1)) Rem all numbers For prime devisor k
n=n+m-noofprod(m,(k-1))
Rem - all numbers that have a devisor smaller than prime k
n=n- k+noofprod(k,(k-1))+1
Rem the correction to the diagonal of the table
EndIf
Next k
x=n
return x
EndIf
End Function
Function noofprim ( y As ulongint)As ulongint
dim l As ulongint
l = int((y-1)/2) Rem l is # of odd numbers
return (l-noofprod(l,int(sqr(y)/2-1))+1) Rem +1 is correction For even prime number 2
End Function
Open "c:/basic/primes.txt" For input As #1 Rem by "ecprime 1.000.001 -p1"
input #1, u Rem nicht die 2
Do while not eof(1)
input #1, u
a((u-1)/2)=1
Rem hier wäre es ideal, Primzahlen zu löschen oder zu definieren
loop
Close #1
Do while u>0
input "(0=end) Calculate # of Primes up to: ", u
If u=0 Then
End
EndIf
s=Timer
Print noofprim (u), maxi
Print "time: ";Timer-s;" sec"
loop
Um die Primzahlen in die Tabelle einzufügen, habe ich sinnvoller Weise das Programm „ecprime.exe“ verwendet. Das hat auch zur Kontrolle der Ergebnisse gedient.
Zum spielen schlage ich zunächst folgenden Einschub vor:
If t Mod 30 = 17 Then
rem Jede 30. Zahl an einer möglichen Primstelle
a((t-1)/2)=0 rem ist 1=prim oder 0=nicht prim
EndIf
Mit der Bitte um Kritik!!!
|
|
|
dr.c.n
(offline)
Newbie
Beiträge: 9
Geschlecht:
Mitglied seit: 12.10.2009
Deutschland
|
|
|
Re: Eine Beschreibung der Primzahlen über die Verteilung der zusammengesetzten Zahlen #4
|
Datum: 15.10.2009, 22:46
|
UNleserlicher Text:
√n = Wurzel (n)
|
|
|
dr.c.n
(offline)
Newbie
Beiträge: 9
Geschlecht:
Mitglied seit: 12.10.2009
Deutschland
|
|
|
Re: Eine Beschreibung der Primzahlen über die Verteilung der zusammengesetzten Zahlen #5
|
Datum: 17.10.2009, 03:50
|
Fehlerteufel!!
im Programm zu spielen hat sich ein Fehlerteufel eingeschlichen:
Der Funktionsaufruf von noofprod (x,y) aus der Funktion noofprim (n) berechnet ein zu kleines 2. Argument, das größte Primzahlenquadrat wird dadurch nicht regelmäßig als Produkt mitgezählt.
Richtig lautet die Befehlszeile:
return (l-noofprod(l,int((sqr(y)-1)/2))+1) Rem +1 is correction for even prime number 2
|
|
|
|
|
|
