The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A001175 Pisano periods (or Pisano numbers): period of Fibonacci numbers mod n. (Formerly M2710 N1087) 157
 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 T. D. Noe, Table of n, a(n) for n = 1..10000 B. Avila and T. Khovanova, Free Fibonacci Sequences, arXiv preprint arXiv:1403.4614 [math.NT], 2014 and Journal of Integer Sequences 17 (2014), #14.8.5. Michael Baake, Natascha Neumarker, and John A. G. Roberts, Orbit structure and (reversing) symmetries of toral endomorphisms on rational lattices, arXiv:1205.1003 [math.DS], 2012. Brennan Benfield and Michelle Manes, The Fibonacci Sequence is Normal Base 10, arXiv:2202.08986 [math.NT], 2022. K. S. Brown, Periods of Fibonacci Sequences mod m. K. S. Brown, Periods of Fibonacci Sequences mod m. [Cached copy in pdf format] Francis N. Castro and Luis A. Medina, Modular periodicity of exponential sums of symmetric Boolean functions and some of its consequences, arXiv:1603.00534 [math.NT], 2016. D. A. Coleman, C. J. Dugan, R. A. McEwen, C. A. Reiter, and T. T. Tang, Periods of (q,r)-Fibonacci sequences and Elliptic Curves, Fibonacci Quart. 44 (1) (2006), 59-70. Joseph Louis de Lagrange, Additions aux éléments d'algèbre d'Euler. Analyse indéterminée. (1774), pp. 143ff. H. T. Engstrom, On sequences defined by linear recurrence relations, Trans. Am. Math. Soc. 33 (1) (1931), 210-218. J. D. Fulton and W. L. Morris, On arithmetical functions related to the Fibonacci numbers, Acta Arithmetica 16 (1969), 105-110. José María Grau and Antonio M. Oller-Marcén, On the last digit and the last non-zero digit of n^n in base b, arXiv preprint arXiv:1203.4066 [math.NT], 2012. James Grime and Brady Haran, Fibonacci Mystery, Numberphile video, 2013. B. H. Hannon and W. L. Morris, Tables of Arithmetical Functions Related to the Fibonacci Numbers. [Annotated and scanned copy] Naoki Sato, Cyrus Hsia, Richard Hoshino, Wai Ling Yee, and Adrian Chan, editors, Fibonacci residues, Crux Mathematicorum 23:4 (1997), pp. 224-226. Dan Ismailescu and Peter C. Shim, On numbers that cannot be expressed as a plus-minus weighted sum of a Fibonacci number and a prime, INTEGERS 14 (2014), #A65. G. Nordh, Perfect Skolem sequences, arXiv:math/0506155 [math.CO], 2005. N. Patson, Pisano period and permutations of n X n matrices, Australian Math. Soc. Gazette, 2007. Noel Patson, Square Matrix Permutations. M. Renault, Periods of Fibonacci Sequence Modulo m. Arpan Saha and C. S. Karthik, A few equivalences of [the] Wall-Sun-Sun prime conjecture, p. 2, arXiv:1102.1636 [math.NT], 2011. Minjia Shi, Zhongyi Zhang, and Patrick Solé, Pisano period codes, arXiv:1709.04582 [cs.IT], 2017. D. D. Wall, Fibonacci series modulo m, Amer. Math. Monthly, 67 (1960), 525-532. Eric Weisstein's World of Mathematics, Pisano Number. Wikipedia, Pisano period. J. W. W. [J. W. Wrench], Review of B. H. Hannon and W. L. Morris tables, Math. Comp., 23 (1969), 459-460. 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(n) = A001177(n)*A001176(n) for n >= 1. - Henry Bottomley, Dec 19 2001 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 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);       if nops(l)<>1 then ilcm(seq(a(i^i), i=l))     else f:= [0, 1];          for k do f:=[f, f+f mod n];                   if f=[0, 1] then break fi          od; k       fi     end: seq(a(n), n=1..100);  # Alois P. Heinz, Sep 18 2013 MATHEMATICA Table[a={1, 0}; a0=a; k=0; While[k++; s=Mod[Plus@@a, n]; a=RotateLeft[a]; a[]=s; a!=a0]; k, {n, 2, 100}] (* T. D. Noe, Jul 19 2005 *) a=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 := 1; A001175[k_]:= NestWhile[nest[k], {1, 1, 1}, test][]; Table[A001175[n], {n, 100}] (* Leo C. Stein, Nov 08 2019 *) Module[{nn=1000, fibs}, fibs=Fibonacci[Range[nn]]; Table[Length[ FindTransientRepeat[ Mod[fibs, n], 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 -- Reinhard Zumkeller, Jan 15 2014 (Sage) def a(n): return BinaryRecurrenceSequence(1, 1).period(n) # Ralf Stephan, Jan 23 2014 (PARI) 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]>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=3< 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, (x+x) % n]         return k # Chai Wah Wu, Jul 17 2019 CROSSREFS Cf. A060305 (Fibonacci period mod prime(n)), A003893. 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). Sequence in context: A225267 A320541 A072396 * A093725 A347118 A306933 Adjacent sequences:  A001172 A001173 A001174 * A001176 A001177 A001178 KEYWORD nonn,nice AUTHOR STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 26 18:11 EDT 2022. Contains 357002 sequences. (Running on oeis4.)