Chaque palindrome avec un nombre pair de chiffres est divisible par 11, donc 11 est le seul [nombre premier palindromique] avec un nombre pair de chiffres. - David Wasserman, OEIS

J'ai appris cela aujourd'hui de manière manuelle, avant de faire mes recherches, lorsque mon programme a sauté des nombres avec un nombre pair de chiffres (sauf 11) lors du calcul des nombres premiers palindromiques. Votre tâche: créer un programme ou une fonction qui, lorsqu'elle reçoit une entrée entière N, génère le Nème terme dans Stephen's Palindromic Sequence ™.

Séquence palindromique de Stephen ™

La séquence palindromique ™ de Stephen commence par 11 et se poursuit avec des demi-amides palindromiques divisibles par 11. Fondamentalement, tous les semi-amorces qui seraient des nombres premiers si 11 ne «comptaient» pas. L'avantage est que cette liste contient des nombres avec un nombre pair de chiffres! Yay. Et, de nombreux nombres avec un nombre impair de chiffres sont ignorés, car ils étaient déjà premiers.

Le début de la séquence:

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

_{^{* Bien que 1331 (11 ^ 3) et similaires correspondent à l'esprit de cette séquence, ils ne correspondent pas aux règles.}}

Cas de test plus longs:

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

Contribution

Entier N,> = 1. Vous pouvez utiliser un N indexé 0 (assurez-vous d'ajuster les cas de test) si vous le spécifiez dans votre réponse. Les nouvelles lignes de fin sont autorisées.

Production

Le Nième terme dans Stephen's Palindromic Sequence ™. Les nouvelles lignes de fin sont autorisées.

Règles

• La seule entrée que votre programme / fonction peut prendre est N. Votre programme ne peut pas, par exemple, récupérer une séquence à partir d'OEIS (alias les échappatoires standard s'appliquent ).
• Vous devez être capable d'imprimer une sortie jusqu'à six chiffres (N = 127). Le temps n'est pas un facteur - cependant, si votre programme / fonction devient très long et très rapide, vous devez prouver que l'algorithme fonctionne. Si votre langue autorise naturellement des sorties plus longues, vous pouvez la laisser s'étendre naturellement jusqu'à sa limite ou la limiter à dix chiffres, selon votre préférence. La sortie / terminaison au-delà de votre limite n'a pas d'importance, tant qu'elle ne semble pas être une sortie valide.
• La fonction de programme / fonction sur une entrée invalide n'est pas pertinente.

Gelée , 18 13 octets

ṬÆẸש11ŒḂµ#ṛ®

Pour une raison quelconque, cela est beaucoup plus lent que ma révision initiale, bien qu'il fasse exactement la même chose.

Essayez-le en ligne!

N = 127

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

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

Comment ça fonctionne

ṬÆẸש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 octets

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

Merci à @WheatWizard pour avoir joué au golf sur 3 octets!

Merci à @ ØrjanJohansen d'avoir joué au golf sur 1 octet!

Merci à @xnor et @ ØrjanJohansen pour avoir ouvert la voie à 68 octets!

L'entrée est indexée 0. Essayez-le en ligne! ou vérifier les 31 premiers cas de test .

Contexte

Rappelons que le théorème de Wilson déclare que pour tous les entiers p> 1 ,

ce qui signifie que (p - 1)! + 1 est divisible par p si et seulement si p est premier.

Si p> 1 n'est pas premier, il est composite; soit q le plus petit diviseur premier de p . Clairement, q ≤ p / q . Il y a deux cas:

• Si q = p / q , on a que p = q² .

  Si q = 2 , (p - 1)! = 3! = 6 , donc (p - 1)! est congru à 2 modulo p .

  Si p / q = q> 2 , alors 2q <p . De cette façon, q et 2q sont tous les deux parmi 1,…, p - 1 , dont le produit est la factorielle de p - 1 , donc 2p = 2q² = q · 2q se divise (p - 1)! uniformément.

• Si q <p / q , q et p / q sont tous les deux parmi 1,…, p - 1 , alors p = q · p / q divise (p - 1)! uniformément.

En résumé,

pour tous les entiers p> 1 .

Maintenant, pour toutes les congruences entières et tous les entiers a , b et c , ce qui suit est vrai.

Lorsque a = -1 , b = 11 et c = -1 , nous suivons cela

et, comme 21 et -23 sont modulo congrus 44 et -1 et 11p-1 sont modulo congru 11p , nous arrivons à la conclusion suivante.

Pour toutes les valeurs possibles de p , le résultat ( 11 , 21 ou 11p - 1 ) tombera dans la plage 0,…, 11p - 1 , donc ces valeurs correspondent à celles qui seront retournées par Python.% opérateur .

Comment ça fonctionne

Nous initialisons c , k et m à 11 après l'enregistrement de l'entrée dans n . c sera constant pour le reste du programme. Puisqu'il y a trois occurrences de c sur la ligne suivante et que l'affectation de c ne coûte que deux octets, cela économise un octet. k peut être considéré comme 11p en utilisant la signification de p du paragraphe précédent; initialement, k = 11 = 11 · 1! . m remplace 11 · (p - 1)! ; initialement, m = 11 = 11 · 0! . k et msatisfera la relation m = 11 · (k / 11)!de tout temps.

n représente le nombre de «palindromes de Stephen» que nous devons trouver. Puisque k = 11 initialement, nous pouvons produire k textuellement sans autre calcul. Cependant, lorsque n est positif, nous entrons dans la boucle while. La boucle commence en multipliant m par k / c = p , puis en ajoutant 11 à k , incrémentant ainsi p . Si k est membre de la séquence, on soustrait 1 de n et on recommence. Une fois que n atteint 0 , nous avons trouvé le membre de séquence à l'index souhaité et sortir de la boucle, puis imprimer la dernière valeur de k.

L'expression

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

effectue le test réel et son résultat ( Vrai / 1 pour les membres de séquence, 0 / Faux sinon) est soustrait de n . Comme vu précédemment, ~ m% k = (-m - 1)% k = (-11 · (p - 1)! - 1)% 11p est égal à 10 si p est premier, 21 si p = 4 et 11p - 1 > 43 si p> 4 est composite. Ainsi, après soustraction de c = 11 , nous nous retrouvons avec -1 pour p premier et un entier positif supérieur à 9 sinon.

Pour le premier p , ​`k`[::-1]nous donne la représentation sous forme de chaîne de k avec l'ordre des chiffres inversé, afin de le comparer pour ​`k`​vérifier si k est un palindrome. Si tel est le cas, toutes les conditions sont remplies et k est un membre de séquence. Cependant, si p n'est pas premier, le pas de grande plage et le fait que k aura toujours plus d'un chiffre signifient qu'il ​`k`[::-1]ne peut pas avoir le même nombre de chiffres que ​`k`​, sans parler d'être égal à lui.

Brachylog , 17 octets

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

Essayez-le en ligne!

Ceci est indexé 1.

Explication

: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

Deux réalisations avec cette réponse:

• Je dois corriger le fait que le passage en exposant aux métaprédicates (avec ⁽) ne fonctionne pas s'il n'y a pas d'entrée à passer (c'est pourquoi je dois ajouter :I).
• J'ai besoin d'ajouter un métaprédicat pour obtenir le Nrésultat d'un prédicat (ce qui éviterait d'utiliser ᶠ⁽tet à la place, par exemple ⁿ⁽).

