A003147 -id:A003147 - 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

A106535 Numbers k such that the smallest x > 1 for which Fibonacci(x) == 0 mod k is x = k - 1.

Original entry on oeis.org

11, 19, 31, 59, 71, 79, 131, 179, 191, 239, 251, 271, 311, 359, 379, 419, 431, 439, 479, 491, 499, 571, 599, 631, 659, 719, 739, 751, 839, 971, 1019, 1039, 1051, 1091, 1171, 1259, 1319, 1399, 1439, 1451, 1459, 1499, 1531, 1559, 1571, 1619, 1759, 1811, 1831

Offset: 1

Peter K. Pearson (ppearson+att(AT)spamcop.net), May 06 2005

nonn

This is a sister sequence to A000057, because this sequence, since {k : A001177(k) = k-1}, might be called a subdiagonal sequence of A001177, and {k : A001177(k) = k+1}, which might be called a superdiagonal sequence of A001177. Sequences A000057 and A106535 are disjoint. Is this sequence the set of all divisors of some family of sequences, like A000057 is? - Art DuPre, Jul 11 2012
Are all members of this sequence prime? Using A069106, any composite members must exceed 89151931. - Robert Israel, Oct 13 2015
From Jianing Song, Jul 02 2019: (Start)
Yes, all terms are primes. See a brief proof below.
Also, if p == 1 (mod 4) then b(p) divides (p-Legendre(p,5))/2. So terms in this sequence are congruent to 11 or 19 modulo 20.
Primes p such that ord(-(3+sqrt(5))/2,p) = p-1, where ord(z,p) is the smallest integer k > 0 such that (z^k-1)/p is an algebraic integer. (End)
Comments from Amiram Eldar, Jan 30 2022 (Start)
Sequence A003147, "Primes p with a Fibonacci primitive root", is defined in the paper: Daniel Shanks, Fibonacci primitive roots, Fibonacci Quarterly, Vol.  10, No. 2 (1972), pp. 163-168, and 181.
A second paper on this subject Daniel Shanks and Larry Taylor, An Observation of Fibonacci Primitive Roots, Fibonacci Quarterly, Vol. 11, No. 2 (1973), pp. 159-160,
deals with terms p == 3 (mod 4) of A003147, i.e., the intersection of A003147 and A002145 (or A004767).
It states that if g is a Fibonacci primitive root of a prime p such that p == 3 (mod 4) then g-1 and g-2 are also primitive roots of p.
The first 2000 terms of (A003147 intersect A002145) agree with the present sequence, although the definitions are quite different. Are these two sequences the same? (End)

Robert Israel, Table of n, a(n) for n = 1..2000
Alfred Brousseau, Primes which are factors of all Fibonacci sequences, Fib. Quart., 2 (1964), 33-38.
Alfred Brousseau, Fibonacci and Related Number Theoretic Tables, Fibonacci Association, San Jose, CA, 1972.
Jianing Song, Proof that all terms are prime

Cf. A000057, A001175, A069106.

Similar sequences that give primes p such that A001177(p) = (p-1)/s: this sequence (s=1), A308795 (s=2), A308796 (s=3), A308797 (s=4), A308798 (s=5), A308799 (s=6), A308800 (s=7),A308801 (s=8), A308802 (s=9).

Filtered([2..2000], n -> Fibonacci(n-1) mod n = 0 and Filtered( [2..n-2], x -> Fibonacci(x) mod n = 0 ) = [] );

A106535 := proc(n)
        option remember;
        if n = 1 then
                11;
        else
                for a from procname(n-1)+1 do
                        if A001177(a) = a-1 then
                                return a;
                        end if;
                end do:
        end if;
end proc: # R. J. Mathar, Jul 09 2012
# Alternative:
fmod:= proc(a,b) local A;
  uses LinearAlgebra[Modular];
  A:= Mod(b, <<1,1>|<1,0>>,integer[8]);
  MatrixPower(b,A,a)[1,2];
end proc:
filter:= proc(n)
  local cands;
  if fmod(n-1,n) <> 0 then return false fi;
  cands:= map(t -> (n-1)/t, numtheory:-factorset(n-1));
  andmap(c -> (fmod(c,n) > 0), cands);
