Primos delicados
Inspirado em Encontre o maior primo frágil .
Removendo pelo menos 1 dígito de um inteiro positivo, podemos obter um inteiro não negativo diferente. Observe que isso é diferente da Removefunção na pergunta vinculada. Dizemos que um número primo é delicado se todos os inteiros gerados dessa forma não forem primos. Por exemplo, \$60649\$ gera os seguintes inteiros:
0, 4, 6, 9, 49, 60, 64, 66, 69, 604, 606, 609, 649, 664, 669, 6049, 6064, 6069, 6649
Nenhum desses inteiros são primos, portanto \$60649\$é um primo delicado. Observe que quaisquer zeros à esquerda são removidos e que o requisito é "não primo", então \$0\$e \$1\$ambos se qualificam, o que significa que, por exemplo, \$11\$ é um primo delicado.
Semelhante à regra de sequência padrão , você deve realizar uma das seguintes tarefas:
- Dado um número inteiro positivo \$n\$, produz dois valores distintos e consistentes * , dependendo se \$n\$ é um primo delicado ou não
- Dado um número inteiro positivo \$n\$, produza o \$n\$o delicado primeiro
- Dado um número inteiro positivo \$n\$, produza o primeiro \$n\$ delicados primos
- Produza infinitamente a lista de números primos delicados
* : Você pode optar por gerar dois conjuntos de valores, onde os valores no conjunto correspondem à definição de verdade e falsa do seu idioma. Por exemplo, uma resposta Python pode gerar uma lista vazia para falsey / truthy e uma lista não vazia caso contrário.
Você pode escolher quais das tarefas deseja fazer.
Você pode inserir e produzir de qualquer maneira padrão e, como se trata de um jogo de código , o código mais curto em bytes ganha
Para referência, os primeiros 20 primos delicados são:
2, 3, 5, 7, 11, 19, 41, 61, 89, 409, 449, 499, 881, 991, 6469, 6949, 9001, 9049, 9649, 9949
Mais alguns itens a serem observados:
821 - False (Removing the 8 and the 1 gives 2 which is prime)
Oferecerei uma recompensa de +100 por uma resposta que implemente uma das I / Os de sequência padrão, em vez do método do problema de decisão , que:
- é mais curto do que uma implementação ingênua de problema de decisão (inclua essa versão como prova, se ainda não tiver sido postada)
- ou que não depende de verificar se os valores são primos delicados ou não ao gerar valores (por exemplo, pode usar o fato de que apenas dígitos específicos podem ocorrer, ou outra coisa que não é simplesmente colocar um "loop sobre números, encontrando primos delicados" )
Isso é um tanto subjetivo quanto ao que conta como "verificar se há primos delicados", então usarei meu melhor julgamento quando se trata de conceder a recompensa.
Respostas
05AB1E , 4 bytes
Código
Usa a codificação 05AB1E. Verifica se o número fornecido é um primo delicado ou não.
æpJΘ
Experimente online! ou Verifique todos os números entre 1 e 9949 .
Explicação
æ # Get the powerset of the number.
p # Check for each element whether it is a prime.
J # Join these numbers into one big number.
Θ # Check whether this joined number is equal to 1.
APL (Dyalog Extended) , 16 14 bytes
</1⍭⍎⍕(⊢,,¨)\⍞
Experimente online!
-2 bytes ( ∊⍎¨¨ → ⍎⍕) graças a @ngn.
Programa completo que pega um único número de stdin e imprime 1 (verdadeiro) ou 0 (falso).
O truque aqui é como ele gera todas as subsequências não vazias:
(⊢,,¨)/ strfornece todas as subsequências dasstrquais incluem o último caractere.
(⊢,,¨)/ '1234'
→ '1' (⊢,,¨) '2' (⊢,,¨) '3' (⊢,,¨) '4'
→ '1' (⊢,,¨) '2' (⊢,,¨) '4' '34'
→ '1' (⊢,,¨) '4' '34' '24' '234'
→ '4' '34' '24' '234' '14' '134' '124' '1234'
(⊢,,¨)\ straplica(⊢,,¨)/- se a cada prefixo destr, fornecendo todas as subsequências não vazias como uma lista de listas de strings.
(⊢,,¨)\ '1234'
→ '1' ('2' '12') ('3' '23' '13' '123') ('4' '34' '24' '234' '14' '134' '124' '1234')
Explicação de todo o código:
</1⍭⍎⍕(⊢,,¨)\⍞
⍞ ⍝ Take n from stdin as a string
( )\ ⍝ For each prefix, reduce from right by
,¨ ⍝ prepend the previous char to each string
⊢, ⍝ and append to the previous list of strings
⍎⍕ ⍝ Convert nested strings to a single string,
⍝ and then eval it to get a simple integer vector
1⍭ ⍝ Test each number for primality
</ ⍝ Test if the only truth is the last one
Brachylog , 7 6 bytes
ṗ⊇ᵘṗˢȮ
Experimente online!
ṗ⊇ᵘṗˢȮ the implicit input
ṗ is a prime
⊇ᵘ and from every unique subset
ṗˢ select the primes
Ȯ and this should be a list with one element (the prime input itself)
Jelly , 7 bytes
DŒPḌẒḄ’
Um Link monádico que aceita um inteiro positivo que retorna zero (falsey) se for um primo delicado, ou um inteiro diferente de zero (verdadeiro) se não for.
Experimente online! Ou veja os primeiros vinte .
Como?
DŒPḌẒḄ’ - Link: n e.g. 824 409
D - decimal digits [8,2,4] [4,0,9]
ŒP - power-set [[],[8]...,[8,2,4]] [[],[4],...,[4,0,9]]
Ḍ - undecimal [0,8,2,4,82,84,24,824] [0,4,0,9,40,49,9,409]
Ẓ - is prime? [0,0,1,0,0,0,0,0] [0,0,0,0,0,0,0,1]
Ḅ - from binary 32 1
’ - decrement 31 0
Japt , 7 bytes
¥à f_°j
Experimente ou teste[0,1000)
¥à f_°j :Implicit input of integer string
¥ :Is equal to
à :Combinations
f :Filter
_ :By passing each through a function
° :Postfix increment, to cast to an integer
j :Is prime?
J , 25 23 bytes
-2 graças a Jonah!
Retorna uma lista contendo 1 sendo verdadeiro ou 0 caso contrário.
1</@p:(#~2#:@i.@^#)&.":
Experimente online!
Como funciona
1</@p:(#~2#:@i.@^#)&.":
&.": convert the number to a string
( 2 ^#) 2 ^ length
#:@i.@ enumerated and to base 2
#~ select from the string based on the bit mask
&.": convert from strings to numbers
1 p: primes -> 1, non-primes -> 0
so in the delicate prime case, we have
(2^L) - 1 zeros and one 1 for the input itself
</@ reduce from left to right with less-than
(so last position is 1, everything else 0)
Pyth , 14 8 bytes
qjfP_sTy
Experimente online!
Explicação
qjfP_sTy
f # filter
y # all subsets of input
P_sT # with a primality test
j # join result of filter on newlines
q # check if it equals input
Retina 0.8.2 , 53 bytes
^
;
+%`;(.)
$1;$'¶$`; .+ $*
%A`^.?$|^(..+)\1+$
^1+¶+$
Experimente online! O link inclui casos de teste. Explicação:
^
;
+%`;(.)
$1;$'¶$`;
Gere todas as subseqüências da entrada.
.+
$*
Converta então para unário.
%A`^.?$|^(..+)\1+$
Exclua aqueles que não são primos, mas não exclua as novas linhas. (Uma substituição de várias linhas também funciona, mas é mais difícil de formatar uma explicação.)
^1+¶+$
Verifique se a entrada original era primo, mas nenhuma das subsequências adequadas era.
Scala , 173 170 bytes
n=>(s"$n".indices.toSet.subsets.filter{x=>1<x.size&x.size<s"$n".size}.map(_.toSeq.sorted.map(""+n).mkString.toInt).toSet+n).filter{x=>x>1&2.to(x/2).forall(x%_>0)}==Set(n)
Experimente online!
R , 163 154 bytes
function(x,n=nchar(x),s=sum)(a=apply(!expand.grid(rep(list(0:1),n)),1,function(v)(y=s((x%/%10^(n:1-1)%%10)[v]*10^(s(v):1-1)))&s(!y%%1:y)==2))[1]&!s(a[-1])
Experimente online!
Verifica se há primos entre os números formados, removendo todas as combinações de dígitos de x. A primeira combinação é a remoção de nenhum dígito: deve ser VERDADEIRO e todos os outros testes principais devem ser FALSO.
Comentado:
is_delicate_prime=
function(x, # x = number to test
n=nchar(x), # n = number of digits of x
s=sum) # s = alias to sum() function
(a= # a = matrix of all prime-tests:
apply( # apply the function v to each of...
!expand.grid(rep(list(0:1),n)), # all combinations of n of TRUE/FALSE...
1, # row-by-row...
function(v) # defining the output of v as:
(y=s((x%/%10^(n:1-1)%%10) # the digits of x...
[v] # (considering only the elements chosen by v)...
*10^(s(v):1-1))) # multiplied by 10^((v-1)..0)...
&s(!y%%1:y)==2)) # tested for primality AND non-zero
[1] # Finally, output TRUE if a[1] is TRUE...
&!s(a[-1]) # and the sum of all other elements of a are FALSE
Linguagem Wolfram (Mathematica) , 54 bytes
Select[FromDigits/@Subsets@@RealDigits@#,PrimeQ]=={#}&
Experimente online!
JavaScript (ES6), 98 95 bytes
Espera ncomo uma string. Retorna um valor booleano.
n=>[...n].reduce((a,x)=>[...a,...a.map(y=>(g=k=>y%--k?g(k):(p+=q=y>1&k<2,y))(y+=x))],[p=0])|q/p
Experimente online!
Como?
Calculamos o conjunto de poderes dos dígitos de nde tal forma que a ordem é preservada e nela mesma é computada por último. O resultado é verdadeiro se o único primo entre os inteiros resultantes for o último.
Python 2 , 139 \$\cdots\$ 145 142 bytes
Adicionados 36 bytes para corrigir um bug gentilmente apontado por pxeger .
Economizei 5 bytes graças ao pxeger !!!
lambda n,R=range:all((g<2or any(g%i<1for i in R(2,g)))-(`g`==n)for g in{int(''.join(n[j]for j in R(len(n))if i>>j&1))for i in R(1,2**len(n))})
Experimente online!
Insere um número inteiro como string e retorna Truese for um primo delicado ou Falsenão.
Python 3.8 (pré-lançamento) , 146 144 bytes
-2 bytes removendo parênteses redundantes
Eu também estava trabalhando em uma resposta muito semelhante pouco antes do Noodle9 postar a sua, e combinei as ideias dela para obter esta ( voto positivo ! ) Aquele agora está bem diferente porque eles inicialmente tinham um quebrado, então pensei em postar o meu.
lambda s,R=range:(l:=len(s))*all((g!=int(s))^(g>1)&all(g%k for k in R(2,g))for g in{int(''.join(s[j]for j in R(l)if i>>j&1))for i in R(1,2**l)})
Experimente online!
Explicação:
lambda s,R=range:(l:=len(s))*all((g!=int(s))^(g>1)&all(g%k for k in R(2,g))for g in{int(''.join(s[j]for j in R(l)if i>>j&1))for i in R(1,2**l)})
lambda s : function
,R=range alias `range` built-in to `R`
{ s[j]for j in R(l)if i>>j&1 for i in R(1,2**l)} compute the power-set (excluding the empty set)
int(''.join( )) convert each list of digits to an integer
all( for g in ) check the integers for primality
all(g%k for k in R(2,g)) check for factors in the number
(g>1)& makes sure 0 and 1 aren't treated as prime
(g!=int(s))^ ensure the number itself is prime
(l:=len(s))* store the length in `l`
SageMath , 139 bytes
def f(n):s=str(n);l=len(s);return p(n)*all(~-p(g)for g in{int(''.join(s[j]for j in R(l)if i>>j&1))for i in R(1,2**l-1)})
R=range;p=is_prime
Experimente online!
Porto da minha resposta Python.
Python 3 ,
Usando itertools e uma receita de golfe para powerset.
lambda s,R=range:all(p(int(''.join(t)),R)for t in sum(([*combinations(s,k)]for k in R(1,len(s))),[]))>p(int(s),R)
from itertools import*
p=lambda n,R:any(n%i<1for i in R(2,n))or 2>n
Experimente online!
Espera a entrada como uma string.
A função pretorna Truese sua entrada não for primo e Falsese for primo; a função principal retorna (forall t, p(t)) > p(s)onde tobtém todos os "subvalores" de s. A única maneira de os booleanos satisfazerem essa desigualdade é True > False, o que significa que todos tsão não-primos e snão são não-primos.
Isenção de responsabilidade: já havia duas respostas python quando postei esta.