Encuentra el período de Pisano

20

La secuencia de Fibonacci es una secuencia bien conocida en la que cada entrada es la suma de las dos anteriores y las dos primeras entradas son 1. Si tomamos el módulo de cada término por una constante, la secuencia se volverá periódica. Por ejemplo, si decidimos calcular la secuencia mod 7 obtendríamos lo siguiente:

1 1 2 3 5 1 6 0 6 6 5 4 2 6 1 0 1 1 ...

Tiene un período de 16. Una secuencia relacionada, llamada secuencia de Pisano , se define de manera tal que a(n)es el período de la secuencia de Fibonacci cuando se calcula el módulo n.

Tarea

Deberá escribir un programa o función que, cuando se proporcione n, calculará y generará el período del mod de secuencia de Fibonacci n. Ese es el enésimo término en la secuencia de Pisano.

Solo debe admitir enteros en el rango 0 < n < 2^30

Esta es una competencia de , por lo que debe intentar minimizar el tamaño de su código fuente según la puntuación por bytes.

Casos de prueba

1  -> 1
2  -> 3
3  -> 8
4  -> 6
5  -> 20
6  -> 24
7  -> 16
8  -> 12
9  -> 24
10 -> 60
11 -> 10
12 -> 24
caja de cartón
fuente
3
La limitación a 2 ^ 30 puede garantizar que todos los valores intermedios sean inferiores a 2 ^ 31, pero aún así no garantiza que el Período Pisano se ajuste a un entero con signo de 32 bits. (¿Supongo que esa es la razón de su limitación?) Los períodos de Pisano pueden ser significativamente mayores que su n . Por ejemplo, el Periodo Pisano de 6 es 24. Las potencias de 10 por encima de 100 salen un 50 por ciento más grandes que n .
Iszi
3
El principio del casillero dice que f(i),f(i+1)puede tomar en la mayoría de los n^2valores mod n. Por lo tanto, nlimitado a 2^30podría terminar produciendo un período de hasta 2^60. Restringiría n <= 2^16daría P(n) <= 2^32.
Boothby
@boothby No estoy muy seguro de entender lo que estás diciendo, o si incluso está abordando adecuadamente el mismo problema que yo. ¿Podría explicar un poco más, tal vez con enlaces adicionales? Siéntase libre de atraerme al chat si es necesario.
Iszi
2
@Iszi Observe eso f(i+2) = f(i+1)+f(i), por lo que el 'estado' de una máquina en bucle durante el período se puede describir con un par de mods de enteros n. Hay en la mayoría de los n^2estados, por lo que el período es como máximo n^2. Oh! Wikipedia afirma que el período es como máximo 6n. No importa mi trivialidad.
Boothby
2
oeis.org/A001175
Trauma digital

Respuestas:

11

GolfScript ( 28 25 24 23 caracteres)

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

Toma entrada en stdin, la deja en stdout (o en la pila, si desea procesarla más ...)

Esto maneja correctamente los casos de esquina ( Demo ).

Como un punto de interés para los programadores de GolfScript, creo que este es el primer programa que he escrito con un despliegue que en realidad salió más corto que los otros enfoques que probé.

Peter Taylor
fuente
7

GolfScript, 24 caracteres

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

Próxima iteración de una implementación de GolfScript. La segunda versión ahora también maneja 1 correctamente. Se hizo bastante largo, pero tal vez alguien pueda encontrar una manera de acortar esta versión. Puede probar la versión anterior en línea .

Howard
fuente
¿Esto maneja la entrada 1correctamente?
Peter Taylor el
@PeterTaylor Nope, no probó ese caso de la esquina. De vuelta al tablero de dibujo.
Howard
@PeterTaylor El nuevo código también funciona para entrada 1, y todavía solo tiene 24 caracteres.
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 ejemplo:

