Redivosite é uma palavra portmanteau inventada com o único objetivo deste desafio. É uma mistura de redução, divisão e composto.
Definição
Dado um número inteiro N> 6 :
- Se N é primo, N não é um número redivosita.
- Se N for composto:
- calcule N '= N / d + d + 1 repetidamente até N' ser primo, em que d é o menor divisor de N maior que 1
- N é um número redivosito se e somente se o valor final de N ' for um divisor de N
Abaixo estão os 100 primeiros números de redivosite (nenhuma entrada do OEIS no momento da postagem):
14,42,44,49,66,70,143,153,168,169,176,195,204,260,287,294,322,350,414,462,518,553,572,575,592,629,651,702,726,735,775,806,850,869,889,891,913,950,1014,1023,1027,1071,1118,1173,1177,1197,1221,1235,1254,1260,1302,1364,1403,1430,1441,1554,1598,1610,1615,1628,1650,1673,1683,1687,1690,1703,1710,1736,1771,1840,1957,1974,2046,2067,2139,2196,2231,2254,2257,2288,2310,2318,2353,2392,2409,2432,2480,2522,2544,2635,2640,2650,2652,2684,2717,2758,2760,2784,2822,2835
Exemplos
- N = 13 : 13 é primo, então 13 não é um número redivosita
- N = 32 : 32/2 + 3 = 19; 19 não é um divisor ou 32, então 32 não é um número redivosito
- N = 260 : 260/2 + 3 = 133, 133/7 + 8 = 27, 27/3 + 4 = 13; 13 é um divisor ou 260, então 260 é um número redivosita
Sua tarefa
- Dado um número inteiro N , retorne um valor verdadeiro se for um Número Redivosita ou um valor falso, caso contrário. (Você também pode gerar dois valores distintos, desde que sejam consistentes.)
- A entrada é garantida para ser maior que 6 .
- Isso é código-golfe , então a resposta mais curta em bytes vence!
code-golf
decision-problem
integer
division
Arnauld
fonte
fonte
a(n)
diretamente ou porque pode calcular um termo dos anteriores). Obrigado, Arnauld, por mudar o desafio. :)Respostas:
Haskell,
918583807574 bytesExperimente online!
Edit: -2 bytes graças a @BMO, -3 bytes graças a @ H.PWiz e
-5-6 bytes graças a @ Ørjan Johansenfonte
Casca , 14 bytes
Experimente online!
-3 graças a H.PWiz .
fonte
Ω
Γ
...Γ
, dada uma lista [a, b, c ...] será aplicada~+→Π
aa
e[b,c...]
.~+→Π
adicionaa+1
aproduct[b,c...]
.a
é o menor divisor,product[b,c...]
éN/d
C (gcc) ,
9489 bytesExperimente online!
Explicação
fonte
Gelatina , 14 bytes
Experimente online!
Como funciona
fonte
Python 2 ,
9791 bytesExperimente online!
Saídas via código de saída.
Ungolfed:
Experimente online!
fonte
05AB1E ,
1716 bytesExperimente online!
Explicação
fonte
Pitão , 20 bytes
Experimente aqui!
Como funciona
E os primeiros 4 bytes (
<P_Q
) apenas verificam se a entrada não está pronta.Com a ajuda de Emigna , consegui salvar 3 bytes.
fonte
head(P)
vez dafiITZ2
peça, pois o menor divisor maior que 1 sempre será primo?Python 3 , 149 bytes
Experimente online!
Usando uma abordagem de peneira. Deve ser rápido (
O(N log log N)
= complexidade temporal da peneira de Eratóstenes), mesmo com grandesN
(mas armazenaO(N)
números inteiros na memória)Nota:
n
não excedemN
eN > 7
p
podem serrange(2,N)
inseridos em vez derange(2,N+1)
peneirados./
não funciona,//
deve ser usado, devido ao índice da lista.range
em outra variável não ajuda, infelizmente.Explicação:
-~N
==N+1
.s
é inicializada comN+1
zeros (Python é indexação 0, então os índices são0..N
)s[n]
espera-se0
que seja sen
é um primo ep
parap
o primo mínimo que dividen
sen
é um composto.s[0]
es[1]
valores não são importantes.Para cada um
p
no intervalo[2 .. N-1]
:s[p] < 1
(isto é,s[p] == 0
), entãop
é primo, e para cadaq
um é um múltiplo dep
es[q] == 0
, atribuas[q] = p
.As duas últimas linhas são diretas, exceto que
n//s[n]-~s[n]
==(n // s[n]) + s[n] + 1
.Python 3 , 118 bytes
Experimente online!
À custa de um desempenho um pouco pior. (Este é executado com
O(N log N)
complexidade de tempo, assume uma implementação razoável de fatias do Python)O programa completo equivalente é 117 bytes .
fonte
n//s[n]-~s[n]
vez den//s[n]+s[n]+1
para 149 bytes.or p
pode ser|p
or p
executa lógica ou, enquanto|p
executa bit a bit ou. Isto é,a or b
éb if a == 0 else a
.for
para usar a fatia em vez de outrafor
. Orange
inverso é invertido; portanto, os índices mais baixos substituem os maiores, e iniciar a fatia em que2*p
você não substituis[0]
ous[p]
.Haskell , 110 bytes
Experimente online!
Não muito feliz ...
fonte
Oitava , 92 bytes
Experimente online!
fonte
APL (Dyalog) , 50 bytes
Experimente online!
fonte
Japonês,
2524 bytesReceio ter ido na direção errada com isso, mas fiquei sem tempo para tentar uma abordagem diferente.
Saídas
0
para falso ou1
verdadeiro.Tente
fonte
Perl 5 , 291 + 1 (-a) = 292 bytes
Maldito Perl por não ter um verificador primário nativo.
Versão não destruída,
Experimente online!
fonte
Wolfram Language (Mathematica) , 64 bytes
Implementação direta usando substituição recursiva de padrões
(substituir "\ [Divide]" pelo símbolo "∣" economiza 7 bytes)
Experimente online!
fonte
Limpo ,
128117114 bytesExperimente online!
fonte
J , 35 bytes
Experimente online!
O divisor mínimo, sendo o primeiro fator principal, foi roubado da solução @ Dennis's Jelly (anteriormente eu estava usando
<./@q:
).Deve haver uma maneira melhor de fazer a iteração, mas não consigo encontrá-la. Pensei em evitar fazer o teste de primalidade (
^:(0&p:)
) e usar o adverso, mas parece que será um pouco mais longo, pois você precisará de_2{
algumas alterações que podem não gerar uma redução líquida.Eu realmente sinto que deve haver uma maneira de evitar parens em torno da verificação de primalidade também.
Explicação (expandida)
fonte
NARS APL, 43 caracteres, 85 bytes
(na esperança de convergir para todos os números> 6):
A idéia de usar 2 funções anônimas chego a outra solução Apl.
fonte
Pyt , 44 bytes
Veja o código abaixo para obter uma explicação - as únicas diferenças são (1) que N é decrementado antes para contabilizar o incremento no início do loop e (2) ele usa NOR em vez de OR.
Experimente online!
Eu fiz isso antes de reler a pergunta e percebi que ela só queria um verdadeiro / falso.
Pyt, 52 bytes
Imprime uma lista infinita de números redivositos.
Explicação:
Experimente online!
fonte