Todo palíndromo com um número par de dígitos é divisível por 11, então 11 é o único [primo palíndrico] com um número par de dígitos. - David Wasserman, OEIS

Aprendi isso hoje da maneira manual, antes de fazer minha pesquisa, quando meu programa pulava números com um número par de dígitos (exceto 11) ao calcular números primos palindrômicos. Sua tarefa: criar um programa ou função que, quando recebida uma entrada inteira N, gera o enésimo termo na Palindromic Sequence ™ de Stephen.

Sequência Palíndrica de Stephen ™

A Palindromic Sequence ™ de Stephen começa com 11 e continua com semiprimes palindrômicos divisíveis por 11. Basicamente, todos os semiprimes que seriam primos se 11 não "contar". A vantagem é que esta lista contém números com um número par de dígitos! Yay. E muitos números com um número ímpar de dígitos são ignorados, pois já eram primos.

O início da sequência:

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

_{^{* Embora 1331 (11 ^ 3) e similares se encaixem no espírito dessa sequência, eles não se encaixam nas regras.}}

Casos de teste mais longos:

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

Inteiro N,> = 1. Você pode usar um N indexado a 0 (certifique-se de ajustar casos de teste) se você especificar isso em sua resposta. Novas linhas à direita permitidas.

Resultado

O enésimo termo da Palindromic Sequence ™ de Stephen. Novas linhas à direita permitidas.

Regras

• A única entrada que seu programa / função pode receber é N. Seu programa não pode, por exemplo, buscar uma sequência no OEIS (também conhecidas como brechas padrão ).
• Você deve poder imprimir uma saída com até seis dígitos (N = 127). O tempo não é um fator - no entanto, se seu programa / função ficar muito longo e muito rápido, você deverá provar que o algoritmo funciona. Se o seu idioma permitir naturalmente saídas mais longas, você pode permitir que ele se expanda naturalmente até o limite ou limite-o com dez dígitos, o que você preferir. A saída / término além do seu limite não importa, desde que não pareça uma saída válida.
• A função de programa / função em entrada inválida é irrelevante.

Geléia , 18 13 bytes

ṬÆẸש11ŒḂµ#ṛ®

Por alguma razão, isso é muito mais lento que minha revisão inicial, apesar de fazer exatamente o mesmo.

Experimente online!

N = 127

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

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

Como 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

Graças a @WheatWizard por jogar fora 3 bytes!

Obrigado a @ ØrjanJohansen por jogar fora um byte!

Obrigado a @xnor e a ØrjanJohansen por abrir caminho para 68 bytes!

A entrada é indexada em 0. Experimente online! ou verifique os 31 primeiros casos de teste .

fundo

Lembre-se de que o teorema de Wilson afirma que para todos os números inteiros p> 1 ,

significando que (p - 1)! + 1 é divisível igualmente por p se e somente se p for primo.

Se p> 1 não é primo, é composto; Seja q o menor divisor principal de p . Claramente, q ≤ p / q . Existem dois casos:

• Se q = p / q , temos que p = q² .

  Se q = 2 , (p - 1)! = 3! = 6 , então (p - 1)! é congruente com 2 módulos p .

  Se p / q = q> 2 , então 2q <p . Dessa forma, q e 2q estão entre 1,…, p - 1 , cujo produto é o fatorial de p - 1 , então 2p = 2q² = q · 2q divide (p - 1)! uniformemente.

• Se q <p / q , q e p / q estão entre 1,…, p - 1 , então p = q · p / q divide (p - 1)! uniformemente.

Resumindo,

para todos os números inteiros p> 1 .

Agora, para todas as congruências inteiros e todos os inteiros de , b e c , o seguinte detém.

Quando a = -1 , b = 11 e c = -1 , seguimos que

e, como 21 e -23 são módulos congruentes 44 e -1 e 11p-1 são módulos congruentes 11p , chegamos à seguinte conclusão.

Para todos os valores possíveis de p , o resultado ( 11 , 21 ou 11p - 1 ) cairá no intervalo 0,…, 11p - 1 , portanto, esses valores correspondem aos que serão retornados pelo %operador do Python .

Como funciona

Nós inicializar c , k e m a 11 após a poupar a entrada no n . c será constante pelo restante do programa. Como há três ocorrências de c na linha a seguir e a atribuição de c custa apenas dois bytes, isso salva um byte. k pode ser pensado em 11p usando o significado de p do parágrafo anterior; inicialmente, k = 11 = 11,1! . m substitui 11 · (p - 1)! ; inicialmente, m = 11 = 11,0! . k e msatisfará a relação m = 11 · (k / 11)! em todos os momentos.

