Primzahlen (Prime number; Sammlung interessanter Fakten)

   

Home...

 

1.      Primzahlpolynome

Zunächst 4 unterschiedliche Quellen zu Primzahlpolynomen (alle unterschiedlich!):

PrimzahlpolynomWiFo1985S66 

PrimzahlpolynomWalterKranzer_SoInteressantIstMathematik 

PrimzahlpolynomErnst-UlrichGekelerUniversitaetSaarland 

PrimzahlpolynomMarkusSchepkeUniHannover2010 

 

Link: http://www.aladin24.de/prim/index.htm

 

2.      Primzahlerzeugende Folgen

·        Jede Zahl testen: Iterationsrechner Beispiel 47 per Funktion IsPrime(x)

·         Rekursion / Iteration aB[i+3]=aB[i]+aB[i+1];aC[i+1]=aB[i+1]/(i+1); siehe Übergabe an Iterationsrechner

Die 1 am Anfang von aD[0] ist absichtlich nicht „wegprogrammiert“, da nur einige Menschen die „2“ als erste Primzahl definierten.

·        Folge mit ggT(x,y): Übergabe an Iterationsrechner

·        Folge A202018 : Übergabe an Iterationsrechner (Polynom erzeugt 40 Primzahlen)


3.      Primzahlzwillinge (Primzahlen Zwillinge engl. Twin Primes)

Zahlenpaar mit Eigenschaft: IsPrime(x) & IsPrime(x+2)
A001359 = A014574 - 1A006512 = A014574 + 1
35
57
1113
1719
2931
4143
5961
7173
101103
......
12609891260991
1840919918409201
49999950174999995019
4999999999999999849149999999999999998493
49999999999999999999999999999999999948194999999999999999999999999999999999994821
3265649959118574797277674739651242588583836442298132656499591185747972776747396512425885838364422983
......
318032361 · 2107001 - 1318032361 · 2107001 + 1
3756801695685 · 2666669 - 13756801695685 · 2666669 + 1

·        Iterationsrechnerbeispiel 46: Iterationsrechner Beispiel 46


4.      Große Primzahlen selbst ausrechnen

a) online (Anfang und Ende; mittlere Stellen bleiben unbekannt)

·        2^607-1: an Iterationsrechner übergeben

·        94550! - 1 = 1.3855410590400807467090325 e429389: an php Umkehrfunktionen Rechner übergeben

·        2^43112609 - 1 = 3.1647026933025592314345372 e12978188: an php Umkehrfunktionen Rechner übergeben (pow mit N=1000000000000)

·        2^57885161 - 1 = 5.81887266232246442175100212113 e17425169: 48. Mersenne-Primzahl


b) offline exakt alle Stellen einer Mersenne-Primzahl ausrechnen
Da die exakte Berechnung von grossen Zahlen über 9 Mio. Stellen extrem lange dauert, muss man schon einen optimierten Compiler einsetzen.
PureBasic erzeugt echten 64 Bit Maschinencode und optimierte Langzahlarithmetik gibt's kostenlos dazu (M44 in etwas über 40 min):
PureBasic grosse Mersenne Primzahl exakt ausrechnen
Ergebnisse:
M44_2hoch32582657-1 ; M45_2hoch37156667-1 ; M46_2hoch42643801-1 ; M47_2hoch43112609-1 ; M48_2Hoch57885161-1

Neuer Weltrekord 07.01.2016: größte bekannte Primzahl aller Zeiten

primes.utm.edu 74207281
mersenne.org
2^74207281-1 = Mxx_2Hoch74207281-1.zip download


5.      Die Funktion Prime(x) und ihre Summendarstellung (erzeugt die x. Prinzahl)


Schon Euler entdeckte das nach ihm benannte Euler-Produkt (später durch Riemann präzisiert): Zeta(x)= 
2 Sonderfälle beweisen die unendliche Anzahl der Primzahlen:
§5a: Grenzwert x -> 1: Die Divergenz der harmonischen Reihe (x-> unendlich für HarmonZahl(x)=Digamma(x+1)+A001620 und Zeta(1)=unendlich) führt zwangsläufig zum Schluß, daß das Produkt unendlich ist -> also muss es unendlich viele Primzahlen geben.
§5b: x=2: Zeta(2)= Pi²/6 = irrationale Zahl! Man kann nur mit unendlich vielen Bruch-Produkten eine irrationale Zahl erzeugen!
Später fand man eine exakte Formel zur Erzeugung der x. Primzahl:
Prime_Summenformel 
online berechenbar auch für sehr große x per Umkehrfunktionen Rechner 1. Komboboxeintrag
wobei für die Anzahl der Primzahlen bis k gilt:
PrimePi(x) oder PrimePi(x)
Später wurde mit der Formeln von Mertens die Summe der Primzahlenkehrwerte verfeinert:  
 
Mit der Zeit wurden immer bessere Approximationsformeln für große x gefunden:  

Damit und mit
n*(Log[n] + Log[Log[n]] - 1) < Prime[n] < n*(Log[n] + Log[Log[n]]) ; n > 5
kann man auch beweisen, dass die Lücken benachbarter Primzahlen unendlich groß werden können:
lim Prime(n+1)-Prime(n) =
lim ((n+1)*(Log[n+1] + Log[Log[n+1]] - 1 + (Log[Log[n+1]] - 2)/Log[n+1]))-(n (Log[n] + Log[Log[n]] - 1 + (Log[Log[n]] - 2)/Log[n]))
= UNENDLICH

