Jedes Palindrom mit einer geraden Anzahl von Ziffern ist durch 11 teilbar, daher ist 11 die einzige [palindromische Primzahl] mit einer geraden Anzahl von Ziffern. - David Wasserman, OEIS

Ich habe dies heute auf manuelle Weise gelernt, bevor ich meine Recherchen durchführte, als mein Programm bei der Berechnung palindromischer Primzahlen Zahlen mit einer geraden Anzahl von Ziffern (mit Ausnahme von 11) übersprang. Ihre Aufgabe: Erstellen Sie ein Programm oder eine Funktion, die bei einer Ganzzahleingabe N den N-ten Term in Stephens Palindromic Sequence ™ ausgibt.

Stephen's Palindromic Sequence ™

Stephens Palindromic Sequence ™ beginnt mit 11 und setzt sich mit palindromischen Halbwerten fort, die durch 11 teilbar sind. Grundsätzlich alle Halbwerte, die Primzahlen wären, wenn 11 nicht "gezählt" hätte. Der Vorteil ist, dass diese Liste Zahlen mit einer geraden Anzahl von Ziffern enthält! Yay. Und viele Zahlen mit einer ungeraden Anzahl von Ziffern werden übersprungen, da sie bereits Primzahlen waren.

Der Beginn der Sequenz:

1   : 11
2   : 22
3   : 33
4   : 55
5   : 77
6   : 121
7   : 737
8   : 979
9   : 1111
10  : 1441
11  : 1661
12  : 1991
13  : 3113
14  : 3223
15  : 3443
16  : 3883
17  : 7117
18  : 7447
19  : 7997
20  : 9119
21  : 9229
22  : 9449
23  : 10901

_{^{* Obwohl 1331 (11 ^ 3) und ähnliches zum Geist dieser Sequenz passen, entsprechen sie nicht den Regeln.}}

Längere Testfälle:

26  : 91619
31  : 103301
41  : 139931
51  : 173371
61  : 305503
71  : 355553
81  : 395593
91  : 725527
101 : 772277
127 : 997799
128 : 1099901
141 : 3190913
151 : 3739373
161 : 7589857
171 : 9460649
200 : 11744711
528 : 39988993

Eingang

Ganzzahl N,> = 1. Sie können ein mit 0 indiziertes N verwenden (stellen Sie sicher, dass Sie die Testfälle anpassen), wenn Sie dies in Ihrer Antwort angeben. Zeilenumbrüche sind erlaubt.

Ausgabe

Der n-te Term in Stephens Palindromic Sequence ™. Zeilenumbrüche sind erlaubt.

Regeln

• Die einzige Eingabe, die Ihr Programm / Ihre Funktion annehmen kann, ist N. Ihr Programm kann beispielsweise keine Sequenz aus OEIS abrufen (auch bekannt als Standardlücken ).
• Sie müssen in der Lage sein, eine Ausgabe mit bis zu sechs Stellen zu drucken (N = 127). Die Zeit spielt keine Rolle. Wenn Ihr Programm / Ihre Funktion jedoch sehr lang und sehr schnell wird, müssen Sie nachweisen, dass der Algorithmus funktioniert. Wenn Ihre Sprache von Natur aus längere Ausgaben zulässt, können Sie sie auf natürliche Weise bis an ihre Grenzen erweitern oder auf zehn Stellen begrenzen, je nachdem, was Sie bevorzugen. Die Ausgabe / Beendigung über Ihr Limit hinaus spielt keine Rolle, solange es sich nicht um eine gültige Ausgabe zu handeln scheint.
• Programm- / Funktionsfunktion bei ungültiger Eingabe ist irrelevant.

Jelly , 18 13 Bytes

ṬÆẸש11ŒḂµ#ṛ®

Aus irgendeinem Grund ist dies viel langsamer als meine anfängliche Überarbeitung, obwohl ich genau dasselbe tue.

Probieren Sie es online!

N = 127

dennis-home:~$ time jelly eun 'ṬÆẸש11ŒḂµ#ṛ®' <<< 127
997799

real    1m43.745s
user    1m43.676s
sys     0m0.113s

Wie es funktioniert

