|
|
A001175
|
|
Pisano periods (or Pisano numbers): period of Fibonacci numbers mod n.
(Formerly M2710 N1087)
|
|
164
|
|
|
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, 72, 84, 108, 72, 20, 48, 72, 42, 58, 120, 60, 30, 48, 96, 140, 120, 136
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
These numbers might also have been called Fibonacci periods.
Also, number of perfect multi-Skolem type sequences of order n.
Index the Fibonacci numbers so that 3 is the fourth number. If the modulo base is a Fibonacci number (>=3) with an even index, the period is twice the index. If the base is a Fibonacci number (>=5) with an odd index, the period is 4 times the index. - Kerry Mitchell, Dec 11 2005
Each row of the image represents a different modulo base n, from 1 at the bottom to 24 at the top. The columns represent the Fibonacci numbers mod n, from 0 mod n at the left to 59 mod n on the right. In each cell, the brightness indicates the value of the residual, from dark for 0 to near-white for n-1. Blue squares on the left represent the first period; the number of blue squares is the Pisano number. - Kerry Mitchell, Feb 02 2013
a(n) = least positive integer k such that F(k) == 0 (mod n) and F(k+1) == 1 (mod n), where F = A000045 is the Fibonacci sequence. a(n) exists for all n by Dirichlet's box principle and the fact that the positive integers are well-ordered. Cf. Saha and Karthik (2011). - L. Edson Jeffery, Feb 12 2014
|
|
REFERENCES
|
B. H. Hannon and W. L. Morris, Tables of Arithmetical Functions Related to the Fibonacci Numbers. Report ORNL-4261, Oak Ridge National Laboratory, Oak Ridge, Tennessee, Jun 1968.
J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 162.
J. H. Silverman, A Friendly Introduction to Number Theory, 3rd ed., Pearson Education, Inc, 2006, pp. 304 - 309.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
S. Vajda, Fibonacci and Lucas numbers and the Golden Section, Ellis Horwood Ltd., Chichester, 1989. See p. 89. - N. J. A. Sloane, Feb 20 2013
|
|
LINKS
|
Naoki Sato, Cyrus Hsia, Richard Hoshino, Wai Ling Yee, and Adrian Chan, editors, Fibonacci residues, Crux Mathematicorum 23:4 (1997), pp. 224-226.
Minjia Shi, Zhongyi Zhang, and Patrick Solé, Pisano period codes, arXiv:1709.04582 [cs.IT], 2017.
|
|
FORMULA
|
Let the prime factorization of n be p1^e1...pk^ek. Then a(n) = lcm(a(p1^e1), ..., a(pk^ek)). - T. D. Noe, May 02 2005
a(n) = n-1 if n is a prime > 5 included in A003147 ( n = 11, 19, 31, 41, 59, 61, 71, 79, 109...). - Benoit Cloitre, Jun 04 2002
K. S. Brown shows that a(n)/n <= 6 for all n and a(n)=6n if and only if n has the form 2*5^k.
a(2^k) = 3*2^(k-1) for k > 0. In general, if a(p) != a(p^2) for p prime, then a(p^k) = p^(k-1)*a(p) [Wall, 1960]. - Chai Wah Wu, Feb 25 2022
|
|
EXAMPLE
|
For n=4, take the Fibonacci sequence (A000045), 1, 1, 2, 3, 5, 8, 13, 21, ... (mod 4), which gives 1, 1, 2, 3, 1, 0, 1, 1, .... This repeats a pattern of length 6, so a(4) = 6. - Michael B. Porter, Jul 19 2016
|
|
MAPLE
|
a:= proc(n) local f, k, l; l:= ifactors(n)[2];
if nops(l)<>1 then ilcm(seq(a(i[1]^i[2]), i=l))
else f:= [0, 1];
for k do f:=[f[2], f[1]+f[2] mod n];
if f=[0, 1] then break fi
od; k
fi
end:
|
|
MATHEMATICA
|
Table[a={1, 0}; a0=a; k=0; While[k++; s=Mod[Plus@@a, n]; a=RotateLeft[a]; a[[2]]=s; a!=a0]; k, {n, 2, 100}] (* T. D. Noe, Jul 19 2005 *)
a[1]=1; a[n_]:= For[k = 1, True, k++, If[Mod[Fibonacci[k], n]==0 && Mod[ Fibonacci[k+1], n]==1, Return[k]]]; Table[a[n], {n, 100}] (* Jean-François Alcover, Feb 11 2015 *)
test[{0, 1, _}]:= False; test[_]:= True;
nest[k_][{a_, b_, c_}]:= {Mod[b, k], Mod[a+b, k], c+1};
A001175[k_]:= NestWhile[nest[k], {1, 1, 1}, test][[3]];
Module[{nn=1000, fibs}, fibs=Fibonacci[Range[nn]]; Table[Length[ FindTransientRepeat[ Mod[fibs, n], 2][[2]]], {n, 70}]] (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, Nov 02 2020 *)
|
|
PROG
|
(Haskell)
a001175 1 = 1
a001175 n = f 1 ps 0 where
f 0 (1 : xs) pi = pi
f _ (x : xs) pi = f x xs (pi + 1)
ps = 1 : 1 : zipWith (\u v -> (u + v) `mod` n) (tail ps) ps
(Sage) def a(n): return BinaryRecurrenceSequence(1, 1).period(n) # Ralf Stephan, Jan 23 2014
(PARI) minWSS=2^64; \\ PrimeGrid search
fibmod(n, m)=((Mod([1, 1; 1, 0], m))^n)[1, 2]
entryp(p)=my(k=p+[0, -1, 1, 1, -1][p%5+1], f=factor(k)); for(i=1, #f[, 1], for(j=1, f[i, 2], if((Mod([1, 1; 1, 0], p)^(k/f[i, 1]))[1, 2], break); k/=f[i, 1])); k
entry(n)=if(n==1, return(1)); my(f=factor(n), v); v=vector(#f~, i, if(f[i, 1]>=minWSS, entryp(f[i, 1]^f[i, 2]), entryp(f[i, 1])*f[i, 1]^(f[i, 2] - 1))); if(f[1, 1]==2&&f[1, 2]>1, v[1]=3<<max(f[1, 2]-2, 1)); lcm(v)
a(n)=if(n==1, return(1)); my(k=entry(n)); forstep(i=k, n^2, k, if(fibmod(i-1, n)==1, return(i))) \\ Charles R Greathouse IV, Feb 13 2014; updated Dec 14 2016; updated Aug 24 2021; updated Jul 08 2024
(Python)
from functools import reduce
from sympy import factorint, lcm
if n == 1:
return 1
f = factorint(n)
if len(f) > 1:
return reduce(lcm, (A001175(a**f[a]) for a in f))
else:
k, x = 1, [1, 1]
while x != [0, 1]:
k += 1
x = [x[1], (x[0]+x[1]) % n]
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|