Mathematiker: Der kleinste nicht gefundene Abstand ist nun 264:


Nicht mehr:
2357881993 und 2357882257

Edit: das fehlende paar zu dem fehlenden Abstand von 286 lautet:
2842739311 und 2842739597 (und ein weiteres liegt bei ca 4,05 mrd)

Hallo,
ich habe mein altes Primzahlsieb wieder ausgekramt und für die Suche nach Primzahlabständen modifiziert. Grundlage ist Gammatester mp_arith.
Blockweise werden jeweils 5 Millionen Zahlen gesiebt und danach ausgewertet. Abstände ermittle ich nur ab 200 und die Startzahl sollte auch nicht kleiner als 100 Millionen sein.

Natürlich ist dies nicht so schnell wie Dein Sieb, hat aber den Vorteil, dass es nach "oben offen" ist.
Wenn Dein Computer schnell genug ist und Du ihn quälen willst, kannst Du auch bis in die Billionen hinein suchen.
Mein PC ist im Moment bei 14 Milliarden und bis 332 sind alle Abstände gefunden.

Beste Grüße
Mathematiker

Nachtrag: Ab 30827138509 folgt ein Abstand mit 334. Jetzt bis 35 Milliarden gesucht und kein Paar für 362.
Nachtrag 2: Ich habe eine Erweiterung (Rev 1) eingebaut. Markiert man Weiterrechnen, so werden bei Abbruch die erzielten Ergebnisse in liste.txt gespeichert und beim Neustart an dieser Stelle weitergerechnet.
Jetzt bin ich bei 52 Milliarden. Der kleinste fehlende Wert ist 370, bis 1000 fehlen insgesamt noch 297 Paare.

Rev 2: Horst_H hat einen bösen Fehler in meinem Programm gefunden. Ich hoffe, dass er jetzt behoben ist. Danke für den Hinweis.

Freut mich
Und ich denke in meinem prog brauch ich das nicht einbauen.. denn
1. mein prog geht nur bis 12 Milliarden und
2. ich bin mir nichtmal mehr sicher, dass meins schneller ist^^
denn vorher habe ich die primzalhne bis 4 Milliarden in ca 15 sek ausgerechnet.. inzwischen bin ich bei nur noch 50 sek (Bit-Boolean)..

ich wüsste zwar jetzt weitere "verkleinerungsmaßnahmen" wie Array halbieren, da nur ungerade zahlen Primzahlen sein können, oder Nach 4 Mrd BooleanArray gegen Int Array ersetzen und nur "richtige" abspeicher.. sozusagen wird aus
Bool[1] (false)
Bool[2] (true)
Bool[3] (true)
Bool[4] (false)
Bool[5] (true)

dann

Int[1] := 2;
Int[2] := 3;
Int[4] := 5;

webei ich natürlich dann wie schon erwähnt wurde nur die Differenz abspeichern müsste, hierdurch wäre kein 32Bit Variable nötig, sondern eine 16bit variante würde reichen (z.B. Word)

aber das würde alles die rechenzeit so stark erhöhen, dass ich mich jetzt daran mache ein nach oben offenes sieb zu programmieren

Denn: ich denke DIREKT auf Minimialer Ram zu programmieren ist letztendlich schneller, als auf Zeit zu programmieren und dann auf Ram zu optimieren

Hallo,

@Mathematiker:
Wie kannst Du bis 52x1e9 nur noch 297 fehlende haben:
primes.utm.edu/notes/GapsTable.html

Zitat:

gap Auftreten bei 463 42.652.618.343 467 127.976.334.671

Mist, Du bist bei 52x10e9 Primzahl also bei

Zitat:

803 90.874.329.411.493 [Nicely99]

Tatsächlich hat mein Programm 2h17 min für die Primzahlen bis 1e12 gebraucht.

Zitat:

539 738832927927 .. 738832928467

Aber ich habe noch das Auftreten der Abstände gezählt, die im unterern Bereich nicht stimmt, weil ich vorgesiebtes Sieb nutze, in dem 2,3,5,7,11,13 und deren Vielfache fehlen.
Exemplarisch

Zitat:

479 4 477 2 475 2 473 10 471 3 469 4 467 5 465 2 463 3 461 12 ... 19 1298682892 17 2246576317 15 1202533146 13 1556469349 11 2753597777 9 2052293026

