Die Aufgabe besteht darin, bei gegebener Zahl n
die kleinste Primzahl zu finden, die mit MINDESTEN n
der Zahl 2
am Anfang der Zahl beginnt . Dies ist eine Sequenz, die ich in OEIS ( A068103 ) gefunden habe.
Die ersten 17 Zahlen in der Sequenz sind unten angegeben. Wenn Sie mehr wollen, muss ich die Sequenz tatsächlich implementieren, was mir nichts ausmacht.
0 = 2
1 = 2
2 = 223
3 = 2221
4 = 22229
5 = 2222203
6 = 22222223 # Notice how 6 and 7 are the same!
7 = 22222223 # It must be **AT LEAST** 6, but no more than necessary.
8 = 222222227
9 = 22222222223 # Notice how 9 and 10 are the same!
10 = 22222222223 # It must be **AT LEAST** 9, but no more than necessary.
11 = 2222222222243
12 = 22222222222201
13 = 22222222222229
14 = 222222222222227
15 = 222222222222222043
16 = 222222222222222221
Ich dachte, dies wäre eine coole Kombination aus String-Manipulation, Prim-Erkennung und Sequenzen. Dies ist Code-Golf , die niedrigste Anzahl von Bytes wird wahrscheinlich Ende des Monats zum Gewinner erklärt.
x
. Wenn Ihre Sprache beispielsweise nur 32-Bit-Ganzzahlen unterstützt, können Sie dies erklären.Antworten:
Brachylog ,
1211 BytesProbieren Sie es online!
Dies führt überraschend direkt zu Brachylog. Dies ist eine Funktion, kein vollständiges Programm (auch wenn der Interpreter
Z
als Befehlszeilenargument angegeben wird, fügt er den entsprechenden Wrapper hinzu, um die Funktion in ein Programm umzuwandeln; das habe ich getan, damit die TIO-Verknüpfung funktioniert). Es ist auch ziemlich bedauerlich, dassj
der Index -1 ist und eine Korrektur benötigt, um dies zu berücksichtigen.Sie können ein vernünftiges Argument dafür vorbringen, dass das
=
nicht notwendig ist, aber ich denke, dass es das ist, wenn man bedenkt, wie das Problem formuliert ist. ohne, ist die Funktion die Menge aller Primzahlen zu beschreiben , die mit der gegebenen Anzahl von beginnen2
s, und ohne eine ausdrückliche Erklärung , dass das Programm tun , etwas mit dieser Beschreibung (in diesem Fall den ersten Wert zu erzeugen), hat es wahrscheinlich nicht Die Spezifikation einhalten.Erläuterung
Bei Verwendung als eine Funktion, die eine Ganzzahl zurückgibt, werden niemals Werte nach dem ersten angefordert, so dass wir uns nur um den ersten Gedanken machen müssen.
Eine Subtilität (in den Kommentaren hervorgehoben):
:Acb
undb:Ac
sind mathematisch äquivalent (da eine vom Anfang entfernt und die andere zum Ende hinzugefügt wird, wobei sich die Region dazwischen nie überlappt); Ich hatte vorherb:Ac
, was natürlicher ist, aber es bricht bei Eingabe 0 ab (was ich vermute, ist, weil es sichc
weigert, eine leere Liste mit irgendetwas zu verknüpfen; viele Brachylog-Builtins neigen aus irgendeinem Grund dazu, bei leeren Listen zu brechen).:Acb
stellt sicher, dassc
niemals eine leere Liste angezeigt werden muss, sodass der Fall von Eingang 0 jetzt auch funktionieren kann.quelle
0
ohne ersichtlichen Grund nicht funktioniert (Brachylog scheint aus irgendeinem Grund allergisch gegen Nullen zu sein; ich vermute, dasc
ist dafür verantwortlich). Das heißt, es ist leicht zu beheben, also werde ich das jetzt beheben.b:Ac
funktioniert nicht, weil für die Eingabe, die0
Sie erhalten2b:Ac
:2b
gibt0
und Sie nichtc
mit einer führenden Null verwenden können. Der Grund dafür ist die Vermeidung von Endlosschleifen in dem allgemeinen Fall, dass Sie immer eine Null voranstellen und die gleichen Ergebnisse erzielen könnten.:2rj
,2:?j
r
; Das ist nur eine deutliche Verbesserung. Ich verstehe, was los istc
(Sie wollen nicht unendlich viele Ergebnisse, wenn Sie rückwärts laufen); Eine wahrscheinliche Verbesserung besteht darin, dass entartete Eingaben nur dann nicht zugelassen werden, wenn sie nicht gebunden sind, während sie zugelassen werden, wenn die Eingabe bereits an einen entarteten Wert gebunden ist.Java (OpenJDK 8) ,
164 -110 ByteVielen Dank an @FryAmTheEggman für ein paar Bytes!
Probieren Sie es online!
quelle
new String(new char[i]))
eine unäre Zeichenfolge mit der Länge gleich der Zahl. Der reguläre Ausdruck stimmt dann mit einer zusammengesetzten Zahl überein, indem geprüft wird, ob die Wiederholung eines Ziffernsatzes für die gesamte Zeichenfolge geeignet ist (im Grunde genommen Testteilung). Wenn ich richtig liege, bedeutet das, dass Sie in der Lage sein sollten, den zweiten Teil zu spielen, ohne einen zu haben?
, werde ich Sie sicher informieren, wenn ich an einen Computer komme.Pyth, 12 Bytes
Im Pseudocode:
Schleift den
lambda
Start abT=1
und erhöht sich um 1, bis die Bedingung erfüllt ist. Die Zeichenfolge von2
s muss eine Teilzeichenfolge vom Anfang der Zeichenfolge sein, dh die Indexmethode muss zurückgeben0
. Wenn die Teilzeichenfolge nicht gefunden wird, wird sie zurückgegeben,-1
was in geeigneter Weise auch wahr ist, sodass kein Ausnahmefall vorliegt.Sie können es hier online ausprobieren , aber der Server erlaubt nur eine Eingabe von
4
.quelle
Perl, 50 Bytes
49 Byte Code +
-p
Flag.Geben Sie den Eingang ohne letzte Zeile ein. Zum Beispiel:
Es dauert eine Weile, bis eine Zahl größer als 4 ausgeführt wird, da jede Zahl getestet wird (es gibt 2 Tests: Der erste
/^2{$_}/
prüft, ob zu Beginn genug 2 vorhanden sind, und der zweite prüft, ob die(1x$\)!~/^1?$|^(11+)\1+$/
Primzahl vorhanden ist (mit sehr schlechten Leistungen)).quelle
Haskell, 73 Bytes
Anwendungsbeispiel:
f 3
->2221
.Rohe Gewalt.
[1..n]>>"2"
Erstellt eine Liste vonn
2
s, die mit den erstenn
Zeichen in der Zeichenfolgendarstellung der aktuellen Primzahl verglichen wird .quelle
Mathematica, 103 Bytes
Unbenannte Funktion, die ein nichtnegatives Ganzzahlargument verwendet
#
und eine Ganzzahl zurückgibt. Es testet buchstäblich alle positiven ganzen Zahlen, bis es eine findet, mit der beide beginnen#
2s und eine Primzahl ist. Schrecklich langsam für Eingaben über 5.vorheriges Ergebnis: Mathematica, 155 Bytes
Mathematica wäre besser zum Golfen geeignet, wenn es nicht so stark getippt wäre. Wir müssen explizit zwischen Integer-, Listen- und String-Typen hin- und herschalten.
Dieser Algorithmus arbeitet auf Listen der Stellen , seltsam, beginnend mit
{2,...,2,1}
. Solange dies nicht die Ziffern einer Primzahl sind, addiert es eine zur letzten Ziffer, wobei die Regel verwendet wird{j___,k_}/;!PrimeQ@d@{j,k}:>({j,k+1}
... und implementiert dann manuell das Übertragen der Eins zur nächsten Ziffer, solange eine der Ziffern existiert Ziffern gleich 10 nach der Regel{a__,b_,10,c___}->{a,b+1,0,c}
... und dann, wenn wir so weit gegangen sind, dass das letzte der führenden2
s zu a geworden ist3
, fängt es am Ende mit einer weiteren Ziffer nach der Regel von vorne an{a,b+1,0,c}/.{a:Repeated[2,#-1],3,b:0..}->{a,2,0,b}
. Das/. 23->2
am Ende behebt nur den Sonderfall, bei dem die Eingabe lautet1
: Die meisten Primzahlen können nicht enden2
, aber2
können. (Einige Fehler sind auf den Eingängen ausgespuckt0
und1
, aber die Funktion findet den Weg zur richtigen Antwort.)Dieser Algorithmus ist ziemlich schnell: Auf meinem Laptop dauert es beispielsweise weniger als 3 Sekunden, um zu berechnen, dass die erste Primzahl, die mit 1.000
2
s beginnt, ist22...220521
.quelle
Pyth, 17 Bytes
Kann nicht
n = 4
online zu lösen scheinen , aber es ist theoretisch korrekt.Erläuterung
quelle
Perl 6 , 53 Bytes
Versuch es
Erweitert:
quelle
Jelly , 14 Bytes
Sehr ineffizient. Probieren Sie es online!
quelle
Pyke, 14 Bytes
Probieren Sie es hier aus!
12 Bytes nach Bugfix und eine neue Funktion
Probieren Sie es hier aus!
quelle
Salbei,
6968 BytesVerwendet einen Generator, um den ersten (daher kleinsten) von unendlich vielen Begriffen zu finden.
quelle
Japt, 20 Bytes
Testen Sie es online! Auf meinem Computer wird es innerhalb von zwei Sekunden für alle Eingaben bis zu 14 Sekunden beendet, und danach verliert es natürlich an Genauigkeit (JavaScript hat nur eine ganzzahlige Genauigkeit von bis zu 2 53 ).
Vielen Dank an @obarakon für die Arbeit daran :-)
Erläuterung
In der neuesten Version von Japt können dies 12 Bytes sein:
Testen Sie es online! Es endet innerhalb einer halben Sekunde auf meinem Computer für alle Eingaben bis zu 14.
quelle
2222203
, nur222223
und bald danach2222210
. Es schlägt auch bei jeder Eingabe fehl, die drei oder mehr zusätzliche Ziffern nach der Zeichenfolge von2
s erfordert , z. B. Eingabe 15.PHP, 76 Bytes
Nimmt Eingaben vom Kommandozeilenargument entgegen. Laufen Sie mit
-r
.Nervenzusammenbruch
quelle
Bash (+ Coreutils), 53 Bytes
Funktioniert bis zu 2 ^ 63-1 (9223372036854775807) , dauert es einige Zeit, bis N> 8 beendet ist.
Golf gespielt
Prüfung
quelle
Python 3, 406 Bytes
Testcode
Testausgang
Ich entschied mich für eine Geschwindigkeit über einen ziemlich großen Bereich anstatt einer Bytegröße. :) Ich verwende einen deterministischen Miller-Rabin-Primalitätstest, der mit diesem Satz von Zeugen bis zu 3317044064679887385961981 garantiert ist. Größere Primzahlen bestehen den Test immer erfolgreich, aber einige Verbundwerkstoffe bestehen möglicherweise auch, obwohl die Wahrscheinlichkeit äußerst gering ist. Ich habe jedoch auch die Ausgangszahlen für i> 22 mit pyecm, einem Programm zur Faktorisierung elliptischer Kurven , getestet und sie scheinen Primzahlen zu sein.
quelle
p()
Anruf einbinden ... OTOH, es wäre schwierig, ein wesentlich kleineres Programm zu schreiben, das in weniger als einer Sekunde eine korrekte Ausgabe für i> 20 liefert (das "schummelt" nicht, wenn man ein eingebautes Programm aufruft Primalitätsprüfer). :)Python 3, 132 Bytes
Jede Hoffnung auf Leistung wurde für eine geringere Anzahl von Bytes geopfert.
quelle
Java, 163 Bytes
Testcode
Ausgabe:
582,5858 Millisekunden
Erläuterung: Schleifen über Ganzzahlen und Hinzufügen dieser als Zeichenfolgen zu der Stammzeichenfolge, bei der es sich um die angegebene Zeichenfolge "2" handelt, und Überprüfen, ob es sich um eine Primzahl handelt oder nicht.
quelle
isProbablePrime
hat gelegentlich Fehlalarme . Dies würde die Antwort ungültig machen, da es Umstände gibt, unter denen der falsche Wert zurückgegeben wird.