Die Mathe-Redaktion - 18.11.2017 03:33 - Registrieren/Login
Auswahl
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 253 Gäste und 5 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von Wauzi
Mathematik » Zahlentheorie » Suche nach Primzahlvierlingen
Thema eröffnet 2017-08-11 17:40 von stpolster
Druckversion
Druckversion
Antworten
Antworten
Seite 2   [1 2 3 4 5 6 7 8 9 10 11 12 13]   13 Seiten
Autor
Kein bestimmter Bereich Suche nach Primzahlvierlingen
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 5058
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.40, eingetragen 2017-08-24


Hallo Horst, Herzlich Willkommen auf dem Matheplaneten,

es gibt die begründete Vermutung, dass für eine n-stellige Zahl etwa c*n4 Summanden getestet werden müssen. Wie groß c im Mittel ist, kann man aus den bisherigen Ergebnissen schätzen, wie viele Summanden man pro Sekunde testen kann, lässt sich messen. Ich komme damit auf eine einstellig Anzahl an CPU-Jahren für meinen Rechner.

Wenn es darauf ankäme, sollte die 1000 bis Silvester erreichbar sein.

Die Frage wäre halt, wie viele Rechner man zusammenbekommt und das hängt davon ab, für wie relevant das Problem erachtet wird.
Ich persönlich habe zumindest den Ehrgeiz die Lücken bis 500 zu schließen und die beiden Hunderter bis 1000 sind auch noch ein Ziel (da werden andere aber vermutlich schneller sein).
Wenn ich danach noch Lust habe, würde ich die großen Lücken stückweise verkleinern (Vielfache von 50, 20 oder 10).
Solange das bei mir nur im Hintergrund läuft und ab und zu mal ein Ergebnis rauspurzelt, kann das Programm auch weiterlaufen. Damit komme ich natürlich nicht auf 168h pro Woche, sondern nur auf 40h.

Viele Grüße,
Kitaktus
[Die Antwort wurde nach Beitrag No.38 begonnen.]


EDIT: Nachdem mir inzwischen klar geworden ist, dass nicht nur der zu durchsuchende Bereich im Schnitt mit n4 wächst, sondern auch noch der Rechenaufwand für jeden Summanden ungefähr mit n2 zunimmt, sehe ich die Prognose nicht mehr ganz so optimistisch.
Vielleicht lässt sich an der Geschwindigkeit des Programms noch etwas machen ...



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 5058
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.41, eingetragen 2017-08-24


So hier mal wieder ein aktualisierter Zwischenstand aus dem Bereich 401-499.
Noch offen (16):
454 457 460 467 470 472 475 
484 486 489 490 492 493 495 496 497 
 
Treffer seit dem 24.08.
441	204586013611   24.08.
447	117721688161   24.08.
452	283207837261   24.08.
453	124918372951   24.08.
459	115356611371   24.08.
 
442	326639680651   25.08.
449	132984453691   25.08.
465	518465913751   25.08.
498	455140246651   25.08.
 
448	182923175011   26.08.
454	186063368131   26.08.
 
450	540018839281   27.08.



  Profil  Quote  Link auf diesen Beitrag Link
stpolster
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 27.03.2014
Mitteilungen: 391
Aus: Chemnitz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.42, vom Themenstarter, eingetragen 2017-08-24


2017-08-24 20:42 - Kitaktus in Beitrag No. 41 schreibt:
So hier mal wieder ein aktualisierter Zwischenstand aus dem Bereich 401-499.
Noch offen (28):
436 437 438 439 440 442 445 448 449 450 
454 457 460 465 467 470 472 475 
484 486 489 490 492 493 495 496 497 498

Mit der 436 quält sich gerade mein Computer seit Stunden.
Durch deine weiteren Lösungen haben wir jetzt insgesamt 485. Sehr schön-

Steffen



  Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 5754
Aus: New York
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.43, eingetragen 2017-08-24


Hi Steffen,

ich sehe gerade, dass du auf deiner Alpha-Seite die OEIS Folge zu den Primzahlvierlingen (noch) gar nicht verlinkt hast. Das wäre noch eine gute Info.

A007530: Prime quadruples: numbers n such that n, n+2, n+6, n+8 are all prime.

Gruß, Slash


-----------------
Drei kleine Regeln, die dich sicher durchs Leben bringen. 1. Vertritt mich mal eben! 2. Oh, gute Idee, Chef! 3. Das war bestimmt jemand anders! (Homer Simpson)



  Profil  Quote  Link auf diesen Beitrag Link
stpolster
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 27.03.2014
Mitteilungen: 391
Aus: Chemnitz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.44, vom Themenstarter, eingetragen 2017-08-24


Hallo Slash,
Danke für die Information.
Ich habe den Link schon gesetzt.

Beste Grüße
Steffen



  Profil  Quote  Link auf diesen Beitrag Link
stpolster
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 27.03.2014
Mitteilungen: 391
Aus: Chemnitz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.45, vom Themenstarter, eingetragen 2017-08-24


Hallo,
die 436 ist erledigt:
436        265232487091
Also wieder eine Zahl weniger bis 500.
Jetzt läuft die 437.

Steffen
Noch offen (27):
437 438 439 440 442 445 448 449 450 
454 457 460 465 467 470 472 475 
484 486 489 490 492 493 495 496 497 498



  Profil  Quote  Link auf diesen Beitrag Link
stpolster
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 27.03.2014
Mitteilungen: 391
Aus: Chemnitz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.46, vom Themenstarter, eingetragen 2017-08-25


Hallo,
wir haben einen neuen absoluten Rekord, gefunden durch Amateur
900        430772369311
Gratulation!
Außerdem gibt's einige neue Einträge. siehe Primzahlvierlinge

Steffen
Noch offen (20):
439 440 448 450 
454 457 460 467 470 472 475 
484 486 489 490 492 493 495 496 497



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 190
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.47, eingetragen 2017-08-25


Hallo Amateur oder andere, die über 600 stellige Zahlen gekommen sind:

könnt Ihr uns bitte die Zeiten für den Suchlauf der
700
800
900 Stellen mitteilen?

Würde gern Zeitbedarf näherungsweise berechnen.

Wenn 551 Stellen bei einigen eine Ergebnisdifferenz (Offset gegenüber Start)
13 h = 46800 s dafür benötigen,
macht das 1657378824451/46800 = 35414077 pro s

