La séquence de Fibonacci est une séquence bien connue dans laquelle chaque entrée est la somme des deux précédentes et les deux premières entrées sont 1. Si nous prenons le modulo de chaque terme par une constante, la séquence deviendra périodique. Par exemple, si nous décidions de calculer la séquence mod 7, nous obtiendrions ce qui suit:

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

Celui-ci a une période de 16. Une séquence apparentée, appelée la séquence de Pisano , est définie telle que a(n)c'est la période de la séquence des fibonacci lorsqu'elle est calculée modulo n.

Tâche

Vous devrez écrire un programme ou une fonction qui, une fois donné n, calculera et affichera la période du mod de séquence de Fibonacci n. C'est le nième terme de la séquence de Pisano.

Vous ne devez prendre en charge que des entiers sur la plage 0 < n < 2^30

Il s'agit d'une compétition de golf de code , vous devez donc viser à minimiser la taille de votre code source telle que notée par octets.

Cas de test

1  -> 1
2  -> 3
3  -> 8
4  -> 6
5  -> 20
6  -> 24
7  -> 16
8  -> 12
9  -> 24
10 -> 60
11 -> 10
12 -> 24

GolfScript ( 28 25 24 23 caractères)

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

Prend l'entrée dans stdin, la laisse sur stdout (ou sur la pile, si vous souhaitez la traiter plus avant ...)

Cela gère correctement les cas d'angle ( démo ).

En tant que point d'intérêt pour les programmeurs GolfScript, je pense que c'est le premier programme que j'ai écrit avec un dépliant qui est sorti plus court que les autres approches que j'ai essayées.

GolfScript, 24 caractères

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

Prochaine itération d'une implémentation GolfScript. La deuxième version gère désormais également 1 correctement. C'est devenu assez long mais peut-être que quelqu'un peut trouver un moyen de raccourcir cette version. Vous pouvez essayer la version ci-dessus en ligne .

Python, 188 132 101 101 95 87 caractères

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

Usage

$ echo 10 | python pisano.py
60

Par exemple:

$ 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

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

Edit: Suggestions mises en œuvre par beary et primo

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

PHP - 61 57 octets

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

Ce script rapportera 2par erreur pour n=1, mais toutes les autres valeurs sont correctes.

Exemple d'E / S, une série tronçable à gauche où π (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

PowerShell: 98

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

Non golfé, avec commentaires:

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

Remarques:

Je ne sais pas exactement quelle est la limite maximale fiable pour $ n avec ce script. C'est probablement moins de 2 ^ 30, car $ x pourrait déborder un int32 avant que $ n n'y arrive. En plus de cela, je n'ai pas testé la limite supérieure moi-même car les durées d'exécution du script atteignaient déjà environ 30 secondes sur mon système pour $ n = 1e7 (ce qui n'est que légèrement supérieur à 2 ^ 23). Pour la même raison, je ne suis pas rapidement enclin à tester et à dépanner la syntaxe supplémentaire nécessaire pour mettre à niveau les variables vers uint32, int64 ou uint64 lorsque cela est nécessaire afin d'élargir la plage de ce script.

Exemple de sortie:

J'ai enveloppé cela dans une autre boucle for:

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

Définissez ensuite $n=$iau lieu de =read-hostet modifiez la sortie "$i | $x"pour obtenir une idée de la fiabilité générale du script. Voici une partie de la sortie:

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

Sidenote: Je ne sais pas vraiment comment certaines périodes Pisano sont significativement plus courtes que $ n. Est-ce normal ou quelque chose ne va pas avec mon script? Peu importe - je viens de me rappeler qu'après 5, les nombres de Fibonacci deviennent rapidement beaucoup plus grands que leur place dans la séquence. Donc, cela a un sens total maintenant.

Perl, 75 , 61 , 62 + 1 = 63

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

Usage

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

Non golfé

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

+1 octet pour le -ndrapeau. Rasé de 13 octets grâce à Gabriel Benamy.

Clojure, 102 octets

Pas trop excitant, itère la formule jusqu'à ce que nous revenions [1 1](j'espère que c'est toujours le cas). Traitement spécial au (f 1)fur et à mesure qu'il 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))