Matroids Matheplanet Forum Index
Moderiert von viertel
Matroids Matheplanet Forum Index » Rätsel und Knobeleien (Knobelecke) » * Unix Prime Stamp
Thema eröffnet 2019-05-22 20:38 von querin
Druckversion
Druckversion
Antworten
Antworten
Seite 2   [1 2]   2 Seiten
Autor
Kein bestimmter Bereich * Unix Prime Stamp
querin
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 12.01.2018
Mitteilungen: 327
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.40, vom Themenstarter, eingetragen 2019-05-30


Mein aktueller Stand sieht so aus (1 Kern, deterministische Lösung):

1. Reduktion auf ca. 40 Millionen Kandidaten (51 sec)
2. Probabilistische Auswahl der Prime Stamps (124 sec)
   An dieser Lösung ändert sich nichts mehr, aber:
3. Verifizierung der Prime Stamps (891 sec)

Gesamtlaufzeit 17:46 Minuten oder 1066 Sekunden, also deutlich langsamer als gonz (632 Sekunden).



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Dies ist eine Knobelaufgabe!
Der Themensteller hat bestimmt, dass Du Lösungen oder Beiträge zur Lösung direkt im Forum posten darfst.
Bei dieser Aufgabe kann ein öffentlicher Austausch über Lösungen, Lösungswege und Ansätze erfolgen. Hier musst Du keine private Nachricht schreiben!
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3568
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.41, eingetragen 2019-05-30


Aaaarg ich muß mich entschuldigen ich habe grob fahrlässig ein falsches Ergebnis angegeben. Tatsächlich bezog sich die Laufzeit auf eine Version, in der die Primzahltests auf mehrere Kerne parallelisiert sind. Es kam mir jetzt doch verdächtig vor und ich habe das Ganze nochmal nachgespielt.

Insgesamt habe ich mit der ein-Kern-Version einen Stand von 1496 Sekunden entsprechend ca. 25 Min.

Es ist mir sehr peinlich. Hier war wohl auch der Wunsch der Vater des Gedankens.... Jedenfalls bleibt damit alles offen. Ich werde mal übers Wochenende gucken, was ich da noch raus holen kann.

Grüße
Gonz



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
querin
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 12.01.2018
Mitteilungen: 327
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.42, vom Themenstarter, eingetragen 2019-06-10


Lösung:
Bisher hat es 14927124 Unix Prime Stamps gegeben. Und das wird sich auch bis Anfang 2027 nicht mehr ändern ;)

Wer dieses Ergebnis in weniger als 1496 Sekunden unter Verwendung von einem Kern und einem deterministischen Primzahltest bestätigen kann, bitte gleich posten!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3568
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.43, eingetragen 2019-06-11


Verwendet wurde hier - einer Anmerkung von Querin folgend - ein "an sich" probabilistische Primzahltest, der aber in dem betrachteten Bereich bekanntermaßen unter geeigneter Auswahl der getesteten Basen verläßlich ist. Diese Verläßlichkeit wurde, wenn ich den Artikel von Gerhard Jaenke richtig verstehe, nicht durch brutales Nachrechnen nachgewiesen ( andernfalls hätte man ja nur die Rechenarbeit sozusagen ausgelagert ). Es wäre bestimmt mal ein nettes Thema, sich damit weiter zu beschäftigen :)





Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
rlk
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.03.2007
Mitteilungen: 10838
Aus: Wien
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.44, eingetragen 2019-06-30


Hallo,
vielen Dank für das interessante Rätsel.
Meine Lösung
Es gibt $14\,927\,124$ im Zeitraum von 1970-2019, die gesuchte Ziffernsumme ist $30$.

Die Ergebnisse habe ich in der untenstehenden Tabelle zusammengefasst. Dabei ist $T$ die Laufzeit auf meinem Rechner (i5-6500, 3.20GHz), $U$ die Anzahl der Unix Prime Stamps, $C$ die Anzahl der Kandidaten, die auf Primalität getestet werden und $G$ die Anzahl der Kandidaten, die Primteiler $p<200$ besitzen.
In den letzten beiden Spalten habe ich den ersten und letzten UPS des jeweiligen Jahres eingetragen.

Die verbleibenden Werte habe ich mit einem für Zahlen dieser Größe deterministischen Miller-Rabin-Test mit den Zeugen 2, 1215, 34862, 574237825 [1] überprüft.

$$ \begin{array}{rrrrrrr}
\text{Jahr} & T~\mathrm{(s)} & U & G & C & \text{erster ups} & \text{letzter ups} \\
\hline
1973 & 35.04 & 1\,774\,077 & 17\,769\,203 & 22\,451\,832 &     97\,466\,522\,011 &    123\,465\,599\,821 \\
1979 & 36.23 & 1\,706\,705 & 17\,769\,761 & 22\,451\,832 &    286\,768\,922\,017 &    312\,767\,999\,983 \\
1987 & 36.89 & 1\,667\,517 & 17\,766\,285 & 22\,451\,832 &    539\,229\,722\,131 &    565\,228\,799\,719 \\
1993 & 37.03 & 1\,650\,122 & 17\,767\,543 & 22\,451\,832 &    728\,618\,522\,053 &    754\,617\,599\,977 \\
1997 & 36.87 & 1\,639\,770 & 17\,768\,438 & 22\,451\,832 &    854\,848\,922\,251 &    880\,847\,999\,947 \\
1999 & 37.23 & 1\,638\,168 & 17\,768\,979 & 22\,451\,832 &    917\,920\,922\,003 &    943\,919\,999\,863 \\
2003 & 37.34 & 1\,628\,241 & 17\,768\,060 & 22\,451\,832 & 1\,044\,151\,322\,023 & 1\,070\,150\,399\,863 \\
2011 & 37.64 & 1\,614\,853 & 17\,768\,480 & 22\,451\,832 & 1\,296\,612\,122\,089 & 1\,322\,611\,199\,977 \\
2017 & 37.71 & 1\,607\,671 & 17\,769\,225 & 22\,451\,832 & 1\,486\,000\,922\,023 & 1\,511\,999\,999\,977 \\
\hline
    & 331.98 & 14\,927\,124 &  159\,915\,974 & 202\,066\,488   &  &  \\
\end{array}
$$ Mein erster Versuch verwendete einen probabilistischen Solovay-Strassen-Test und war viel langsamer ( 8416 s).

[1]

Servus,
Roland






Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
querin
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 12.01.2018
Mitteilungen: 327
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.45, vom Themenstarter, eingetragen 2019-06-30


Hallo Roland rlk,

Gratulation und vielen Dank für deinen Beitrag!

Die neue Bestmarke liegt damit bei 332 Sekunden.

@Gonz: Jetzt musst du den goldenen Wanderpokal an rlk weitergeben. Aber ich darf dir hiermit feierlich die große silberne Ehrenschale überreichen ;)


LG querin



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3568
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.46, eingetragen 2019-06-30


Das mach ich doch gerne! Er gebührt ja auch RLK wirklich. Schöne Lösung!





Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
querin hat die Antworten auf ihre/seine Frage gesehen.
querin hatte hier bereits selbst das Ok-Häkchen gesetzt.
Dies ist eine Knobelaufgabe!
Der Themensteller hat bestimmt, dass Du Lösungen oder Beiträge zur Lösung direkt im Forum posten darfst.
Bei dieser Aufgabe kann ein öffentlicher Austausch über Lösungen, Lösungswege und Ansätze erfolgen. Hier musst Du keine private Nachricht schreiben!
Seite 2Gehe zur Seite: 1 | 2  
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


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-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. 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]