login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

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)
104
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]. - 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.

Review of B. H. Hannon and W. L. Morris tables, Math. Comp., 23 (1969), 459-460.

J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 162.

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, 2014

Michael Baake, Natascha Neumarker and John A. G. Roberts, Orbit structure and (reversing) symmetries of toral endomorphisms on rational lattices.

K. S. Brown, Periods of Fibonacci Sequences mod m

D. A. Coleman et al., Periods of (q,r)-Fibonacci sequences and Elliptic Curves, Fibonacci Quart. 44, no 1 (2006) 59-70.

J. D. Fulton and W. L. Morris, On arithmetical functions related to the Fibonacci numbers, Acta Arithmetica, 16 (1969), 105-110.

Jose Maria Grau and Antonio M. Oller-Marcen, On the last digit and the last non-zero digit of n^n in base b, Arxiv preprint arXiv:1203.4066, 2012. - From N. J. A. Sloane, Sep 16 2012

Cyrus Hsia et al., editors Fibonacci residues, Crux Mathematicorum 23:4 pp. 224-226.

Joseph Louis de Lagrange, Additions aux éléments d'algèbre d'Euler. Analyse indéterminée. (1774), pp. 143ff.

Kerry Mitchell, Illustration of Pisano Numbers as Periods of Fibonacci Numbers Mod n

G. Nordh, Perfect Skolem sequences

N. Patson, Pisano period and permutations of n X n matrices, Australian Math. Soc. Gazette, 2007.

Noel Patson,Square Matrix Permutations [From Noel Patson (n.patson(AT)cqu.edu.au), Mar 28 2010]

M. Renault, Periods of Fibonacci Sequence Modulo m

Arpan Saha and Karthik C S, A few equivalences of Wall-Sun-Sun prime conjecture, p. 2.

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

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

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:

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[[2]]=s; a!=a0]; k, {n, 2, 100}] (* T. D. Noe, Jul 19 2005 *)

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]

entry_p(p)=my(k=1, c=Mod(1, p), o); while(c, [o, c]=[c, c+o]; k++); k

entry(n)=if(n==1, return(1)); my(f=factor(n), v); v=vector(#f~, i, if(f[i, 1]>1e14, entry_p(f[i, 1]^f[i, 2]), entry_p(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

CROSSREFS

Cf. A060305 (Fibonacci period mod prime(n)), A003893.

Cf. A001178 (Fibonacci frequency), A001179 (Leonardo logarithm), A235702 (fixed points).

Sequence in context: A164654 A225267 A072396 * A093725 A011413 A010629

Adjacent sequences:  A001172 A001173 A001174 * A001176 A001177 A001178

KEYWORD

nonn,nice

AUTHOR

N. J. A. Sloane.

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified August 23 05:20 EDT 2014. Contains 245977 sequences.