Inspirado por esta pergunta Math.SE .
fundo
A sequência de Fibonacci (chamada F
) é a sequência, começando de 0, 1
modo que cada número ( F(n)
) (após os dois primeiros) seja a soma dos dois antes dele ( F(n) = F(n-1) + F(n-2)
).
Uma sequência de Fibonacci mod K (chamada M
) é a sequência dos números de Fibonacci mod K ( M(n) = F(n) % K
).
Pode-se mostrar que a sequência K de Fibonacci mod é cíclica para todo K, já que cada valor é determinado pelo par anterior, e existem apenas K 2 pares possíveis de números inteiros não negativos ambos menores que K. Porque a sequência de Fibonacci mod K é cíclico após seu primeiro par de termos repetido, um número que não aparece no modelo K de Fibonacci Sequence antes que o primeiro par de termos repetido nunca apareça.
Para K = 4
0 1 1 2 3 1 0 1 ...
Para K = 8
0 1 1 2 3 5 0 5 5 2 7 1 0 1 ...
Observe que para K = 8, 4 e 6 não aparece antes da repetição 0 1
, portanto 4 e 6 nunca aparecerão no Modon de Fibonacci Sequence 8.
Desafio
Dado um número inteiro K estritamente maior que 0, produza todos os números inteiros não negativos menores que K que não aparecem no modelo K. de Fibonacci Sequence
Regras
Você pode supor que K caiba no seu tipo inteiro nativo ( dentro do motivo ).
Se houver números não negativos menores que K que não apareçam no Fibonacci Sequence mod K, seu programa / função deve gerar todos esses números de maneira razoável.
Se não houver números inteiros não negativos inferiores a K que não apareçam no Fibonacci Sequence mod K, seu programa / função poderá indicar isso retornando uma lista vazia, imprimindo nada, produzindo um erro etc.
Ordem não importa.
Isso é código-golfe , então a resposta mais curta em cada idioma vence.
Casos de teste
Casos de teste não vazios
8 [4, 6]
11 [4, 6, 7, 9]
12 [6]
13 [4, 6, 7, 9]
16 [4, 6, 10, 12, 14]
17 [6, 7, 10, 11]
18 [4, 6, 7, 9, 11, 12, 14]
19 [4, 6, 7, 9, 10, 12, 14]
21 [4, 6, 7, 9, 10, 11, 12, 14, 15, 16, 17, 19]
22 [4, 6, 7, 9, 15, 17, 18, 20]
23 [4, 7, 16, 19]
24 [4, 6, 9, 11, 12, 14, 15, 18, 19, 20, 22]
26 [4, 6, 7, 9, 17, 19, 20, 22]
28 [10, 12, 14, 16, 18, 19, 23]
29 [4, 6, 7, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 27]
31 [4, 6, 9, 12, 14, 15, 17, 18, 19, 22, 25, 29]
32 [4, 6, 10, 12, 14, 18, 20, 22, 26, 28, 30]
33 [4, 6, 7, 9, 15, 17, 18, 20, 24, 26, 27, 28, 29, 31]
34 [4, 6, 7, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 27, 28, 30]
36 [4, 6, 7, 9, 10, 11, 12, 14, 16, 18, 20, 22, 23, 24, 25, 26, 27, 29, 30, 31, 32]
37 [9, 10, 14, 17, 20, 23, 27, 28]
38 [4, 6, 7, 9, 10, 11, 12, 14, 15, 16, 18, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 31, 32, 33, 36]
39 [4, 6, 7, 9, 15, 17, 19, 20, 22, 24, 30, 32, 33, 35]
...
200 [4, 6, 12, 14, 20, 22, 28, 30, 36, 38, 44, 46, 52, 54, 60, 62, 68, 70, 76, 78, 84, 86, 92, 94, 100, 102, 108, 110, 116, 118, 124, 126, 132, 134, 140, 142, 148, 150, 156, 158, 164, 166, 172, 174, 180, 182, 188, 190, 196, 198]
...
300 [6, 18, 30, 42, 54, 66, 78, 90, 102, 114, 126, 138, 150, 162, 174, 186, 198, 210, 222, 234, 246, 258, 270, 282, 294]
...
400 [4, 6, 10, 12, 14, 20, 22, 26, 28, 30, 36, 38, 42, 44, 46, 52, 54, 58, 60, 62, 68, 70, 74, 76, 78, 84, 86, 90, 92, 94, 100, 102, 106, 108, 110, 116, 118, 122, 124, 126, 132, 134, 138, 140, 142, 148, 150, 154, 156, 158, 164, 166, 170, 172, 174, 180, 182, 186, 188, 190, 196, 198, 202, 204, 206, 212, 214, 218, 220, 222, 228, 230, 234, 236, 238, 244, 246, 250, 252, 254, 260, 262, 266, 268, 270, 276, 278, 282, 284, 286, 292, 294, 298, 300, 302, 308, 310, 314, 316, 318, 324, 326, 330, 332, 334, 340, 342, 346, 348, 350, 356, 358, 362, 364, 366, 372, 374, 378, 380, 382, 388, 390, 394, 396, 398]
...
Casos de teste vazios (nenhuma saída, erro, lista vazia etc. é saída aceitável)
1, 2, 3, 4, 5, 6, 7, 9, 10, 14, 15, 20, 25, 27, 30, 35 ... 100 ...
Respostas:
Geléia ,
98 bytesExperimente online!
Com base no período pisano
p(n) <= 6n
de A001175 . Além disso,p(n) <= 6n <= n^2
paran >= 6
ep(n) <= n^2
paran < 6
. Salve este byte graças a Dennis.fonte
²
deve funcionar em vez de×6
.Haskell , 70 bytes
Alguma quantidade de bytes salvos graças ao Esolanging Fruit
8 bytes economizados graças ao Laikoni
Experimente online!
fonte
read$show
funciona em vez defromInteger
neste caso e salva dois bytes.zip[1..x^2]
para truncar economiza mais alguns bytes: Experimente online!Perl 6 ,
43 42 3932 bytesTeste-o
Teste-o
Teste-o
Teste-o
Expandido:
fonte
> <> , 48 bytes
Experimente online!
Recebe entrada através do sinalizador -v.
Imprime muitas linhas de excesso, mas realiza o trabalho. Isso basicamente usa a primeira linha para armazenar o conjunto de números que apareceram até agora na sequência.
Como funciona:
fonte
Python 2 , 69 bytes
Experimente online!
fonte
MATL ,
1918 bytesExperimente online!
-1 byte graças a Guiseppe.
fonte
X~
!Python 3 , 91 bytes
Experimente online!
fonte
Casca ,
13 1210 bytesObrigado @Zgarb por -2 bytes!
Imprime uma lista vazia, caso todos os números apareçam, tente online!
Explicação
fonte
U2
para obter o prefixo mais longo, onde nenhum par adjacente se repete.Python 3 , 78 bytes
Experimente online!
Imprime um conjunto, de modo que a saída para casos de teste vazios é
set()
, que é o conjunto vazio.fonte
R,
9286 bytesObrigado a @ Giuseppe por salvar 6 bytes!
Experimente online!
Implementação bastante direta ( versão anterior , mas o mesmo conceito):
fonte
setdiff
, boa ideia!1:k^2
abordagem que todo mundo usaPython 3,
173152143131 bytesAgradecimentos especiais a @ovs.
Experimente Online
Como funciona?
A primeira função usa dois parâmetros m e n e retorna o enésimo número de mf de Fibonacci mod m. A segunda função percorre os números de Fibonacci mod k e verifica se 0 e 1 são repetidos. Ele armazena os números em uma lista e o compara com uma lista que contém os números 1-n. Os números duplicados são removidos e os números restantes são retornados.
fonte
set()
e comparações encadeadas.05AB1E , 10 bytes
Experimente online!
-3 bytes graças a Emigna.
fonte
Ruby , 47 bytes
Experimente online!
Embora ele use parte da mesma lógica, isso não se baseia na resposta do GB .
Explicação:
fonte
Lisp comum, 106 bytes
Experimente online!
fonte
Pari / GP , 55 bytes
Experimente online!
fonte
Elixir ,
148144 bytesExperimente online!
Não é uma resposta especialmente competitiva, mas foi realmente divertido jogar golfe! Elixir é uma linguagem bastante legível, mas segue uma explicação para a bagunça de personagens no meio.
Esta explicação está em duas seções, o mod-fibonacci e o funcionamento nele
Mod-fib:
Isso retorna um fluxo infinito de fibonacci mod
x
. Começa com um acumulador{1,1}
e aplica a seguinte operação ad infinitum: dado acumulador{p,n}
, saídap mod x
para o fluxo. Em seguida, defina o acumulador para{n,p+n}
.O resto:
fonte
SNOBOL4 (CSNOBOL4) , 153 bytes
Experimente online!
fonte
Ruby ,
5553 bytesExperimente online!
fonte
JavaScript (ES6), 84 bytes
fonte
Python 3, 76 bytes
Isso simplesmente examina o ciclo mais longo possível dos números de Fibonnaci (n ^ 2) e cria uma lista de todos os números que ocorrem nesse período. Para simplificar a lógica, os números são armazenados no módulo n.
fonte