找到皮萨诺时期

Question

Fibonacci序列是一个众所周知的序列，其中每个条目都是前两个项之和，前两个项之和为1。如果我们以常数取每个项的模，则序列将成为周期序列。例如，如果我们决定计算序列mod 7，我们将得到以下结果：

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

它的周期为16。定义了一个称为皮萨诺序列的相关序列，使得当计算模n时，a(n)是fibonacci序列的周期。

任务

您应该编写一个程序或函数，当给定n时，该程序或函数将计算并输出Fibonacci序列mod n的周期。这是Pisano序列中的第n项。

必须只支持范围0 < n < 2^30上的整数。

这是一个密码-高尔夫竞争，所以你应该把你的源代码按字节的大小降到最低。

测试用例

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

Answer 1

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

Answer 2

外壳，9字节

LU_2M`%İf

在网上试试！

解释

我不确定我以前是否用过带有否定论点的U。

LU_2M`%İf  Implicit input, say n=8.
       İf  Infinite list of Fibonacci numbers:
             [1,1,2,3,5,8,13,21..
    M      Map
     `%    modulo n:
             [1,1,2,3,5,0,5,5,2,7,1,0,1,1,2..
 U_2       Cut at the start of first repeated sublist of length 2 (here [1,1]):
             [1,1,2,3,5,0,5,5,2,7,1,0]
L          Length: 12

Answer 3

Dyalog扩展，21字节

{≢(⍵|1⌽+\)⌂traj⍵|1 1}

在网上试试！

以n作为其正确参数的匿名函数(dfn)。

是如何工作的

{≢(⍵|1⌽+\)⌂traj⍵|1 1}  ⍝ Anonymous function; Input ⍵←n
{                1 1}  ⍝ Two ones (initial two values of Fibonacci)
               ⍵|      ⍝ Modulo n (to handle special case)
  (      )⌂traj        ⍝ Repeat and collect until the same value appears...
     1⌽+\              ⍝   (a,b) → (a+b,a)
   ⍵|                  ⍝   Modulo n
 ≢                     ⍝ Count the iterations before the same value appears