Dies ist die Sequenz A054261
Die te Primzahl ist die niedrigste Zahl, die die ersten Primzahlen als Teilzeichenfolgen enthält. Zum Beispiel ist die Zahl die niedrigste Zahl, die die ersten 3 Primzahlen als Teilzeichenfolgen enthält, was sie zur dritten Primzahl macht.
Es ist trivial herauszufinden, dass die ersten vier Primzahlen , , und , aber dann wird es interessanter. Da die nächste Primzahl 11 ist, ist die nächste Primzahl nicht , sondern da sie als die kleinste Zahl mit der Eigenschaft definiert ist.
Die eigentliche Herausforderung ergibt sich jedoch, wenn Sie über 11 hinausgehen. Die nächste Primzahl lautet . Beachten Sie, dass sich in dieser Nummer die Teilzeichenfolgen und überlappen. Die Nummer überschneidet sich auch mit der Nummer .11
13
3
13
Es ist leicht zu beweisen, dass diese Folge zunimmt, da die nächste Zahl alle Kriterien der Zahl davor erfüllen und eine weitere Teilzeichenfolge haben muss. Die Sequenz nimmt jedoch nicht unbedingt zu, wie die Ergebnisse für n=10
und zeigen n=11
.
Herausforderung
Ihr Ziel ist es, so viele Primzahlen wie möglich zu finden. Ihr Programm sollte sie in einer geordneten Weise ausgeben, beginnend mit 2 bis hinauf.
Regeln
- Sie dürfen Primzahlen fest codieren.
- Es ist Ihnen nicht gestattet, Primzahlen (dies
2
ist die einzige Ausnahme) oder magische Zahlen, die die Herausforderung trivial machen , fest zu codieren . Bitte sei nett. - Sie können eine beliebige Sprache verwenden. Bitte fügen Sie eine Liste von Befehlen hinzu, um die Umgebung für die Ausführung des Codes vorzubereiten.
- Sie können sowohl CPU als auch GPU verwenden und Multithreading verwenden.
Wertung
Die offizielle Wertung stammt von meinem Laptop (Dell XPS 9560). Ihr Ziel ist es, innerhalb von 5 Minuten so viele Primzahlen wie möglich zu generieren.
Technische Daten
- 2,8 GHz Intel Core i7-7700HQ (3,8 GHz Boost) 4 Kerne, 8 Threads.
- 16 GB 2400 MHz DDR4-RAM
- NVIDIA GTX 1050
- Linux Mint 18.3 64-Bit
Die bisher gefundenen Zahlen, zusammen mit der letzten zur Zahl hinzugefügten Primzahl:
1 => 2 ( 2)
2 => 23 ( 3)
3 => 235 ( 5)
4 => 2357 ( 7)
5 => 112357 ( 11)
6 => 113257 ( 13)
7 => 1131725 ( 17)
8 => 113171925 ( 19)
9 => 1131719235 ( 23)
10 => 113171923295 ( 29)
11 => 113171923295 ( 31)
12 => 1131719237295 ( 37)
13 => 11317237294195 ( 41)
14 => 1131723294194375 ( 43)
15 => 113172329419437475 ( 47)
16 => 1131723294194347537 ( 53)
17 => 113172329419434753759 ( 59)
18 => 2311329417434753759619 ( 61)
19 => 231132941743475375961967 ( 67)
20 => 2311294134347175375961967 ( 71)
21 => 23112941343471735375961967 ( 73)
22 => 231129413434717353759619679 ( 79)
23 => 23112941343471735359619678379 ( 83)
24 => 2311294134347173535961967837989 ( 89)
25 => 23112941343471735359619678378979 ( 97)
26 => 2310112941343471735359619678378979 (101)
27 => 231010329411343471735359619678378979 (103)
28 => 101031071132329417343475359619678378979 (107)
29 => 101031071091132329417343475359619678378979 (109)
30 => 101031071091132329417343475359619678378979 (113)
31 => 101031071091131272329417343475359619678378979 (127)
32 => 101031071091131272329417343475359619678378979 (131)
33 => 10103107109113127137232941734347535961967838979 (137)
34 => 10103107109113127137139232941734347535961967838979 (139)
35 => 10103107109113127137139149232941734347535961967838979 (149)
36 => 1010310710911312713713914923294151734347535961967838979 (151)
Vielen Dank an Ardnauld, Ourous und japh für die Erweiterung dieser Liste.
Beachten Sie, dass n = 10
und n = 11
dieselbe Nummer sind, da die niedrigste Nummer ist, die alle Nummern , aber auch .
Als Referenz können Sie die Tatsache verwenden, dass das ursprüngliche Python-Skript, das ich geschrieben habe, um diese Liste oben zu generieren, die ersten 12 Terme in ungefähr 6 Minuten berechnet.
Zusätzliche Regeln
Nachdem die ersten Ergebnisse eingegangen sind, habe ich festgestellt, dass es eine gute Chance gibt, dass die besten Ergebnisse die gleiche Punktzahl haben. Im Falle eines Unentschieden ist der Gewinner derjenige, der die kürzeste Zeit hat, um sein Ergebnis zu erzielen. Wenn zwei oder mehr Antworten gleich schnell zu Ergebnissen führen, ist dies einfach ein Sieg.
Schlussbemerkung
Die 5-minütige Laufzeit soll nur eine faire Wertung gewährleisten. Ich wäre sehr gespannt, ob wir die OEIS-Sequenz weiter vorantreiben können (im Moment enthält sie 17 Zahlen). Mit Ourous 'Code habe ich bis alle Zahlen generiert n = 26
, aber ich plane, den Code für einen längeren Zeitraum laufen zu lassen.
Anzeigetafel
- Python 3 + Google OR-Tools : 169
- Scala : 137 (inoffiziell)
- Concorde TSP-Löser : 84 (inoffiziell)
- C ++ (GCC) + x86-Assembly : 62
- Sauber : 25
- JavaScript (Node.js) : 24
quelle
n=11
trivial macht, da Sie nur überprüfen müssen, obn=10
auch die neue Bedingung erfüllt ist. Ich würde auch argumentieren, dass Hardcodierung nur hilft, bisn=17
, soweit ich es herausfinden konnte, keine Zahlen darüber hinaus bekannt sind.[1,22,234,2356,112356,113256,1131724,113171924,1131719234,113171923294,113171923294,1131719237294]
und eine Suche von jedem StartAntworten:
Python 3 + Google OR-Tools , Punktzahl 169 in 295 Sekunden (offizielle Punktzahl)
Wie es funktioniert
Zeichnen Sie nach dem Verwerfen redundanter Primzahlen, die in anderen Primzahlen enthalten sind, einen gerichteten Graphen mit einer Kante von jeder Primzahl zu jedem Suffix mit dem Abstand Null und einer Kante zu jeder Primzahl von jedem Präfix, wobei der Abstand durch die Anzahl der hinzugefügten Ziffern definiert wird . Wir suchen den lexikografisch ersten kürzesten Weg durch den Graphen, beginnend mit dem leeren Präfix, über jeden Prim (aber nicht unbedingt durch jedes Präfix oder Suffix) und endend mit dem leeren Suffix.
Beispielsweise sind hier die Kanten des optimalen Pfades ε → 11 → 1 → 13 → 3 → 31 → 1 → 17 → ε → 19 → ε → 23 → ε → 29 → ε → 5 → ε für n = 11 entsprechend auf die Ausgabezeichenfolge 113171923295.
Verglichen mit der einfachen Reduktion auf das Problem des Handlungsreisenden ist zu beachten, dass durch die indirekte Verbindung der Primzahlen über diese zusätzlichen Suffix- / Präfixknoten anstelle einer direkten Verbindung die Anzahl der zu berücksichtigenden Kanten drastisch reduziert wurde. Da die zusätzlichen Knoten jedoch nicht genau einmal durchlaufen werden müssen, handelt es sich nicht mehr um eine Instanz von TSP.
Wir verwenden den inkrementellen CP-SAT-Constraint-Löser von Google OR-Tools, um zuerst die Gesamtlänge des Pfads und dann jede Gruppe hinzugefügter Ziffern in der angegebenen Reihenfolge zu minimieren. Wir initialisieren das Modell nur mit lokalen Einschränkungen: Jeder Prim steht vor einem Suffix und folgt einem Präfix, während jedem Suffix / Präfix die gleiche Anzahl von Primzahlen vorangeht und folgt. Das resultierende Modell kann getrennte Zyklen enthalten. In diesem Fall fügen wir dynamisch zusätzliche Konnektivitätsbeschränkungen hinzu und führen den Solver erneut aus.
Code
Ergebnisse
Hier sind die ersten 1000 Primzahlen , die in 1½ Tagen auf einem 8-Core / 16-Thread-System berechnet wurden.
quelle
C ++ (GCC) + x86-Assembly, Ergebnis
323662 in 259 Sekunden (offiziell)Bisher berechnete Ergebnisse. Mein Computer hat danach keinen Speicher mehr
65
.Diese stimmen alle mit der Ausgabe des Concorde-basierten Lösers überein , sodass sie gute Chancen haben, korrekt zu sein.
Änderungsprotokoll:
Falsche Berechnung der benötigten Kontextlänge. Die frühere Version war 1 zu groß und hatte auch einen Fehler. Prüfungsergebnis:
3234Optimierung für gleiche Kontextgruppen hinzugefügt. Prüfungsergebnis:
3436Überarbeitung des Algorithmus zur korrekten Verwendung kontextfreier Zeichenfolgen sowie einiger anderer Optimierungen. Prüfungsergebnis:
3662Fügte eine korrekte Beschreibung hinzu.
Primzahlvariante hinzugefügt.
Wie es funktioniert
Warnung: Dies ist ein Brain Dump. Scrollen Sie bis zum Ende, wenn Sie nur den Code möchten.
Abkürzungen:
Dieses Programm verwendet grundsätzlich den dynamischen Programmieralgorithmus des Lehrbuchs für den TSP.
Das sind viele potenzielle Fehler. Nachdem ich mit Anselms Eintrag herumgespielt und keine falschen Ergebnisse herausgefordert habe, sollte ich zumindest beweisen, dass mein Gesamtansatz korrekt ist.
Obwohl die Concorde-basierte Lösung (viel, viel) schneller ist, basiert sie auf derselben Reduzierung, sodass diese Erklärung für beide gilt. Zusätzlich kann diese Lösung für OEIS A054260 angepasst werden , die Prim-enthaltende Primsequenz ; Ich weiß nicht, wie ich das im TSP-Framework effizient lösen soll. Es ist also immer noch etwas relevant.
TSP-Reduzierung
Beginnen wir damit, zu beweisen, dass die Reduzierung auf TSP richtig ist. Wir haben eine Reihe von Zeichenfolgen, sagen wir
und wir wollen den kleinsten Superstring finden, der diese Elemente enthält.
Die Länge zu kennen ist genug
Wenn es für die PCN mehrere kürzeste Zeichenfolgen gibt, müssen wir die lexikografisch kleinste zurückgeben. Wir werden uns jedoch ein anderes (und einfacheres) Problem ansehen.
Wenn wir die SCS-Länge lösen können, können wir die kleinste Lösung rekonstruieren und die PCN erhalten. Wenn wir wissen, dass die kleinste Lösung mit unserem Präfix beginnt, versuchen wir, es zu erweitern, indem wir jedes Element in lexikografischer Reihenfolge anhängen und erneut nach der Länge suchen. Wenn wir den kleinsten Artikel finden, für den die Lösungslänge gleich ist, wissen wir, dass dies der nächste Artikel in der kleinsten Lösung sein muss (warum?), Also fügen Sie ihn hinzu und verwenden Sie die restlichen Artikel. Diese Methode zum Erreichen der Lösung wird als Selbstreduktion bezeichnet .
Rundgang durch den Maximalüberlappungsgraphen
Angenommen, wir haben begonnen, SCS für das obige Beispiel von Hand zu lösen. Wir würden wahrscheinlich:
13
und37
, weil sie bereits Teilzeichenfolgen der anderen Elemente sind. Jede Lösung, die137
beispielsweise enthält , muss auch13
und enthalten37
.113,137 → 1137
,211,113 → 2113
usw.Dies ist in der Tat das Richtige, aber wir wollen es der Vollständigkeit halber beweisen. Nehmen Sie eine SCS-Lösung. beispielsweise Superstring ein kürzester für
A
ISund es kann in eine Verkettung aller Elemente in zerlegt werden
A
:(Wir ignorieren die überflüssigen Elemente
13, 37
.) Beachten Sie Folgendes:Wir werden zeigen, dass jeder kürzeste Superstring folgendermaßen zerlegt werden kann:
Für jedes Paar benachbarter Elemente
x,y
,y
beginnt und endet in späteren Positionen alsx
. Ist dies nicht der Fall, handelt es sich entwederx
um eine Teilzeichenfolge vony
oder umgekehrt. Wir haben jedoch bereits alle Elemente entfernt, die Teilzeichenfolgen sind, sodass dies nicht passieren kann.Angenommen, benachbarte Elemente in der Sequenz haben weniger als die maximale Überlappung, z . B.
21113
anstelle von2113
. Aber das würde das Extra1
überflüssig machen. Kein späteres Element benötigt das Initial1
(wie in 2 1 113), da es früher auftritt113
und alle Elemente, die danach erscheinen,113
nicht mit einer Ziffer davor beginnen können113
(siehe Punkt 1). Ein ähnliches Argument verhindert, dass das letzte Extra1
(wie in 211 1 3) von einem vorherigen Element verwendet wird211
. Unser kürzester Superstring wird jedoch definitionsgemäß keine redundanten Ziffern haben, sodass solche nicht maximalen Überlappungen nicht auftreten.Mit diesen Eigenschaften können wir jedes SCS-Problem in einen TSP konvertieren:
x
,y
hinzufügen, eine Kante vonx
zuy
dessen Gewicht die Anzahl der zusätzlichen Symbole hinzugefügt durch Anhängey
anx
mit maximaler Überlappung. Zum Beispiel würden wir eine Kante von211
bis113
mit der Gewichtung 12113
hinzufügen , weil eine weitere Ziffer hinzugefügt wird211
. Wiederholen Sie dies für die Kante vony
bisx
.Jeder Pfad in diesem Diagramm ab dem anfänglichen Präfix entspricht einer maximalen Überlappungsverkettung aller Elemente auf diesem Pfad, und die Gesamtgewichtung des Pfads entspricht der Länge der verketteten Zeichenfolge. Daher entspricht jede Tour mit dem geringsten Gewicht, die alle Elemente mindestens einmal besucht, einem kürzesten Superstring.
Und das ist die Reduzierung von SCS (und SCS-Length) auf TSP.
Dynamischer Programmieralgorithmus
Dies ist ein klassischer Algorithmus, aber wir werden ihn ziemlich modifizieren, deshalb hier eine kurze Erinnerung.
(Ich habe dies als Algorithmus für SCS-Length anstelle von TSP geschrieben. Sie sind im Wesentlichen gleichwertig, aber das SCS-Vokabular hilft, wenn wir zu den SCS-spezifischen Optimierungen gelangen.)
Rufen Sie die Menge der Eingabeelemente
A
und das angegebene Präfix aufP
. Für jedek
-Element-TeilmengeS
inA
und jedes Elemente
vonS
berechnen wir die Länge der kürzesten Zeichenfolge, die mit beginnt , alle ElementeP
enthältS
und mit endete
. Dies beinhaltet das Speichern einer Tabelle von Werten(S, e)
bis zu ihren SCS-Längen.Wenn wir zu jeder Teilmenge kommen
S
, muss die Tabelle bereits die ErgebnisseS - {e}
für alle
in enthaltenS
. Da die Tabelle sehr groß werden kann, berechne ich die Ergebnisse für allek
-Element-Teilmengenk+1
usw. Dazu müssen wir nur die Ergebnisse fürk
undk+1
zu einem bestimmten Zeitpunkt speichern . Dies reduziert die Speichernutzung um einen Faktor von ungefährsqrt(|A|)
.Noch ein Detail: Anstatt die minimale SCS-Länge zu berechnen, berechne ich tatsächlich die maximale Gesamtüberlappung zwischen den Elementen. (Um die SCS-Länge zu erhalten, subtrahieren Sie einfach die Gesamtüberlappung von der Summe der Längen der Elemente.) Die Verwendung von Überlappungen hilft bei einigen der folgenden Optimierungen.
[2.] Gegenstandskontexte
Ein Kontext ist das längste Suffix eines Elements, das sich mit folgenden Elementen überschneiden kann. Wenn unsere Artikel sind
113,211,311
, dann11
ist der Kontext für211
und311
. (Es ist auch der Präfix-Kontext für113
, den wir uns in Teil [4.] ansehen werden.)Im obigen DP-Algorithmus haben wir die SCS-Lösungen verfolgt, die mit jedem Element enden, aber es ist uns eigentlich egal, in welchem Element ein SCS endet. Wir müssen nur den Kontext kennen. Wenn beispielsweise zwei SCSs für den gleichen Satz in
23
und enden43
, funktioniert jeder SCS, der von einem fortfährt, auch für den anderen.Dies ist eine signifikante Optimierung, da nicht-triviale Primzahlen nur mit den Ziffern enden
1 3 7 9
. Die vier einstelligen Kontexte1,3,7,9
(plus der leere Kontext) reichen tatsächlich aus, um die PCNs für Primzahlen bis zu zu berechnen131
.[3.] Kontextfreie Elemente
Andere haben bereits darauf hingewiesen, dass viele Primzahlen mit den Ziffern beginnen
2,4,5,6,8
, wie z23,29,41,43...
. Keines davon kann sich mit einem vorherigen Prim überschneiden (abgesehen von2
und5
können Primzahlen nicht mit diesen Ziffern enden2
und5
wurden bereits als redundant entfernt). Im Code werden diese als kontextfreie Zeichenfolgen bezeichnet .Wenn unsere Eingabe kontextfreie Elemente enthält, kann jede SCS-Lösung in Blöcke aufgeteilt werden
und die Überlappungen in jedem Block sind unabhängig von den anderen Blöcken. Wir können die Blöcke mischen oder Elemente zwischen Blöcken mit demselben Kontext austauschen, ohne die SCS-Länge zu ändern.
Daher müssen wir nur die möglichen Mehrfachmengen von Kontexten verfolgen , eine für jeden Block.
Vollständiges Beispiel: Für die Primzahlen unter 100 haben wir 11 kontextfreie Elemente und deren Kontexte:
Unser anfänglicher Multiset-Kontext:
Der Code bezeichnet diese als kombinierte Kontexte oder c- Kontexte . Dann müssen wir nur Teilmengen der verbleibenden Elemente berücksichtigen:
[4.] Zusammenführen von Kontexten
Sobald wir zu Primzahlen mit 3 oder mehr Ziffern kommen, gibt es mehr Redundanzen:
Diese Gruppen haben den gleichen Anfangs- und Endkontext (in der Regel hängt es davon ab, welche anderen Primzahlen in der Eingabe enthalten sind), sodass sie beim Überlappen anderer Elemente nicht unterschieden werden können. Wir kümmern uns nur um Überlappungen, also können wir Primzahlen in diesen kontextgleichen Gruppen als nicht unterscheidbar behandeln. Jetzt werden unsere DP-Subsets zu Multisubsets zusammengefasst
(Aus diesem Grund maximiert der Solver auch die Überlappungslänge, anstatt die SCS-Länge zu minimieren. Bei dieser Optimierung wird die Überlappungslänge beibehalten.)
Zusammenfassung: die übergeordneten Optimierungen
Wenn Sie mit der
INFO
Debug-Ausgabe arbeiten, werden Statistiken wie folgt gedrucktDiese spezielle Zeile ist für die SCS-Länge der ersten 62 Primzahlen,
2
bis293
.1,3,7,11,13,27
plus die leere Zeichenfolge.43,47,53,59,61,89,211,223,227,229,241,251,257,263,269,281,283
. Diese und das angegebene Präfix (in diesem Fall leere Zeichenfolge) bilden die Grundlage für den anfänglichen kombinierten Kontext .N_search
) gibt es 16 nichttriviale Gruppen mit gleichem Kontext .Durch Ausnutzen dieser Strukturen muss die SCS-Längenberechnung nur 8498336
(multiset, ccontext)
Kombinationen prüfen . Eine unkomplizierte dynamische Programmierung würde43×2^43 > 3×10^14
Schritte erfordern, und das rohe Erzwingen der Permutationen würde6×10^52
Schritte erfordern. Das Programm muss SCS-Length noch einige Male ausführen, um die PCN-Lösung zu rekonstruieren, aber das dauert nicht viel länger.[5., 6.] Die Low-Level-Optimierungen
Anstatt Zeichenfolgenoperationen auszuführen, arbeitet der SCS-Längenlöser mit Indizes von Elementen und Kontexten. Ich berechne auch den Überlappungsbetrag zwischen jedem Kontext und Elementpaar vor.
Der Code verwendete anfänglich GCCs
unordered_map
, bei denen es sich anscheinend um eine Hash-Tabelle mit verknüpften Listenbereichen und primären Hash-Größen (dh teuren Abteilungen) handelt. Also habe ich meine eigene Hash-Tabelle mit linearer Abtastung und Potenz von zwei Größen geschrieben. Dies führt zu einer dreifachen Beschleunigung und einer dreifachen Reduzierung des Speichers.Jeder Tabellenzustand besteht aus einer Vielzahl von Elementen, einem kombinierten Kontext und einer Überlappungsanzahl. Diese sind in 128-Bit-Einträge gepackt: 8 für die Überlappungszahl, 56 für die Mehrfachmenge (als Bitmenge mit Lauflängencodierung) und 64 für den c-Kontext (1-begrenzte RLE). Das Codieren und Decodieren des c-Kontexts war der schwierigste Teil, und ich habe die neue
PDEP
Anweisung verwendet (sie ist so neu, dass GCC noch keine eigene hat).Schließlich ist der Zugriff auf eine Hash-Tabelle bei
N
großen Datenmengen sehr langsam , da die Tabelle nicht mehr in den Cache passt. Der einzige Grund, warum wir in die Hash-Tabelle schreiben, ist die Aktualisierung der bekanntesten Überlappungsanzahl für jeden Zustand. Das Programm teilt diesen Schritt in eine Vorabrufwarteschlange auf, und die innere Schleife ruft jede Tabellensuche einige Iterationen vorab ab, bevor dieser Slot tatsächlich aktualisiert wird. Nochmal 2 × Speedup auf meinem Computer.Bonus: weitere Verbesserungen
AKA Wie ist Concorde so schnell?
Ich weiß nicht viel über TSP-Algorithmen, daher hier eine grobe Vermutung.
Concorde verwendet die Branch-and-Cut- Methode, um TSPs zu lösen.
Offensichtliche Ideen, die wir versuchen könnten:
Die Branch-and-Cut-Kombination ist jedoch sehr leistungsfähig, sodass wir einen hochmodernen Solver wie Concorde möglicherweise nicht für große Werte von schlagen können
N
.Bonusbonus: Die Prim-Containment-Prims
Im Gegensatz zur Concorde-basierten Lösung kann dieses Programm geändert werden, um die kleinsten Primzahlen zu ermitteln ( OEIS A054260 ). Dies beinhaltet drei Änderungen:
Ändern Sie den SCS-Length-Solver-Code, um Lösungen danach zu kategorisieren, ob ihre Ziffernsummen durch 3 teilbar sind. Dazu wird jedem DP-Status ein weiterer Eintrag, die Ziffernsumme mod 3, hinzugefügt. Dies verringert die Wahrscheinlichkeit, dass der Hauptlöser bei Nicht-Prim-Permutationen hängen bleibt, erheblich. Dies ist die Änderung, die ich nicht herausfinden konnte, wie ich in TSP übersetzen soll. Es kann mit ILP codiert werden, aber dann müsste ich etwas über dieses Ding namens "Subtour-Ungleichheit" lernen und wie man diese erzeugt.
Es kann sein, dass alle kürzesten PCNs durch 3 teilbar sind. In diesem Fall muss die kleinste Prim-Containment-Primzahl mindestens eine Stelle länger als die PCN sein. Wenn unser SCS-Längenlöser dies erkennt, kann der Lösungsrekonstruktionscode an jeder Stelle des Prozesses eine zusätzliche Ziffer hinzufügen . Es wird versucht, jede mögliche Ziffer
0..9
und jedes verbleibende Element in lexikografischer Reihenfolge zum aktuellen Lösungspräfix hinzuzufügen .Mit diesen Änderungen kann ich die Lösungen bis zu erhalten
N=62
. Ausgenommen47
, der Rekonstruktionscode bleibt hängen und gibt nach 1 Million Schritten auf (ich weiß noch nicht warum). Die Prim-Containment-Primzahlen sind:Code
Kompilieren mit
Verlinken Sie für die Primzahl-Version auch mit GMPlib, z
Dieses Programm verwendet den PDEP-Befehl, der nur auf aktuellen (Haswell +) x86-Prozessoren verfügbar ist. Sowohl mein Computer als auch Maxbs unterstützen es. Wenn dies nicht der Fall ist, wird das Programm in einer langsamen Softwareversion kompiliert. In diesem Fall wird eine Kompilierungswarnung gedruckt.
Probieren Sie es online!
Und die Prime-Only-Version von TIO . Sorry, aber ich habe diese Programme nicht golfen und es gibt ein Post-Längenlimit.
quelle
debug_dummy
können Sie verwenden#define DEBUG(x) void(0)
.debug_dummy
weil ich möchte, dass die Argumente überprüft und ausgewertet werden, auch wenn das Debuggen ausgeschaltet ist.N=32
Benötigt aber nur ca. 500MB, denke ich.main
, aber ich habe ihn über den TIO-Link gefunden.JavaScript (Node.js) , Punktzahl 24 in 241 Sekunden
Ergebnisse
Algorithmus
Dies ist eine rekursive Suche, bei der alle möglichen Methoden zum Zusammenführen von Zahlen ausprobiert werden und die resultierenden Listen schließlich in lexikografischer Reihenfolge sortiert werden, wenn ein Blattknoten erreicht wird.
Zu Beginn jeder Iteration wird jeder Eintrag, der sich in einem anderen Eintrag befindet, aus der Liste entfernt.
Eine signifikante Beschleunigung wurde erzielt, indem die besuchten Knoten verfolgt wurden, so dass wir vorzeitig abbrechen können, wenn verschiedene Vorgänge zu derselben Liste führen.
Eine kleine Beschleunigung wurde erzielt, indem die Liste nach Möglichkeit aktualisiert und wiederhergestellt wurde, anstatt eine Kopie zu erstellen, wie von
einem anonymen Benutzer,Neil, vorgeschlagen.Beispiel
Code
Probieren Sie es online!
quelle
Concorde TSP-Löser , Ergebnis 84 in 299 Sekunden
Nun ... ich bin dumm, dass ich das erst jetzt merke.
Diese ganze Sache ist im Wesentlichen ein Problem für reisende Verkäufer . Fügen Sie für jedes Primzahlenpaar
p
undq
eine Kante hinzu, deren Gewicht der Anzahl der hinzugefügten Ziffern entsprichtq
(Entfernen überlappender Ziffern). Fügen Sie außerdem zu jeder Primzahlp
, deren Gewicht der Länge von entspricht , eine erste Kante hinzup
. Der kürzeste Handelsweg entspricht der Länge der kleinsten Primzahl.Dann kann ein industrietauglicher TSP-Löser wie Concorde dieses Problem schnell lösen.
Dieser Eintrag sollte wahrscheinlich als nicht konkurrierend angesehen werden.
Ergebnisse
Der Solver erreicht
N=350
in etwa 20 CPU-Stunden. Die vollständigen Ergebnisse sind zu lang für einen SE-Beitrag, und das OEIS möchte sowieso nicht so viele Begriffe. Hier sind die ersten 200:Code
Hier ist ein Python 3-Skript, mit dem der Concorde-Solver immer wieder aufgerufen werden kann, bis die Lösungen erstellt sind.
Concorde ist für die akademische Nutzung kostenlos. Sie können eine ausführbare Binärdatei von Concorde herunterladen, die mit dem eigenen linearen Programmierpaket QSopt erstellt wurde, oder, wenn Sie eine Lizenz für IBM CPLEX haben, Concorde aus dem Quellcode für die Verwendung von CPLEX erstellen .
quelle
Sauber , 25 Punkte in 231 Sekunden (offizielle Punktzahl)
Ergebnisse
1 < n <= 23
in4236 Sekunden auf TIOn = 24 (2311294134347173535961967837989)
in3224 Sekunden vor Ortn = 25 (23112941343471735359619678378979)
in210160 Sekunden vor Ortn = 1
ton = 25
wurde in 231 Sekunden für die offizielle Wertung gefunden (bearbeitet von maxb)Hierbei wird ein ähnlicher Ansatz wie bei der JS-Lösung von Arnauld verwendet, der auf der Zurückweisung rekursiver Permutationen basiert und einen speziellen Baumsatz verwendet, um viel Geschwindigkeit zu erzielen.
Für jede Primzahl, die in die Zahl passen muss:
Entfernen Sie dann für jedes Paar von Unterzeichenfolgen, die wir verbunden haben, alle Unterzeichenfolgen dieses verbundenen Paares aus der Liste der Unterzeichenfolgen und wiederholen Sie den Vorgang.
Sobald keine Unterzeichenfolgen mehr mit anderen Unterzeichenfolgen in einem Zweig unserer Rekursion verbunden werden können, verwenden wir die bereits geordnete Baumgruppe, um schnell die niedrigste Zahl zu finden, die die Unterzeichenfolgen enthält.
Dinge, die verbessert / hinzugefügt werden müssen:
Es gab große Leistungseinbußen zwischen
19 -> 20
und24 -> 25
aufgrund der doppelten Behandlung durch den Zusammenführungsversuchsschritt und den Ablehnungsschritt für Kandidaten, aber diese wurden behoben.Optimierungen:
removeOverlap
ist so konzipiert, dass immer eine Reihe von Unterzeichenfolgen bereits in der optimalen Reihenfolge angegeben werdenuInsertMSpec
Reduziert Check-If-Is-Member und Insert-New-Member auf einen Satz TraversalcontainmentNumbersSt
prüft, ob die vorherige Lösung für eine neue Nummer funktioniertProbieren Sie es online!
Speichern
main.icl
und kompilieren mit:clm -fusion -b -IL Dynamics -IL StdEnv -IL Platform main
Dies erzeugt eine Datei,
a.out
die ausgeführt werden soll alsa.out -h <heap_size>M -s <stack_size>M
, wobei<heap_size> + <stack_size>
der Speicher, der vom Programm verwendet wird, in Megabyte ist.(Ich setze den Stack im Allgemeinen auf 50 MB, aber ich habe selten Programme, die sogar so viel verwenden)
quelle
Scala , Punktzahl 137Bearbeiten:
Der Code hier vereinfacht das Problem.
Somit funktioniert die Lösung für viele Eingaben, jedoch nicht für alle.
Ursprünglicher Beitrag:
Grundidee
Einfacheres Problem
Zuerst generieren wir die Primzahlen und entfernen alle, die bereits Teilzeichenfolgen anderer sind. Dann können wir mehrere Regeln anwenden. Wenn es also nur eine Zeichenfolge gibt, die in einer Sequenz endet, und nur eine, die mit derselben Sequenz beginnt, können wir sie zusammenführen. Eine andere Möglichkeit wäre, dass eine Zeichenfolge, die mit derselben Sequenz beginnt und endet (wie 101), an eine andere Zeichenfolge angehängt / angehängt werden kann, ohne dass das Ende geändert wird. (Diese Regeln geben nur unter bestimmten Bedingungen nach, seien Sie also vorsichtig, wenn Sie sie anwenden.)
Das eigentliche Problem
10103
0
10103
1
Wenn also die Regeln im obigen Algorithmus immer ausreichend wären, hätte sich gezeigt, dass das Problem nicht NP-hart ist.
findSeq
Versuchen Sie es online
Code
Wie Anders Kaseorg in den Kommentaren hervorhob, kann dieser Code suboptimale (daher falsche) Ergebnisse liefern.
Ergebnisse
187
188
189
193
quelle
1234
,3423
,2345
erzeugen Sie123453423
statt der optimalen12342345
.457, 571, 757
(alle Primzahlen).findSeq
würde dafür zurückkehren,7574571
aber die kürzeste Länge ist457571
. Ihr Ansatz spielt also mit dem Feuer. Trotzdem wurde er für seine Kühnheit ausgezeichnet.