Encontre o período Pisano

20

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 , 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
caixa de papelão
fonte
3
A limitação a 2 ^ 30 pode garantir que todos os valores intermediários sejam menores que 2 ^ 31, mas ainda não garante que o período Pisano caiba dentro de um número inteiro assinado de 32 bits. (Presumo que essa seja a razão da sua limitação?) Os períodos de Pisano podem ser significativamente maiores que os n . Por exemplo, o período Pisano de 6 é 24. Poderes de 10 acima de 100 são 50% maiores que n .
Iszi
3
O princípio Pigeonhole diz que f(i),f(i+1)pode levar no máximo n^2valores mod n. Assim, nlimitado a 2^30pode acabar produzindo um período de até 2^60. Restringir n <= 2^16daria P(n) <= 2^32.
Boothby
@ boothby Não tenho muita certeza de entender o que você está dizendo, ou mesmo se estiver abordando adequadamente o mesmo problema que eu. Você poderia explicar um pouco mais, talvez com links adicionais? Sinta-se livre para me puxar para o bate-papo, se necessário.
Iszi
2
@ Iszi Observe que 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 mod n. Existem no máximo n^2estados, portanto o período é no máximo n^2. Oh! A Wikipedia afirma que o período é no máximo 6n. Deixa pra lá minha trivialidade.
Boothby
2
oeis.org/A001175
Digital Trauma

Respostas:

11

GolfScript ( 28 25 24 23 caracteres)

~1.{(2$+}{.@+2$%}/+\-,)

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.

Peter Taylor
fonte
7

GolfScript, 24 caracteres