end proc:
select(filter, [$2..10^4]); # Robert Israel, Oct 13 2015

f[n_] := Block[{x = 2}, While[Mod[Fibonacci@ x, n] != 0, x++]; x];Select[Range@ 1860, f@ # == # - 1 &] (* Michael De Vlieger, Oct 13 2015 *)

isok(n) = {x = 2; while(fibonacci(x) % n, x++); x == n-1;} \\ Michel Marcus, Oct 20 2015

{n: A001177(n) = n-1}. - R. J. Mathar, Jul 09 2012

Corrected by T. D. Noe, Oct 25 2006

A060305 Pisano periods for primes: period of Fibonacci numbers mod prime(n).

Original entry on oeis.org

3, 8, 20, 16, 10, 28, 36, 18, 48, 14, 30, 76, 40, 88, 32, 108, 58, 60, 136, 70, 148, 78, 168, 44, 196, 50, 208, 72, 108, 76, 256, 130, 276, 46, 148, 50, 316, 328, 336, 348, 178, 90, 190, 388, 396, 22, 42, 448, 456, 114, 52, 238, 240, 250, 516, 176, 268, 270, 556

Offset: 1

Louis Mello (mellols(AT)aol.com), Mar 26 2001

nonn

Assuming Wall's conjecture (which is still open) allows one to calculate A001175(m) when m is a prime power since for any k >= 1: A001175(prime(n)^k) = a(n)*prime(n)^(k-1). For example: A001175(2^k) = 3*2^(k-1) = A007283(k-1).

Alois P. Heinz, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
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.
A. Elsenhans and J. Jahnel, The Fibonacci sequence modulo p^2 -- An investigation by computer for p < 10^14, (2004).
D. D. Wall, Fibonacci series modulo m, Amer. Math. Monthly, 67 (1960), 525-532.
Wikipedia, Pisano period.

Cf. A001175, A000961, A071774, A003147, A296240.

a:= proc(n) option remember; local F, k, p;
      F:=[1,1]; p:=ithprime(n);
      for k while F<>[0,1] do
        F:=[F[2], irem(F[1]+F[2],p)]
      od: k
    end:
seq(a(n), n=1..70);  # Alois P. Heinz, Oct 16 2015

Table[p=Prime[n]; a={1,0}; a0=a; k=0; While[k++; s=Mod[Plus@@a,p];a=RotateLeft[a]; a[[2]]=s; a!=a0]; k, {n,100}] (* T. D. Noe, Jun 12 2006 *)

for(n=1,100,s=1; while(sum(i=n,n+s,abs(fibonacci(i)%prime(n)-fibonacci(i+s)%prime(n)))+sum(i=n+1,n+1+s,abs(fibonacci(i)%prime(n)-fibonacci(i+s)%prime(n)))>0,s++); print1(s,","))

from itertools import count
from sympy import prime
def A060305(n):
    x, p = (1,1), prime(n)
    for k in count(1):
        if x == (0,1):
            return k
        x = (x[1], (x[0]+x[1]) % p) # Chai Wah Wu, May 31 2022

a(n) = A001175(prime(n)). - Jonathan Sondow, Dec 09 2017

a(n) = (3 - L(p))/2 * (p - L(p)) / A296240(n) for n >= 4, where p = prime(n) and L(p) = Legendre(p|5); so a(n) <= p-1 if p == +- 1 mod 5, and a(n) <= 2*p+2 if p == +- 2 mod 5. See Wall's Theorems 6 and 7. - Jonathan Sondow, Dec 10 2017

Corrected by Benoit Cloitre, Jun 04 2002

Name clarified by Jonathan Sondow, Dec 09 2017

A308787 Primes p such that A001175(p) = (p-1)/2.

Original entry on oeis.org

29, 89, 101, 181, 229, 349, 401, 509, 761, 941, 1021, 1061, 1109, 1229, 1249, 1361, 1409, 1549, 1621, 1669, 1709, 1741, 1789, 1861, 2029, 2069, 2089, 2441, 2621, 2801, 2861, 3089, 3169, 3301, 3389, 3461, 3581, 3821, 3881, 3989, 4001, 4049, 4201, 4229, 4549, 4729

Offset: 1

Jianing Song, Jun 25 2019

nonn

Primes p such that ord((1+sqrt(5))/2,p) = (p-1)/2, where ord(z,p) is the smallest integer k > 0 such that (z^k-1)/p is an algebraic integer.
Let {T(n)} be a sequence defined by T(0) = 0, T(1) = 1, T(n) = k*T(n-1) + T(n-2), K be the quadratic field Q[sqrt(k^2+4)], O_K be the ring of integer of K, u = (k+sqrt(k^2+4))/2. For a prime p not dividing k^2 + 4, the Pisano period of {T(n)} modulo p (that is, the smallest m > 0 such that T(n+m) == T(n) (mod p) for all n) is ord(u,p); the entry point of {T(n)} modulo p (that is, the smallest m > 0 such that T(m) == 0 (mod p)) is ord(-u^2,p).
For an odd prime p:
(a) if p decomposes in K, then (O_K/pO_K)* (the multiplicative group of O_K modulo p) is congruent to C_(p-1) X C_(p-1), so the Pisano period of {T(n)} modulo p is equal to (p-1)/s, s = 1, 2, 3, 4, ...;
(b) if p is inert in K, then u^(p+1) == -1 (mod p), so the Pisano period of {T(n)} modulo p is equal to 2*(p+1)/r, r = 1, 3, 5, 7, ...
Here k = 1, and this sequence gives primes such that (a) holds and s = 2.
Note that the Pisano period of {T(n)} modulo p must be even, so we have p == 1 (mod 4) for primes p in this sequence.
The number of terms below 10^N:
  N | Number | Decomposing primes*
  3 |     10 |            78
  4 |     89 |           609
  5 |    630 |          4777
  6 |   5207 |         39210
  7 |  44296 |        332136
  8 | 382966 |       2880484
  * Here "Decomposing primes" means primes such that Legendre(5,p) = 1, i.e., p == 1, 4 (mod 5).

Similar sequences that give primes such that (a) holds: A003147/{5} (s=1), this sequence (s=2), A308788 (s=3), A308789 (s=4), A308790 (s=5), A308791 (s=6), A308792 (s=7), A308793 (s=8), A308794 (s=9).

pn[n_] := For[k = 1, True, k++, If[Mod[Fibonacci[k], n] == 0 && Mod[ Fibonacci[k+1], n] == 1, Return[k]]];
Reap[For[p = 2, p <= 4729, p = NextPrime[p], If[pn[p] == (p-1)/2, Print[p]; Sow[p]]]][[2, 1]] (* Jean-François Alcover, Jul 01 2019 *)

Pisano_for_decomposing_prime(p) = my(k=1, M=[k, 1; 1, 0], Id=[1, 0; 0, 1]); if(isprime(p)&&kronecker(k^2+4,p)==1, my(v=divisors(p-1)); for(d=1, #v, if(Mod(M,p)^v[d]==Id, return(v[d]))))
forprime(p=2, 4800, if(Pisano_for_decomposing_prime(p)==(p-1)/2, print1(p, ", ")))

A308789 Primes p such that A001175(p) = (p-1)/4.

Original entry on oeis.org

769, 809, 1049, 1289, 1721, 2729, 3049, 3929, 4289, 4649, 5009, 5441, 5689, 6361, 6961, 7321, 7841, 8209, 8329, 8369, 8681, 9689, 9769, 11161, 11489, 11969, 12049, 12281, 12601, 12721, 13649, 13721, 14969, 15241, 15569, 16649, 17489, 18329, 19961, 21169, 21881

Offset: 1

Jianing Song, Jun 25 2019

nonn

Primes p such that ord((1+sqrt(5))/2,p) = (p-1)/4, where ord(z,p) is the smallest integer k > 0 such that (z^k-1)/p is an algebraic integer.
Let {T(n)} be a sequence defined by T(0) = 0, T(1) = 1, T(n) = k*T(n-1) + T(n-2), K be the quadratic field Q[sqrt(k^2+4)], O_K be the ring of integer of K, u = (k+sqrt(k^2+4))/2. For a prime p not dividing k^2 + 4, the Pisano period of {T(n)} modulo p (that is, the smallest m > 0 such that T(n+m) == T(n) (mod p) for all n) is ord(u,p); the entry point of {T(n)} modulo p (that is, the smallest m > 0 such that T(m) == 0 (mod p)) is ord(-u^2,p).
For an odd prime p:
(a) if p decomposes in K, then (O_K/pO_K)* (the multiplicative group of O_K modulo p) is congruent to C_(p-1) X C_(p-1), so the Pisano period of {T(n)} modulo p is equal to (p-1)/s, s = 1, 2, 3, 4, ...;
(b) if p is inert in K, then u^(p+1) == -1 (mod p), so the Pisano period of {T(n)} modulo p is equal to 2*(p+1)/r, r = 1, 3, 5, 7, ...
Here k = 1, and this sequence gives primes such that (a) holds and s = 4.
Note that the Pisano period of {T(n)} modulo p must be even, so we have p == 1 (mod 8) for primes p in this sequence.
Number of terms below 10^N:
  N | Number | Decomposing primes*
  3 |      2 |            78
  4 |     23 |           609
  5 |    165 |          4777
  6 |   1290 |         39210
  7 |  10958 |        332136
  8 |  95746 |       2880484
  * Here "Decomposing primes" means primes such that Legendre(5,p) = 1, i.e., p == 1, 4 (mod 5).

Bob Bastasz, Lyndon words of a second-order recurrence, Fibonacci Quarterly (2020) Vol. 58, No. 5, 25-29.

Similar sequences that give primes such that (a) holds: A003147/{5} (s=1), A308787 (s=2), A308788 (s=3), this sequence (s=4), A308790 (s=5), A308791 (s=6), A308792 (s=7), A308793 (s=8), A308794 (s=9).

pn[n_] := For[k = 1, True, k++, If[Mod[Fibonacci[k], n] == 0 && Mod[ Fibonacci[k + 1], n] == 1, Return[k]]];
Reap[For[p=2, p <= 21881, p = NextPrime[p], If[pn[p] == (p-1)/4, Print[p]; Sow[p]]]][[2, 1]] (* Jean-François Alcover, Jul 01 2019 *)

Pisano_for_decomposing_prime(p) = my(k=1, M=[k, 1; 1, 0], Id=[1, 0; 0, 1]); if(isprime(p)&&kronecker(k^2+4,p)==1, my(v=divisors(p-1)); for(d=1, #v, if(Mod(M,p)^v[d]==Id, return(v[d]))))
forprime(p=2, 22000, if(Pisano_for_decomposing_prime(p)==(p-1)/4, print1(p, ", ")))

A308792 Primes p such that A001175(p) = (p-1)/7.

Original entry on oeis.org

2269, 2731, 2969, 3739, 4831, 6091, 6329, 11159, 11789, 13049, 13679, 14281, 14449, 14771, 16871, 19559, 20399, 24179, 26111, 29191, 31039, 33181, 33811, 34511, 34679, 35911, 40111, 41651, 42701, 43961, 49211, 54881, 55259, 55721, 56099, 58129, 60859, 62819, 66809

Offset: 1

Jianing Song, Jun 25 2019

nonn

Primes p such that ord((1+sqrt(5))/2,p) = (p-1)/7, where ord(z,p) is the smallest integer k > 0 such that (z^k-1)/p is an algebraic integer.
Let {T(n)} be a sequence defined by T(0) = 0, T(1) = 1, T(n) = k*T(n-1) + T(n-2), K be the quadratic field Q[sqrt(k^2+4)], O_K be the ring of integer of K, u = (k+sqrt(k^2+4))/2. For a prime p not dividing k^2 + 4, the Pisano period of {T(n)} modulo p (that is, the smallest m > 0 such that T(n+m) == T(n) (mod p) for all n) is ord(u,p); the entry point of {T(n)} modulo p (that is, the smallest m > 0 such that T(m) == 0 (mod p)) is ord(-u^2,p).
For an odd prime p:
(a) if p decomposes in K, then (O_K/pO_K)* (the multiplicative group of O_K modulo p) is congruent to C_(p-1) X C_(p-1), so the Pisano period of {T(n)} modulo p is equal to (p-1)/s, s = 1, 2, 3, 4, ...;
(b) if p is inert in K, then u^(p+1) == -1 (mod p), so the Pisano period of {T(n)} modulo p is equal to 2*(p+1)/r, r = 1, 3, 5, 7, ...
Here k = 1, and this sequence gives primes such that (a) holds and s = 7.
Number of terms below 10^N:
  N | Number | Decomposing primes*
  3 |      0 |            78
  4 |      7 |           609
  5 |     55 |          4777
  6 |    507 |         39210
  7 |   4144 |        332136
  8 |  36319 |       2880484
  * Here "Decomposing primes" means primes such that Legendre(5,p) = 1, i.e., p == 1, 4 (mod 5).

Amiram Eldar, Table of n, a(n) for n = 1..10000

Similar sequences that give primes such that (a) holds: A003147/{5} (s=1), A308787 (s=2), A308788 (s=3), A308789 (s=4), A308790 (s=5), A308791 (s=6), this sequence (s=7), A308793 (s=8), A308794 (s=9).

pn[n_] := For[k = 1, True, k++, If[Mod[Fibonacci[k], n] == 0 && Mod[ Fibonacci[k + 1], n] == 1, Return[k]]];
Reap[For[p = 2, p < 50000, p = NextPrime[p], If[Mod[p, 7] == 1, If[pn[p] == (p - 1)/7, Print[p]; Sow[p]]]]][[2, 1]] (* Jean-François Alcover, Jul 05 2019 *)

Pisano_for_decomposing_prime(p) = my(k=1, M=[k, 1; 1, 0], Id=[1, 0; 0, 1]); if(isprime(p)&&kronecker(k^2+4,p)==1, my(v=divisors(p-1)); for(d=1, #v, if(Mod(M,p)^v[d]==Id, return(v[d]))))
forprime(p=2, 67000, if(Pisano_for_decomposing_prime(p)==(p-1)/7, print1(p, ", ")))

A308793 Primes p such that A001175(p) = (p-1)/8.

Original entry on oeis.org

1009, 3329, 8081, 12401, 15889, 19681, 25601, 25841, 26641, 32321, 33329, 33521, 34369, 36929, 41681, 42929, 47809, 53569, 55249, 64849, 70289, 74209, 76081, 85361, 86209, 87649, 88129, 88801, 90001, 93089, 93329, 97649, 98689, 99089, 100049, 101489, 107441, 117841

Offset: 1

Jianing Song, Jun 25 2019

nonn

Primes p such that ord((1+sqrt(5))/2,p) = (p-1)/8, where ord(z,p) is the smallest integer k > 0 such that (z^k-1)/p is an algebraic integer.
Let {T(n)} be a sequence defined by T(0) = 0, T(1) = 1, T(n) = k*T(n-1) + T(n-2), K be the quadratic field Q[sqrt(k^2+4)], O_K be the ring of integer of K, u = (k+sqrt(k^2+4))/2. For a prime p not dividing k^2 + 4, the Pisano period of {T(n)} modulo p (that is, the smallest m > 0 such that T(n+m) == T(n) (mod p) for all n) is ord(u,p); the entry point of {T(n)} modulo p (that is, the smallest m > 0 such that T(m) == 0 (mod p)) is ord(-u^2,p).
For an odd prime p:
(a) if p decomposes in K, then (O_K/pO_K)* (the multiplicative group of O_K modulo p) is congruent to C_(p-1) X C_(p-1), so the Pisano period of {T(n)} modulo p is equal to (p-1)/s, s = 1, 2, 3, 4, ...;
(b) if p is inert in K, then u^(p+1) == -1 (mod p), so the Pisano period of {T(n)} modulo p is equal to 2*(p+1)/r, r = 1, 3, 5, 7, ...
Here k = 1, and this sequence gives primes such that (a) holds and s = 8.
Note that the Pisano period of {T(n)} modulo p must be even, so we have p == 1 (mod 16) for primes p in this sequence.
Number of terms below 10^N:
  N | Number | Decomposing primes*
  3 |      0 |            78
  4 |      3 |           609
  5 |     34 |          4777
  6 |    315 |         39210
  7 |   2751 |        332136
  8 |  23878 |       2880484
  * Here "Decomposing primes" means primes such that Legendre(5,p) = 1, i.e., p == 1, 4 (mod 5).

Similar sequences that give primes such that (a) holds: A003147/{5} (s=1), A308787 (s=2), A308788 (s=3), A308789 (s=4), A308790 (s=5), A308791 (s=6), A308792 (s=7), this sequence (s=8), A308794 (s=9).

pn[n_] := For[k = 1, True, k++, If[Mod[Fibonacci[k], n] == 0 && Mod[ Fibonacci[k + 1], n] == 1, Return[k]]];
Reap[For[p = 2, p < 50000, p = NextPrime[p], If[Mod[p, 8] == 1, If[pn[p] == (p - 1)/8, Print[p]; Sow[p]]]]][[2, 1]] (* Jean-François Alcover, Jul 05 2019 *)

Pisano_for_decomposing_prime(p) = my(k=1, M=[k, 1; 1, 0], Id=[1, 0; 0, 1]); if(isprime(p)&&kronecker(k^2+4,p)==1, my(v=divisors(p-1)); for(d=1, #v, if(Mod(M,p)^v[d]==Id, return(v[d]))))
forprime(p=2, 118000, if(Pisano_for_decomposing_prime(p)==(p-1)/8, print1(p, ", ")))

A308788 Primes p such that A001175(p) = (p-1)/3.

Original entry on oeis.org

139, 151, 331, 619, 661, 811, 829, 1069, 1231, 1279, 1291, 1381, 1471, 1579, 1699, 1999, 2239, 2251, 2281, 2371, 2659, 2689, 2749, 3271, 3331, 3391, 3499, 3631, 3919, 4051, 4159, 4231, 4261, 4759, 4909, 5059, 5581, 5701, 5821, 5839, 6079, 6229, 6469, 6619, 6691

Offset: 1

Jianing Song, Jun 25 2019

nonn

Primes p such that ord((1+sqrt(5))/2,p) = (p-1)/3, where ord(z,p) is the smallest integer k > 0 such that (z^k-1)/p is an algebraic integer.
Let {T(n)} be a sequence defined by T(0) = 0, T(1) = 1, T(n) = k*T(n-1) + T(n-2), K be the quadratic field Q[sqrt(k^2+4)], O_K be the ring of integer of K, u = (k+sqrt(k^2+4))/2. For a prime p not dividing k^2 + 4, the Pisano period of {T(n)} modulo p (that is, the smallest m > 0 such that T(n+m) == T(n) (mod p) for all n) is ord(u,p); the entry point of {T(n)} modulo p (that is, the smallest m > 0 such that T(m) == 0 (mod p)) is ord(-u^2,p).
For an odd prime p:
(a) if p decomposes in K, then (O_K/pO_K)* (the multiplicative group of O_K modulo p) is congruent to C_(p-1) X C_(p-1), so the Pisano period of {T(n)} modulo p is equal to (p-1)/s, s = 1, 2, 3, 4, ...;
(b) if p is inert in K, then u^(p+1) == -1 (mod p), so the Pisano period of {T(n)} modulo p is equal to 2*(p+1)/r, r = 1, 3, 5, 7, ...
Here k = 1, and this sequence gives primes such that (a) holds and s = 3.
The number of terms below 10^N:
  N | Number | Decomposing primes*
  3 |      7 |            78
  4 |     64 |           609
  5 |    455 |          4777
  6 |   3688 |         39210
  7 |  31412 |        332136
  8 | 272318 |       2880484
  * Here "Decomposing primes" means primes such that Legendre(5,p) = 1, i.e., p == 1, 4 (mod 5).

Similar sequences that give primes such that (a) holds: A003147/{5} (s=1), A308787 (s=2), this sequence (s=3), A308789 (s=4), A308790 (s=5), A308791 (s=6), A308792 (s=7), A308793 (s=8), A308794 (s=9).

pn[n_] := For[k = 1, True, k++, If[Mod[Fibonacci[k], n] == 0 && Mod[ Fibonacci[k + 1], n] == 1, Return[k]]];
Reap[For[p = 2, p <= 6691, p = NextPrime[p], If[pn[p] == (p-1)/3, Print[p]; Sow[p]]]][[2, 1]] (* Jean-François Alcover, Jul 01 2019 *)

Pisano_for_decomposing_prime(p) = my(k=1, M=[k, 1; 1, 0], Id=[1, 0; 0, 1]); if(isprime(p)&&kronecker(k^2+4,p)==1, my(v=divisors(p-1)); for(d=1, #v, if(Mod(M,p)^v[d]==Id, return(v[d]))))
forprime(p=2, 7000, if(Pisano_for_decomposing_prime(p)==(p-1)/3, print1(p, ", ")))

A308790 Primes p such that A001175(p) = (p-1)/5.

Original entry on oeis.org

211, 281, 421, 691, 881, 991, 1031, 1151, 1511, 1871, 1951, 2591, 3251, 3851, 4391, 4651, 4691, 4751, 4871, 5381, 5531, 5591, 5801, 6011, 6101, 6211, 6271, 6491, 7211, 7451, 8011, 8171, 8831, 8861, 9011, 9091, 9241, 9371, 9431, 9931, 10061, 10391, 10531, 10691

Offset: 1

Jianing Song, Jun 25 2019

nonn

Primes p such that ord((1+sqrt(5))/2,p) = (p-1)/5, where ord(z,p) is the smallest integer k > 0 such that (z^k-1)/p is an algebraic integer.
Let {T(n)} be a sequence defined by T(0) = 0, T(1) = 1, T(n) = k*T(n-1) + T(n-2), K be the quadratic field Q[sqrt(k^2+4)], O_K be the ring of integer of K, u = (k+sqrt(k^2+4))/2. For a prime p not dividing k^2 + 4, the Pisano period of {T(n)} modulo p (that is, the smallest m > 0 such that T(n+m) == T(n) (mod p) for all n) is ord(u,p); the entry point of {T(n)} modulo p (that is, the smallest m > 0 such that T(m) == 0 (mod p)) is ord(-u^2,p).
For an odd prime p:
(a) if p decomposes in K, then (O_K/pO_K)* (the multiplicative group of O_K modulo p) is congruent to C_(p-1) X C_(p-1), so the Pisano period of {T(n)} modulo p is equal to (p-1)/s, s = 1, 2, 3, 4, ...;
(b) if p is inert in K, then u^(p+1) == -1 (mod p), so the Pisano period of {T(n)} modulo p is equal to 2*(p+1)/r, r = 1, 3, 5, 7, ...
Here k = 1, and this sequence gives primes such that (a) holds and s = 5.
Number of terms below 10^N:
  N | Number | Decomposing primes*
  3 |      6 |            78
  4 |     40 |           609
  5 |    280 |          4777
  6 |   2289 |         39210
  7 |  18903 |        332136
  8 | 163395 |       2880484
  * Here "Decomposing primes" means primes such that Legendre(5,p) = 1, i.e., p == 1, 4 (mod 5).

Similar sequences that give primes such that (a) holds: A003147/{5} (s=1), A308787 (s=2), A308788 (s=3), A308789 (s=4), this sequence (s=5), A308791 (s=6), A308792 (s=7), A308793 (s=8), A308794 (s=9).

pn[n_] := For[k = 1, True, k++, If[Mod[Fibonacci[k], n] == 0 && Mod[Fibonacci[k + 1], n] == 1, Return[k]]];
Reap[For[p = 2, p < 11000, p = NextPrime[p], If[Mod[p, 5] == 1, If[pn[p] == (p - 1)/5, Print[p]; Sow[p]]]]][[2, 1]] (* Jean-François Alcover, Jul 05 2019 *)

Pisano_for_decomposing_prime(p) = my(k=1, M=[k, 1; 1, 0], Id=[1, 0; 0, 1]); if(isprime(p)&&kronecker(k^2+4,p)==1, my(v=divisors(p-1)); for(d=1, #v, if(Mod(M,p)^v[d]==Id, return(v[d]))))
forprime(p=2, 11000, if(Pisano_for_decomposing_prime(p)==(p-1)/5, print1(p, ", ")))

A308791 Primes p such that A001175(p) = (p-1)/6.

Original entry on oeis.org

541, 709, 2389, 3121, 3529, 4561, 4861, 5869, 7069, 8821, 9001, 10789, 12421, 12781, 13309, 14341, 14869, 16981, 18289, 19249, 19309, 19429, 19501, 20389, 20809, 20929, 21649, 22741, 23629, 24181, 25189, 26821, 27109, 27409, 28669, 30181, 30469, 30781, 30949, 31189

Offset: 1

Jianing Song, Jun 25 2019

nonn

Primes p such that ord((1+sqrt(5))/2,p) = (p-1)/6, where ord(z,p) is the smallest integer k > 0 such that (z^k-1)/p is an algebraic integer.
Let {T(n)} be a sequence defined by T(0) = 0, T(1) = 1, T(n) = k*T(n-1) + T(n-2), K be the quadratic field Q[sqrt(k^2+4)], O_K be the ring of integer of K, u = (k+sqrt(k^2+4))/2. For a prime p not dividing k^2 + 4, the Pisano period of {T(n)} modulo p (that is, the smallest m > 0 such that T(n+m) == T(n) (mod p) for all n) is ord(u,p); the entry point of {T(n)} modulo p (that is, the smallest m > 0 such that T(m) == 0 (mod p)) is ord(-u^2,p).
For an odd prime p:
(a) if p decomposes in K, then (O_K/pO_K)* (the multiplicative group of O_K modulo p) is congruent to C_(p-1) X C_(p-1), so the Pisano period of {T(n)} modulo p is equal to (p-1)/s, s = 1, 2, 3, 4, ...;
(b) if p is inert in K, then u^(p+1) == -1 (mod p), so the Pisano period of {T(n)} modulo p is equal to 2*(p+1)/r, r = 1, 3, 5, 7, ...
Here k = 1, and this sequence gives primes such that (a) holds and s = 6.
Note that the Pisano period of {T(n)} modulo p must be even, so we have p == 1 (mod 12) for primes p in this sequence.
Number of terms below 10^N:
  N | Number | Decomposing primes*
  3 |      2 |            78
  4 |     11 |           609
  5 |    112 |          4777
  6 |    898 |         39210
  7 |   7777 |        332136
  8 |  68115 |       2880484
  * Here "Decomposing primes" means primes such that Legendre(5,p) = 1, i.e., p == 1, 4 (mod 5).

Similar sequences that give primes such that (a) holds: A003147/{5} (s=1), A308787 (s=2), A308788 (s=3), A308789 (s=4), A308790 (s=5), this sequence (s=6), A308792 (s=7), A308793 (s=8), A308794 (s=9).

pn[n_] := For[k = 1, True, k++, If[Mod[Fibonacci[k], n] == 0 && Mod[ Fibonacci[k + 1], n] == 1, Return[k]]];
Reap[For[p = 2, p < 32000, p = NextPrime[p], If[Mod[p, 6] == 1, If[pn[p] == (p - 1)/6, Print[p]; Sow[p]]]]][[2, 1]] (* Jean-François Alcover, Jul 05 2019 *)

Pisano_for_decomposing_prime(p) = my(k=1, M=[k, 1; 1, 0], Id=[1, 0; 0, 1]); if(isprime(p)&&kronecker(k^2+4,p)==1, my(v=divisors(p-1)); for(d=1, #v, if(Mod(M,p)^v[d]==Id, return(v[d]))))
forprime(p=2, 32000, if(Pisano_for_decomposing_prime(p)==(p-1)/6, print1(p, ", ")))

cp's OEIS Frontend

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

A106535 Numbers k such that the smallest x > 1 for which Fibonacci(x) == 0 mod k is x = k - 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Maple

Mathematica

PARI

Formula

Extensions

A060305 Pisano periods for primes: period of Fibonacci numbers mod prime(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A308787 Primes p such that A001175(p) = (p-1)/2.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

A308789 Primes p such that A001175(p) = (p-1)/4.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A308792 Primes p such that A001175(p) = (p-1)/7.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A308793 Primes p such that A001175(p) = (p-1)/8.

Views

Author

Keywords

Comments