Die Zahl 113
ist die erste Primzahl, deren Länge 3
Primzahl, digitale Summe 5 = 1 + 1 + 3
Primzahl und digitales Produkt 3 = 1 * 1 * 3
Primzahl ist.
Eine Primzahl mit diesen drei Eigenschaften wird als höchste Primzahl bezeichnet . Die Primzahlen 11117
und 1111151
sind andere Beispiele.
Tor
Schreiben Sie ein Programm, das die größte findet höchst prime Zahl möglich in weniger als eine Stunde auf einem anständigen modernen Personal - Computer (wie die bevorzugte spec hier ).
Sie sollten uns nicht einfach eine große höchste Priorität geben. Sie müssen uns Ihren Suchvorgang mit tatsächlich funktionierendem Code zeigen. Sie können auf den Lösungen Ihrer Mitarbeiter oder anderer Personen aufbauen, aber Sie sollten ihnen unbedingt Anerkennung zollen. Wir versuchen gemeinsam, die höchste auf einem normalen Computer realisierbare Primzahl in einer Stunde zu finden.
Wertung
Die Einreichung, die die größte höchste Primzahl findet, gewinnt. Wenn sich herausstellt, dass es endlich viele höchste Primzahlen gibt, gewinnt die erste Einreichung, die die höchsten höchsten Primzahlen generiert.
(Wenn Sie mathematisch beweisen können, dass es unendlich viele höchste Primzahlen gibt oder nicht, gebe ich Ihnen 200 Kopfgeld-Wiederholungen, nur weil. :))
Einzelheiten
- Sie können jede Quelle verwenden, um Ihre Primzahlen zu generieren (z. B. Internet).
- Sie können probabilistische Primärtestmethoden anwenden.
- Alles ist in der Basis 10.
- Null und Eins werden NICHT als Primzahl betrachtet.
- Primzahlen, die enthalten,
0
haben ein digitales Produkt von0
so offensichtlich, dass sie nicht überlegen sein können. Um die Seite übersichtlicher zu halten, setzen Sie große (über 100-stellige) oberste Primzahlen in die Form:
{[number of 1's before the prime digit]}[prime digit]{[number of 1's after the prime digit]}
So
1111151
könnte ausgedrückt werden als{5}5{1}
.
quelle
Antworten:
Perl, 15101 Ziffern, {83} 7 {15017}, 8 Minuten. Max gefunden: 72227 Stellen
Mit meinem Modul Math :: Prime :: Util und seinem GMP- Backend . Es verfügt über eine Reihe von Komposititätstests, darunter is_prob_prime () mit einem ES BPSW-Test (etwas strenger als Paris ispseudoprime), is_prime (), der einen MR auf Zufallsbasis hinzufügt, und is_provable_prime (), der BLS75 T5 oder ECPP ausführt. Bei diesen Größen und Typen wird das Erstellen eines Proofs viel Zeit in Anspruch nehmen. Ich habe einen weiteren MR-Test im Sub Pedantic Verifier durchgeführt. Mal auf einem Core2 E7500 was definitiv nicht mein schnellster Computer ist (es dauert 2,5 Minuten auf meinem i7-4770K).
Wie Tim S. betont, könnten wir weiter nach größeren Werten suchen, bis zu dem Punkt, an dem ein einzelner Test eine Stunde dauert. Bei ~ 15000 Stellen auf diesem E7500 dauert ein MR-Test etwa 26 Sekunden und der gesamte is_prime-Test 2 Minuten (Versuchsdivision plus Basis-2-MR plus ES Lucas plus ein Zufallsbasis-MR). Mein i7-4770K ist über 3x schneller. Ich habe ein paar Größen ausprobiert, hauptsächlich um zu sehen, wie sich das auf die Ergebnisse anderer auswirkt. Ich habe 8k, 20k und 16k ausprobiert und jeweils nach ~ 5 Minuten getötet. Ich habe dann 15k in Progression für jeweils ~ 10m ausprobiert und beim 4. Glück gehabt.
Die PRP-Tests von OpenPFGW sind mit Sicherheit nach etwa 4000 Stellen schneller und in der Tat viel schneller im Bereich von über 50.000. Der Test enthält jedoch eine ganze Reihe von Fehlalarmen, was ihn zu einem großartigen Vortest macht, aber man möchte die Ergebnisse trotzdem mit etwas anderem überprüfen.
Dies könnte mit Perl-Threads oder mit MCE parallelisiert werden, ähnlich den parallelen Fibonacci-Prime-Finder-Beispielen im Modul.
Timing und Ergebnisse auf einem inaktiven i7-4770K mit Single Core:
Für das 32k-stellige Ergebnis habe ich 6 Skripte gestartet, die jeweils mit aufeinander folgenden Argumenten ab 32000 gleichzeitig ausgeführt wurden. Nach 26,5 Minuten war man mit dem angezeigten 32063-stelligen Ergebnis fertig. Für 57.000 ließ ich aufeinanderfolgende Skripte eine Stunde lang in 500er-Schritten jeweils 6 ausführen, bis das 57.000-Ergebnis in 57 Minuten zurückgegeben wurde. Das 72.000-stellige Ergebnis wurde durch Ausführen aufeinanderfolgender Primzahlen ab 70.000 gefunden, also definitiv nicht innerhalb einer Stunde (obwohl dies der Fall ist, sobald Sie wissen, wo Sie anfangen sollen).
Das Drehbuch:
quelle
gmpy2
und PyPy mitmy_math
) zu iterieren : codepad.org/aSzc0esTforprimes { ...do stuff... } 1e7;
die 10x oder schneller sind (ein Lob an Pari / GP für viele großartige Ideen). Ich freue mich immer über Feedback. Lassen Sie mich wissen, wenn etwas nicht so funktioniert, wie Sie es möchten.Python 2.7 unter PyPy, {2404} 3 {1596} (~ 10 ^ 4000)
Fand dieses etwa 50 Minuten nach dem Start von 4000. Daher würde ich schätzen, dass dies die Obergrenze dieses Code-Ansatzes ist.
Änderung: Ich habe festgestellt, dass einige Längen für die Erzeugung dieser Art von Primzahlen fruchtbarer zu sein scheinen als andere. Deshalb habe ich beschlossen, nur 50 zufällige Stellen der Ziffer, die nicht 1 ist, anstelle aller möglichen Stellen zu überprüfen, bevor ich mich bewege auf. Ich bin nicht ganz sicher, ob dies die Leistung verbessern wird oder ob 50 richtig ist, aber wir werden sehen.
Die Liste der Möglichkeiten wird basierend auf der Tatsache erstellt, dass für die Erfüllung der Produktanforderung nur eine einzige Zahl mit Ausnahme einer Primzahl erforderlich ist. Darüber hinaus darf die Primzahl aufgrund des Verhältnisses von Summe und Länge nicht 2 sein, und die digitale Summe darf nicht durch drei teilbar sein, da die% 3-Anforderungen erfüllt sind.
is_prime von http://codepad.org/KtXsydxK , geschrieben von @primo
Hinweis: Diese is_prime-Funktion ist eigentlich ein Baillie-PSW-Pseudoprime-Test, es sind jedoch keine Gegenbeispiele bekannt, sodass ich mich nicht um die Unterscheidung kümmern werde.
quelle
is_very_very_very_very_very_very_very_probably_prime()
...PARI / GP, 4127 Stellen
(10 4127 & ndash; 1) / 9 + 2 × 10 515
Dies ist eine recht unkomplizierte Suche: Überprüfen Sie nur die Länge der Primzahlen, berechnen Sie dann die möglichen zu verwendenden Primzahlen und durchlaufen Sie dann alle Möglichkeiten. Ich habe die häufigsten Fälle, in denen 0 oder 1 geeignete Primzahlen zu verwenden sind, als Sonderfall behandelt.
Die Berechnung auf einem Kern einer ziemlich alten Maschine dauerte 36 Minuten. Ich bin mir sicher, dass es kein Problem sein würde, eine solche Primzahl mit mehr als 5000 Stellen in einer Stunde zu finden, aber ich bin auch ungeduldig.
Eine bessere Lösung wäre, eine beliebige vernünftige Sprache zu verwenden, um alles außer der innersten Schleife auszuführen , und dann eine abc-Datei für primeform zu erstellen, die für diese bestimmte Art der Berechnung optimiert ist. Dies sollte in der Lage sein, die Berechnung auf mindestens 10.000 Stellen zu erhöhen.
Bearbeiten : Ich habe die oben beschriebene Hybridlösung implementiert, aber auf meinem alten Computer kann ich den ersten Begriff mit> = 10.000 Stellen in weniger als einer Stunde nicht finden. Wenn ich es nicht schneller laufen lasse, muss ich zu einem weniger hohen Ziel wechseln.
quelle
Mathematica 3181 Ziffern
Update: In meiner ersten Einsendung gab es einige schwerwiegende Fehler. Ich konnte einige Zeit aufwenden, um die Ergebnisse für dieses zu überprüfen. Die Ausgabe wird als Ziffernliste formatiert. Dies erleichtert die Überprüfung der einzelnen Bedingungen.
Beispiel
Dies war mein erster Test, eine Suche nach einer Lösung mit 3181 Ziffern. Es fand den ersten Fall in 26 Sekunden.
Lassen Sie uns die Überlegungen durchgehen. Dann treten wir in das Programm selbst ein.
Beginnen wir wie ich: "Was ist die 450. Primzahl?" Können wir eine Lösung mit so vielen Ziffern finden (3181)?
Die Nummer wird durch Verknüpfen der Ziffern ermittelt.
Aber anstatt es anzuzeigen, können wir stattdessen fragen, was die Ziffern sind und wo sie liegen.
Dies bedeutet, dass es 3180 Instanzen der Ziffer 1 und eine einzelne Instanz der Ziffer 7 gab.
An welcher Stelle steht die Ziffer 7?
Die Ziffer 7 ist also die 142. Ziffer. Alle anderen sind Einsen.
Natürlich muss das Produkt der Ziffern eine Primzahl sein, nämlich 7.
Und die Summe der Ziffern ist auch eine Primzahl.
Und wir wissen, dass die Anzahl der Ziffern eine Primzahl ist. Denken Sie daran, wir haben die 450. Primzahl ausgewählt, nämlich 3118.
Damit sind alle Voraussetzungen erfüllt.
quelle
4002 * 1 + 7 = 4009
müsstest du nicht 4003 testen und entsprechend der Spezifikation.Python 2.7, 6217 Ziffern: {23} 5 {6193} 6 Minuten, 51 Sekunden
Ich arbeitete an meiner eigenen Version und war enttäuscht zu sehen, dass @issacg mich mit einem sehr ähnlichen Ansatz ins Schwarze getroffen hatte, wenn auch mit is_ (sehr wahrscheinlich) _prime (). Ich sehe jedoch, dass ich einige signifikante Unterschiede habe, die zu einer besseren Antwort in kürzerer Zeit führen (wenn ich auch is_prime verwende). Um dies zu verdeutlichen, erreiche ich ab 4000 in nur 26 Minuten und 37 Sekunden eine bessere 4001-stellige Antwort ({393} 7 {3607}) mit dem Standard- Python-Interpreter (ebenfalls in Version 2.7), nicht mit PyPy Ausführung. Außerdem überprüfe ich die Zahlen nicht vor Ort. Alle Kandidaten werden geprüft.
Hier sind die wichtigsten Verbesserungen:
Verwenden Sie einen Primgenerator ( https://stackoverflow.com/questions/567222/simple-prime-generator-in-python/568618#568618 ), um eine Liste von Primzahlen zu erstellen, gegen die geprüft werden soll, und (seine Version von "kleinen Primzahlen") und zum Erzeugen geeigneter Nummernlängen.
Wir wollen unsere Zeit damit verbringen, nach der größten höchsten Primzahl einer bestimmten Länge zu suchen, nicht nach der kleinsten. Deshalb konstruiere ich zuerst die größtmöglichen Zahlen, um sie zu überprüfen, und nicht nach der kleinsten. Sobald einer gefunden ist, können wir sofort zur nächsten Länge übergehen.
EDIT: Jetzt mit Multiprocessing
Dies ist eine wesentliche Änderung gegenüber früheren Versionen. Zuvor bemerkte ich, dass mein 8-Core-Rechner kaum funktionierte, und beschloss, mich in Python (zum ersten Mal) an der Mehrfachverarbeitung zu versuchen. Die Ergebnisse sind sehr schön!
In dieser Version werden 7 untergeordnete Prozesse erzeugt, die eine 'Aufgabe' aus einer Warteschlange potenzieller Möglichkeiten (num_length + zulässige Ziffern) abrufen. Sie probieren verschiedene [7,5,3] Positionen aus, bis sie eine finden. In diesem Fall wird der Master-Prozess über die neue längste gefundene Länge informiert. Wenn Kinder an einer kürzeren Anzahl_Längen arbeiten, müssen sie nur auf Kaution gehen und die nächste Länge abrufen.
Ich habe diesen Lauf mit 6000 begonnen und er läuft noch, aber bis jetzt bin ich sehr zufrieden mit dem Ergebnis.
Das Programm stoppt noch nicht richtig, aber für mich kein großes Problem.
Nun der Code:
quelle
my_math
kann auch verwendet werden, um eine Liste von Primzahlen zu generieren, à lawhile prime < 20006: prime = next_prime(prime)
. Scheint ungefähr dreimal so schnellgen_primes
und wesentlich speichereffizienter zu sein.C, GMP - {7224} 5 {564} = 7789
Ein großes Lob an @issacg und euch alle für die Inspirationen und Tricks.
Und auch der meisterhafte Fragesteller @ Calvins Hobbys zu dieser Frage.
Kompilieren:
gcc -I/usr/local/include -o p_out p.c -pthread -L/usr/local/lib -lgmp
Wenn Sie Ihre Rechenleistung spenden möchten oder neugierig auf die Leistung sind, können Sie den Code kopieren und kompilieren. ;) Du musst GMP installiert haben.
quelle
PFGW, 6067 Ziffern, {5956} 7 {110}
Führen Sie PFGW mit der folgenden Eingabedatei aus und stellen Sie
-f100
die Zahlen vor. In ca. 2-3 CPU-Minuten auf meinem Computer (i5 Haswell) wird PRP (10 ^ (6073-6) -1) / 9 + 6 * 10 ^ 110 oder {5956} 7 {110} gefunden . Ich habe 6000 Stellen als Ausgangspunkt gewählt, um eine Nummer zu erhalten, die ein wenig höher ist als alle vorherigen Einreichungen.Anhand der Geschwindigkeit, mit der ich diese gefunden habe, konnte ich die Anzahl der Stellen leicht erhöhen und innerhalb einer Stunde immer noch einen PRP finden. Mit der Schreibweise der Regeln kann ich sogar feststellen, wie groß meine CPU ist, die auf allen vier Kernen läuft, einen PRP-Test in einer Stunde abschließt, lange Zeit für die Suche nach einem PRP benötigt und nur aus meiner "Suche" besteht des einen PRP.
PS In gewisser Hinsicht ist dies keine "Code" -Lösung, da ich nichts anderes als die Eingabedatei geschrieben habe ... Aber dann könnten viele einzeilige Mathematica-Lösungen für mathematische Probleme genauso beschrieben werden wie möglich mit einer Bibliothek, die die harte Arbeit für Sie erledigt. In Wirklichkeit finde ich es schwierig, eine gute Grenze zwischen den beiden zu ziehen. Wenn Sie möchten, könnte ich ein Skript schreiben, das die PFGW-Eingabedatei erstellt und PFGW aufruft. Das Skript könnte sogar parallel suchen, um alle 4 Kerne zu nutzen und die Suche um das ~ 4-fache zu beschleunigen (auf meiner CPU).
PPS Ich denke, LLR kann die PRP-Tests für diese Zahlen durchführen, und ich würde erwarten, dass es viel schneller als PFGW ist . Ein spezielles Siebprogramm könnte diese Zahlen auch besser berücksichtigen als das von PFGW nacheinander. Wenn Sie diese kombinieren, könnten Sie die Grenzen sicherlich noch viel höher setzen als bei den aktuellen Lösungen.
quelle
Python 2.7, 17-19 Ziffern
Gefunden 5111111111111 (13 Ziffern) in 3 Sekunden und diese 17 Ziffern höchste Primzahl in 3 Minuten. Ich vermute, dass der Zielcomputer dies ausführen und in weniger als einer Stunde eine 19-stellige höchste Primzahl erhalten könnte. Dieser Ansatz lässt sich nicht gut skalieren, da Primzahlen bis zur Hälfte der Anzahl der Zielziffern im Speicher bleiben. 17-stellige Suche erfordert das Speichern eines Arrays von 100 Millionen Booleschen Werten. 19 Stellen würden ein 1B-Elementarray erfordern, und der Speicher wäre erschöpft, bevor 23 Stellen erreicht würden. Laufzeit wäre wahrscheinlich auch.
Primalitätstest-Ansätze, die keine lächerlich große Anzahl von Divisor-Primzahlen beinhalten, schneiden viel besser ab.
quelle
Mathematica
42114259 ZiffernMit der Nummer:
{1042} 7 {3168}{388} 3 {3870}Welches wurde durch den folgenden Code generiert:
Die Würfe führen dazu, dass der Test auf andere Zahlen mit denselben Ziffern wie den aktuell gefundenen abgebrochen wird. Da der Test bei der höchstwertigen Ziffer beginnt, wird immer die größte Zahl zurückgegeben, es sei denn, die Anzahl der Ziffern ist Mitglied eines Primtripletts.
Einfach angefangen zu testen knapp unter dem Wert einer der vorhergehenden Antworten :)
Sobald dies abgeschlossen ist, wird die Nummer in der Variablen curlargest gespeichert
quelle
JavaScript, 3019 Ziffern, {2.273} 5 {745}
Hierfür wird der in BigInteger.js enthaltene MillerRabin-Test von Tom Wu verwendet.
Ausgehend von 0 => 2.046 Ziffern = {1799} 7 {263} in einer Stunde .
Ab 3000 => 3.019 Stellen = {2.273} 5 {745} in einer Stunde, weniger als 3 Sekunden .
Beim Start von 0 sprang das Programm vor und suchte erneut mit einer Länge von 1,5X der Länge des zuletzt gefundenen S-Prims. Als ich dann sah, wie schnell es lief, schätzte ich, dass es eines ab 3000 in einer Stunde finden würde - und das mit nur 3 Sekunden Zeitersparnis.
Sie können es hier ausprobieren: http://goo.gl/t3TmTk
(Zum Berechnen aller S-Primzahlen oder zum Überspringen.)
Das Programm erstellt Zeichenfolgen aller "1", jedoch mit einer "3", "5" oder "7". Ich habe einen schnellen Check in der IsStrPrime-Funktion hinzugefügt, um Zahlen mit der Endung "5" abzulehnen.
Das war ziemlich lustig. Erinnert mich an ein Rätsel, das ich vor vielen Jahren gemacht habe, um die sogenannte Ziffer ohne Primzahl zu berechnen . Dies ist eine Primzahl. Wenn Sie eine Ziffer entfernen, ist die verbleibende Zahl immer noch eine Primzahl. Beispielsweise ist 1037 eine Ziffer ohne Primzahl, da 1037, 037, 137, 107 und 103 Primzahlen sind. Ich habe eine 84-stellige gefunden und die längste, die ich kenne, ist 332-stellig. Ich bin sicher, dass wir mit den Techniken, die für dieses Rätsel verwendet wurden, noch viel länger fündig werden können. (Aber die Auswahl der Testnummern ist etwas schwieriger - vielleicht?)
quelle
Axiom, 3019 Ziffern {318} 5 {2700}
ergebnis aus dem startwert 3000 in 529 sek
quelle