Um primo truncável à direita é um primo em que todo prefixo é um primo (na base 10). Um primo truncável à esquerda é exatamente o oposto, onde todo postfix é um primo (primos que começam com 0 não são permitidos). Ambas as seqüências são finitas (existem apenas 83 truncáveis ​​à direita, enquanto existem 4260 truncáveis ​​à esquerda).

Você precisa escrever um programa que aceite um único número como entrada e produz o n º privilegiada-truncatable. No entanto, quando o programa é lido para trás dispostos , deve produzir o n º deixou-truncatable prime.

Para organizar um programa para trás, dividimos o programa em palavras e depois invertemos a ordem das palavras. Uma palavra pode consistir em qualquer número de caracteres.

Por exemplo, se o seu programa foi o seguinte:

hello world
1234567890

Todos os itens a seguir seriam permitidos como possíveis acordos reversos:

Divisão em cada personagem:

0987654321
dlrow olleh

Divisão em espaço em branco:

1234567890
world hello

Divisão arbitrariamente (tubos adicionados para maior clareza):

hel|lo w|orld
1|23456|7|8|90

908723456orld
1lo whel

Ao organizar seu programa para trás, todos os espaços em branco devem ser considerados e revertidos, como qualquer outro caractere.

Entradas de teste de encaminhamento:

1:  2
2:  3
21: 379
60: 239933
83: 73939133

Entradas de teste para trás:

1:    2
2:    3
39:   647
187:  29173
4260: 357686312646216567629137

Os programas devem poder executar em um período de tempo razoável (menos de um minuto)

Este é um código de golfe , então o programa com o menor número de bytes vence!

Geléia , 26 23 bytes

frente

Ѷp9¶7ÆR2ĿV€$ÆPÐf$ÐĿFị@

Experimente online!

Palavras

Ñ ¶ p 9 ¶ 7ÆR2ĿV€$ÆPÐf$ÐĿFị@

Para trás

7ÆR2ĿV€$ÆPÐf$ÐĿFị@¶9p¶Ñ

Experimente online!

Palavras

7ÆR2ĿV€$ÆPÐf$ÐĿFị@ ¶ 9 p ¶ Ñ

Como funciona

Todos os programas Jelly consistem em links (funções de assumir as funções da Jelly), que são separados por feeds de linha ou pilcrows ( ¶). O último deles é o link principal ; é chamado automaticamente quando o programa é executado.

O programa de encaminhamento funciona da seguinte maneira.

Ñ                   Helper link. Unused.


p9                  Helper link. Take the Cartesian product with [1, ..., 9].


7ÆR2ĿV€$ÆPÐf$ÐĿFị@  Main link. Argument: n

7ÆR                 Yield all primes up to 7.
             ÐĿ     
            $ÐĿ     Combine the two quicklinks to the left into a monadic chain,
                    and call it repeatedly until the results are no longer unique.
                    Return the array of all intermediate results.
       $              Combine the two links to the left into a monadic chain.
   2Ŀ               Call the helper link on line 2.
     Ṿ€                 Eval each array in the product. This casts to string
                        before evaluating, thus concatenating both numbers.
        ÆPÐf        Filter by primality; keep only primes.
               F    Flatten the resulting array.
                ị@  Retrieve the element at index n.

O programa anterior faz quase exatamente o mesmo; existem apenas duas diferenças.

• O link principal é agora Ñ, que simplesmente chama o link abaixo (em volta), ou seja, o link principal do programa de encaminhamento.

• 9pem vez de p9devolver o produto cartesiano invertido.

Python 2, 143 139 bytes

I=1
a={2}
def f(s):
 for d in'123456789':u=d[I:]+s+d*I;z=int(u);z+=z<3;z%91>0<2==pow(2,z,z)>a.add(z)<f(u)
f('')
lambda n:sorted(a)[~-n]
I=0

Consiste em cinco partes:

1. I=1
2. Uma nova linha
3. a={2}…[~-n]
4. Uma nova linha
5. I=0

Então a reversão é apenas inverter o valor de I.

Explicação

A função fexecuta uma pesquisa recursiva por primos truncáveis ​​à esquerda (LTPs) ou primos truncáveis ​​à direita (RTPs), dependendo do valor global I. Esses valores são adicionados ao conjunto a. Em seguida, lambda n:sorted(a)[~-n]retorna o n-th.

Vamos definir uma folha como um LTP, um RTP, algum dígito diferente de zero + um LTP ou um RTP + algum dígito diferente de zero. Esses são todos os valores que você fpode querer verificar quanto à primalidade.

Eu projetei um teste de pseudoprime Fermat que funciona para todas as folhas:

(63973 é um número Carmichael .)

Se esse teste retornar verdadeiro, zdeverá ser adicionado ao conjunto ae continuaremos str(z). O código responsável é:

z+=z<3;z%91>0<2==pow(2,z,z)>a.add(z)<f(u)

Primeiro, queremos lidar com o caso z == 2. Fazemos isso simplesmente esquivando-o aqui e codificando 2quando definimos inicialmente a! (Edição: E nada prejudicial acontece se também capturarmos z == 1.) Portanto, podemos assumir isso z ≥ 3agora.

Eu traduzi alguns "e" s em uma comparação encadeada em curto-circuito: as três primeiras comparações precisam ter sucesso antes a.add(z)e f(u)são avaliadas. Aqui estão todos os seus papéis:

1. z%91>0codifica nossa primeira condição. (63973 é divisível por 91, o que não é uma folha em si, é assim que a reconhecemos.)
2. 0<2é sempre verdade, mas o encadeamento é mais curto que and.
3. 2==pow(2,z,z) codifica nossa segunda condição.
4. pow(2,z,z)>a.add(z)aciona a adição e sempre é verdadeira, pois set.addretornos Nonee números inteiros são sempre maiores que None.
5. a.add(z)<f(u)aciona a recursão. Seu valor de verdade não é importante.

Reconhecimentos

• Dennis salvou quatro bytes ( u=[d+s,s+d][I]→ u=d[I:]+s+d*I; z==2→ z<3e o truque do mod 91 ). Obrigado!