12 und 18 kommen als Abstand am häufigsten vor.

Gruß Horst

Edit 16:40 Uhr:
In so hohen Zahlbereichen ist so simples sieben zu langsam.50,8 Mio zahlen zu verarbeiten, wovon über 99 % ( ab 10 Mio) bei jedem Durchgang nicht im Sieb landen ist sehr uneffektiv.
deshalb hatte Gammatester mal vorgeschlagen einfach mit den ersten Primzahlen bis 2^16 zu sieben und dann erst Miller-Rabin zu starten.Wenn die 6542 Zahlen gesiebt haben, wobei Zahl und Uebertrag vom Typ word sein können und dann der Test kommt, muss ich hier noch 50.8 Mio Zahlen ( Zahl Dword, Uebertrag int64 )verarbeiten.In der Zeit kann man viele Miller-Rabin Tests machen.

Hallo Horst_H,

Horst_H hat folgendes geschrieben :

Tatsächlich hat mein Programm 2h17 min für die Primzahlen bis 1e12 gebraucht.

Gratulation. Das ist richtig schnell. Für 1 Billion brauche ich geschätzt 16 Stunden.

Horst_H hat folgendes geschrieben :

In so hohen Zahlbereichen ist so simples sieben zu langsam.50,8 Mio zahlen zu verarbeiten, wovon über 99 % ( ab 10 Mio) bei jedem Durchgang nicht im Sieb landen ist sehr uneffektiv.

Deshalb siebe ich mit 41537 Primzahlen (ohne 2) bis 499979 und überlasse den Rest dem Rabin-Miller-Test.

Nachdem ich gesehen habe, dass das Thema im Netz schon soweit abgearbeitet ist, dass schon Paare mit 2000 und mehr Abstand gefunden wurden (wohin ich mit meinem Programm nie komme), habe ich die Suche auf "einsame Primzahlen" abgeändert.
Unter einer einsamen Primzahl versteht man eine Primzahl p, deren Summe s der Abstände zur vorhergehenden und zur nachfolgenden Primzahl größer ist, als bei jeder vorhergehenden Primzahl.
Zum Beispiel ist die 211 eine einsame Primzahl. Die vorhergehende Primzahl ist 199, die nachfolgende 223. Deren Abstand ist mit 24 so groß, wie bei keiner Primzahl < 211.

Dazu habe ich im Netz noch nicht viel gefunden. Man kann also "Geschichte schreiben".
Gegenwärtig ist mein Programm bei 13 Milliarden (15 Minuten) und hat als größte einsame Primzahl 10726905041; Abstand 438 von 10726904659 bis 10726905097 gefunden.

Beste Grüße
Mathematiker

Wunderbar soviele Primzahl Verwendungszwecke^^

Mathematiker: du beschäfitgst dich also mit "einsamen Primzahlen"
Horst_H: du beschäftigst dich also mit dem Abstand?

Dann werde ich mal zurückspringen und eine Liste der "immer größer werdenden Abstände zwischen den Primzahlen" erstellen (bis 4 Mrd)

Und: @alle^^ warum kann Delphi nicht über 2^32 -1 hinaus ? (ja Delphi ist eine 32-Bit Anwendung und somit ist 2^32 -1 die größte mögliche zahl...)
aber Cardinal*Cardinal = >2^32 -1 ... IMMER ! hierdruch erreiche ich viele Fehler
also Beispiel:
4 Mrd * 2 = 8Mrd (wäre logisch) mein Delphi spuckt aber ganz komische zahlen aus... (z.B. 3.705.032.704 also ca 3,7 Mrd)

Ihr könnt es ja auch mal testen:

hierdurch kann nich nämlich keine Primzahlen > 2^32 -1 errechnen

teilweise wird auch:

Zitat:

Überlauf bei Konvertierung oder arithmetischer Operation

ausgegeben...

Cardinal ist vorzeichenloser Int, insofern halt bis 2^32-1.
Dein Ergebnis sind die Bits 0-31 des korrekten Produktes.

Für Größere Zahlen: int64 nehmen

IhopeonlyReader hat folgendes geschrieben :