ṬÆẸש11ŒḂµ#ṛ®  Main link. No arguments.

         µ     Combine all links to the left into a chain.
          #    Read an integer n from STDIN and call the chain monadically, with
               argument k = 0, 1, 2, ... until n values of k result in a truthy
               output. Return the array of all matching values of k.
Ṭ                Untruth; yield [0, 0, 0, ..., 1] (k-1 zeroes followed by a 1) or
                 [] if k = 0.
 ÆẸ              Unexponents; consider the resulting array as exponents of the
                 sequence of primes and yield the corresponding integer. For k = 0,
                 this yields 1. For k > 0, it yields the k-th prime.
   ש11          Multiply the result by 11 and copy the product to the register.
       ŒḂ        Test if the product is a palindrome.
           ṛ®  Replace the resulting array with the integer in the register.

Python 2 , 76 73 72 70 69 68 Bytes

n=input();c=k=m=11
while n:m*=k/c;k+=c;n-=`k`==`k`[::~m%k-c]
print k

Vielen Dank an @WheatWizard für das Golfen mit 3 Bytes!

Vielen Dank an @ ØrjanJohansen für das Golfen ab 1 Byte!

Vielen Dank an @xnor und @ ØrjanJohansen, die den Weg zu 68 Bytes geebnet haben!

Eingang ist 0-indiziert. Probieren Sie es online! oder überprüfen Sie die ersten 31 Testfälle .

Hintergrund

Denken Sie daran, dass Wilsons Satz besagt, dass für alle ganzen Zahlen p> 1 ,

was bedeutet, dass (p - 1)! + 1 ist genau dann durch p teilbar, wenn p Primzahl ist.

Wenn p> 1 ist nicht Primzahl ist , ist es Verbund; Sei q der kleinste Primteiler von p . Offensichtlich ist q ≤ p / q . Es gibt zwei Fälle:

• Wenn q = p / q ist, ist p = q² .

  Wenn q = 2 , (p - 1)! = 3! = 6 , also (p - 1)! ist kongruent zu 2 modulo p .

  Wenn p / q = q> 2 , so ist 2q <p . Auf diese Weise gehören q und 2q beide zu 1,…, p - 1 , dessen Produkt die Fakultät von p - 1 ist , also 2p = 2q² = q · 2q dividiert (p - 1)! gleichmäßig.

• Wenn q <p / q , q und p / q sind beide unter 1, ..., p - 1 , so ist p = q · p / q dividiert (p - 1)! gleichmäßig.

Zusammenfassen,

für alle ganzen Zahlen p> 1 .

Nun, für alle ganzzahligen Kongruenzen und alle ganzen Zahlen a , b und c Folgendes.

Wenn a = -1 , b = 11 und c = -1 , folgen wir dem

und da 21 und -23 kongruentes Modulo 44 und -1 und 11p-1 kongruentes Modulo 11p sind , kommen wir zu der folgenden Schlussfolgerung.

Für alle möglichen Werte von p fällt das Ergebnis ( 11 , 21 oder 11p - 1 ) in den Bereich 0,…, 11p - 1 , sodass diese Werte mit denen übereinstimmen, die vom Python- %Operator zurückgegeben werden.

Wie es funktioniert

Wir initialisieren c , k und m auf 11, nachdem wir die Eingabe in n gespeichert haben . c bleibt für den Rest des Programms konstant. Da es in der folgenden Zeile drei Vorkommen von c gibt und die Zuweisung von c nur zwei Byte kostet, wird ein Byte gespart. k kann unter Verwendung der Bedeutung von p aus dem vorhergehenden Absatz von 11p gedacht werden ; anfangs ist k = 11 = 11 · 1! . m tritt an die Stelle von 11 · (p - 1)! ; anfangs ist m = 11 = 11 · 0! . k und merfüllt die Beziehung m = 11 · (k / 11)! jederzeit.

n steht für die Anzahl der zu findenden „Stephen-Palindrome“. Da anfänglich k = 11 ist , können wir k ohne weitere Berechnung wörtlich ausgeben . Wenn jedoch n positiv ist, treten wir in die while-Schleife ein. Die Schleife beginnt mit der Multiplikation von m mit k / c = p und addiert dann 11 zu k , wodurch p inkrementiert wird . Wenn k ein Mitglied der Sequenz ist, subtrahieren wir 1 von n und fangen von vorne an. Sobald n 0 erreicht , haben wir das Sequenzelement am gewünschten Index gefunden und brechen aus der Schleife aus und geben dann den letzten Wert von k aus.

