18

Bem, o bibliotecário pegou você trapaceando em seu trabalho usando seu algoritmo de classificação , então agora você está sendo punido. Você recebeu uma ordem para criar algum código para que o bibliotecário possa impressionar o objeto de seu afeto não correspondido, o professor de matemática. Então é isso que significa "Outros deveres como atribuídos" ...

Todo mundo está familiarizado com a sequência numérica natural na base 10, chamada N :

0, 1, 2, 3, 4, 5, 6, ...

A partir disso, podemos gerar a sequência de números primos, vamos chamá-la de P , de modo que todo elemento em P tenha exatamente dois divisores em N , a saber, 1ele próprio. Esta sequência é:

2, 3, 5, 7, 11, 13, ...

OK, rotina bonita até agora.

O bibliotecário pensou em uma função bacana F (x, y) que pega um número xde N , com a condição 0 <= x <= 9e um número yde N , e insere xa yexpansão decimal de todas as posições (por exemplo, pré-anexando, inserindo ou anexando xa y) e, em seguida, retorna o conjunto classificado de novos números.
Por exemplo, F (6, 127) resultaria em

1267, 1276, 1627, 6127

Isso ainda é meio chato, no entanto. O bibliotecário quer apimentar um pouco mais as coisas, especificando uma nova função z -> {p : p in P and F(z,p) subset of P}, ordenada ascendente.
Por exemplo, z (7) seria

3, 19, 97, 433, 487, 541, ...

porque 37e 73são ambos primos 719 179e 197todos são primos, etc.

Observe que z (2) está vazio, porque nenhum primo 2anexado ainda será primo. Da mesma forma para {0,4,5,6,8}.

Sua tarefa é escrever o código que irá gerar e gerar os primeiros 100 números em sequência z (x) para um dado x .

Entrada

Um único inteiro x tal que 0 <= x <= 9. A entrada pode ser via argumento de função, STDIN ou equivalente.

Resultado

Uma sequência dos 100 primeiros números, delimitada por sua escolha, para STDOUT ou equivalente, de modo que a sequência satisfaça z (x) conforme descrito acima. E se z (x) estiver vazio, como é o caso de {0,2,4,5,6,8}, as palavras Empty Setdevem ser exibidas.

Restrições

Isso é código-golfe, já que você precisará transcrever isso em um cartão de índice para que o bibliotecário possa mostrar ao professor de matemática e suas mãos cãibras facilmente.
Aplicam-se restrições de brecha padrão. O bibliotecário não tolera trapaceiros.

Sequências de referência

x = 1: A069246
x = 3: A215419
x = 7: A215420
x = 9: A215421

Relacionado: Encontre o maior primo frágil / Encontre o menor primo de uma substring / Encontre o maior primo que ainda é um primo após a exclusão do dígito

code-golf math sequence primes number-theory AdmBorkBork
fonte

5

Pitão, 49 bytes

Assim como o Python3 e outras respostas Pyth, o tempo de execução para encontrar 100 números é proibitivo. (suíte de teste fornece 10)

?}z"1379".f&!tPZ!|FmtPvjzc`Z]dhl`Z*TT3"Empty Set"

Experimente online

Brian Tuck
fonte

1

A trilha "é desnecessária, um trabalho muito agradável.

FryAmTheEggman

Thanx pelo lembrete. Porque EOL não termina uma corda, eu tenho evitado cordas terminadas, mas é claro, EOF ainda funciona

Brian Tuck

4

Python 3, 188 bytes

x=input()
k=1
i=100
if x in"024568":i=print("Empty Set")
while i:k+=1;s=str(k);i-=all(sum(p%d<1for d in range(2,p))<4for p in[k*int(s[:j]+x+s[j:])for j in range(len(s)+1)])and not print(k)

Mal jogado, mas aqui está algo por enquanto. Em vez de verificar p in P and F(z,p) subset of P, verificamos que p*fé um semiprime para cada um f in F(z,p). Combine isso com a divisão de teste para teste de primalidade e você obterá um O(scary)algoritmo.

Sp3000
fonte

+1 paraO(scary)

AdmBorkBork

1

Bom truque ao definir i como Nenhum.

lirtosiast

3

Perl, 124 bytes

$p=prime_iterator;y/1379//or$i=+~print'Empty Set'}while($i<100){$_=&$p;is_prime"$`@F$'"or redo while//g;$i++

Requer a seguinte opção de linha de comando: -palMntheory=:all contada como 16. Entrada retirada de stdin.

Usa o módulo do @DanaJMath::Prime::Util para perl (carregado com o pragma ntheory). Obtenha com:

cpan install Math::Prime::Util
cpan install Math::Prime::Util::GMP

is_primeé determinístico para todos os valores menores que 2 ⁶⁴ , o que é suficiente para nossos propósitos.

Uso da amostra

$ echo 2|perl -palMntheory=:all oscary.pl
Empty Set

$ echo 7|perl -palMntheory=:all oscary.pl
3
19
97
433
487
541
691
757
853
1471
.
.
.
718705783
720574573
737773357
745157779
747215167
767717017
768743377
770294977
771778477
774577777

Tempo de execução esperado

x = 1 : 1m 09.2s
x = 3 : 0m 04.2s
x = 7 : 2m 52.5s
x = 9 : 0m 11.5s

primo
fonte

1

Pyth, 58

L}bPb|*"Empty Set"}Qj204568T.f&yZ.Amyi++<JjZTdQ>JdThl`Z100

Este conjunto de testes calcula apenas os 10 primeiros números porque leva muito tempo para gerar o restante. O bruto força a primalidade e a inserção dos dígitos. Demonstra um desempenho tão ruim que não consegui executá-lo até 100, por isso, diga-me se houver problemas.

FryAmTheEggman
fonte

Sequência aritmética de primos do bibliotecário louco