A060305 -id:A060305 - cp's OEIS frontend

A001175 Pisano periods (or Pisano numbers): period of Fibonacci numbers mod n.

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

Offset: 1

N. J. A. Sloane

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

			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

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

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.
Kerry Mitchell, Illustration of Pisano Numbers as Periods of Fibonacci Numbers Mod n
G. Nordh, Perfect Skolem sequences, arXiv:math/0506155 [math.CO], 2005.
Noel 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.

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

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

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

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[1] := 1;
A001175[k_]:= NestWhile[nest[k], {1, 1, 1}, test][[3]];
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][[2]]],{n,70}]] (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, Nov 02 2020 *)

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<Charles R Greathouse IV, Feb 13 2014; updated Dec 14 2016; updated Aug 24 2021; updated Jul 08 2024

from functools import reduce
from sympy import factorint, lcm
def A001175(n):
    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]
        return k # Chai Wah Wu, Jul 17 2019

def a(n): return BinaryRecurrenceSequence(1,1).period(n) # Ralf Stephan, Jan 23 2014

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

A001177 Fibonacci entry points: a(n) = least k >= 1 such that n divides Fibonacci number F_k (=A000045(k)).

Original entry on oeis.org

1, 3, 4, 6, 5, 12, 8, 6, 12, 15, 10, 12, 7, 24, 20, 12, 9, 12, 18, 30, 8, 30, 24, 12, 25, 21, 36, 24, 14, 60, 30, 24, 20, 9, 40, 12, 19, 18, 28, 30, 20, 24, 44, 30, 60, 24, 16, 12, 56, 75, 36, 42, 27, 36, 10, 24, 36, 42, 58, 60, 15, 30, 24, 48, 35, 60, 68, 18, 24, 120

Offset: 1

N. J. A. Sloane

nonn

In the formula, the relation a(p^e) = p^(e-1)*a(p) is called Wall's conjecture, which has been verified for primes up to 10^14. See A060305. Primes for which this relation fails are called Wall-Sun-Sun primes. - T. D. Noe, Mar 03 2009
All solutions to F_m == 0 (mod n) are given by m == 0 (mod a(n)). For a proof see, e.g., Vajda, p. 73. [Old comment changed by Wolfdieter Lang, Jan 19 2015]
If p is a prime of the form 10n +- 1 then a(p) is a divisor of p-1. If q is a prime of the form 10n +- 3 then a(q) is a divisor of q+1. - Robert G. Wilson v, Jul 07 2007
Definition 1 in Riasat (2011) calls this k(n), or sometimes just k. Corollary 1 in the same paper, "every positive integer divides infinitely many Fibonacci numbers," demonstrates that this sequence is infinite. - Alonso del Arte, Jul 27 2013
If p is a prime then a(p) <= p+1. This is because if p is a prime then exactly one of the following Fibonacci numbers is a multiple of p: F(p-1), F(p) or F(p+1). - Dmitry Kamenetsky, Jul 23 2015
From Renault 1996:
  1. a(lcm(n,m)) = lcm(a(n), a(m)).
  2. if n|m then a(n)|a(m).
  3. if m has prime factorization m=p1^e1 * p2^e2 * ... * pn^en then a(m) = lcm(a(p1^e1), a(p2^e2), ..., a(pn^en)). - Dmitry Kamenetsky, Jul 23 2015
