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

A128924 T(n,m) is the number of m's in the fundamental period of Fibonacci numbers mod n.

Original entry on oeis.org

1, 1, 2, 2, 3, 3, 1, 3, 1, 1, 4, 4, 4, 4, 4, 2, 6, 3, 4, 3, 6, 2, 4, 2, 1, 1, 2, 4, 2, 3, 2, 1, 0, 3, 0, 1, 2, 5, 2, 2, 2, 2, 2, 2, 5, 4, 8, 4, 8, 4, 8, 4, 8, 4, 8, 1, 3, 2, 1, 0, 1, 0, 0, 1, 0, 1, 2, 5, 2, 2, 1, 5, 0, 1, 1, 2, 2, 1, 4, 4, 2, 2, 0, 4, 0, 0, 4, 0, 2, 2, 4, 2, 8, 2, 2, 1, 4, 4, 4, 4, 4, 1, 2, 2, 8

Offset: 1

R. J. Mathar, Apr 25 2007

T(n,m) is the triangle read by rows, 0<=m

A118965 and A066853 give numbers of zeros and nonzeros in n-th row, respectively. - Reinhard Zumkeller, Jan 16 2014

			{F(k) mod 4} has fundamental period (0,1,1,2,3,1), see A079343, with
T(4,0)=1 zero, T(4,1)=3 ones, T(4,2)=1 two's, T(4,3)=1 three's. The triangle starts
1,
1, 2,
2, 3, 3,
1, 3, 1, 1,
4, 4, 4, 4, 4,
2, 6, 3, 4, 3, 6,
2, 4, 2, 1, 1, 2, 4,
2, 3, 2, 1, 0, 3, 0, 1,
2, 5, 2, 2, 2, 2, 2, 2, 5,
4, 8, 4, 8, 4, 8, 4, 8, 4, 8,
1, 3, 2, 1, 0, 1, 0, 0, 1, 0, 1,
2, 5, 2, 2, 1, 5, 0, 1, 1, 2, 2, 1,
4, 4, 2, 2, 0, 4, 0, 0, 4, 0, 2, 2, 4,
2, 8, 2, 2, 1, 4, 4, 4, 4, 4, 1, 2, 2, 8,
2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3,
2, 3, 4, 1, 0, 3, 0, 1, 2, 3, 0, 1, 0, 3, 0, 1,
4, 4, 2, 2, 4, 2, 0, 0, 2, 2, 0, 0, 2, 4, 2, 2, 4,

Reinhard Zumkeller, Rows n = 1..125 of triangle, flattened
G. Darvasi and St. Eckmann, Zur Verteilung der Reste der Fibonacci-Folge modulo 5c, Elemente der Mathematik 50 (1995) pp. 76-80.

Cf. A053029, A053030, A053031, A001175 (row sums), A001176 (1st column).

import Data.List (group, sort)
a128924 n k = a128924_tabl !! (n-1) !! (k-1)
a128924_tabl = map a128924_row [1..]
a128924_row 1 = [1]
a128924_row n = f [0..n-1] $ group $ sort $ g 1 ps where
   f []     _                            = []
   f (v:vs) wss'@(ws:wss) | head ws == v = length ws : f vs wss
                          | otherwise    = 0 : f vs wss'
   g 0 (1 : xs) = []
   g _ (x : xs) = x : g x xs
   ps = 1 : 1 : zipWith (\u v -> (u + v) `mod` n) (tail ps) ps
-- Reinhard Zumkeller, Jan 16 2014

A128924 := proc(m,h)
    local resul,k,M ;
    resul :=0 ;
    for k from 0 to A001175(m)-1 do
        M := combinat[fibonacci](k) mod m ;
        if M = h then
            resul := resul+1 ;
        end if ;
    end do;
    resul ;
end proc:
seq(seq(A128924(m,h),h=0..m-1),m=1..17) ;

A001175[1] = 1; A001175[n_] := For[k = 1, True, k++, If[Mod[Fibonacci[k], n] == 0 && Mod[Fibonacci[k+1], n] == 1, Return[k]]]; T[m_, h_] := Module[{resul, k, M}, resul = 0; For[k = 0, k <= A001175[m]-1, k++, M = Mod[Fibonacci[k], m]; If[ M == h, resul++]]; Return[resul]]; Table[T[m, h], {m, 1, 17}, {h, 0, m-1}] // Flatten (* Jean-François Alcover, Feb 11 2015, after Maple code *)

T(n,n) = A235715(n). - Reinhard Zumkeller, Jan 17 2014

A189768 Irregular triangle in which row n contains the set of residues of the sequence Fibonacci(i) mod n for i=0,1,2,....

Original entry on oeis.org

