Cada palíndromo con un número par de dígitos es divisible por 11, por lo que 11 es el único [primo palindrómico] con un número par de dígitos. - David Wasserman, OEIS

Aprendí esto hoy de forma manual, antes de hacer mi investigación, cuando mi programa omitió números con un número par de dígitos (excepto 11) al calcular números primos palindrómicos. Su tarea: crear un programa o función que, cuando se le da una entrada entera N, genera el enésimo término en Stephen's Palindromic Sequence ™.

Secuencia Palindrómica de Stephen ™

Stephen's Palindromic Sequence ™ comienza con 11, y continúa con semiprimes palindrómicos divisibles por 11. Básicamente, todas las semiprimes que serían primos si 11 no "contaran". ¡Lo bueno es que esta lista contiene números con un número par de dígitos! Hurra. Y se omiten muchos números con un número impar de dígitos, ya que ya eran primos.

El comienzo de la secuencia:

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

_{^{* Aunque 1331 (11 ^ 3) y similares se ajustan al espíritu de esta secuencia, no se ajustan a las reglas.}}

Casos de prueba más largos:

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

Entrada

Entero N,> = 1. Puede usar un N indexado a 0 (asegúrese de ajustar los casos de prueba) si así lo especifica en su respuesta. Nuevas líneas finales permitidas.

Salida

El enésimo término en Stephen's Palindromic Sequence ™. Nuevas líneas finales permitidas.

Reglas

• La única entrada que su programa / función puede tomar es N. Su programa no puede, por ejemplo, obtener una secuencia de OEIS (también conocido como lagunas estándar ).
• Debe poder imprimir una salida de hasta seis dígitos (N = 127). El tiempo no es un factor, sin embargo, si su programa / función se alarga mucho, debe probar que el algoritmo funciona. Si su idioma permite naturalmente salidas más largas, puede dejar que se expanda naturalmente hasta su límite, o limitarlo a diez dígitos, lo que prefiera. La salida / terminación más allá de su límite no importa, siempre que no parezca una salida válida.
• La función de programa / función en una entrada no válida es irrelevante.

Jalea , 18 13 bytes

ṬÆẸש11ŒḂµ#ṛ®

Por alguna razón, esto es mucho más lento que mi revisión inicial, a pesar de hacer exactamente lo mismo.

Pruébalo en línea!

N = 127

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

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

Cómo funciona

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

¡Gracias a @WheatWizard por jugar golf en 3 bytes!

¡Gracias a @ ØrjanJohansen por jugar golf en 1 byte!

¡Gracias a @xnor y @ ØrjanJohansen por allanar el camino a 68 bytes!

La entrada está indexada en 0. Pruébalo en línea! o verificar los primeros 31 casos de prueba .

Antecedentes

Recordemos que el teorema de Wilson establece que para todos los enteros p> 1 ,

lo que significa que (p - 1)! + 1 es divisible por p si y solo si p es primo.

Si p> 1 no es primo, es compuesto; sea q el divisor primo más pequeño de p . Claramente, q ≤ p / q . Hay dos casos:

• Si q = p / q , tenemos que p = q² .

  Si q = 2 , (p - 1)! = 3! = 6 , entonces (p - 1)! es congruente con 2 módulo p .

  Si p / q = q> 2 , entonces 2q <p . De esta manera, q y 2q están entre 1, ..., p - 1 , cuyo producto es el factorial de p - 1 , entonces 2p = 2q² = q · 2q divide (p - 1). igualmente.

• Si q <p / q , q y p / q están ambos entre 1, ..., p - 1 , entonces p = q · p / q se divide (p - 1). igualmente.

Resumiendo,

para todos los enteros p> 1 .

Ahora, para todas las congruencias enteros y todos los números enteros a , b , y c , se cumple lo siguiente.

Cuando a = -1 , b = 11 y c = -1 , seguimos que

y, dado que 21 y -23 son congruentes módulo 44 y -1 y 11p-1 son congruentes módulo 11p , llegamos a la siguiente conclusión.

Para todos los valores posibles de p , el resultado ( 11 , 21 o 11p - 1 ) estará en el rango 0, ..., 11p - 1 , por lo que estos valores coinciden con los que devolverá el %operador de Python .

Cómo funciona

Inicializamos c , k y m a 11 después de guardar la entrada en n . c será constante durante el resto del programa. Como hay tres ocurrencias de c en la siguiente línea y la asignación de c cuesta solo dos bytes, esto ahorra un byte. k puede pensarse en 11p usando el significado de p del párrafo anterior; inicialmente, k = 11 = 11 · 1! . m toma el lugar de 11 · (p - 1)! ; inicialmente, m = 11 = 11 · 0! . k y msatisfará la relación m = 11 · (k / 11)! en todo momento.