a(n)=n if and only if n=5^k or n=12*5^k for some k >= 0 (see Marques 2012). - Dmitry Kamenetsky, Aug 08 2015
Every positive integer (except 2) eventually appears in this sequence. This is because every Fibonacci number bigger than 1 (except Fibonacci(6)=8 and Fibonacci(12)=144) has at least one prime factor that is not a factor of any earlier Fibonacci number (see Knott reference). Let f(n) be such a prime factor for Fibonacci(n); then a(f(n))=n. - Dmitry Kamenetsky, Aug 08 2015
We can reconstruct the Fibonacci numbers from this sequence using the formula Fibonacci(n+2) = 1 + Sum_{i: a(i) <= n} phi(i)*floor(n/a(i)), where phi(n) is Euler's totient function A000010 (see the Stroinski link). For example F(6) = 1 + phi(1)*floor(4/a(1)) + phi(2)*floor(4/a(2)) + phi(3)*floor(4/a(4)) = 1 + 1*4 + 1*1 + 2*1 = 8. - Peter Bala, Sep 10 2015
Conjecture: Sum_{d|n} phi(d)*a(d) = A232656(n). - Logan J. Kleinwaks, Oct 28 2017
a(F_m) = m for all m > 1. Indeed, let (b(j)) be defined by b(1)=b(2)=1, and b(j+2) = (b(j) + b(j+1)) mod n. Then a(n) equals the index of the first occurrence of 0 in (b(j)). Example: if n=4 then b = A079343 = 1,1,2,3,1,0,1,1,..., so a(4)=6. If n is a Fibonacci number n=F_m, then obviously a(n)=m. Note that this gives a simple proof of the fact that all integers larger than 2 occur in (a(n)). - Michel Dekking, Nov 10 2017

			a(4) = 6 because the smallest Fibonacci number that 4 divides is F(6) = 8.
a(5) = 5 because the smallest Fibonacci number that 5 divides is F(5) = 5.
a(6) = 12 because the smallest Fibonacci number that 6 divides is F(12) = 144.
From _Wolfdieter Lang_, Jan 19 2015: (Start)
a(2) = 3, hence 2 | F(m) iff m = 2*k, for k >= 0;
a(3) = 4, hence 3 | F(m) iff m = 4*k, for k >= 0;
etc. See a comment above with the Vajda reference.
(End)

A. Brousseau, Fibonacci and Related Number Theoretic Tables. Fibonacci Association, San Jose, CA, 1972, p. 25.
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, June 1968.
Alfred S. Posamentier & Ingmar Lehmann, The (Fabulous) Fibonacci Numbers, Afterword by Herbert A. Hauptman, Nobel Laureate, 2. 'The Minor Modulus m(n)', Prometheus Books, NY, 2007, page 329-342.
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.
N. N. Vorob'ev, Fibonacci numbers, Blaisdell, NY, 1961.

T. D. Noe, Table of n, a(n) for n = 1..10000
A. Allard and P. Lecomte, Periods and entry points in Fibonacci sequence, Fib. Quart. 17 (1) (1979) 51-57.
R. C. Archibald (?), Review of B. H. Hannon and W. L. Morris, Tables of arithmetical functions related to the Fibonacci numbers, Math. Comp., 23 (1969), 459-460.
B. Avila and T. Khovanova, Free Fibonacci Sequences, arXiv preprint arXiv:1403.4614 [math.NT], 2014 and J. Int. Seq. 17 (2014) # 14.8.5.
Alfred Brousseau, Fibonacci and Related Number Theoretic Tables, Fibonacci Association, San Jose, CA, 1972. See p. 25.
J. D. Fulton and W. L. Morris, On arithmetical functions related to the Fibonacci numbers, Acta Arithmetica, 16 (1969), 105-110.
Molly FitzGibbons, Steven J. Miller, and Amanda Verga, Dynamics of the Fibonacci Order of Appearance Map, arXiv:2309.14501 [math.NT], 2023.
Ramon Glez-Regueral, An entry-point algorithm for high-speed factorization, Thirteenth Internat. Conf. Fibonacci Numbers Applications, Patras, Greece, 2008.
B. H. Hannon and W. L. Morris, Tables of Arithmetical Functions Related to the Fibonacci Numbers [Annotated and scanned copy]
Ron Knott, The first 300 Fibonacci numbers factorized
Paolo Leonetti and Carlo Sanna, On the greatest common divisor of n and the nth Fibonacci number, arXiv:1704.00151 [math.NT], 2017. See z(n).
Diego Marques, Fixed points of the order of appearance in the Fibonacci sequence, Fibonacci Quart. 50:4 (2012), pp. 346-352.
Diego Marques, The order of appearance of the product of consecutive Lucas numbers, Fibonacci Quarterly, 51 (2013), 38-43.
Diego Marques, Sharper upper bounds for the order of appearance in the fibonacci sequence, Fibonacci Quarterly, 51 (2013), pp. 233-238.
Zuzana Masáková and Edita Pelantová, Midy's Theorem in non-integer bases and divisibility of Fibonacci numbers, arXiv:2401.03874 [math.NT], 2024. See page 9.
Marc Renault, The Fibonacci sequence under various moduli, Masters Thesis, Wake Forest University, 1996.
Samin Riasat, Z[phi] and the Fibonacci Sequence Modulo n, Mathematical Reflections 1 (2011): 1 - 7.
H. J. A. Salle, A Maximum Value for the Rank of Apparition of Integers in Recursive Sequences , Fibonacci Quart. 13.2 (1975) 159-161.
U. Stroinski, Connection between Euler's totient function and Fibonacci numbers, Mathematics Stack Exchange, Feb 17 2015.
D. D. Wall, Fibonacci series modulo m, Amer. Math. Monthly 67 (6) (1960) 525-532.
Eric Weisstein, MathWorld: Wall-Sun-Sun Prime