Der Ausdruck

`k`==`k`[::~m%k-c]

Führt den eigentlichen Test durch und das Ergebnis ( True / 1 für Sequenzmitglieder, andernfalls 0 / False ) wird von n abgezogen . Wie zuvor gesehen, ist ~ m% k = (-m - 1)% k = (-11 · (p - 1)! - 1)% 11p gleich 10, wenn p eine Primzahl ist, 21, wenn p = 4 und 11p - 1 > 43 wenn p> 4 zusammengesetzt ist. Nach dem Subtrahieren von c = 11 bleibt also -1 für Primzahl p und eine positive ganze Zahl größer als 9 übrig .

Für prime p , ​`k`[::-1]gibt uns die Stringdarstellung k mit umgekehrter Reihenfolge Ziffer, so ist es zu vergleichen ​`k`​prüft , ob k ein Palindrom ist. Wenn dies der Fall ist, sind alle Bedingungen erfüllt und k ist ein Sequenzmitglied. Wenn jedoch p keine Primzahl ist, bedeuten der große Bereichsschritt und die Tatsache, dass k immer mehr als eine Ziffer hat, dass ​`k`[::-1]es nicht die gleiche Anzahl von Ziffern wie haben kann ​`k`​, geschweige denn gleich sein kann.

Brachylog , 17 Bytes

:I{11|ṗ×₁₁≜.↔}ᶠ⁽t

Probieren Sie es online!

Dies ist 1-indiziert.

Erläuterung

:I{          }ᶠ⁽t    Find the Input'th result of the following:
   11                  Output = 11
     |                 Or
          ≜.           Output is an integer…
      ṗ×₁₁             …which is the result of multiplying a prime by 11…
           .↔          …and Output reversed is still the Output

Zwei Erkenntnisse mit dieser Antwort:

• Ich muss die Tatsache beheben, dass die hochgestellte Übergabe an Metapredicates (mit ⁽) nicht funktioniert, wenn keine Eingabe übergeben werden muss (weshalb ich hinzufügen muss :I).
• Ich muss ein Metapredikat hinzufügen, um das NErgebnis eines Prädikats zu erhalten (was die Verwendung von ᶠ⁽tund anstelle von zB vermeiden würde ⁿ⁽).

Durch die Implementierung beider Änderungen würde diese Antwort 14 Bytes lang sein.

Mathematica, 65-60 Bytes