Habe gerade was eigenes am Testen und schaffe bei 1000 stelligen Zahlen
Offset von nur 30000 pro s :-(

Entweder bricht die Rechenzeit wirklich so ein, oder mein Programm ist noch nicht gut genug optimiert (Faktor über 1000 mal langsamer gegenüber 551stelliger Zahl ist schon enttäuschend)



  Profil  Quote  Link auf diesen Beitrag Link
Amateur
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 01.10.2012
Mitteilungen: 823
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.48, eingetragen 2017-08-26


Hallo hyperG,

exakte Werte habe ich momentan nicht parat, aber bei n=800 müsste das Programm Primzahlvierlinge.exe auf einem Kern einen Offset von etwa 2 Millionen pro Sekunde geschafft haben.

Viele Grüße A.



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 485
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.49, eingetragen 2017-08-26


Hallo hyperG,

meine Berechnung für n=1000 läuft momentan noch, daher kann ich noch nichts abschließendes dazu sagen. Ich habe die bisherige Berechnungszeit nicht exakt dokumentiert, aber kann sie in etwa überschlagen. Dabei kommt heraus, dass bislang ein Offset von ca. 1 Million pro Sekunde erreicht wurde.

Auf jeden Fall gehe ich davon aus, dass der Offset pro Sekunde mit wachsenden Stellenzahlen immer mehr sinkt. Wenn ich den Offset pro Sekunde zwischen n=297 und n=1000 vergleiche, komme ich in etwa auf einen Verlangsamungsfaktor von grob gesagt ca. 20 bis 30. Für eine ungefähre Abschätzung der Gesamtberechnungszeit für ein bestimmtes n müsste eine Näherung für den ungefähr zu erwartenden Verlangsamungsfaktor noch kombiniert werden mit der Zeit, die der Algorithmus ohnehin schon länger benötigt wegen der gestiegenen Stellenzahl des ungefähr zu erwartenden Summanden a.

Eine Näherungsfunktion für die zu erwartende Berechnungszeit hab ich zwar nicht, aber dafür hab ich mal eine Näherungsfunktion für die ungefähr zu erwartende Stellenanzahl des Summanden a ermittelt. Diese lautet:

<math>digits(n)\approx 0.883772+0.896623\cdot ln(-6.77181+0.884412\cdot n^{2})</math>

Die Formel ist ab <math>n=3</math> aufwärts nutzbar.

z. B.:
<math>digits(3)\approx 1.03816</math>
<math>digits(100)\approx 9.03115</math>
<math>digits(500)\approx 11.9179</math>
<math>digits(1000)\approx 13.1609</math>

LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
stpolster
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 27.03.2014
Mitteilungen: 391
Aus: Chemnitz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.50, vom Themenstarter, eingetragen 2017-08-26


Hallo,
ich habe einen interessanten Artikel von Roonguthai gefunden:
mathforum.org/kb/thread.jspa?threadID=16803

Steffen



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 3510
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.51, eingetragen 2017-08-26


2017-08-26 11:00 - stpolster in Beitrag No. 50 schreibt:
ich habe einen interessanten Artikel von Roonguthai gefunden:
mathforum.org/kb/thread.jspa?threadID=16803

Ja, und das ist jetzt nicht wirklich neu, sondern nur die "ausführliche Version" von dem, was ich in #26 schon gesagt habe. Allerdings beschreibt die dort angegebene Konstante nur in etwa den sog "worst case", da damit der Abstand zum letzen Quadrupel und nicht zu der Startzahl <math>10^n</math> gemessen wird. Wenn man nchts anderes weiß, dann ist wohl die "vernünftigste" Annahme, dass die Startzahl irgendwo in der Mitte zwischen diesen zwei Quadrupeln liegt, d.h., dass für den "average case" die Konstante nur etwa halb so groß ist, wie dort angegeben.

Und ja, wie ich ja hoffentlich nicht extra betonen muss, sind das alles nur statistische Gesetzmäßigkeiten, wobei in Einzelfällen (z.B. für n=899 in Amateurs "Fund") die Abweichung sehr groß sein kann.  wink



  Profil  Quote  Link auf diesen Beitrag Link
stpolster
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 27.03.2014
Mitteilungen: 391
Aus: Chemnitz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.52, vom Themenstarter, eingetragen 2017-08-26


Hallo,
2017-08-26 11:14 - weird in Beitrag No. 51 schreibt:
Ja, und das ist jetzt nicht wirklich neu, sondern nur die "ausführliche Version" von dem, was ich in #26 schon gesagt habe.
Sorry, das hatte ich wohl übersehen.

Eine Bitte hätte ich an die Profis hier.
Ich habe mir einmal die Mühe gemacht, meine Vierlingsseite ins Englische zu transformieren. Da mein (Schrift-)Englisch, nett gesagt, zu wünschen übrig lässt, wäre es nett, wenn jemand von euch auf den 1.Versuch
mathematikalpha.de/prime-quadruplets
sehen könnte; bevor ich es richtig öffentlich mache.
Da ich vermute, dass viele Stellen "merkwürdig" sind, und dieser Thread nicht "übervoll" werden soll, wäre eine private Nachricht schön.

Danke
Steffen

Nachtrag: Warum ich das auch in Englisch möchte?
Auf meiner Seite sind täglich rund 1/3 "Ausländer" unterwegs und wir brauchen doch Rechnerleistung für das Ziel 1000 Stellen. wink

Nachtrag 2:
439        631490948161
war ein "schwere Geburt".



  Profil  Quote  Link auf diesen Beitrag Link
Horst_h
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.08.2017
Mitteilungen: 44
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.53, eingetragen 2017-08-26


Hallo,

ihr wollt Laufzeiten?
Ihr bekommt Laufzeiten!
30 Mio Siebprimzahlen in einem 2*3*5*7*11*13*17*19*23 ( 223 Mio ) großen Sieb, in dem vorab die Zahlen Primzahlen (2 nur ungerade im Sieb)3..23 schon gestrichen haben.
Ich sammelte 6000 Kandidaten die anschliessend von 4 Threads auf einem i3-4330 3.5Ghz Rechner Fermat-getestet wurden.
Der hat 2 Kerne mit SMT. Mit nur einem thread habe ich mal 425 getestet.SMT bringt doch überraschend viel.

551 war bisher das härteste...
Nichts,will nur text
  359 234910677001     01:01:17.133
359 240446677001  -> da scheint ja nur die Anzahl der Siebe falsch gezählt gewesen zu sein.
 
  361    63491184571     00:16:38.911
  362    38086866271     00:10:21.979
  363   220030203541     00:57:22.308
  364    67357615561     00:17:53.901
  365    20623030981     00:05:58.202
  366   170947982491     00:45:24.565
  367    23047543891     00:06:35.025
  368   159921004411     00:42:34.547
  369   120299291581     00:32:11.996
  370    65863090711     00:17:43.948
  371      333330451     00:00:41.729
  372   281711387641     01:15:00.173
  373   261188801701     01:09:32.334
die hast Du ja schon korrigiert:
 
  379   314528981761     01:26:07.736
#################
  411   116551881061     00:35:41.289
  412   558553626271     02:56:47.516
 
  416   116833886191     00:36:23.224
  417   173270301541     00:53:40.217
  418  1095538480831     05:37:50.940
  419   175564214371     00:54:28.044
  420   121660027291     00:38:01.602
  421   202336765891     01:04:40.244
  422   505339601431     02:41:46.714
  423    81463263421     00:26:04.560
  424    51798422791     00:16:55.040
  425    53960807761     00:17:30.398
........
single thread
  425    53960807761     00:49:07.473
........
  426   225812801491     01:14:15.536
  427    97936745461     00:31:32.110
  428    99664364731     00:32:26.618
  429   210404172511     01:07:01.791
  430     6969624301     00:02:46.210 // nur zur Kontolle
#################
 Ab 550 Stellen braucht es ewiglich
  550   365298043561
  551  1657378824451     13:19:37.454
  552   491609414041     04:01:50.770
  553  1447073137021     11:53:33.600
  554    60981519151     00:30:27.472
  555   810409786501     06:42:22.471
  556   402848796061     03:18:52.145
  557   415508989831     03:25:37.753
  558   827917005991     06:49:30.162

Gruß Horst



  Profil  Quote  Link auf diesen Beitrag Link
Horst_h
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.08.2017
Mitteilungen: 44
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.54, eingetragen 2017-08-26


Hallo,
@hyperG
2017-08-25 23:29 - hyperG in Beitrag No. 47 schreibt:
Wenn 551 Stellen bei einigen eine Ergebnisdifferenz (Offset gegenüber Start)
13 h = 46800 s dafür benötigen,
macht das 1657378824451/46800 = 35414077 pro s

Habe gerade was eigenes am Testen und schaffe bei 1000 stelligen Zahlen
Offset von nur 30000 pro s :-(

Ich habe mein Programm mit 1000 Stellen mal gestartet.
Bis die Überträge der Siebprimzahlen bestimmt sind vergehen 54 Sekunden.
Für 1,785x10^9 Zahlen zu sieben, um 4000 Kandidaten zu finden, und anschliessend zu testen braucht mein Rechner ~232 Sekunden.
Das sind 7,32 Mio/s.
Ich hatte mal mit Faktor (Stellenzahl1/Stellenzahl2)^ 2.2 bei kleineren Stellenzahlen abgeschätzt.
(550/1000) ^ 2.2 * 35e6 = 9.4 Mio/s
Das passt also nicht.Aber es sind mehr als 30000 1/s

Gruß Horst



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 485
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.55, eingetragen 2017-08-26


Hallo Horst_h,

vielen Dank für Deine Laufzeiten.
Ich habe diese mal ausgewertet und versucht, eine Näherungsfunktion für die ungefähr zu erwartende Berechnungszeit zu ermitteln unter der Annahme, dass diese Funktion der Form <math>c\cdot n^{k}</math> entspricht.

Es ergibt sich für die Stellenzahl n folgende prognostizierte Berechnungszeit in Sekunden:

<math>time(n)\approx 7.41528\cdot 10^{-10}\cdot n^{4.89871}</math>

Man muss natürlich berücksichtigen, dass man Ausreißer nach unten oder nach oben bezüglich des Summandenwertes a nicht als Kontrollwerte nutzen kann, aber für ein n, dessen Summandenwert a in etwa im Durchschnittsbereich liegt (d. h. dem ungefähren Erwartungswert entspricht), können die Zeiten ja mal überprüft werden.

Natürlich muss ebenfalls noch berücksichtigt werden, dass sich diese Zeiten auf Host_h's Referenzrechner beziehen. Um noch einen korrigierenden Faktor mit zu berücksichtigen, kann man unter nachfolgendem Link die CPU von Horst_h (Intel Core i3 4330) mal mit der eigenen CPU abgleichen (dort werden Geschwindigkeitsindizes angezeigt) und den Wert <math>time(n)</math> noch entsprechend multiplizieren bzw. dividieren:

CPU-Geschwindigkeitsvergleich

Die meisten Summanden a sind jedoch Ausreißer nach unten oder nach oben, so dass eigentlich nur wenige Werte im Durchschnittsbereich liegen. Daher dürften die tatsächlichen Zeiten mal darüber und mal darunter liegen. Die Funktion <math>time(n)</math> gibt also lediglich die durchschnittlich erwartete ungefähre Berechnungszeit wieder.

Falls jemand einen besseren Vorschlag für eine Näherungsfunktion zur Berechnungszeit hat - nur her damit. wink

LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2652
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.56, eingetragen 2017-08-26


Zur erwarteten Laufzeit der Suche nach dem kleinsten Primzahlvierling > 10^n:

Im folgenden ignoriere ich mal alle Faktoren, die nur doppelt-logarithmisch in n wachsen, d.h. f=O*(g) <==> Es gibt ein c mit f=O( loglog(n)^c * g).

Dann betrachten wir mal, was eigentlich passiert: Zuerst wird mit einer Reihe an Primzahlen p gesiebt. Zur Initialisierung muss dafür erst einmal 10^n mod p bestimmt werden, was aber nur eine in n logaritmische Anzahl an Multiplikationen mod p bedarf, die selbst wiederum für p < S < 10^n in O*(log S) ablaufen.  Insgesamt braucht die Initialisierung für das Sieben mit p also O*(log S) Schritte.

Dann müssen die durch p teilbaren Zahlen in dem Sieb herausgestrichen werden. Das geht in O(1) für jede Zahl im betrachteten Bereich. Und dieser muss eine Größe von O(n^4) enthalten, damit mit einer beliebig großen konstanten Wahrscheinlichkeit < 1 ein Primzahl-Vierling darin gefunden werden kann. (Wir können annehmen, dass die Treffer mit einer Wsk. c/n^4 Poisson-verteilt auftreten.) Das Sieben mit p benötigt also O(n^4) Schritte, wobei die Initialisierung wegen log S < c * n dabei nicht mehr ins Gewicht fällt.

Gesiebt wird mit allen Primzahlen < S. Davon gibt es O(S/log S) Stück, sodass der gesammte Siebprozess O(n^4 * S/ log S) Schritte benötigt.

Nach dem Sieben hat jede überlebende Zahl eine Wahrscheinlichkeit von  P(S, n) := c * log S / n prim zu sein. Die Wahrscheinlichkeit für einen Primzahl-Vierling steigt damit auf O(log^4 S / n^4), sodass von den ursprünglichen O(n^4) Kandidaten nun nur noch O(n^4 / log^4 S) zu testende übrig sind.

Für einen Fermat-Test einer Zahl N muss i.W. die Potenz a^N mod N berechnet werden. Dies benötigt O(log N) Multiplikationen mod N, also für N=10^n demzufolge O(n) Multiplikationen mod N, wobei jede einzelne davon in O(n * log n * loglog n) durch Schnelles Multiplizieren [mit FFT] ausgeführt werden kann. Insgesamt ergibt sich also für einen Fermat-Test einer Zahl der Größenordnung 10^n eine Laufzeit von O(n^2 * log n * loglog n). Da pro Kandidat O(1) Fermat-Tests ausgeführt werden, dauert das Testen also pro "das Sieben überlebenden Kandidatem" auch O(n^2 * log n * loglog n) Schritte.

Da man im Erwartungswert einen konstanten Anteil aller ausgesiebten Kandidaten aus dem oben genannten Bereich betrachten muss, ergibt sich also für das Fermat-Testen eine Gesamtlaufzeit von O(n^6 / log^4 S * log n * loglog n) bzw. für die gesamte Berechnung von O(n^6 / log^4 S * log n * loglog n + n^4 * S / log S) Schritten.

Dieser Term wird minimal für S = O(n^2 / log^2 n), was zu einer Gesamtlaufzeit von O*(n^6 / log^3 n) führt.


Bemerkung: Hier sind Asymptotiken für n-->oo angegeben. Die werden an sich erst für große n greifen. Wenn man z.B. über die betrachteten Bereich die FFT-Größe, die man sinnvollerweise zur Berechnung verwendet, konstant halten kann, dann hat man natürlich andere Abhängigkeiten.

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 190
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.57, eingetragen 2017-08-26


Danke an alle, die die Zeiten angaben.

Wenn bei 800 Stellen etwa 2 Mio /s machbar ist, war das das Ziel.

Um Primentus bei seinen 1000 Stellen einzuholen (denn der sucht ja schon "von unten")
habe ich jetzt einen Offset-Start eingebaut. Außerdem kann man so beliebig enden und am nächsten Tag weitersuchen.

Die 30000 pro s waren viel zu schwach! Also 800 Modulo Ergebnisse der Startzahl gemerkt und nur mit kleinen 64Bit Variablen das "Add-Mod"
-> ergibt nun
c++ Ergebnisse
Start mit A^B+C
A=10
B=999
C=1003189000000
Prim-Puffer:800
...
i=30 Mio. in  65.929 s
i=60 Mio. in 147.520 s
i=90 Mio. in 240.717 s
i=120 Mio. in 336.504 s
i=150 Mio. in 429.044 s
i=180 Mio. in 525.369 s 180000000/525=342857 /s
Statt intern parallel zu rechnen (bringt wegen der externen GMP-DLL und der schlechten Parallelisierbarkeit nur negative Effekte),
starte ich die selbe exe 8 mal mit versetzten Start (1 exe pro i7-Kern
) und komme auf
*8=2742857=2,74 Mio /s

Wenn ich mehr Zeit habe, könnte ich die exe auch wie stpolster online anbieten...

Mein nächster PC wird bestimmt einer mit 24 logischen Kernen wie
AMD Ryzen Threadripper 1920X für nur 799 $ :-)



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 485
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.58, eingetragen 2017-08-27


Hallo,

ich habe mal cyrix' detaillierte Komplexitätsüberlegungen meiner Näherungsformel <math>time(n)</math> aus Beitrag #55 gegenübergestellt, indem ich den Faktor, um den der voraussichtliche Rechenaufwand von jeweils n zu n+100 ungefähr steigt, ermittelt habe.
Tabelle
       | nach cyrix:                 | nach Primentus:   
       | ((n + 100)^6/log^3(n+100))/ | (7.41528*10^(-10)*(n+100)^4.89871)/
     n | (n^6/log^3(n))              | (7.41528*10^(-10)*n^4.89871)
-------+-----------------------------+-------------------------------------
   100 |                     42.0246 | 29.8304
   200 |                     9.13004 | 7.28820
   300 |                     4.84755 | 4.09297
   400 |                     3.41836 | 2.98356
   500 |                     2.73788 | 2.44279
   600 |                     2.34778 | 2.12791
   700 |                     2.09731 | 1.92347
   800 |                     1.92379 | 1.78066
   900 |                     1.79688 | 1.67553
  1000 |                     1.70021 | 1.59504
     : |                           : |       :
  5000 |                     1.11834 | 1.10187
     : |                           : |       :
 10000 |                     1.05809 | 1.04995
     : |                           : |       :
100000 |                     1.00575 | 1.00491
     : |                           : |       :

Da sich die Quotienten der beiden Spalten für zunehmendes n immer mehr annähern und somit mit den detaillierten Überlegungen von cyrix weitgehend übereinstimmen, kann meine Formel, die ja auf den Zeitmessungen von Horst_h basiert, denke ich als relativ gute Näherung angesehen werden. Aber wie gesagt - es ist halt immer nur eine Art Durchschnittswert, der bei meiner Formel berechnet wird.

2017-08-26 21:29 - hyperG in Beitrag No. 57 schreibt:
Um Primentus bei seinen 1000 Stellen einzuholen (denn der sucht ja schon "von unten")
habe ich jetzt einen Offset-Start eingebaut.

2017-08-26 21:29 - hyperG in Beitrag No. 57 schreibt:
c++ Ergebnisse
C=1003189000000


Ja, ich bin für n=1000 jetzt ungefähr bei der Mitte der 12stelligen Zahlen angelangt. Ich gebe dann Bescheid, ob ich bis 1003189000000 etwas gefunden habe. Das wird aber voraussichtlich noch ca. zwei Wochen dauern.

LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
Horst_h
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.08.2017
Mitteilungen: 44
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.59, eingetragen 2017-08-27


Hallo,

eigentlich ging es nicht um absolute Laufzeiten, um eine Lösung zu finden, sondern um die Laufzeit, einen gewissen Zahlenbereich zu
testen.
@hyperG:
Prim-Puffer:800. Heißt, Du benutzt 800 Primzahlen, um eine Vorauswahl zu treffen?
Das halte ich für viel zu wenig.
Der Fermattest dauert ja eine Ewigkeit.
Ich siebe die 1,78e9 Zahlen = 8 Siebe in etwa 16 Sekunden mit 30 Mio Primzahlen auf einem CPU-Kern.Langsam, aber wenn man bedenkt, dass der Fermattest der 4000 Kandidaten anschliessend ( sehr gut parallelisierbar ) 216 Sekunden pro Kern läuft, also jeder Test, bei 4 Kernen, 0,216 s dauert, lohnt sich es sich sehr.
Vielleicht ist gmp da schneller.Das lässt sich sicher mit ein paar Probezahlen bestimmen.
Vielleicht kann man eine Grenze bestimmen, wo sieben mit noch mehr Zahlen länger dauert, als der immer langwieriger werdende Fermattest.Aber die liegt ja gewaltig hoch, auch wenn die Initalisierung entsprechend Zeit kostet.

Heute Nacht fertig geworden, ohne das jemand am Rechner war:
  559  838455299971     06:53:12.225 ( 33,8e6 / s )

560 läuft schon über 10,5h

Gruß Horst
P.S.
Ich grübele momentan, über die Verkleinerung des Primzahlsiebes.
Man will ja nur Quadrupel testen.
Die haben die Form 30*n+11(+0,2,6,8)
Wenn ich nun statt jede zusammengesetzte Zahl im Sieb mit Primzahlen zu markieren, nur die n betrachte, steht so jedes Feld steht für 30 Zahlen.
Jetzt markiere ich nur, wenn Zahl mod 30 in [11,13,17,19] ist.
Als simples Beipiel mal 7 mod 30 von 1 bis 30 *7
 0R 7
 0R14
 0R21
 0R28
 1R 5
 1R12
 1R19 -> Markiert "kein Quadrupel"
 1R26
 2R 3
 2R10
 2R17 -> Markiert "kein Quadrupel"
 2R24
 3R 1
 3R 8
 3R15
 3R22
 3R29
 4R 6
 4R13 -> Markiert "kein Quadrupel"
 4R20
 4R27
 5R 4
 5R11 -> Markiert "kein Quadrupel"
 5R18
 5R25
 6R 2
 6R 9
 6R16
 6R23
 7R 0
 7R 7 -> siehe oben eben 7*30 weiter
also muss ich mir nur 4 Kandidaten merken:
 1R19 -> 7*7 Markiert "kein Quadrupel"
 2R17 ->11*7 Markiert "kein Quadrupel"
 4R13 ->19*7 Markiert "kein Quadrupel"
 5R11 ->23*7 Markiert "kein Quadrupel"
Ich streiche also 1,2,4,5..k*7+(1,2,4,5)
Das Sieb wird um den Faktor 30 kleiner und ich muss nur 4- statt 30-mal streichen.
Noch etwas schönes m*30+7, als Beipiel 37 streicht auch bei 7*,11*,19*,23*
 8R19 -> 7*37 Markiert "kein Quadrupel"
13R17 ->11*37 Markiert "kein Quadrupel"
23R13 ->19*37 Markiert "kein Quadrupel"
28R11 ->23*37 Markiert "kein Quadrupel"
von 0..30-1 gibt es nicht viele Zahlen zu beachten.

Ich hänge noch an der richtigen Bestimmung der Überträge in das Sieb.



  Profil  Quote  Link auf diesen Beitrag Link
stpolster
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 27.03.2014
Mitteilungen: 391
Aus: Chemnitz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.60, vom Themenstarter, eingetragen 2017-08-27


Hallo,
da die Suche nach neuen Primzahlvierlingen immer mühsamer wird, die 440 läuft seit gestern, habe ich mich "abgelenkt" und mir einmal die Primzahlachter, d.h. zwei unmittelbar aufeinanderfolgende Vierlinge im Abstand 30, angesehen.
Die sind noch seltener, aber irgendwie reizvoll.

Die Suche nach den Vierlingen geht weiter ...
Schönen Sonntag
Steffen



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2652
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.61, eingetragen 2017-08-27


@stpolster: Üblicherweise fordert man für Primzahl-k-linge, dass sie von der Form <math>p + (0, a_1, \dots , a_{k-1})</math> sind mit <math>0<a_1<\dots<a_{k-1}</math>, der Eigenschaft, dass keine Primzahl q existiert, für die <math>\{0, a_1, \dots , a_{k-1}\}</math> ein vollständiges Repräsentantensystem der Restklassen mod q enthält, und natürlich, dass unter diesen Bedingungen das minimale <math>a_{k-1}</math> gewählt wird.

Die expliziert ausformulierte Eigenschaft sichert, dass nicht aus trivialen Gründen immer mindestens eine der Zahlen duch q teilbar ist (weshalb (2, 3) auch kein Primzahlzwilling ist, da mod 2 ein vollständiges Repräsentantensystem enthalten ist).

Für k=8 ist das minimale <math>a_{k-1}</math>, wie du es auch auf deiner Seite angibst, 26, während du mit 38 rechnest.

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
stpolster
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 27.03.2014
Mitteilungen: 391
Aus: Chemnitz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.62, vom Themenstarter, eingetragen 2017-08-27


Hallo Cyrix,
2017-08-27 11:43 - cyrix in Beitrag No. 61 schreibt:
Für k=8 ist das minimale <math>a_{k-1}</math>, wie du es auch auf deiner Seite angibst, 26, während du mit 38 rechnest.
Ist mir klar. Deshalb spreche ich ja auch von "Achtern" und nicht von "Achtlingen".
Was mich daran interessiert, sind nicht 8 Primzahlen in einem kleinen Intervall der Länge 26, sondern zwei aufeinander folgende Vierlinge.
Da die so selten sind, finde ich es schon bemerkenswert, dass man auch bei etwas längeren Zahlen so etwas noch findet.

Schönen Sonntag
Steffen



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2652
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.63, eingetragen 2017-08-27


Nach der Primzahl-k-Tupel-Vermutung sollten die etwa gleichhäufig wie die Achtlinge sein (bis auf einen konstanten Faktor). Konkret: Unterhalb von x sollte es c * x/(ln^8 x) von jeder Sorte (mit leicht unterschiedlichen Konstanten c) geben.

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
Horst_h
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.08.2017
Mitteilungen: 44
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.64, eingetragen 2017-08-27


Hallo,

560 läuft schon 16 Stunden.
Ich habe jetzt mal gmp getestet.
Es ist etwa 7x schneller in 64-Bit in höheren Stellenzahlen.
Ich werde das Programm umstricken.Das kann ich nicht ignorieren.

Gruß Horst
Edit:
Ich habe das Testprogramm mal hier eingestellt.
Mittlerweile 17h21min...




  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 190
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.65, eingetragen 2017-08-27


Hallo Primentus,
zu " für n=1000 jetzt ungefähr bei der Mitte der 12stelligen Zahlen angelangt"
woran siehst Du, wie weit Du bist? Genau das fehlte mir - oder ist der Offset zum
Startwert versteckt?

Hallo Horst_h,
ja, die Puffergröße war zu klein:
 800: 30 Mio. in  56.973 s
1228: 30 Mio. in  47.212 s
1600: 30 Mio. in  43.051 s
3200: 30 Mio. in  36.009 s
4000: 30 Mio. in  35.556 s
mehr bringt nicht viel Gewinn. Multitasking bringt bei der externen DLL nichts.
Dafür starte ich die EXE mehrfach mit anderen Startwerten.

Bei 559 Stellen war der Puffer=4000 eher ein Hindernis:
i=90 Mio. in  42.947 s 90000000/42.947 ->2095606 /s = 2.08 Mio /s
 *8 Kerne (8 exe Parallel) = 16 Mio /s
 (weit entfernt von den 33,8 Mio /s von Horst_h)
 
Aber bei 1000 Stellen dürfte der Abfall nicht so stark ausfallen:
i=90 Mio. in 104.507 s        90000000/104.5 = 857142 /s = 0,8 Mio /s
*8 = 6857142 /s = 6,8 Mio. /s

Folgende Bereiche der 1000stelligen Zahlen Ergebnislos durchsucht:
c++ Suchbereiche
10^999+1000000000000..1021189000000
10^999+2000000000000..2021000000000
10^999+5000000000000..5021795000000
10^999+6000000000000..6021642000000
10^999+7000000000000..7021645000000
10^999+8000000000000..8020680000000
10^999+9000000000000..9020110000000
10^999+3000000000000..3013270000000
10^999+6400000000000..6402700000000
10^999+6500000000000..6502760000000


offen sind folgende Start-Bereiche:
10^999+4000000000000
10^999+900000000000 (Grenze zu Primentus)

Wer will, kann parallel mitsuchen oder Geschwindigkeiten vergleichen:
GMP_PrimeQuadModAr4000S5


Hinweise:
- wegen des schwachen Prim-Tests, muss Ergebnis immer kontrolliert werden!
- wegen universeller Potenzeingabe ist n hier um 1 kleiner als bei stpolster
- nur für 64 Bit CPU mit SSE2 Befehlen ab Win7 aufwärts
- keine Garantie für Schäden (alte Pentium CPU kann abstürzen)



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 485
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.66, eingetragen 2017-08-27


2017-08-27 18:52 - hyperG in Beitrag No. 65 schreibt:
Hallo Primentus,
zu " für n=1000 jetzt ungefähr bei der Mitte der 12stelligen Zahlen angelangt"
woran siehst Du, wie weit Du bist? Genau das fehlte mir - oder ist der Offset zum
Startwert versteckt?

Hallo hyperG,

wenn man im Programm von stpolster auf den Abbruch-Button klickt, werden die Werte in der Suchliste (Anzeige im Programm und als Datei) aktualisiert. Daran kann man ablesen, wie weit er gekommen ist bzw. wo er das nächste mal weitersucht. Der Abbruch-Button hat sich dabei wieder in einen Suche-Button verwandelt, und wenn man den dann anklickt (ggf. auch erst am nächsten Tag bei neuem Programmstart), dann sucht er bei dem angezeigten Offset weiter. Man darf dann halt nur nicht mehr auf den Initialisieren-Button klicken, weil sonst wieder alle Offsets auf 0 gesetzt werden. Das Initialisieren braucht man also nur, wenn man alles bei 0 starten will. Direkt eingebbar ist der Start-Offset aber nicht.

LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
Horst_h
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.08.2017
Mitteilungen: 44
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.67, eingetragen 2017-08-27


Hallo,

Puh!
  560  2301213470311     19:15:01.611

Jetzt werde ich das Programm umstricken.Ich hoffe, ich kann threads benutzen, auch wenn ich dies das erste mal hier gemacht habe.
Wie im Delphi-Forum geschrieben habe, doppelte Stellenzahl etwa 2^3-fache Laufzeit für den schwachen Primzahltest:
s_mp_is_psp2(TestZahl)
oder für gmp
mpz_probab_prime_p(TestZahl, 0);
Gut das ich für Linux 64-Bit compiliert habe, denn 32-Bit CPU's brauchen nochmals 6x länger.
Ich würde ja gerne die Quelltexte anhängen, aber soll hier wohl nicht sein.

Gruß Horst







[Die Antwort wurde vor Beitrag No.1 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 485
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.68, eingetragen 2017-08-27


Hallo,

soweit ich gesehen habe, haben wir jetzt alle Werte bis n=449 erfolgreich abgearbeitet. Ich habe für diese Stellenanzahlen mal ein paar Daten zusammengetragen, und zwar bei welchem n der jeweils erste s-stellige Summand a auftritt.
Tabelle
 s |    n 
---+-----------------
 1 |    2  
 2 |    -
 3 |    4
 4 |    5
 5 |    8
 6 |   13
 7 |   17
 8 |   37
 9 |   51
10 |   91
11 |  163
12 |  289
13 |  418
14 | ca. 636 (Prognose) Edit: bessere Prognose mit firstSdigitExp(s): ca. 697 
15 | ca. 930 (Prognose) Edit: bessere Prognose mit firstSdigitExp(s): ca. 1132 
16 | ca. 1325 (Prognose) Edit: bessere Prognose mit firstSdigitExp(s): ca. 1839  
17 | ca. 1848 (Prognose) Edit: bessere Prognose mit firstSdigitExp(s): ca. 2988
18 | ca. 2530 (Prognose) Edit: bessere Prognose mit firstSdigitExp(s): ca. 4853
19 | ca. 3404 (Prognose) Edit: bessere Prognose mit firstSdigitExp(s): ca. 7882
20 | ca. 4511 (Prognose) Edit: bessere Prognose mit firstSdigitExp(s): ca. 12803

Die Werte ab s=14 sind ungefähre Prognosen basierend auf einer Näherungsfunktion, die ich auf Basis der bisherigen Werte ermittelt habe. Man übergibt s und bekommt das ungefähre n heraus. Die Funktion lautet:

<math>firstSdigit(s)\approx 0.000323889\cdot s^{5.49096}</math>

Der erste 14stellige Summand a ist also voraussichtlich bei ungefähr n=636 zu erwarten und der erste 15stellige bei etwa 930, wobei auch hier aber wieder gilt, dass solche (frühen) Ausreißer letztlich etwas schwierig vorherzusagen sind. Aber so hat man zumindest mal eine ungefähre Hausnummer. Bin mal gespannt auf später, wie gut die Näherung dann hinkommt.

Und insbesondere bedeutet die Prognose auch, dass für n=1000 der Summand im worst case schon 15stellig sein könnte.

LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2652
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.69, eingetragen 2017-08-27


@Primentus: Es sollte <math>a = \mathcal{O}\left(n^4\right)</math> und damit umgekehrt <math>n = \mathcal{O}\left(a^{\frac{1}{4}}\right)</math> bzw. mit <math>a=10^s</math> also <math>n = \mathcal{O}\left(10^{\frac{1}{4} \cdot s}\right) = \mathcal{O}\left(1.778...^s\right)</math> gelten. Insbesondere sollte also deine Funktion exponentiell und nicht polynomiell in s steigen...

Und zu deinem edit: Es ist äußerst unwahrscheinlich, dass für n=1000 schon ein a>10^14 gebraucht wird, wo doch eines der Größe <10^13 erwartet wird. Das sollte mit einer a-priori-Wahrscheinlichkeit von < e^{-10} eintreten, was schon ziemlich unwahrscheinlich ist.


Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
Horst_h
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 22.08.2017
Mitteilungen: 44
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.70, eingetragen 2017-08-27


Hallo,

etwas "Murkserei", aber es klappt erst einmal.
vorher:
  371      333330451     00:00:41.729
  430     6969624301     00:02:46.210
jetzt:
  371   333330451     00:00:19.273
  430  6969624301     00:01:16.596

Die Zeit zum sieben hat jetzt einen Anteil ~80%
Also mal statt 30Mio Primzahlen nun 500.000
  371   333330451     00:00:08.944
  430  6969624301     00:01:26.658

Was für ein Witz
371 Stellen wird erheblich schneller, 430 wird schon langsamer....

Gruß Horst



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 485
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.71, eingetragen 2017-08-27


Hallo cyrix,

ich hatte erst schon überlegt, ob es eher exponentiell oder eher polynomiell sein müsste, hatte aber mit exponentiell keine so gute Passung zu den bekannten Werten hinbekommen. Leider weiß man immer nie, welche Werte Ausreißer sind und welche nicht, d. h. welche man als Kontrollwerte nutzen kann und welche nicht.

Aber ich hab jetzt mal noch mit Hilfe Deines Vorschlages und der bekannten Werte eine exponentielle Funktion ermittelt, diese würde dann wie folgt lauten:

<math>firstSdigitExp(s)\approx 0.783507\cdot 1.62429^{s}</math>

Das kommt Deinen Überlegungen ja recht nahe und würde bedeuten, dass ab ca. n=697 der erste 14stellige Summand a zu erwarten wäre und ab ca. n=1132 der erste 15stellige. Dann wäre es tatsächlich so, dass bis n=1000 maximal 14stellige Summanden auftreten würden.

Ich nehme die so entstehenden Werte auch mal in die Tabelle von Beitrag #68 auf.

LG Primentus

[Die Antwort wurde nach Beitrag No.69 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 190
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.72, eingetragen 2017-08-28


zu"..im Programm von stpolster auf den Abbruch-Button klickt, werden die Werte in der Suchliste..."
Danke Primentus, ich dachte, dass nach Abbruch alles für immer vorbei ist . Dabei stehen die Werte in einer txt-Datei...

Nun konnte ich am selben PC vergleichen & das unterschiedliche "Einbrechen" bei höherer Stellenanzahl bestätigte sich:
Offset-Geschwindigkeit
Stellen		stpolster	hyperG		Faktor
500		11,8 Mio/s	2,3 Mio/s	5,17
1000		1,77 Mio/s	0,8 M/s		2,07
2000		268203/s	171193/s	1,56
3000		 87700/s	65789/s		1,4

(beide exe nuten nur je 1 Kern)

Mein "Vorfilter-Algorithmus" scheint den "Sieb-Algorithmus" irgendwann einzuholen... (aber dafür ist es heute zu spät)

Hallo Horst,
kannst Du Deine Windows-EXE auch bereitstellen, um objektiv am selben PC testen zu können?





  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 5058
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.73, eingetragen 2017-08-28


Wie versprochen nähern wir uns dem Ende der 400er:
Noch offen (0):
--- 
 
Treffer 25.-28.08.
460	704088441661
467	998157886621
470	854728225981
472	743909076601
475	577386013381
484	640918409101
490	1107804358741
492	775667524351
495	962116913401
496	689387354821
497	616462327921
 
und als Bonus noch
650	82108489351
 
Treffer 28.08.
457	936237692791
 
Treffer 29.08.
486	1925420017051
489	1936751015551
493	1289890525801

So, damit ist das Ziel erreicht. Alle Lösungen bis n=500 wurden gefunden. Die letzten beiden waren ziemlich hartnäckig und stellen zwei weitere Längenrekorde dar (es gibt keine kleineren n, die größere Summanden benötigen).



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 485
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.74, eingetragen 2017-08-28


2017-08-28 00:22 - hyperG in Beitrag No. 72 schreibt:
zu"..im Programm von stpolster auf den Abbruch-Button klickt, werden die Werte in der Suchliste..."
Danke Primentus, ich dachte, dass nach Abbruch alles für immer vorbei ist . Dabei stehen die Werte in einer txt-Datei...

Ja, also der Abbruch-Button ist gleichzeitig auch ein Speichern-Button sozusagen (und die Berechnung wird an der Stelle gestoppt). Nur wenn man erneut auf den Initialisieren-Button klickt, dann sind tatsächlich alle bisherigen Offsets wieder weg (sprich die Suchliste-Datei wird komplett überschrieben mit lauter Offsets, die auf Null gesetzt sind).

LG Primentus

Edit:
Bezüglich eingebbarer Offset könnte man sich bei stpolster's Programm notfalls so behelfen:
Zunächst über die Programmoberfläche per Initialisieren-Button eine Suchliste-Datei initialisieren. Dann die Suchliste-Datei mit einem Texteditor bearbeiten und dort einen anderen Offset bei der gewünschten Zeile eingeben, falls man sich sicher ist, zu einem bestimmten n einen entsprechenden Anfangsbereich schon durchsucht zu haben oder man sich die Suche mit jemandem aufteilen will. Man muss halt nur das Format der einzelnen Datensätze beachten (ohne Leerzeichen):
Zahl Komma Zahl Return
Und dann kann man die Suche starten.
Aber allzu viel rumeditieren würde ich jetzt auch nicht in der Datei, sonst blickt man irgendwann nicht mehr durch, wer schon was untersucht hat.



  Profil  Quote  Link auf diesen Beitrag Link
stpolster
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 27.03.2014
Mitteilungen: 391
Aus: Chemnitz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.75, vom Themenstarter, eingetragen 2017-08-29


Hallo Kitaktus,
2017-08-28 08:13 - Kitaktus in Beitrag No. 73 schreibt:
So, damit ist das Ziel erreicht. Alle Lösungen bis n=500 wurden gefunden. Die letzten beiden waren ziemlich hartnäckig und stellen zwei weitere Längenrekorde dar (es gibt keine kleineren n, die größere Summanden benötigen).
Gratulation. Ich habe schon wieder alles in die Liste eingetragen.
Die Hälfte haben wir geschafft.

Allerdings kommen mir doch ein paar Zweifel, ob 1000 realistisch ist. Ich habe mir das Intervall [501 ; 520] vorgenommen und nach vier Tagen erst 2 neue Vierlinge.
Es wird leider immer mühseliger.

Vielleicht können wir auf ein neues Programm von Horst_H hoffen, dass, wie es im Moment aussieht, erheblich schneller sein wird.

Fröhliches Weitersuchen und Danke an alle, die ihre Computer dafür einsetzen
Steffen

Nachtrag: Ich habe versucht den Anteil an den gefundenen Vierlingen zu berechnen. Dazu habe ich einfach die Summe von Stellenzahl * Summand gebildet.
Es ist mir klar, dass dies wahrscheinlich kein korrektes Maß ist (alternative Vorschläge sind sehr willkommen). Dabei ergibt sich
1. Kitaktus	1,17*10^16
2. Horst_H	7,83*10^15
3. Amateur	6,47*10^15
4. Polster	4,79*10^15
5. Roonguthai	1,72*10^15
6. Hänel	1,87*10^14
7. Gammatester	3,06*10^13

D.h., Kitaktus hat mit großem Abstand den größten Anteil am bisherigen Erfolg. Gratulation und großes Danke.



  Profil  Quote  Link auf diesen Beitrag Link
hyperG
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 190
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.76, eingetragen 2017-08-29


Hallo Primentus,
zu "mit einem Texteditor bearbeiten ..." (Beitrag 74)
ja, genau das meinte ich im Beitrag 72 mit "stehen die Werte in einer txt-Datei... Nun konnte ich am selben PC vergleichen".


Dank Amateur haben wir Fundstellen um 900 Stellen und können mit beliebigen Offset starten.
Dank Horst_h & stpolster kann man nun bei höheren Stellenzahlen objektiv vergleichen.
Vergleich der 3 Programme mit 1 Thread
Stellen /Offset		stpolster	hyperG		Horst_h
900	/30 Mio		17 s		33,2 s		88,9 s
900	/60 Mio		34 s		66 s		96,9 s
3598	/30 Mio		-		683 s		500,6 s
4000	/30 Mio		830 s		830 s		-


Die Striche bedeuten:
- bei stpolster kann man 2673092556681*15^3048-30000004 nicht eingeben
- bei Horst_h kann man ohne Fundstelle kein aktuelles Offset erkennen/bestimmen

Bei kleinem Offset ist die Sieb-Initialisierung von Horst_h nachteilig, aber schon die zweiten 30 Mio. dauern nur 8 s länger als die ersten!
Es ist also bei großem Offset und Stellenanzahl um 1000 das schnellste.

Ich bin noch bei der Optimierung der Vorfilter-Puffergröße, da sie mit der Stellenanzahl wächst.



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 5058
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.77, eingetragen 2017-08-29


Mein nächstes persönliches Ziel sind die Vielfachen von 50 bzw. 10. Das ist nicht ganz so viel Arbeit, wie eine komplette Liste bis 1000.
Hier der Stand:
50er
----
Erledigt (8):  550 600 650 700 800 900 950 1000
Offen (2):     750 850 
 
10er
----
Erledigt (13): 530 550 560 580 600 620 640 650 700 800 
               900 950 1000
Offen (37):    510 520 540 570 590 610 630 660 670 680 
               690 710 720 730 740 750 760 770 780 790 
               810 820 830 840 850 860 870 880 890 910 
               920 930 940 960 970 980 990 
 
In Arbeit:    
 n   Fortschritt (in Mrd.)
540  1422   92%(*)
610   755   53%
630   565   38%
660   464   29%
670   223   15%
680   516   29%
690   267   17%
710   353   19%
720   119    4%
730   161    7%
740    13    0% (inaktiv)
750   198    7%
760    49    2% (inaktiv)
840    29    0% (inaktiv)
850   141    3%
860    15    0% (inaktiv)
 
Treffer:
640	 55412522161	30.08.17
950	 21769172551	30.08.17
530	351186811261	31.08.17
 
Außer der Reihe (**):
547	 35816383081	31.08.17
546	181600476901	02.09.17
 
(*) Geschätzte Wahrscheinlichkeit mit der (bei zufällig gewählter 
Startzahl in dieser Größenordnung) im durchsuchten Bereich eine Lösung 
gefunden wird. 
Der Treffer bei n=950 war ein Glückstreffer. 
Die Wahrscheinlichkeit dafür lag deutlich unter 1%.
 
(**) Auf einem Rechner der sporadisch im Einsatz ist, laufen zur Zeit 
die Werte 546, 548, 549 und 605.

Sollte jemand an den gleichen n rechnen, oder bestimmte Werte übernehmen wollen, sagt mir bescheid, damit wir Doppelarbeit vermeiden.



  Profil  Quote  Link auf diesen Beitrag Link
stpolster
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 27.03.2014
Mitteilungen: 391
Aus: Chemnitz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.78, vom Themenstarter, eingetragen 2017-08-29


Hallo,
wenn ich Primentus' Ergebnis aus #17 verwende, bekomme ich für eine Stellenzahl n im Durchschnitt
<math>a\approx 10^{\frac{\ln{\frac{n}{0.783507}}}{\ln{0.162429}}</math>
Summanden bis zum Erreichen des Vierlings.

Summiere ich dies von 1 bis 500 auf, sind es insgesamt
<math>1.80614\cdot 10^{14}</math>
Summanden, und von 500 bis 1000
<math>9.49302\cdot 10^{15}</math>
Summanden. Wir haben somit im Moment etwa 1,8 % geschafft.
Gehe ich von im Mittel 30 Millionen Summanden je s (Horst_H's Ergebnis) aus, liefen die Rechner jetzt schon 1670 Stunden und würden bis 1000 noch weitere 87800 Stunden laufen.

Wo ist mein Denkfehler? Ich hoffe, ich habe einen richtig großen Fehler produziert.

Beste Grüße
Steffen



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2652
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.79, eingetragen 2017-08-29


Wie gesagt: Alles (die gut unterlegte Primzahl-k-Tupel-Vermutung) spricht dafür, dass sich a ~ n^4 verhalten sollte. Alle n <= m zu untersuchen erfordert damit einen Aufwand ~ m^5. Das Verhältnis der erwarteten  notwendigen Arbeit für m = 1000 ist also 2^5 = 32 mal so groß wie die für m = 500.

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
-->> Fortsetzung auf der nächsten Seite -->>
Seite 2Gehe zur Seite: 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13  
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 

 AQA

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2017 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]