Cf. A000045, A001175, A001176, A060383, A001602. First occurrence of k is given in A131401. A233281 gives such k that a(k) is a prime.
From Antti Karttunen, Dec 21 2013: (Start)
Various derived sequences:
A047930(n) = A000045(a(n)).
A037943(n) = A000045(a(n))/n.
A217036(n) = A000045(a(n)-1) mod n.
A132632(n) = a(n^2).
A132633(n) = a(n^3).
A214528(n) = a(n!).
A215011(n) = a(A000217(n)).
A215453(n) = a(n^n).
Analogous sequence for the tribonacci numbers: A046737, for Lucas numbers: A223486, for Pell numbers: A214028.
Cf. also A000057, A106535, A120255, A120256, A175026, A213648, A214031, A214781, A214783, A230359, A233283, A233285, A233287. (End)

a001177 n = head [k | k <- [1..], a000045 k `mod` n == 0]
-- Reinhard Zumkeller, Jan 15 2014

A001177 := proc(n)
        for k from 1 do
                if combinat[fibonacci](k) mod n = 0 then
                        return k;
                end if;
        end do:
end proc: # R. J. Mathar, Jul 09 2012
N:= 1000: # to get a(1) to a(N)
L:= ilcm($1..N):
count:= 0:
for n from 1 while count < N do
  fn:= igcd(L,combinat:-fibonacci(n));
  divs:= select(`<=`,numtheory:-divisors(fn),N);
  for d in divs do if not assigned(A[d]) then count:= count+1; A[d]:= n fi od:
od:
seq(A[n],n=1..N); # Robert Israel, Oct 14 2015

fibEntry[n_] := Block[{k = 1}, While[ Mod[ Fibonacci@k, n] != 0, k++ ]; k]; Array[fibEntry, 74] (* Robert G. Wilson v, Jul 04 2007 *)

a(n)=if(n<0,0,s=1;while(fibonacci(s)%n>0,s++);s) \\ Benoit Cloitre, Feb 10 2007