n representa o número de "palíndromos de Estevão" que precisamos encontrar. Como k = 11 inicialmente, podemos produzir k literalmente sem mais cálculos. No entanto, quando n é positivo, entramos no loop while. O loop começa multiplicando m por k / c = p , adicionando 11 a k , aumentando assim p . Se k é um membro da sequência, subtraímos 1 de n e recomeçamos. Quando n atingir 0 , encontramos o membro sequência no índice desejado e sair do ciclo, em seguida, imprimir o último valor de k .

A expressão

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

executa o teste real e seu resultado ( True / 1 para membros da sequência, 0 / False caso contrário) é subtraído de n . Como visto anteriormente, ~ m% k = (-m - 1)% k = (-11 · (p - 1)! - 1)% 11p é igual a 10 se p for primo, 21 se p = 4 e 11p - 1 > 43 se p> 4 for composto. Assim, depois de subtrair c = 11 , ficamos com -1 para prime p e um número inteiro positivo maior que 9 caso contrário.

Para prime p , ​`k`[::-1]nos fornece a representação de string de k com a ordem dos dígitos invertidos, comparando-a com a ​`k`​verificação de se k é um palíndromo. Se for, todas as condições são atendidas e k é um membro da sequência. No entanto, se p não for primo, a etapa de grande alcance e o fato de k sempre ter mais de um dígito significa que ​`k`[::-1]não pode ter o mesmo número de dígitos que ​`k`​, muito menos ser igual a ele.

Braquilog , 17 bytes

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

Experimente online!

Isso é indexado em 1.

Explicação

: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

Duas realizações com esta resposta:

• Preciso corrigir o fato de que a passagem sobrescrita para metapredicados (com ⁽) não funcionará se não houver entrada a ser passada (e é por isso que tenho que adicionar :I).
• Preciso adicionar um metapredicado para obter o Nresultado de um predicado (o que evitaria o uso ᶠ⁽te, por exemplo, por exemplo ⁿ⁽).

A implementação de ambas as alterações tornaria a resposta 14 bytes.

Mathematica, 65 60 bytes

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

Repete diretamente através de números primos usando NextPrimee verifica se 11 vezes o número primo é um palíndromo. Trabalha até N = 528 . Os resultados 528 e 529 estão separados por mais de 2 ¹⁶ números primos, momento em que //.falhará ao tentar um número suficiente de substituições.

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

Dennis me derrotou aqui , então vá ver a resposta dele.

Esta resposta é zero 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

Experimente online!

Um byte economizado graças ao viciado em matemática

Explicação

Primeiro, pegamos a entrada e configuramos para ntambém criar uma nova variável r=1. Contaremos a rprocura de palíndromos que são o produto de um primo e 11. Cada vez que encontrarmos um, diminuiremos naté atingir 0.

Então começamos um loop:

while n:

A primeira coisa que fazemos é incrementar r

r+=1

Também predefinimos uma variável ccomo a representação de string der*11

c=`r*11`

Agora queremos diminuir nse tivermos encontrado esse número. Subtrairemos simplesmente um booleano representando se r*11encaixa no padrão r. Se for esse o caso False, subtrairemos zero e, se for True, subtrairemos 1.

Para calcular o booleano, fazemos:

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

A primeira parte alldeterminará se ré primo. Multiplicamos o resultado por cse rfor primo, isso será apenas, cmas se rfor composto "", a sequência vazia. Em seguida, comparamos isso com c[::-1]o inverso de c. Se rfor primo e cfor um palíndromo, será True, se um deles falhar, a coisa toda será avaliada como falsa.

Quando né zero, simplesmente print c.

83 bytes

Aqui está uma solução recursiva que é mais curta, mas infelizmente não atende às especificações, porque atinge o limite de recursão do python muito 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

Experimente online!

05AB1E , 15 bytes

Indexado a 0.

11Iµ11N*DÂQNp*½

Experimente online!

Explicação

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

Experimente online! Exemplo de uso:([n|n<-[0,11..],(==)=<<reverse$show n,3>2#n]!!) 127 .

[0,11..]constrói a lista infinita [0,11,22,33, ...](o zero é necessário para tornar a sequência indexada em 1). Para cada nlista nesta lista, verificamos n==(read.reverse.show)nse né um palíndromo. 3>2#nverifica se nhá no máximo dois divisores principais. Porquen é sempre divisível por 11, não obtemos primos reais, mas apenas semiprimes.

Edit: Obrigado a Ørjan Johansen por jogar 4 bytes!

PHP, 82 bytes

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

Experimente online!

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

Aqui g (700) = 92511529, portanto o limite seria> 700; ww (1000) = 703999307 mas usando nextPrime ()