1 im "Alle setzen" ist die 8Bit-Variante schneller ! 2 im erstellen, loeschen, alle lesen nicht testbar (von mir), da die werte immer schwankten, mal das mal das war größer/brauchte mehr zeit Deshalb würde ich euch einfach mal bitte diese Units auszutesten und evt. sogar verbesserungen vorzuschlagen

Da sich dazu noch keiner wirklich geäußert hat... habe ich mein Sieb des Eratosthenes mal auf beide Varianten aufgebaut.. (dank der Units nur 3 kleine Änderungen (uses list ändern, typ von TBitBooleans8 zu TBitBooleans32 ändern, beim erstellen anstatt TBitBooleans8.erstellen(Anzahl) TBitBooleans32.erstellen(Anzahl)) also die 8 durch 32 ersetzten

Bei vielfachen Lesen und schreiben, sind hier ein paar Verwerte zum Vergleich:

Zitat:

Basis (8 oder 32)...............Primzahlen bis:...............Initialiserung (alle Setzen)...............Zeit (für alle Berechnungen und Zugriffe auf Booleans) 8..............................100mio..............................0,03..................................................2,668 32..............................100mio..............................0,58..................................................2,21 8..............................1 Mrd...............................0,28..................................................28,174 32..............................1 Mrd...............................5,43..................................................24,54 8..............................2 Mrd................................0,53.................................................57,877 32..............................2 Mrd................................11,51................................................50,099 8..............................3 Mrd................................0,76.................................................92,261 32..............................3 Mrd................................16,5.................................................77,66 8..............................4 Mrd................................1,03 ................................................120,104 32..............................4 Mrd................................21,6 ................................................104,5

Fazit: Zum einzelnen Lesen/Schreiben ist die Bit-Boolean Variante aufbauend auf 32 Bit schneller ( ca 13% schneller )
Allerdings braucht man zum initialisieren ca 20x so lang! Somit ist die GesamtZeit größer als die zum 8 Bit Variante...
Wenn es eine Möglichkeit gäbe, die 32-Booleans aufeinmal auf True/False zu setzen wäre die 32 Bit variante geeigneter, so allerdings ist bei kleinen Berechnungen die 8 Bit Variante besser

(Für alle die sich fragen warum das so ist: 1. Schaut euch die Units doch einfach an^^... das liegt daran, dass bei der 8Bit Variante Byte als Grundlage genommen wird, wenn man also alle Bits auf True setzen will, setzt man den ganzen Byte auf 255 (2^8 -1), will man alle Bits in dem Byte auf 0 setzten so genügt es das Byte auf 0 zu setzen.. Bei der 32er Variante wird jedes einzelne Bit durchgeganen)
um 64 Bit-Booleans auf True zu setzen, wird bei der 32-variante 2x32 Bits auf 1 gesetzt, bei der 8-variante 8x1Byte auf 255 gesetzt
somit stehen 64 den 8 gegenüber... ebenfalls dauert es länger ein Bit auf True zu setzen, als ein Byte einem Wert zuzuweisen (komisch?!)
hierdurch entsteht das 20 zu 1 verhältnis

wieso wird gesagt
if ( (VMrd)>=floor(power(T, 1/2))) then
ergäbe immer True? wenn T>(4Mrd)² ist dann nicht! oder sieht Delphi dann nur den Bereich bis 2^64 -1 (aber selbst dann.. die wurzel davon wäre nämlich ca 2^32 und somit >4Mrd?

Aber beim 32bit kann man das doch genau so machen??

oder so...

@jfheins
schau dir bitte erstmal die Zusammentsetztung der 32-Bit-Variante von Horst_H an...

Zitat:

Verfasst: Mi 17.04.13 13:01

oder lade dir die Unit (32Variante) von mir herunter (beides in diesem Topic auf seite 2)

Denn die 32er Variante basiert NICHT auf Integer, Cardinal oder so..

IhopeonlyReader hat folgendes geschrieben :

Fazit: Zum einzelnen Lesen/Schreiben ist die Bit-Boolean Variante aufbauend auf 32 Bit schneller ( ca 13% schneller ) Allerdings braucht man zum initialisieren ca 20x so lang!

Beim Sieb des Erastothenes kann man doch die Zahlen entsprechend vorinitialisieren. Nehmen wir mal an, ein nicht gesetztes Bit bedeutet keine Primzahl. Bei einem Integer ist das höchstwertigste Bit links, das niederwertigste Bit rechts. Statt nun beim Initialisieren alle Bits auf 1 zu setzen, kann man auch gleich alle geraden Zahlen auf 0 setzen. Das erspart das Sieben mit der Primzahl 2. --> 01010101010101010101010101010101. Das entspricht dezimal 1.431.655.765. Danach müssen einmalig zwei Bits im ersten Integer anders gesetzt werden (1 keine Primzahl, 2 gleich Primzahl).
Man kann natürlich auch die ersten Primzahlen beim Initialisieren berücksichtigen: 2, 3, 5, 7. Dazu braucht man ein kleines Array of Integer. Die Anzahl der benötigten Integerwerte berechnet man mit dem kgV: 3^1 * 5^1 * 7^1 * 2^5 = 3360 Bits = 105 Integer. Beim 106. Integer würde es wieder von vorne beginnen. Mit diesen 105 Integern kann man fortlaufend das große Array initialisieren. Danach auch hier das erste Integer anpassen. Danach kann man beim Sieben mit der Primzahl 11 anfangen. Das sollte die Sache schon etwas beschleunigen.
Edit: Rechenfehler beim kgV korrigiert.

das ist ne gute Idee so erspare ich mir 25% rechenzeit^^
das ist mit beiden möglich, allerdings ist dann die 8 BitVariante immer noch 20x schneller! (wenn nicht noch schneller), da man bei der 32bit variante dann bit für bit immer abwechseln auf 1 und 0 setzen..
bei der 8erVariante setzte ich einfach das 1 Byte auf 172 (10101100)
die anderen auf 170 (10101010)

die abfrage beginne ich dann erst mit 3

Edit: 18% schneller

Ach ja, wenn ihr natürlich mit Sets arbeitet, dann schaut das ungefähr so aus:


Das geht aber echt nur mit der 32bit Version. (Mit einem cast auf UInt64 vielleicht auch noch bei 64 bit)
Man könnte aber auch die Byte-variante auf Cardional erweitern. Müsste dann ebenso schnell laufen, letztlich ist das set of ... ja nur syntactic sugar für die Bitmasken und entsprechende bitweisen Operationen.

warum mit dem Hexadezimalsystem arbeiten (F)
man könnte genausogut (und leichter verständlich) 4294967295 verwenden.. vorallem ist es dann leichter einzelne bits bei der initialiserung direkt zu ändern´(da man dann einfach "errechnen" kann welche zahl 1010101010101010.. ist, als das ganze im hexadeximalsystem zu schreiben.. (ein F setzt ja direkt 4 Bits)

Edit: aber das mit Cardinal(x) := ... wusste ich nicht danke

IhopeonlyReader hat folgendes geschrieben :

18% schneller

Man kann das noch weiter beschleunigen:
Nehmen wir mal die 3 als Primzahl. Man braucht dann nicht von der Zahl 3 ausgehend jede dritte Zahl zu prüfen, also 3, 6, 9, 12, 15 usw. Wie man sehen kann, erfolgt jede zweite Prüfung bei einer geraden Zahl, die ja keine Primzahl sein kann. Als Schrittweite beim Prüfen bietet sich also die doppelte Primzahl an: 3, 9, 15, 21 usw. (Schrittweite jeweils 2 * 3). Das gilt auch für alle anderen Primzahlen (außer bei der 2).

IhopeonlyReader hat folgendes geschrieben :

warum mit dem Hexadezimalsystem arbeiten (F) man könnte genausogut (und leichter verständlich) 4294967295 verwenden.. vorallem ist es dann leichter einzelne bits bei der initialiserung direkt zu ändern´(da man dann einfach "errechnen" kann welche zahl 1010101010101010.. ist, als das ganze im hexadeximalsystem zu schreiben.. (ein F setzt ja direkt 4 Bits)

Ja, gerade deshalb bietet sich das Hexadezimalsystem ja an

Wenn du jetzt 10101010 in hex haben möchtet, kann ich das im Kopf: $AA. Wenn du jetzt 1010101010101010 willst, ganz einfach: $AAAA.
Ganz anders bei der Umrechnung ins Dezimalsystem: 170 und 43.690 sehen sich auf den ersten Blick nicht ähnlich. (43.690 = 170 * 257)

Und wenn du 4294967295 schreibt, habe ich keine Ahnung, ob das jetzt 2^32 ist oder 2^32+1 oder 2^32-1 oder whatever. Ich weiß dass es ungefähr 2^32 ist - mehr aber auch nicht. Bei $FFFFFFFF weiß ist sofort was Sache ist. (=2^32-1) Du siehst, bei Dezimaldarstellung muss man immer nachrechnen, bei Hexadezimaldarstellung kann man es direkt sehen.

Vor allem unverständlich ist das hier:

Zitat:

[Mit dezimal ist es]leichter einzelne bits direkt zu ändern

Weil im Hex-System ist eine Ziffer genau 4 bits. Wenn du also ein Bit ändern möchtest, weißt du sofort welche Ziffer du wie abändern musst. Bei Dezimal ist eine Ziffer 3,32 bits. Und da in der basis die 5 mit drin steckt, ändern sich mal gleich alle Ziffern, die niedriger sind als dein Flag. Das soll einfach sein?

naja.. ich mache das so (am Beispiel Byte (8Bit) da es da nur 8 und nicht 32 bits sind )
1 Ich screibe auf, wie es aussehen muss (von den Bits) :
1 0 1 0 1 0 1 0
2. ich schreibe auf, welche werte das sind (von hinten angefangen)
1 2 4 8 16 32 64 128 (dann eben schnell umdrehen)
128 64 32 16 8 4 2 1
(und dann da wo 1en sind addieren)
128+32+8+2
= 170

so kann ich sozusagen direkt Cardinal(x) := 170;

bei deiner Methode check ich noch nicht wie ich das SCHNELL machen soll^^
1 0 0 0 = 2^3 = 8
also bei deiner Hexadezimalschreibweise 8
bei
1 1 1 1 = 2^4 -1 = 16-1= 15
bei deiner Schreibweise F
1 0 1 0 = 2^3+2^1 = 8+2 = 10
bei deiner Schreibweise A

wenn ich also zu deiner Hexadezimalschreibweise kommen will, unterteile ich die Bits in 4er-Teile und rechne den Wert aus, dafür setze ich dann den Buchstaben/Ziffer.. verstehst du jetzt warum das für mich komplizierter ist? oder gibt's ne einfachere Variante?

Gerd Kayser hat folgendes geschrieben :

Nehmen wir mal die 3 als Primzahl. Man braucht dann nicht von der Zahl 3 ausgehend jede dritte Zahl zu prüfen, also 3, 6, 9, 12, 15 usw. Wie man sehen kann, erfolgt jede zweite Prüfung bei einer geraden Zahl, die ja keine Primzahl sein kann. Als Schrittweite beim Prüfen bietet sich also die doppelte Primzahl an: 3, 9, 15, 21 usw. (Schrittweite jeweils 2 * 3). Das gilt auch für alle anderen Primzahlen (außer bei der 2).

Theoretisch: Muss man 1. muss man bei den Quadratzahlen beginnen...
also wenn ich alle vielfache von 5 z.B: rausstreichen will, muss ich bei 5x5 (25) anfangen, da 5x2 = vielfaches von 2 5x3 = vielfaches von 3 und 5x4 = 5x2x2 = vielfaches von 2..
somit muss man 5 nicht immer von 2 erhöhen (mache ich bereits), sondern kann 5 am anfang x5 nehmen dann Primzahl1nach5 (7) wäre dann 5x7=35,
danach Primzahl2nach5 (11) = 5*11 = 55.. etc, (es muss nur Primzahl*Primzahl gerechnet werden, da alles andere vielfache von anderen zahlen sind und somit schon draußen sind (40 von der 2, 45 von der 3)

da aber die "größeren" Primzahlen fehlen muss man dort "jeden 2ten" nehmen, da (x)*y*Primzahl da wenn x=gerade dann ist das Ergebnis ein vielfaches von 2...

aber wie gesagt, dass ist alles drin ich rechne auch nur bis "abgerundete wurzel von BisXsuchen"

- die 32-BitBooleans Unit wurde aktualisiert (Rev 1) -