ap(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
a(n)=if(n==1,return(1)); my(f=factor(n), v); v=vector(#f~, i, if(f[i,1]>1e14,ap(f[i,1]^f[i,2]), ap(f[i,1])*f[i,1]^(f[i,2]-1))); if(f[1,1]==2&&f[1,2]>1, v[1]=3<Charles R Greathouse IV, May 08 2017

(define (A001177 n) (let loop ((k 1)) (cond ((zero? (modulo (A000045 k) n)) k) (else (loop (+ k 1)))))) ;; Antti Karttunen, Dec 21 2013

A001175(n) = A001176(n) * a(n) for n >= 1.
a(n) = n if and only if n is of form 5^k or 12*5^k (proved in Marques paper), a(n) = n - 1 if and only if n is in A106535, a(n) = n + 1 if and only if n is in A000057, a(n) = n + 5 if and only if n is in 5*A000057, ... - Benoit Cloitre, Feb 10 2007
a(1) = 1, a(2) = 3, a(4) = 6 and for e > 2, a(2^e) = 3*2^(e-2); a(5^e) = 5^e; and if p is an odd prime not 5, then a(p^e) = p^max(0, e-s)*a(p) where s = valuation(A000045(a(p)), p) (Wall's conjecture states that s = 1 for all p). If (m, n) = 1 then a(m*n) = lcm(a(m), a(n)). See Posamentier & Lahmann. - Robert G. Wilson v, Jul 07 2007; corrected by Max Alekseyev, Oct 19 2007, Jun 24 2011
Apparently a(n) = A213648(n) + 1 for n >= 2. - Art DuPre, Jul 01 2012
a(n) < n^2. [Vorob'ev]. - Zak Seidov, Jan 07 2016
a(n) < n^2 - 3n + 6. - Jinyuan Wang, Oct 13 2018
a(n) <= 2n [Salle]. - Jon Maiga, Apr 25 2019

Definition corrected by Wolfdieter Lang, Jan 19 2015

A071774 Related to Pisano periods: integers k such that the period of Fibonacci numbers mod k equals 2*(k+1).

Original entry on oeis.org

3, 7, 13, 17, 23, 37, 43, 53, 67, 73, 83, 97, 103, 127, 137, 157, 163, 167, 173, 193, 197, 223, 227, 257, 277, 283, 293, 313, 317, 337, 367, 373, 383, 397, 433, 443, 457, 463, 467, 487, 503, 523, 547, 577, 587, 593, 607, 613, 617, 643, 647, 653, 673, 683, 727

Offset: 1

Benoit Cloitre, Jun 04 2002

Terms are primes with final digit 3 or 7.
Apparently these are the primes given in A003631 without 2 and A216067. - Klaus Purath, Dec 11 2020
If k is a term, then for m=5*k the period of Fibonacci numbers mod m equals 2*(m+5). - Matthew Goers, Jan 13 2021

Michael De Vlieger, Table of n, a(n) for n = 1..3969
Bob Bastasz, Lyndon words of a second-order recurrence, Fibonacci Quarterly (2020) Vol. 58, No. 5, 25-29.

Cf. A001175, A060305, A071776.

Cf. A003631, A216067.

Select[Prime@ Range[129], Function[n, Mod[Last@ NestWhile[{Mod[#2, n], Mod[#1 + #2, n], #3 + 1} & @@ # &, {1, 1, 1}, #[[1 ;; 2]] != {0, 1} &], n] == Mod[2 (n + 1), n] ]] (* Michael De Vlieger, Mar 31 2021, after Leo C. Stein at A001175 *)

for(n=2,5000,t=2*(n+1);good=1;if(fibonacci(t)%n==0, for(s=0,t,if(fibonacci(t+s)%n!=fibonacci(s)%n,good=0;break); if(s>1&&s

forprime(p=3,3000,if(p%5==2||p%5==3,a=1;b=0;c=1;while(a!=0||b!=1,c++;d=a;a=b;a=(a+d)%p;b=d%p);if(c==(2*(p+1)),print1(p",")))) /* V. Raman, Nov 22 2012 */

More terms from Lambert Klasen (Lambert.Klasen(AT)gmx.net), Dec 21 2004

A296240 Pisano quotients: a(n) = (p-1)/k(p) if p == +- 1 mod 5, = (2*p+2)/k(p) if p == +- 2 mod 5, where p = prime(n) and k(p) = Pisano period(p).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 3, 1, 3, 1, 1, 1, 3, 1, 3, 1, 1, 1, 1, 1, 2, 1, 1, 1, 9, 5, 1, 1, 2, 9, 1, 1, 1, 1, 3, 1, 1, 1, 5, 1, 1, 7, 1, 1, 1, 3, 1, 3, 2, 3, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 5, 1, 1, 1, 1, 1, 1, 10, 1, 1, 1, 1, 1, 1, 1, 2, 20, 1, 6, 1, 9, 3, 1, 1, 1, 1, 1, 1

Offset: 4

Jonathan Sondow, Dec 09 2017

nonn

Wall (1960) in Theorems 6 and 7 proved that a(n) is an integer for n >= 4. Jarden (1946) proved that the sequence is unbounded. See Elsenhans and Jahnel (2010), pp. 1-2.

A. Elsenhans and J. Jahnel, The Fibonacci sequence modulo p^2 -- An investigation by computer for p < 10^14, arXiv 1006.0824 [math.NT], 2010.
D. Jarden, Two theorems on Fibonacci's sequence, Amer. Math. Monthly, 53 (1946), 425-427.
D. D. Wall, Fibonacci series modulo m, Amer. Math. Monthly, 67 (1960), 525-532.
Wikipedia, Wall-Sun-Sun prime

Cf. A001175, A092330, A060305, A222361, A222413.

With[{p = Prime[n]}, T = Table[a = {1, 0}; a0 = a; k = 0; While[k++; s = Mod[Plus @@ a, p]; a = RotateLeft[a]; a[[2]] = s; a != a0]; k, {n, 1, 130}]; Table[L = KroneckerSymbol[p, 5]; (3 - L)/2 (p - L)/T[[n]], {n, 4, 130}]] (* after T. D. Noe *)

a(n) = (3 - L(p))/2 * (p - L(p)) / k(p), where p = prime(n), L(p) = Legendre(p|5), and k(p) = Pisano period(p) = A001175(p).

a(n) > 1 if and only if prime(n) is in A222413.

A222413 All primes p > 5 such that A001175(p) is smaller than the maximal value permitted by Wall's Theorems 6 and 7.

Original entry on oeis.org

29, 47, 89, 101, 107, 113, 139, 151, 181, 199, 211, 229, 233, 263, 281, 307, 331, 347, 349, 353, 401, 421, 461, 509, 521, 541, 557, 563, 619, 661, 677, 691, 709, 743, 761, 769, 797, 809, 811, 829, 859, 881, 911, 919, 941, 953, 967, 977, 991, 1009, 1021, 1031, 1049, 1061, 1069, 1087, 1097, 1103, 1109, 1151, 1217, 1223, 1229, 1231, 1249, 1277

Offset: 1

N. J. A. Sloane, Feb 28 2013

nonn

Included because A001175 is still a mystery (as are many sequences of the same type).
A222414 gives the corresponding values of A001175(a(n)).
The maximal value for a prime p > 5 is p-1 if p == 1 or 9 (mod 10) and 2*(p+1) if p == 3 or 7 (mod 10). See Wall's Theorems 6 and 7. These values are given in A253806. - Wolfdieter Lang, Jan 16 2015
Prime(n) is a member if and only if A296240(n) > 1. - Jonathan Sondow, Dec 10 2017

			From _Wolfdieter Lang_, Jan 16 2015: (Start)
a(1) = 29 because A001175(29) = 14 but the maximal value is 29 - 1 = 28.
a(2) = 47 because A001175(47) = 32 but the maximal value is 2*(47 + 1) = 96.
All other primes p > 5 have A001175(p) = maximal value for p.
E.g., p = 11 has  A001175(11) = 11-1 = 10 and  p = 7 has A001175(7) = 2*(7 + 1) = 16. (End)

D. D. Wall, Fibonacci series modulo m, Amer. Math. Monthly, 67 (1960), 525-532.

Cf. A001175, A060305, A222414, A296240.

Cf. A001176, A001177. - Wolfdieter Lang, Jan 16 2015

Name corrected by Wolfdieter Lang, Jan 16 2015

A271953 a(n) is the period of A000930 modulo n.

Original entry on oeis.org

1, 7, 8, 14, 31, 56, 57, 28, 24, 217, 60, 56, 168, 399, 248, 56, 288, 168, 381, 434, 456, 420, 528, 56, 155, 168, 72, 798, 840, 1736, 930, 112, 120, 2016, 1767, 168, 342, 2667, 168, 868, 1723, 3192, 1848, 420, 744, 3696, 46, 56, 399, 1085, 288, 168, 468, 504, 1860, 1596, 3048, 840, 3541, 1736, 1240, 6510

Offset: 1

Joerg Arndt, Apr 17 2016

nonn

Joerg Arndt, Table of n, a(n) for n = 1..1000
H. T. Engstrom, On sequences defined by linear recurrence relations, Trans. Am. Math. Soc. 33 (1) (1931) 210-218.
K. Kirthi, Narayana Sequences for Cryptographic Applications, arXiv preprint arXiv:1509.05745 [math.NT], 2015.
M. B. Nathanson, Linear recurrences and uniform distribution, Proc. Amer. Math. Soc. 48 (1975), 289-291.
D. D. Wall, Fibonacci series modulo m, Amer. Math. Monthly, 67 (1960), 525-532.

Cf. A000930, A271901 (periods mod primes), A001175 (periods of A000045 modulo n).

minlen = 100; maxlen = 2*10^4;
per[lst_] := FindTransientRepeat[lst, 2] // Last // Length;
a[n_] := Module[{p0=0, len=minlen}, While[p0 = Mod[LinearRecurrence[{1, 0, 1}, {1, 1, 1}, len], n] // per; p0<=1 && len<=maxlen, len = 2 len]; p0];
Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 1, 100}] (* Jean-François Alcover, Jul 21 2018 *)

per(n, S, R) = {  \\ S[]: leading terms, R[]: recurrence
    if ( n==1, return( 1 ) );
    my ( r = #R );
    if ( r != #S , error("Mismatch in length of S[] and R[]") );
    S = vector(#S, j, Mod(S[j], n) );
    R = vector(#S, j, Mod(R[j], n) );
    my( T = S );
    my( j = 0 );
    until ( 0,  \\ forever
        j += 1;
        my( t = sum(i=1, r, R[i] * T[r+1-i] ) );  \\ next term
        for (k=1, r-1, T[k] = T[k+1] );
        T[r] = t;
        if ( T == S , return(j) );
    );
}
\\vector(66, n, per(n, [0,1], [1,1]) )  \\ A001175
\\vector(66, n, per(prime(n), [0,1], [1,1]) )  \\ A060305
vector(66, n, per(n, [0,0,1], [1,0,1]) )  \\ A271953
\\vector(66, n, per(prime(n), [0,0,1], [1,0,1]) )  \\ A271901
\\vector(66, n, per(n, [0,0,1], [0,1,1]) )  \\ A104217
/* Joerg Arndt, Apr 17 2016 */

Let the prime factorization of n be p1^e1*...*pk^ek. Then a(n) = lcm(a(p1^e1), ..., a(pk^ek)) [Engstrom]. - N. J. A. Sloane, Feb 18 2017

Conditions on p_n mod 4 and mod 5 restrict possible values of a(n). The unknown (?) case is p = 1 mod 4 and (5|p) = 1, equivalently, p = 1 or 9 mod 20, where {1, 2, 4} all occur.

Number of zeros in fundamental period of Fibonacci numbers mod prime(n). [From T. D. Noe, Jan 14 2009]

If the generalized Wall's conjecture to A006190 is true, then we can calculate A175182(m) when m is a prime power since for any k>=1 : A175182(prime(n)^k)=a(n)*prime(n)^(k-1). For example: A175182(2^k)=3*2^(k-1)=A007283(k-1).

In fact, the conjecture fails on p=241, and this is the only counterexample below 10^8.

cp's OEIS Frontend

A366951 a(n) = 2*(p_n - 1)/A060305(n) iff p_n == +/- 1 (mod 5), 2*(p_n + 1)/A060305(n) iff p_n == +/- 2 (mod 5), 0 iff p_n = 5.

Views

Author

Keywords

Crossrefs

Formula

A001175 Pisano periods (or Pisano numbers): period of Fibonacci numbers mod n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Sage

Formula

A001177 Fibonacci entry points: a(n) = least k >= 1 such that n divides Fibonacci number F_k (=A000045(k)).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Scheme

Formula

Extensions

A071774 Related to Pisano periods: integers k such that the period of Fibonacci numbers mod k equals 2*(k+1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Extensions

A296240 Pisano quotients: a(n) = (p-1)/k(p) if p == +- 1 mod 5, = (2*p+2)/k(p) if p == +- 2 mod 5, where p = prime(n) and k(p) = Pisano period(p).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A222413 All primes p > 5 such that A001175(p) is smaller than the maximal value permitted by Wall's Theorems 6 and 7.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A271953 a(n) is the period of A000930 modulo n.

Views

Author

Keywords

Links

Crossrefs

Programs

A366951 a(n) = 2(p_n - 1)/A060305(n) iff p_n == +/- 1 (mod 5), 2(p_n + 1)/A060305(n) iff p_n == +/- 2 (mod 5), 0 iff p_n = 5.