n representa el número de "palíndromos de Stephen" que tenemos que encontrar. Como k = 11 inicialmente, podemos generar k textualmente sin más cálculos. Sin embargo, cuando n es positivo, ingresamos al ciclo while. El ciclo comienza multiplicando m por k / c = p , luego sumando 11 a k , incrementando así p . Si k es un miembro de la secuencia, restamos 1 de n y comenzamos de nuevo. Una vez que n alcanza 0 , encontramos el miembro de secuencia en el índice deseado y salimos del bucle, luego imprimimos el último valor de k.

La expresion

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

realiza la prueba real, y su resultado ( Verdadero / 1 para miembros de secuencia, 0 / Falso de lo contrario) se resta de n . Como se vio antes, ~ m% k = (-m - 1)% k = (-11 · (p - 1)! - 1)% 11p es igual a 10 si p es primo, 21 si p = 4 y 11p - 1 > 43 si p> 4 es compuesto. Por lo tanto, después de restar c = 11 , nos queda -1 con primo p y un entero positivo mayor que 9 de lo contrario.

Para prime p , ​`k`[::-1]nos da la representación de cadena de k con orden inverso de dígitos, por lo que la compara con ​`k`​cheques si k es un palíndromo. Si es así, se cumplen todas las condiciones yk es un miembro de secuencia. Sin embargo, si p no es primo, el paso de rango grande y el hecho de que k siempre tendrá más de un dígito significa que ​`k`[::-1]no puede tener el mismo número de dígitos que ​`k`​, y mucho menos ser igual a él.

Brachylog , 17 bytes

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

Pruébalo en línea!

Esto es 1 indexado.

Explicación

: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

Dos realizaciones con esta respuesta:

• Necesito corregir el hecho de que el superíndice que pasa a metapredicados (con ⁽) no funciona si no hay entrada para pasar (por eso tengo que agregar :I).
• Necesito agregar un metapredicado para obtener el Nresultado de un predicado (lo que evitaría usar ᶠ⁽ty, por el contrario, por ejemplo ⁿ⁽).

Implementar ambos cambios haría que la respuesta sea de 14 bytes.

Mathematica, 65 60 bytes

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

Itera directamente a través de primos usando NextPrimey comprueba si 11 veces el primo es un palíndromo Funciona hasta N = 528 . Los resultados 528 y 529 están separados por más de 2 ¹⁶ primos, en cuyo punto //.no se podrá intentar un número suficiente de sustituciones.

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

Dennis me ha golpeado aquí , así que ve a ver su respuesta.

Esta respuesta es cero indexada

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

Pruébalo en línea!

Un byte guardado gracias al adicto a las matemáticas

Explicación

Primero tomamos datos y lo configuramos para nque también hagamos una nueva variable r=1. Seguiremos rbuscando palíndromos que sean producto de un primo y 11. Cada vez que encontremos uno disminuiremos nhasta llegar a 0.

Entonces comenzamos un ciclo:

while n:

Lo primero que hacemos es incrementar r

r+=1

También predefinimos una variable ccomo la representación de cadena der*11

c=`r*11`

Ahora queremos disminuir nsi hemos encontrado ese número. Simplemente restaremos un booleano que representa si se r*11ajusta al patrón r. Si esto es Falseasí, restaremos cero y si es Trueasí, restaremos 1.

Para calcular el booleano hacemos:

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

La primera parte alldeterminará si res primo. Multiplicamos el resultado por csi res primo, esto solo será, cpero si res compuesto, será ""la cadena vacía. Luego comparamos esto con lo c[::-1]que es lo contrario de c. Si res primo y ces un palíndromo, esto será True, si alguno falla, todo se evaluará como falso.

Cuando nes cero, simplemente print c.

83 bytes

Aquí hay una solución recursiva que es más corta pero desafortunadamente no cumple con las especificaciones porque alcanza el límite de recursión de Python demasiado rápido.

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

Pruébalo en línea!

05AB1E , 15 bytes

0 indexado.

11Iµ11N*DÂQNp*½

Pruébalo en línea!

Explicación

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

Pruébalo en línea! Ejemplo de uso: ([n|n<-[0,11..],(==)=<<reverse$show n,3>2#n]!!) 127.

[0,11..]construye la lista infinita [0,11,22,33, ...](el cero es necesario para hacer que la secuencia esté indexada en 1). Para cada uno nen esta lista, verificamos n==(read.reverse.show)nsi nes un palíndromo. 3>2#ncomprueba si ntiene como máximo dos divisores primos. Debido a nque siempre es divisible por 11, no obtenemos primos reales sino solo semiprimes.

Editar: ¡ Gracias a Ørjan Johansen por jugar al golf 4 bytes!

PHP, 82 bytes

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

Pruébalo en línea!

Axioma, 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, código de prueba y resultados

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

Aquí g (700) = 92511529, entonces el límite sería> 700; ww (1000) = 703999307 pero usando nextPrime ()