$ 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
fuente
¡Gracias, beary605 , por el golf adicional!
ESultanik
Es posible que desee contar sus caracteres de nuevo. Mi recuento de su respuesta está por debajo del recuento de su respuesta.
DavidC
@David: ¿Estás contando espacios en blanco? Acabo de verificar dos veces (haciendo catting wc -cy obtengo el mismo número.
ESultanik
Utilizo una rutina proporcionada por Wolfram Research. Cuenta el espacio en blanco necesario, creo.
DavidC
if k>0 and s[0:k]==s[k:]:breakse puede cambiar a if s and s[:k]==s[k:]:break. También puede reducir significativamente eliminando el iterador, cambiando el forciclo a while 1:y realizando a,b=a,a+bal final del ciclo while.
Strigoides
4

Pitón 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: sugerencias implementadas por beary y primo

Scleaver
fuente
85:, a.append(c) -> a+=[c]mientras que el bucle se puede poner en una sola línea,((n>1)>>(c in a)) -> (n>1)>>(c in a)
beary605
appenden realidad tiene una funcionalidad diferente que +=. Gracias por los consejos sin embargo.
scleaver
Creo que funciona de la misma manera en este caso.
beary605
(n>1)>>(c in a) -> (c in a)<1%npor 3 bytes. Y estoy de acuerdo con Beary sobre el anexo. Ya sea que agregue una referencia co se extienda apor el valor de c, es exactamente lo mismo de cualquier manera (ya que destruye inmediatamente su referencia de ctodos modos).
primo
Ah ok, mi error fue que estaba usando en a+=clugar 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
fuente
2

PHP - 61 57 bytes

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

Este script informar erróneamente 2a n=1, pero todos los demás valores son correctos.

Muestra de E / S, una serie truncable a la izquierda donde π (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
fuente
1
1<$a.$b=+$a+$a=!$i+++$b%$n+=fgets(STDIN)Oh dios, ese es un orden de explotación de explotación allí mismo.
Sr. Llama
1

PowerShell: 98

Código de golf:

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)}

Sin golf, con comentarios:

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:

No estoy seguro exactamente cuál es el límite máximo confiable para $ n con este script. Es posiblemente menos de 2 ^ 30, ya que $ x podría desbordar un int32 antes de que $ n llegue allí. Además de eso, no he probado el límite superior porque los tiempos de ejecución del script ya alcanzaron alrededor de 30 segundos en mi sistema por $ n = 1e7 (que es solo un poco más de 2 ^ 23). Por la misma razón, no me inclino rápidamente a probar y solucionar cualquier sintaxis adicional que pueda ser necesaria para actualizar las variables a uint32, int64 o uint64 cuando sea necesario para expandir el rango de este script.


Salida de muestra:

Envolví esto en otro bucle for:

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

Luego configure en $n=$ilugar de =read-host, y cambie la salida a "$i | $x"para tener una idea de la confiabilidad general del script. Aquí hay algunos de los 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 al margen: no estoy realmente seguro de cómo algunos períodos de Pisano son significativamente más cortos que $ n. ¿Es esto normal o hay algo mal con mi script? No importa: acabo de recordar que, después de 5, los números de Fibonacci rápidamente se vuelven mucho más grandes que su lugar en la secuencia. Entonces, esto tiene mucho sentido ahora.

Iszi
fuente
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

Sin golf

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

+1 byte para -nbandera. Afeitado 13 bytes gracias a Gabriel Benamy.

Silvio Mayolo
fuente
1
Puede deshacerse de $n=<>;(-6) y reemplazarlo con la -nbandera (+1), luego todas las instancias de $npueden reemplazarse con $_. Puede usar -M5.010de forma gratuita, lo que le permite usar el saycomando en lugar de print(-2). Las whileinstrucciones modificadoras no necesitan paréntesis alrededor de la condición (-2). En lugar de @{[%h]}/2, puede tener un contador $a++,antes ($m,$k)=y luego tenerlo say$a-1al final (-2). En lugar de "$m,$k"uso $m.$k(-2). Esto debería salir $k=1%$_;$a++,($m,$k)=($k,($m+$k)%$_)while!$h{$m.$k}++;say$a-1con la -nbandera, para 61 + 1 = 62 bytes.
Gabriel Benamy
Claramente, no soy tan inteligente con Perl como pensaba que era. Gracias por los consejos.
Silvio Mayolo
¡Hay muchos consejos útiles en los Consejos para jugar al golf en el hilo de Perl ! ¡Buena suerte! ^^
Gabriel Benamy
En realidad, me equivoqué: necesita en "$m,$k"lugar de $m.$k(+2), pero puede guardar 1 byte cambiando while!$ha until$h(-1). ¡Lo siento!
Gabriel Benamy
Hm? ¿Bajo qué entrada $m.$kfalla? Parecía funcionar de mi parte.
Silvio Mayolo
0

Clojure, 102 bytes

No es demasiado emocionante, itera la fórmula hasta que volvamos [1 1](espero que este sea siempre el caso). Manejo especial de (f 1)como 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
fuente