6.      Sophie Germain Primzahlen A005384 und A005385

Zahlenpaar mit Eigenschaft: IsPrime(x) & IsPrime(2x+1)
A005384=Sophie Germain PrimzahlenA005385
25
37
511
1123
2347
2959
4183
53107
83167
......
1939136338782727
9824525631964905127
100000000000000000000000000000007171200000000000000000000000000000014343
9999999999999999999999999999999999902211999999999999999999999999999999999980443
49999999999999999999999999999999999895399999999999999999999999999999999999979079
49999999999999999999999999999999999898219999999999999999999999999999999999979643
99999999999999999999999999999999999999999999965759199999999999999999999999999999999999999999999931519
H.Dubner fand diese 727 Stellen 1999 Dubner Primzahl mit 23
......
3364553235 · 288888 - 1(3364553235 · 288888 - 1)·2+1
18543637900515 · 2666667 - 1(18543637900515 · 2666667 - 1)·2+1


7.      Primzahldrilling (A022004 prime triples (p, p+2, p+6))

A022004A022004 +2A022004 +6
5711
111317
171923
644051644053644057
100000000000000000000000000000076884110000000000000000000000000000007688431000000000000000000000000000000768847
.........
81505264551807 · 233444 - 181505264551807 · 233444 +181505264551807 · 233444 +5


8.      Primzahlvierling



Exotische Primzahlen:
A005478[14]=Fibonacci(A001605[14]=137)=19134702400093278081449423917
A005478[15]=Fibonacci(A001605[15]=359)=475420437734698220747368027166749382927701417016557193662268716376935476241

=32656499591185747972776747396512425885838364422981 (Primzahlzwilling aber keine Sophie Germain Primzahl)


9.      Vorkommen und Anwendungen

- Informatik: http://de.wikipedia.org/wiki/RSA-Kryptosystem
- Informatik: gleichmäßige Belastung vieler Prozesse und Threads (Multitasking, Multiprocessing, PC, Server usw.) durch Taktrate=NextPrimeAfter(Taktrate) -> dadurch keine Aufschaukelung, da die Primzahl-Perioden nie Vielfache haben und so nie zeitgleich ablaufen
- Mathematik: Berechnung für Pi: Kreiszahl Berechnung per §3e
- Biologie: Fortpflanzungsrhythmus von Tieren =NextPrimeAfter(>4), damit sind Fressfeinde überfordert siehe http://de.wikipedia.org/wiki/Zikade#Fortpflanzung_und_Entwicklung
Was Zikaden mit Primzahlen zu tun haben
- Mechanik: Querschwingungen der Flügel werden bei N=NextPrimeAfter(N) weniger belastet (Laufrad einer 23-flügeligen Pelton-Turbine)
- Chemie: Es gibt in dem Zahlenbereich von 1 bis 83 der stabilen Ordnungszahlen und der beiden Lückenzahlen folgende Primzahlzwillinge: (5;7),(11;13),(17;19),(29;31), (41;43),(59;61),(71;73) http://www.primzahlen.de/primzahlen/chemie.pdf
- Astro- & SETI: http://de.wikipedia.org/wiki/SETI (bei Suche und Kontaktaufnahme spielen Primzahlen eine Rolle)
Vorkommen unter Vorbehalt (kann Zufall sein):
- Mathematik: in Alle n-stellige Zeichenketten garantiert in Pi zu finden: A036903≈10^n*(1.7+2.15*n)=43n*2^(n-2)*5^(n-1)+17*10^(n-1) -> 4 Primzahlen!
- (Prime(21)=73 Quasare = größte bisher entdeckte Struktur im Universum http://www.golem.de/news/astronomie-forscher-entdecken-unermesslich-grosse-struktur-im-all-1301-96932.html )
- http://www.astrobegleitung.de/Das_sonnensystem_als_organismus_primzahlen.html
- http://www.drillingsraum.de/room-forum/showthread.php?tid=1060
- Funktion PowPowMod() für Divisionsrest extrem großer Potenzen

Schnelle Prim-Algorithmen für große Zahlen:
1. http://en.wikipedia.org/wiki/General_number_field_sieve
2. http://de.wikipedia.org/wiki/Quadratisches_Sieb
3. http://en.wikipedia.org/wiki/Lenstra_elliptic_curve_factorization (Elliptic Curve Method)


10.      Online Rechner Primfaktorzerlegung

- Funktion PrimfaktorenProdukt(x) (prime factorization 78 digits)
- Carmichael-Zahl-Faktorisierer (1000 digits)

50 Mio. Primzahlen:
http://primes.utm.edu/lists/small/millions/
Typen & Gruppierungen:
https://en.wikipedia.org/wiki/List_of_prime_numbers
http://mathworld.wolfram.com/TwinPrimes.html
http://mathworld.wolfram.com/PrimeTriplet.html
http://mathworld.wolfram.com/PrimeQuadruplet.html
http://mathworld.wolfram.com/PrimeConstellation.html
http://mathworld.wolfram.com/SexyPrimes.html
http://mathworld.wolfram.com/CousinPrimes.html
http://mathworld.wolfram.com/SophieGermainPrime.html
http://mathworld.wolfram.com/PrimeGaps.html (Lücken)