A sequência de Fibonacci é uma sequência bem conhecida, na qual cada entrada é a soma das duas anteriores e as duas primeiras são 1. Se tomarmos o módulo de cada termo por uma constante, a sequência se tornará periódica. Por exemplo, se decidimos computar a sequência mod 7, obteríamos o seguinte:
1 1 2 3 5 1 6 0 6 6 5 4 2 6 1 0 1 1 ...
Tem um período de 16. Uma sequência relacionada, denominada sequência de Pisano , é definida de modo que a(n)
seja o período da sequência de fibonacci quando calculado no módulo n.
Tarefa
Você deve escrever um programa ou função que, quando fornecido n
, calculará e produzirá o período do mod de sequência de Fibonacci n
. Esse é o enésimo termo na sequência de Pisano.
Você deve suportar apenas números inteiros no intervalo 0 < n < 2^30
Como é uma competição de código-golfe , você deve minimizar o tamanho do seu código-fonte, conforme marcado por bytes.
Casos de teste
1 -> 1
2 -> 3
3 -> 8
4 -> 6
5 -> 20
6 -> 24
7 -> 16
8 -> 12
9 -> 24
10 -> 60
11 -> 10
12 -> 24
f(i),f(i+1)
pode levar no máximon^2
valores modn
. Assim,n
limitado a2^30
pode acabar produzindo um período de até2^60
. Restringirn <= 2^16
dariaP(n) <= 2^32
.f(i+2) = f(i+1)+f(i)
, para que o 'estado' de uma máquina em loop durante o período possa ser descrito com um par de números inteiros modn
. Existem no máximon^2
estados, portanto o período é no máximon^2
. Oh! A Wikipedia afirma que o período é no máximo6n
. Deixa pra lá minha trivialidade.Respostas:
GolfScript (
28 25 2423 caracteres)Pega entrada no stdin, deixa no stdout (ou na pilha, se você quiser processá-lo mais ...)
Isso lida corretamente com os casos de canto ( demonstração ).
Como um ponto de interesse para os programadores do GolfScript, acho que este é o primeiro programa que escrevi com um desdobramento que realmente saiu mais curto do que as outras abordagens que tentei.
fonte
GolfScript, 24 caracteres
Próxima iteração de uma implementação GolfScript. A segunda versão agora também lida com 1 corretamente. Tornou-se bastante longo, mas talvez alguém possa encontrar uma maneira de encurtar esta versão. Você pode tentar a versão acima online .
fonte
1
corretamente?1
- e ainda apenas 24 caracteres.Python,
1881321019587 caracteresUso
Por exemplo:
fonte
cat
ting parawc -c
e fico com o mesmo número.if k>0 and s[0:k]==s[k:]:break
pode ser alterado paraif s and s[:k]==s[k:]:break
. Você também pode reduzir significativamente removendo o iterador, alterando ofor
loop parawhile 1:
e executandoa,b=a,a+b
no final do loop while.Python
908596949082Editar: sugestões implementadas por beary e primo
fonte
a.append(c) -> a+=[c]
, while pode ser colocado em uma única linha,((n>1)>>(c in a)) -> (n>1)>>(c in a)
append
realmente tem uma funcionalidade diferente de+=
. Obrigado pelas dicas embora.(n>1)>>(c in a)
->
(c in a)<1%n
por 3 bytes. E eu concordo com beary sobre o anexo. Se você anexa uma referênciac
ou estendea
pelo valor dec
, é exatamente o mesmo de qualquer maneira (como você destrói sua referência imediatamentec
)a+=c
, em vez dea+=[c]
Mathematica 73
fonte
PHP -
6157 bytesEsse script reportará erroneamente
2
paran=1
, mas todos os outros valores estão corretos.Amostra de E / S, uma série truncável à esquerda em que π (n) = 2n + 2:
fonte
1<$a.$b=+$a+$a=!$i+++$b%$n+=fgets(STDIN)
Oh Deus, isso é alguma ordem de exploração de operação ali.PowerShell: 98
Código de golfe:
Ungolfed, com comentários:
Notas:
Não sei exatamente qual é o limite máximo confiável para $ n com este script. É possivelmente menor que 2 ^ 30, pois $ x poderia estourar um int32 antes de $ n chegar lá. Além disso, eu não testei o limite superior porque os tempos de execução do script já atingem cerca de 30 segundos no meu sistema por $ n = 1e7 (que é um pouco acima de 2 ^ 23). Pelo mesmo motivo, não estou inclinado a testar e solucionar problemas de qualquer sintaxe adicional necessária para atualizar as variáveis para uint32, int64 ou uint64, quando necessário, a fim de expandir o alcance desse script.
Saída de amostra:
Eu envolvi isso em outro loop for:
Em seguida, defina em
$n=$i
vez de=read-host
e altere a saída"$i | $x"
para ter uma idéia da confiabilidade geral do script. Aqui estão alguns dos resultados:...
Nota:
Não tenho muita certeza de como alguns períodos de Pisano são significativamente menores que $ n. Isso é normal ou há algo errado com o meu script?Deixa pra lá - lembrei-me de que, depois das cinco, os números de Fibonacci rapidamente se tornam muito maiores do que o seu lugar na sequência. Então, isso faz total sentido agora.fonte
Perl,
75,61, 62 + 1 = 63Uso
Ungolfed
+1 byte para
-n
sinalizador. Raspou 13 bytes graças a Gabriel Benamy.fonte
$n=<>;
(-6) e substituí-lo pelo-n
sinalizador (+1), e todas as instâncias de$n
podem ser substituídas por$_
. Você pode usar-M5.010
gratuitamente, o que permite usar osay
comando em vez deprint
(-2). Aswhile
instruções do modificador não precisam de parênteses em torno da condição (-2). Em vez de@{[%h]}/2
, você pode ter um contador$a++,
antes($m,$k)=
e depois apenas tersay$a-1
no final (-2). Em vez de"$m,$k"
usar$m.$k
(-2). Isso deve aparecer$k=1%$_;$a++,($m,$k)=($k,($m+$k)%$_)while!$h{$m.$k}++;say$a-1
com o-n
sinalizador, para 61 + 1 = 62 bytes."$m,$k"
vez de$m.$k
(+2), mas pode salvar 1 byte, alterandowhile!$h
parauntil$h
(-1). Desculpe!$m.$k
falha? Pareceu funcionar do meu lado.Clojure, 102 bytes
Não é muito emocionante, itera a fórmula até chegarmos em volta
[1 1]
(espero que seja sempre esse o caso). Manuseio especial de(f 1)
como ele converge[0 0]
.fonte