0, 0, 1, 0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 5, 7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 5, 8, 10, 0, 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 0, 1, 2, 3, 5, 8, 10, 11, 12

Offset: 1

T. D. Noe, May 10 2011

Sequence A066853 gives the lengths of the rows. Sequence A079002 gives the n that have a complete set of residues.

			The triangle begins
0
0, 1
0, 1, 2
0, 1, 2, 3
0, 1, 2, 3, 4
0, 1, 2, 3, 4, 5
0, 1, 2, 3, 4, 5, 6
0, 1, 2, 3, 5, 7
0, 1, 2, 3, 4, 5, 6, 7, 8
0, 1, 2, 3, 4, 5, 6, 7, 8, 9

T. D. Noe, Rows n = 1..100, flattened

Cf. A000045 (Fibonacci numbers), A066853, A079002.

pisano[n_] := Module[{a = {1, 0}, a0, k = 0, s}, If[n == 1, 1, a0 = a; While[k++; s = Mod[Total[a], n]; a[[1]] = a[[2]]; a[[2]] = s; a != a0]; k]]; Flatten[Table[p=pisano[n]; f=Mod[Fibonacci[Range[0,p]],n]; Union[f], {n,15}]]

A118965 Number of missing residues in Fibonacci sequence mod n.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 4, 1, 4, 0, 0, 5, 4, 7, 7, 0, 12, 8, 4, 11, 0, 8, 0, 7, 19, 0, 12, 11, 14, 21, 0, 21, 8, 25, 14, 10, 22, 24, 10, 24, 0, 25, 32, 33, 12, 0, 16, 22, 16, 25, 43, 31, 24, 38, 22, 5, 36, 41, 40, 22, 20, 28, 16, 48, 40, 0, 27, 57

Offset: 1

Casey Mongoven, May 07 2006

nonn

If n belongs to A079002, then a(n) = 0. - Michel Marcus, May 27 2013

a(n) = number of zeros in n-th row of triangle A128924. - Reinhard Zumkeller, Jan 16 2014

			The Fibonacci sequence mod 8 is { 0 1 1 2 3 5 0 5 5 2 7 1 0 1 1 ... } - a periodic sequence with a period of 12 (see A001175). Two residues do not occur in this sequence (4 and 6), therefore a(8) = 2.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Cyrus Hsia et al., Mathematical Mayhem Editors, Fibonacci residues, Crux Mathematicorum, 1997 Vol. 23 No. 4, pp. 224-226.