~:&1.{.2$+&%.2$(|}do](-,

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 .

Howard
fonte
Isso manipula a entrada 1corretamente?
22812 Peter Taylor
@ PeterTaylor Nope, não testou o caso da esquina. De volta à prancheta.
Howard
@PeterTaylor O novo código também funciona para entrada 1- e ainda apenas 24 caracteres.
23412 Howard
4

Python, 188 132 101 95 87 caracteres

n=input()
s=[]
a=k=0
b=1
while s[:k]!=s[k:]or k<1:s+=[a%n];k=len(s)/2;a,b=b,a+b
print k

Uso

$ echo 10 | python pisano.py
60

Por exemplo:

$ for i in {1..50}; do; echo $i | python pisano.py; done
1
3
8
6
20
24
16
12
24
60
10
24
28
48
40
24
36
24
18
60
16
30
48
24
100
84
72
48
14
120
30
48
40
36
80
24
76
18
56
60
40
48
88
30
120
48
32
24
112
300
ESultanik
fonte
Obrigado, beary605 , pelo golfe adicional!
ESultanik
Você pode querer contar seus caracteres novamente. Minha contagem da sua resposta está abaixo da contagem da sua resposta.
21412
@ David: Você está contando espaço em branco? Eu apenas verificado duas vezes (por catting para wc -ce fico com o mesmo número.
ESultanik
Eu uso uma rotina fornecida pela Wolfram Research. Isso conta com espaço em branco necessário, eu acho.
21412
if k>0 and s[0:k]==s[k:]:breakpode ser alterado para if s and s[:k]==s[k:]:break. Você também pode reduzir significativamente removendo o iterador, alterando o forloop para while 1:e executando a,b=a,a+bno final do loop while.
Strigoides
4

Python 90 85 96 94 90 82

n=input();c=[1,1];a=[]
while(c in a)<1%n:a+=[c];c=[c[1],sum(c)%n]
print len(a)or 1

Editar: sugestões implementadas por beary e primo

cortador
fonte
85: a.append(c) -> a+=[c], while pode ser colocado em uma única linha,((n>1)>>(c in a)) -> (n>1)>>(c in a)
beary605
appendrealmente tem uma funcionalidade diferente de +=. Obrigado pelas dicas embora.
Scleaver 24/10/12
Eu acho que funciona da mesma maneira neste caso.
beary605
(n>1)>>(c in a) -> (c in a)<1%npor 3 bytes. E eu concordo com beary sobre o anexo. Se você anexa uma referência cou estende apelo valor de c, é exatamente o mesmo de qualquer maneira (como você destrói sua referência imediatamente c)
Primo
Ah ok, meu erro foi que eu estava usando a+=c, em vez dea+=[c]
scleaver
2

Mathematica 73

p = {1, 0}; j = 0; q = p;
While[j++; s = Mod[Plus @@ p, n]; p = RotateLeft@p; p[[2]] = s; p != q]; j
DavidC
fonte
2

PHP - 61 57 bytes

<?for(;1<$a.$b=+$a+$a=!$i+++$b%$n+=fgets(STDIN););echo$i;

Esse script reportará erroneamente 2para n=1, mas todos os outros valores estão corretos.

Amostra de E / S, uma série truncável à esquerda em que π (n) = 2n + 2:

$ echo 3 | php pisano.php
8
$ echo 13 | php pisano.php
28
$ echo 313 | php pisano.php
628
$ echo 3313 | php pisano.php
6628
$ echo 43313 | php pisano.php
86628
$ echo 543313 | php pisano.php
1086628
$ echo 4543313 | php pisano.php
9086628
$ echo 24543313 | php pisano.php
49086628
primo
fonte
1
1<$a.$b=+$a+$a=!$i+++$b%$n+=fgets(STDIN)Oh Deus, isso é alguma ordem de exploração de operação ali.
Llama
1

PowerShell: 98

Código de golfe:

for($a,$b=0,(1%($n=read-host))){$x++;if($a+$b-eq0-or("$a$b"-eq10)){$x;break}$a,$b=$b,(($a+$b)%$n)}

Ungolfed, com comentários:

for
(
    # Start with $a as zero, and $b as 1%$n.
    # Setting $b like this at the start helps catch the exceptional case where $n=1.
    $a,$b=0,(1%
    (
        # Grab user input for n.
        $n=read-host
    ))
)
{
    # Increasing the counter ($x) and testing for the end of the period at the start ensures proper output for $n=1.
    $x++;

    # Test to see if we've found the end of the Pisano Period.
    if
    (
        # The first part catches $n=1, since $a and $b will both be zero at this point.
        $a+$b-eq0-or
        (
            # A shorter way of testing $a-eq1-and$b-eq0, which is the end of a "normal" Pisano Period.
            "$a$b"-eq10
        )
    )
    {
        # Pisano Period has reached its end. Output $x and get out of the loop.
        $x;break
    }

    # Pisano Period still continues, perform operation to calculate next number.
    # Works pretty much like a Fibonacci sequence, but uses ($a+$b)%$n for the new $b instead.
    # This takes advantage of the fact we don't really need to track the actual Fibonacci numbers, just the Fibonacci pattern of %$n.
    $a,$b=$b,(($a+$b)%$n)
}

# Variable cleanup - not included in golfed code.
rv n,a,b,x

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:

for($i=1;;$i++)

Em seguida, defina em $n=$ivez de =read-hoste altere a saída "$i | $x"para ter uma idéia da confiabilidade geral do script. Aqui estão alguns dos resultados:

1 | 1
2 | 3
3 | 8
4 | 6
5 | 20
6 | 24
7 | 16
8 | 12
9 | 24
10 | 60
11 | 10
12 | 24
13 | 28
14 | 48
15 | 40
16 | 24
17 | 36
18 | 24
19 | 18
20 | 60

...

9990 | 6840
9991 | 10192
9992 | 624
9993 | 4440
9994 | 1584
9995 | 6660
9996 | 1008
9997 | 1344
9998 | 4998
9999 | 600
10000 | 15000
10001 | 10212
10002 | 3336
10003 | 5712
10004 | 120
10005 | 1680
10006 | 10008
10007 | 20016
10008 | 552
10009 | 3336
10010 | 1680

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.

Iszi
fonte
1

Perl, 75 , 61 , 62 + 1 = 63

$k=1%$_;$a++,($m,$k)=($k,($m+$k)%$_)until$h{"$m,$k"}++;say$a-1

Uso

$ echo 8 | perl -n -M5.010 ./pisano.pl
12

Ungolfed

$k = 1 % $_;
$a++, ($m, $k) = ($k, ($m + $k) % $_) until $h{"$m,$k"}++;
say $a - 1

+1 byte para -nsinalizador. Raspou 13 bytes graças a Gabriel Benamy.

Silvio Mayolo
fonte
1
Você pode se livrar de $n=<>;(-6) e substituí-lo pelo -nsinalizador (+1), e todas as instâncias de $npodem ser substituídas por $_. Você pode usar -M5.010gratuitamente, o que permite usar o saycomando em vez de print(-2). As whileinstruçõ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 ter say$a-1no 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-1com o -nsinalizador, para 61 + 1 = 62 bytes.
Gabriel Benamy
Claramente, não sou tão inteligente com Perl quanto pensei que era. Obrigado pelas dicas.
Silvio Mayolo
Existem muitas dicas úteis nas dicas para jogar golfe no segmento Perl ! Boa sorte! ^^
Gabriel Benamy
Na verdade, eu estava errado - você precisa em "$m,$k"vez de $m.$k(+2), mas pode salvar 1 byte, alterando while!$hpara until$h(-1). Desculpe!
Gabriel Benamy
Hum? Sob que entrada $m.$kfalha? Pareceu funcionar do meu lado.
Silvio Mayolo
0

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].

#(if(< % 2)1(+(count(take-while(fn[v](not=[1 1]v))(rest(iterate(fn[[a b]][b(mod(+ a b)%)])[1 1]))))1))
NikoNyrh
fonte