|
%I M2710 N1087 #246 Nov 03 2023 12:12:18
%S 1,3,8,6,20,24,16,12,24,60,10,24,28,48,40,24,36,24,18,60,16,30,48,24,
%T 100,84,72,48,14,120,30,48,40,36,80,24,76,18,56,60,40,48,88,30,120,48,
%U 32,24,112,300,72,84,108,72,20,48,72,42,58,120,60,30,48,96,140,120,136
%N Pisano periods (or Pisano numbers): period of Fibonacci numbers mod n.
%C These numbers might also have been called Fibonacci periods.
%C Also, number of perfect multi-Skolem type sequences of order n.
%C 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
%C 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
%C 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
%D 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.
%D J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 162.
%D J. H. Silverman, A Friendly Introduction to Number Theory, 3rd ed., Pearson Education, Inc, 2006, pp. 304 - 309.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D 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
%H T. D. Noe, <a href="/A001175/b001175.txt">Table of n, a(n) for n = 1..10000</a>
%H B. Avila and T. Khovanova, <a href="http://arxiv.org/abs/1403.4614">Free Fibonacci Sequences</a>, arXiv preprint arXiv:1403.4614 [math.NT], 2014 and <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Avila/avila4.html">Journal of Integer Sequences 17 (2014), #14.8.5</a>.
%H Michael Baake, Natascha Neumarker, and John A. G. Roberts, <a href="http://arxiv.org/abs/1205.1003">Orbit structure and (reversing) symmetries of toral endomorphisms on rational lattices</a>, arXiv:1205.1003 [math.DS], 2012.
%H Brennan Benfield and Michelle Manes, <a href="https://arxiv.org/abs/2202.08986">The Fibonacci Sequence is Normal Base 10</a>, arXiv:2202.08986 [math.NT], 2022.
%H K. S. Brown, <a href="http://www.mathpages.com/home/kmath078/kmath078.htm">Periods of Fibonacci Sequences mod m</a>.
%H K. S. Brown, <a href="/A001175/a001175_1.pdf">Periods of Fibonacci Sequences mod m</a>. [Cached copy in pdf format]
%H Francis N. Castro and Luis A. Medina, <a href="http://arxiv.org/abs/1603.00534">Modular periodicity of exponential sums of symmetric Boolean functions and some of its consequences</a>, arXiv:1603.00534 [math.NT], 2016.
%H D. A. Coleman, C. J. Dugan, R. A. McEwen, C. A. Reiter, and T. T. Tang, <a href="http://www.fq.math.ca/Papers1/44-1/quartreiter01_2006.pdf">Periods of (q,r)-Fibonacci sequences and Elliptic Curves</a>, Fibonacci Quart. 44 (1) (2006), 59-70.
%H Joseph Louis de Lagrange, <a href="http://gallica.bnf.fr/ark:/12148/bpt6k2299428/f145.image">Additions aux éléments d'algèbre d'Euler. Analyse indéterminée.</a> (1774), pp. 143ff.
%H H. T. Engstrom, <a href="https://doi.org/10.1090/S0002-9947-1931-1501585-5">On sequences defined by linear recurrence relations</a>, Trans. Am. Math. Soc. 33 (1) (1931), 210-218.
%H J. D. Fulton and W. L. Morris, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa16/aa1621.pdf">On arithmetical functions related to the Fibonacci numbers</a>, Acta Arithmetica 16 (1969), 105-110.
%H José María Grau and Antonio M. Oller-Marcén, <a href="http://arxiv.org/abs/1203.4066">On the last digit and the last non-zero digit of n^n in base b</a>, arXiv preprint arXiv:1203.4066 [math.NT], 2012.
%H James Grime and Brady Haran, <a href="https://www.youtube.com/watch?v=Nu-lW-Ifyec">Fibonacci Mystery</a>, Numberphile video, 2013.
%H B. H. Hannon and W. L. Morris, <a href="/A001175/a001175.pdf">Tables of Arithmetical Functions Related to the Fibonacci Numbers</a>. [Annotated and scanned copy]
%H Naoki Sato, Cyrus Hsia, Richard Hoshino, Wai Ling Yee, and Adrian Chan, editors, <a href="http://math.ca/crux/v23/n4/">Fibonacci residues</a>, Crux Mathematicorum 23:4 (1997), pp. 224-226.
%H Dan Ismailescu and Peter C. Shim, <a href="http://www.emis.de/journals/INTEGERS/papers/o65/o65.Abstract.html">On numbers that cannot be expressed as a plus-minus weighted sum of a Fibonacci number and a prime</a>, INTEGERS 14 (2014), #A65.
%H Kerry Mitchell, <a href="/A001175/a001175.jpg">Illustration of Pisano Numbers as Periods of Fibonacci Numbers Mod n</a>
%H G. Nordh, <a href="http://arXiv.org/abs/math.NT/0506155">Perfect Skolem sequences</a>, arXiv:math/0506155 [math.CO], 2005.
%H Noel Patson, <a href="https://web.archive.org/web/20171109081927/http://www.austms.org.au/Gazette/2007/Mar07/39PatsonPisano.pdf">Pisano period and permutations of n X n matrices</a>, Australian Math. Soc. Gazette, 2007.
%H Noel Patson, <a href="http://demonstrations.wolfram.com/SquareMatrixPermutations/">Square Matrix Permutations</a>.
%H M. Renault, <a href="http://webspace.ship.edu/msrenault/fibonacci/fib.htm">Periods of Fibonacci Sequence Modulo m</a>.
%H Arpan Saha and C. S. Karthik, <a href="http://arxiv.org/abs/1102.1636">A few equivalences of [the] Wall-Sun-Sun prime conjecture</a>, p. 2, arXiv:1102.1636 [math.NT], 2011.
%H Minjia Shi, Zhongyi Zhang, and Patrick Solé, <a href="https://arxiv.org/abs/1709.04582">Pisano period codes</a>, arXiv:1709.04582 [cs.IT], 2017.
%H D. D. Wall, <a href="http://www.jstor.org/stable/2309169">Fibonacci series modulo m</a>, Amer. Math. Monthly, 67 (1960), 525-532.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PisanoPeriod.html">Pisano Number</a>.
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Pisano_period">Pisano period</a>.
%H J. W. W. [J. W. Wrench], <a href="http://dx.doi.org/10.1090/S0025-5718-69-99644-6">Review of B. H. Hannon and W. L. Morris tables</a>, Math. Comp., 23 (1969), 459-460.
%F 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
%F 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
%F 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.
%F a(n) = A001177(n)*A001176(n) for n >= 1. - _Henry Bottomley_, Dec 19 2001
%F a(n) <= 2*n+2 if n is a prime > 5, by Wall's Theorems 6 and 7; see A060305, A222413, A296240. - _Jonathan Sondow_, Dec 10 2017
%F 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
%e 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
%p a:= proc(n) local f, k, l; l:= ifactors(n)[2];
%p if nops(l)<>1 then ilcm(seq(a(i[1]^i[2]), i=l))
%p else f:= [0, 1];
%p for k do f:=[f[2], f[1]+f[2] mod n];
%p if f=[0, 1] then break fi
%p od; k
%p fi
%p end:
%p seq(a(n), n=1..100); # _Alois P. Heinz_, Sep 18 2013
%t 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 *)
%t 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 *)
%t test[{0, 1, _}]:= False; test[_]:= True;
%t nest[k_][{a_, b_, c_}]:= {Mod[b, k], Mod[a+b, k], c+1};
%t A001175[1] := 1;
%t A001175[k_]:= NestWhile[nest[k], {1, 1, 1}, test][[3]];
%t Table[A001175[n], {n, 100}] (* _Leo C. Stein_, Nov 08 2019 *)
%t 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 *)
%o (Haskell)
%o a001175 1 = 1
%o a001175 n = f 1 ps 0 where
%o f 0 (1 : xs) pi = pi
%o f _ (x : xs) pi = f x xs (pi + 1)
%o ps = 1 : 1 : zipWith (\u v -> (u + v) `mod` n) (tail ps) ps
%o -- _Reinhard Zumkeller_, Jan 15 2014
%o (Sage) def a(n): return BinaryRecurrenceSequence(1,1).period(n) # _Ralf Stephan_, Jan 23 2014
%o (PARI) fibmod(n,m)=((Mod([1,1;1,0],m))^n)[1,2]
%o 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
%o entry(n)=if(n==1,return(1)); my(f=factor(n), v); v=vector(#f~, i, if(f[i,1]>9.2e18, 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)
%o 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
%o (Python)
%o from functools import reduce
%o from sympy import factorint, lcm
%o def A001175(n):
%o if n == 1:
%o return 1
%o f = factorint(n)
%o if len(f) > 1:
%o return reduce(lcm, (A001175(a**f[a]) for a in f))
%o else:
%o k,x = 1, [1,1]
%o while x != [0,1]:
%o k += 1
%o x = [x[1], (x[0]+x[1]) % n]
%o return k # _Chai Wah Wu_, Jul 17 2019
%Y Cf. A060305 (Fibonacci period mod prime(n)), A003893.
%Y Cf. A001178 (Fibonacci frequency), A001179 (Leonardo logarithm), A235702 (fixed points), A066853 (number of elements in the set of residua), A222413, A296240 (Pisano quotients for primes).
%K nonn,nice
%O 1,2
%A _N. J. A. Sloane_
|