Casey Mongoven, Sonification of multiple Fibonacci-related sequences, Annales Mathematicae et Informaticae, 41 (2013) pp. 175-192.
D. D. Wall, Fibonacci series modulo m, Amer. Math. Monthly (67 #6, Jun-Jul 1960), pp. 525-532.

Cf. A066853, A001175.

a118965 = sum . map (0 ^) . a128924_row
-- Reinhard Zumkeller, Jan 16 2014

With[{fibs=Fibonacci[Range[300]]},Table[Length[Complement[Range[0,n-1],Union[ Mod[fibs,n]]]],{n,80}]] (* Harvey P. Dale, Jul 01 2021 *)

a(n)=if(n<8, return(0)); my(v=List([1,2])); while(v[#v] || v[#v-1]!=1, listput(v,(v[#v]+v[#v-1])%n)); n-#Set(v) \\ Charles R Greathouse IV, Jun 20 2017

a(n) = n - A066853(n). - Michel Marcus, May 27 2013

Offset corrected by Michel Marcus, May 27 2013

A137750 Number of distinct residues in the Fibonacci sequence mod the n-th prime.

Original entry on oeis.org

2, 3, 5, 7, 7, 9, 13, 12, 19, 10, 19, 29, 19, 33, 15, 37, 37, 25, 51, 44, 57, 49, 63, 17, 69, 35, 79, 33, 49, 33, 97, 82, 109, 33, 61, 37, 113, 123, 127, 137, 112, 62, 119, 149, 149, 16, 30, 169, 171, 80, 21, 149, 103, 157, 193, 85

Offset: 1

Casey Mongoven, Feb 10 2008

nonn

			The 5th prime number is 11. The Fibonacci sequence mod 11 is {0,1,1,2,3,5,8,2,10,1,0,1,...} - a periodic sequence. There are 7 distinct residues in this sequence, namely {0,1,2,3,5,8,10}. So a(5) = 7.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Casey Mongoven, Unique Residues Primes no. 1; electro-acoustic music created with this sequence.

Cf. A066853, A137751, A000045, A001175.

With[{f=Fibonacci[Range[500]]},Table[Length[Union[Mod[f,Prime[n]]]],{n,60}]] (* Harvey P. Dale, Aug 15 2012 *)

a(n)=my(v=List([0,1]),p=prime(n));while(v[#v]||v[#v-1]!=1, listput(v,(v[#v]+v[#v-1])%p));#vecsort(Vec(v),,8) \\ Charles R Greathouse IV, Apr 24 2012

a(n) = A066853(A000040(n)). - Max Alekseyev, Feb 08 2023

A066981 Number of residues of Lucas numbers modulo n.

Original entry on oeis.org

1, 2, 3, 4, 4, 6, 7, 6, 9, 8, 7, 10, 12, 14, 7, 11, 16, 11, 12, 10, 13, 14, 19, 14, 12, 24, 27, 20, 10, 14, 19, 22, 17, 20, 13, 15, 28, 13, 24, 10, 19, 26, 33, 20, 17, 21, 15, 17, 37, 24, 31, 36, 44, 29, 16, 28, 29, 20, 37, 18, 28, 21, 33, 42, 16, 34, 51, 26, 33, 26, 44, 17, 56

Offset: 1

Reiner Martin, Jan 26 2002

nonn

			a(15)=7, since Lucas numbers reduced modulo 15 are {1, 2, 3, 4, 7, 11, 14}.

Cf. A000032, A066853.

Table[Length[Union[Mod[LucasL[Range[500]],n]]],{n,75}] (* Harvey P. Dale, Dec 17 2014 *)

A336683 Sum of 2^k for all residues k found in the Fibonacci sequence mod n.

Original entry on oeis.org

1, 3, 7, 15, 31, 63, 127, 175, 511, 1023, 1327, 4031, 7471, 16383, 32767, 43951, 127807, 238895, 502063, 1048575, 1319215, 2719023, 7798639, 10692015, 33554431, 61209903, 134217727, 259173375, 337649967, 1073741823, 1571892655, 2880154543, 5417565487, 15638470959

Offset: 1

Michael De Vlieger, Oct 04 2020

Row n of A079002 compactified as a binary number.

			a(1) = 1 by convention.
a(2) = 3 = 2^0 + 2^1, since the Fibonacci sequence mod 2 is {0,1,1} repeated, and 0 and 1 appear in the sequence.
a(8) = 175 = 2^0 + 2^1 + 2^2 + 2^3 + 2^5 + 2^7, since the Fibonacci sequence mod 8 is {0,1,1,2,3,5,0,5,5,2,7,1} repeated, and we are missing 4 and 6, leaving the exponents of 2 as shown.
Binary equivalents of first terms:
   n    a(n)   a(n) in binary
   --------------------------
   1      1                 1
   2      3                11
   3      7               111
   4     15              1111
   5     31             11111
   6     63            111111
   7    127           1111111
   8    175          10101111
   9    511         111111111
  10   1023        1111111111
  11   1327       10100101111
  12   4031      111110111111
  13   7471     1110100101111
  14  16383    11111111111111
  15  32767   111111111111111
  16  43951  1010101110101111
  ...

Michael De Vlieger, Table of n, a(n) for n = 1..3322
Michael De Vlieger, Plot of bits of a(n) beginning with 2^0 at left for 1 <= n <= 5000.

Cf. A000045, A001175, A066853, A079002, A128924, A189768.

{1}~Join~Array[Block[{w = {0, 1}}, Do[If[SequenceCount[w, {0, 1}] == 1, AppendTo[w, Mod[Total@ w[[-2 ;; -1]], #]], Break[]], {i, 2, Infinity}]; Total[2^Union@ w]] &, 33, 2]
(* Second program: generate the first n terms using the plot in Links *)
With[{n = 34, img = ImageData@ ColorNegate@ Import["https://oeis.org/A336683/a336683.png"]}, Map[FromDigits[#, 2] &@ Drop[#, LengthWhile[#, # == 0 &]] &@ Reverse[IntegerPart[#]] &, img[[1 ;; n]]]] (* Michael De Vlieger, Oct 05 2020 *)

a(n) = Sum(2^k) for all k in row n of A189768.

a(n) = 2^(n+1) - 1 for n in A079002.

A189761 Numbers n for which the set of residues {Fibonacci(k) mod n, k=0,1,2,....} is minimal.

Original entry on oeis.org

1, 2, 3, 4, 5, 8, 11, 21, 29, 55, 76, 144, 199, 377, 521, 987, 1364, 2584, 3571, 6765, 9349, 17711, 24476, 46368, 64079, 121393, 167761, 317811, 439204, 832040, 1149851, 2178309, 3010349, 5702887, 7881196, 14930352, 20633239, 39088169, 54018521, 102334155

Offset: 1

T. D. Noe, May 10 2011

Sequence A066853 gives the number of possible residues of the Fibonacci numbers mod n. For the n in this sequence, it appears that A066853(n) < A066853(m) for all m > n. For these n, the set of residues consists of Fibonacci numbers < n and some of their negatives (see example).
Interestingly, for n > 5, this sequence alternates the even-index Fibonacci and odd-indexed Lucas numbers, A001906 and A002878. See A109794 for the sequence without 2 and 5.
The number of residues is 1, 2, 3, 4, 5, 6, 7, 9, 10, 12, 13, 15, 16, ..., which is A032766 with 2 and 5 included.

			For n=55, the residues are {0, 1, 2, 3, 5, 8, 13, 21, 34, 47, 52, 54} which can also be written as {0, 1, 2, 3, 5, 8, 13, 21, -21, -8, -3, -1}.

Index entries for linear recurrences with constant coefficients, signature (0,3,0,-1).

Cf. A001906, A002878, A032766, A066853, A109794, A189768.

Union[{2, 5}, Fibonacci[Range[2, 20, 2]], LucasL[Range[1, 20, 2]]]

Vec(x*(x^8+x^7-x^6-2*x^5-3*x^4-2*x^3+2*x+1)/((x^2-x-1)*(x^2+x-1)) + O(x^100)) \\ Colin Barker, Oct 29 2013

From Colin Barker, Oct 29 2013: (Start)
a(n) = 3*a(n-2) - a(n-4) for n > 9.
G.f.: x*(x^8 + x^7 - x^6 - 2*x^5 - 3*x^4 - 2*x^3 + 2*x + 1) / ((x^2-x-1)*(x^2+x-1)). (End)

A189767 Least number k such that the set of numbers {Fibonacci(i) mod n, i=0..k-1} contains all possible residues of Fibonacci(i) mod n.

Original entry on oeis.org

1, 2, 4, 5, 10, 10, 13, 11, 17, 22, 9, 23, 19, 37, 20, 23, 25, 19, 17, 53, 15, 25, 37, 23, 50, 61, 53, 45, 13, 58, 29, 47, 39, 25, 77, 23, 55, 17, 47, 59, 31, 37, 65, 29, 93, 37, 25, 23, 81, 148, 67, 75, 77, 53, 19, 45, 71, 37, 57, 119, 43, 29, 45, 95, 103

Offset: 1

T. D. Noe, May 10 2011

nonn

Sequence A066853 gives the number of possible residues of the sequence Fibonacci(i) mod n for i=0,1,2,.... Here we compute the smallest k required to find all A066853(n) residues in the first k terms (starting at i=0) of Fibonacci sequence (mod n). We know that k is at most A001175(n), the period of Fibonacci(i) mod n. It appears that when n is a prime in A053032, then a(n)=n-1.

			Consider n=8. The Fibonacci numbers mod 8 have period 12: 0, 1, 1, 2, 3, 5, 0, 5, 5, 2, 7, 1. The set of residues is {0, 1, 2, 3, 5, 7}. How long does it take to find all 6 residues in the sequence Fibonacci(i) mod n? The answer is 11 because 7 finally appears as Fibonacci(10) mod 8.

T. D. Noe, Table of n, a(n) for n = 1..1000

Cf. A000045 (Fibonacci numbers), A001175, A053032, A066853, A189768 (residues).

F:= proc(n)
 local r, k, a,ap, t, V;
ap:= 0: a:= 1; r:= 1;
V:= Array(0..n-1);
V[0]:= 1;
V[1]:= 1;
for k from 2 do
     t:= a + ap mod n;
     ap:= a;
     a:= t;
     if ap = 0 and a = 1 then return r +1 fi;
     if V[t] = 0 then
        r:=k;
        V[t]:= 1;
     fi
od:
end proc:
F(1):= 1:
seq(F(n),n=1..100); # Robert Israel, Dec 23 2015

pisano[n_] := Module[{a={1,0},a0,k=0,s}, If[n==1, 1, a0=a; While[k++; s=Mod[Total[a],n]; a[[1]]=a[[2]]; a[[2]]=s; a != a0]; k]]; Table[p=pisano[n]; f=Mod[Fibonacci[Range[0,p]],n]; u=Union[f]; k=1; While[Union[Take[f,k]] != u, k++]; k, {n,100}]

Showing 1-10 of 12 results. Next

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

A079002 Numbers n such that the Fibonacci residues F(k) mod n form the complete set (0,1,2,...,n-1).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A128924 T(n,m) is the number of m's in the fundamental period of Fibonacci numbers mod n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

A189768 Irregular triangle in which row n contains the set of residues of the sequence Fibonacci(i) mod n for i=0,1,2,....

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A118965 Number of missing residues in Fibonacci sequence mod n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

Extensions

A137750 Number of distinct residues in the Fibonacci sequence mod the n-th prime.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A066981 Number of residues of Lucas numbers modulo n.