n=NextPrime;11Nest[n@#//.x_/;!PalindromeQ[11x]:>n@x&,1,#-1]&

Iteriert direkt durch Primzahlen mit NextPrimeund prüft, ob das 11-fache der Primzahl ein Palindrom ist. Funktioniert bis zu N = 528 . Die Ergebnisse 528 und 529 sind mehr als 2 ¹⁶ Primzahlen voneinander entfernt, und an diesem Punkt //.kann keine ausreichende Anzahl von Substitutionen versucht werden.

Python 2 , 111 107 103 102 101 100 91 90 89 Bytes

Dennis hat mich hier geschlagen , also schau dir seine Antwort an.

Diese Antwort ist mit Null indiziert

n=input()
r=1
while n:r+=1;c=`r*11`;n-=all(r%x for x in range(2,r))*c==c[::-1]
print r*11

Probieren Sie es online!

Ein Byte gespart dank Mathe-Junkie

Erläuterung

Zuerst nehmen wir die Eingabe und setzen sie, num auch eine neue Variable zu erstellen r=1. Wir werden rnach Palindromen suchen, die das Produkt einer Primzahl und 11 sind. Jedes Mal, wenn wir eine finden, werden wir sie dekrementieren, nbis sie 0 erreicht.

Also starten wir eine Schleife:

while n:

Das erste, was wir tun, ist das Inkrementieren r

r+=1

Wir definieren auch eine Variable cals die Zeichenfolgendarstellung vonr*11

c=`r*11`

Jetzt wollen wir dekrementieren, nob wir eine solche Zahl gefunden haben. Wir werden einfach einen Booleschen Wert subtrahieren, der darstellt, ob r*11das Muster von passt r. Wenn dies der FalseFall ist, subtrahieren wir Null und wenn dies der Fall ist True, subtrahieren wir 1.

Um den Booleschen Wert zu berechnen, gehen Sie wie folgt vor:

all(r%x for x in range(2,r))*c==c[::-1]

Der erste Teil allbestimmt, ob res sich um eine Primzahl handelt. Wir multiplizieren das Ergebnis mit cif ris prime, dies wird nur sein, caber wenn res zusammengesetzt ist, wird es ""der leere String sein. Wir vergleichen dies dann mit c[::-1]dem Gegenteil von c. Wenn rprime und cein Palindrom ist, ist dies True, wenn eines der beiden fehlschlägt, wird das Ganze als falsch gewertet.

Wann nist Null wir einfach print c.

83 Bytes

Hier ist eine rekursive Lösung, die kürzer ist, aber leider nicht den Spezifikationen entspricht, da sie die Rekursionsgrenze von Python zu schnell erreicht.

f=lambda n,r=1:n and f(n-all(r%x*(`r*11`==`r*11`[::-1])for x in range(2,r)),r+1)+11

Probieren Sie es online!

05AB1E , 15 Bytes

0-indiziert.

11Iµ11N*DÂQNp*½

Probieren Sie es online!

Erläuterung

11               # initialize stack with 11
  Iµ             # loop over N in [1 ... inf] until counter equals input
    11N*         # multiply N by 11
        D        # duplicate
         ÂQ      # check if the copy equals its reverse
           Np    # check if N is prime
             *   # multiply the results of the checks together
              ½  # if 1, increase counter

Haskell , 94-90 Bytes

h#n|n<2=0|mod n h<1=1+h#div n h|j<-h+1=j#n
([n|n<-[0,11..],(==)=<<reverse$show n,3>2#n]!!)

Probieren Sie es online! Beispiel Nutzung: ([n|n<-[0,11..],(==)=<<reverse$show n,3>2#n]!!) 127.

[0,11..]erstellt die unendliche Liste [0,11,22,33, ...](die Null wird benötigt, um die Sequenz 1-indiziert zu machen). Für jeden nin dieser Liste wird geprüft n==(read.reverse.show)n, ob nes sich um ein Palindrom handelt. 3>2#nPrüft, ob nhöchstens zwei Primteiler vorhanden sind. Da nes immer durch 11 teilbar ist, erhalten wir keine echten Primzahlen, sondern nur Halbzahlen.

Edit: Danke an Ørjan Johansen für das Golfen mit 4 Bytes!

PHP, 82 Bytes

for(;$d<$argn;$i>1||($p=11*$n)!=strrev($p)?:$d++)for($i=++$n;--$i&&$n%$i;);echo$p;

Probieren Sie es online!

Axiom, 105 Bytes

g(n)==(i:=c:=1;repeat(c=n=>break;i:=i+1;if(prime? i)then(x:=(11*i)::String;x=reverse(x)=>(c:=c+1)));i*11)

ungolf, testcode und ergebnisse

f(n)==
   i:=c:=1
   repeat
      c=n=>break
      i:=i+1
      if(prime? i)then(x:=(11*i)::String;x=reverse(x)=>(c:=c+1))
   i*11


(5) -> [[i,g(i)]  for i in 1..23]
   (5)
   [[1,11], [2,22], [3,33], [4,55], [5,77], [6,121], [7,737], [8,979],
    [9,1111], [10,1441], [11,1661], [12,1991], [13,3113], [14,3223], [15,3443],
    [16,3883], [17,7117], [18,7447], [19,7997], [20,9119], [21,9229],
    [22,9449], [23,10901]]
                                          Type: List List PositiveInteger
(6) -> [[i,g(i)]  for i in [26,31,41,101,151,200]]
   (6)
   [[26,91619], [31,103301], [41,139931], [101,772277], [151,3739373],
    [200,11744711]]

Hier ist g (700) = 92511529, die Grenze wäre also> 700; ww (1000) = 703999307 aber mit nextPrime ()