Die Mathe-Redaktion - 19.09.2019 05:03 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Sept.
ListenpunktFormeleditor fedgeo
Schwarzes Brett
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. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

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

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
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
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 12.01.2018
Mitteilungen: 202
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).



  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: 3177
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


-----------------
~ to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
querin
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 12.01.2018
Mitteilungen: 202
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 wink

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



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3177
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 :)





-----------------
~ to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
rlk
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.03.2007
Mitteilungen: 10520
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] primes.utm.edu/prove/prove2_3.html

Servus,
Roland






  Profil  Quote  Link auf diesen Beitrag Link
querin
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 12.01.2018
Mitteilungen: 202
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 wink


LG querin



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3177
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!





-----------------
~ to fight! (Don Quijote de la Mancha)



  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-2019 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]