L'implémentation des deux modifications rendrait cette réponse 14 octets.

Mathematica, 65 60 octets

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

Itère directement à travers les nombres premiers en utilisant NextPrimeet vérifie si 11 fois le nombre premier est un palindrome. Fonctionne jusqu'à N = 528 . Les résultats 528 et 529 sont distants de plus de 2 ¹⁶ nombres premiers, auquel cas //.ils ne parviendront pas à tenter un nombre suffisant de substitutions.

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

Dennis m'a battu ici , alors allez voir sa réponse.

Cette réponse est indexée zéro

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

Essayez-le en ligne!

Un octet sauvé grâce au drogué des mathématiques

Explication

Nous prenons d'abord la saisie et la configurons pour ncréer également une nouvelle variable r=1. Nous comptons jusqu'à rrechercher des palindromes qui sont le produit d'un nombre premier et de 11. Chaque fois que nous en trouvons un, nous décrémenterons njusqu'à ce qu'il atteigne 0.

Nous commençons donc une boucle:

while n:

La première chose que nous faisons est d'augmenter r

r+=1

Nous prédéfinissons également une variable ccomme représentation sous forme de chaîne der*11

c=`r*11`

Maintenant, nous voulons décrémenter nsi nous avons trouvé un tel nombre. Nous soustraireons simplement un booléen représentant si r*11correspond au modèle r. Si c'est le cas, Falsenous soustraireons zéro et si c'est le cas, Truenous soustraireons 1.

Pour calculer le booléen, nous faisons:

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

La première partie alldéterminera si rest premier. Nous multiplions le résultat par csi rest premier ce sera juste cmais si rc'est composite ce sera "", la chaîne vide. Nous comparons ensuite ce c[::-1]qui est l'inverse de c. Si rest premier et cest un palindrome, ce sera le cas True, si l'un ou l'autre échoue, le tout sera évalué comme faux.

Quand nest zéro, nous simplement print c.

83 octets

Voici une solution récursive qui est plus courte mais qui ne répond malheureusement pas aux spécifications car elle atteint le plafond de récursivité de python trop rapidement.

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

Essayez-le en ligne!

05AB1E , 15 octets

0 indexé.

11Iµ11N*DÂQNp*½

Essayez-le en ligne!

Explication

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 octets

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]!!)

Essayez-le en ligne! Exemple d' utilisation: ([n|n<-[0,11..],(==)=<<reverse$show n,3>2#n]!!) 127.

[0,11..]construit la liste infinie [0,11,22,33, ...](le zéro est nécessaire pour rendre la séquence indexée 1). Pour chacun ndans cette liste, nous vérifions n==(read.reverse.show)ns'il ns'agit d'un palindrome. 3>2#nvérifie s'il na au plus deux diviseurs premiers. Parce que nest toujours divisible par 11, nous n'obtenons pas de nombres premiers réels mais uniquement des demi-nombres premiers.

Edit: Merci à Ørjan Johansen pour avoir joué au golf 4 octets!

PHP, 82 octets

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

Essayez-le en ligne!

Axiome, 105 octets

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, code de test et résultats

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

Ici g (700) = 92511529 donc la limite serait> 700; ww (1000) = 703999307 mais en utilisant nextPrime ()