A079002 -id:A079002 - cp's OEIS frontend

A066853 Number of different remainders (or residues) for the Fibonacci numbers (A000045) when divided by n (i.e., the size of the set of F(i) mod n over all i).

1, 2, 3, 4, 5, 6, 7, 6, 9, 10, 7, 11, 9, 14, 15, 11, 13, 11, 12, 20, 9, 14, 19, 13, 25, 18, 27, 21, 10, 30, 19, 21, 19, 13, 35, 15, 29, 13, 25, 30, 19, 18, 33, 20, 45, 21, 15, 15, 37, 50, 35, 30, 37, 29, 12, 25, 33, 20, 37, 55, 25, 21, 23, 42, 45, 38, 51, 20, 29, 70, 44, 15, 57

Offset: 1

Reiner Martin, Jan 21 2002

nonn

The Fibonacci numbers mod n for any n are periodic - see A001175 for period lengths. - Ron Knott, Jan 05 2005

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

			a(8)=6 since the Fibonacci numbers, 0,1,1,2,3,5,8,13,21,34,55,89,144,... when divided by 8 have remainders 0,1,1,2,3,5,0,5,5,2,7,1 (repeatedly) which only contains the remainders 0,1,2,3,5 and 7, i.e., 6 remainders, so a(8)=6.
a(11)=7 since Fibonacci numbers reduced modulo 11 are {0, 1, 2, 3, 5, 8, 10}.

T. D. Noe, Table of n, a(n) for n = 1..10000
Casey Mongoven, Sonification of multiple Fibonacci-related sequences, Annales Mathematicae et Informaticae, 41 (2013) pp. 175-192.

Cf. A001175, A079002.

a066853 1 = 1
a066853 n = f 1 ps [] where
   f 0 (1 : xs) ys = length ys
   f _ (x : xs) ys = if x `elem` ys then f x xs ys else f x xs (x:ys)
   ps = 1 : 1 : zipWith (\u v -> (u + v) `mod` n) (tail ps) ps
-- Reinhard Zumkeller, Jan 16 2014

a[n_] := Module[{v = {1, 2}}, If[n<8, n, While[v[[-1]] != 1 || v[[-2]] != 0, AppendTo[v, Mod[v[[-1]] + v[[-2]], n]]]; v // Union // Length]]; Array[a, 100] (* Jean-François Alcover, Feb 15 2018, after Charles R Greathouse IV *)

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

A082116 Fibonacci sequence (mod 5).

Original entry on oeis.org

0, 1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, 2, 2, 4, 1, 0, 1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, 2, 2, 4, 1, 0, 1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, 2, 2, 4, 1, 0, 1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, 2, 2, 4, 1, 0, 1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, 2, 2, 4, 1, 0, 1, 1

Offset: 0

Eric W. Weisstein, Apr 03 2003

This sequence contains the complete set of residues modulo 5. See A079002. - Michel Marcus, Jan 31 2020

S. Vajda, Fibonacci and Lucas numbers and the Golden Section, Ellis Horwood Ltd., Chichester, 1989. See p. 88. - N. J. A. Sloane, Feb 20 2013

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Brandon Avila and Yongyi Chen, On Moduli For Which the Lucas Numbers Contain a Complete Residue System, Fibonacci Quart. 51 (2013), no. 2, 151-152. See p. 151.
S. A. Burr, On moduli for which the Fibonacci sequence contains a complete system of residues, The Fibonacci Quarterly, 9.5 (1971), 497-504.
Diana Savin and Elif Tan, On Companion sequences associated with Leonardo quaternions: Applications over finite fields, arXiv:2403.01592 [math.CO], 2024. See p. 11.
Minjia Shi and Patrick Solé, The largest number of weights in cyclic codes, arXiv:1807.08418 [cs.IT], 2018.
Eric Weisstein's World of Mathematics, Fibonacci Number
Index entries for linear recurrences with constant coefficients, signature (0,1,0,-1,1,1,-1,-1,1,0,-1,0,1).

Cf. A000045, A011655, A082115, A079343, A082116, A082117, A079344, A079002.

[Fibonacci(n) mod 5: n in [0..100]]; // Vincenzo Librandi, Feb 04 2014

Table[Mod[Fibonacci[n], 5], {n, 0, 125}] (* Alonso del Arte, Jul 29 2013 *)

a(n)=fibonacci(n)%5 \\ Charles R Greathouse IV, Oct 07 2015

Sequence is periodic with Pisano period 20.
a(n) = 2 + ((n mod 20) - ((n - 1) mod 20) - ((n - 3) mod 20) - ((n - 4) mod 20) + 3*((n - 5) mod 20) - 3*((n - 6) mod 20) + 2*((n - 8) mod 20) - 3*((n - 9) mod 20) + 4*((n - 10) mod 20) - 4*((n - 11) mod 20) + ((n - 13) mod 20) + ((n - 14) mod 20) + 2*((n - 15) mod 20) - 2*((n - 16) mod 20) - 2*((n - 18) mod 20) + 3*((n - 19) mod 20))/20. - Hieronymus Fischer, Jun 30 2007
G.f.: (x + x^2 + 2x^3 + 3x^4 + 3x^6 + 3x^7 + x^8 + 4x^9 + 4x^11 + 4x^12 + 3x^13 + 2x^14 + 2x^16 + 2x^17 + 4x^18 + x^19)/(1 - x^20), not reduced. - Hieronymus Fischer, Jun 30 2007
a(n) = A010073(n) mod 5. - Hieronymus Fischer, Jun 30 2007
G.f.: -x*(1 + x + x^2 + 2*x^3 + 3*x^6 - x^7 - 2*x^8 - x^4 + x^9 + 4*x^10 + x^11) / ( (x - 1) * (x^4 + x^3 + x^2 + x + 1) * (x^8 - x^6 + x^4 - x^2 + 1) ). - R. J. Mathar, Jul 14 2012

Added a(0)=0 from Vincenzo Librandi, Feb 04 2014

A079344 F(n) mod 8, where F(n) = A000045(n) is the n-th Fibonacci number.

Original entry on oeis.org

0, 1, 1, 2, 3, 5, 0, 5, 5, 2, 7, 1, 0, 1, 1, 2, 3, 5, 0, 5, 5, 2, 7, 1, 0, 1, 1, 2, 3, 5, 0, 5, 5, 2, 7, 1, 0, 1, 1, 2, 3, 5, 0, 5, 5, 2, 7, 1, 0, 1, 1, 2, 3, 5, 0, 5, 5, 2, 7, 1, 0, 1, 1, 2, 3, 5, 0, 5, 5, 2, 7, 1, 0, 1, 1, 2, 3, 5, 0, 5, 5, 2, 7, 1, 0, 1, 1, 2, 3, 5, 0, 5, 5, 2, 7, 1, 0, 1, 1, 2, 3, 5, 0, 5, 5

Offset: 0

Jon Perry, Jan 04 2003

This sequence does not contain the complete set of residues modulo 8. See A079002. - Michel Marcus, Jan 31 2020

			a(8) = F(8) mod 8 = 21 mod 8 = 5.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Brandon Avila and Yongyi Chen, On Moduli For Which the Lucas Numbers Contain a Complete Residue System, Fibonacci Quart. 51 (2013), no. 2, 151-152. See p. 151.
S. A. Burr, On moduli for which the Fibonacci sequence contains a complete system of residues, The Fibonacci Quarterly, 9.5 (1971), 497-504.
P. Ribenboim, FFF (Favorite Fibonacci Flowers), Fib. Q. 43 (No. 1, 2005), 3-14.
Eric Weisstein's World of Mathematics, Fibonacci Number
Index entries for linear recurrences with constant coefficients, signature (1,0,0,-1,1,0,0,-1,1).

Cf. A000045, A011655, A082115, A079343, A082116, A082117, A079344, A079345, A111958, A079002.

[Fibonacci(n) mod 8: n in [0..100]]; // Vincenzo Librandi, Feb 04 2014

Mod[Fibonacci[Range[0,110]],8] (* or *) LinearRecurrence[ {1,0,0,-1,1,0,0,-1,1},{0,1,1,2,3,5,0,5,5},110] (* Harvey P. Dale, Jan 16 2014 *)

for (n=0,100,print1(fibonacci(n)%8","))

Sequence is periodic with Pisano period 12 = A001175(8).

G.f.: -x*(1+x^2+x^3+3*x^4+6*x^6-5*x^5+x^7) / ( (x-1)*(x^2-x+1)*(1+x+x^2)*(x^4-x^2+1) ). - R. J. Mathar, Aug 08 2012

Edited by N. J. A. Sloane, Dec 06 2008 at the suggestion of R. J. Mathar

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

A224482 Numbers n for which the Lucas numbers modulo n is nondefective (residue complete).

Original entry on oeis.org

2, 3, 4, 6, 7, 9, 14, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467, 3486784401, 10460353203, 31381059609, 94143178827, 282429536481, 847288609443, 2541865828329, 7625597484987

Offset: 1

Jonathan Vos Post, Apr 10 2013

These are the numbers n = 2, 4, 6, 7, 14, and the powers of 3 (without 3^0=1).

Michael De Vlieger, Table of n, a(n) for n = 1..2100
B. Avila and Y. Chen, On moduli for which the Lucas numbers contain a complete residue system, Fibonacci Quarterly, 51 (2013), 151-152.
Cheng Lien Lang and Mong Lung Lang, Fibonacci system and residue completeness, arXiv:1304.2892 [math.NT], 2013.
Index entries for linear recurrences with constant coefficients, signature (3).

Cf. A000244 (powers of 3), A079002.

With[{nn = 27}, Union[TakeWhile[{2, 4, 6, 7, 14}, # <= 3^nn &], Array[3^# &, nn]]] (* Michael De Vlieger, Oct 06 2020 *)

G.f.: x*(15*x^7+13*x^6+12*x^5+11*x^4+6*x^3+5*x^2+3*x-2) / (3*x-1). - Colin Barker, Apr 14 2013

Corrected (term 9 was 27), Joerg Arndt, Apr 14 2013

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.

A249104 Defective numbers: A complete residue system mod a(n) does not exist in the Fibonacci sequence.

Original entry on oeis.org

8, 11, 12, 13, 16, 17, 18, 19, 21, 22, 23, 24, 26, 28, 29, 31, 32, 33, 34, 36, 37, 38, 39, 40, 41, 42, 43, 44, 46, 47, 48, 49, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 71, 72, 73, 74, 76, 77, 78, 79, 80, 82, 83, 84, 85, 86, 87

Offset: 1

Franz Vrabec, Oct 21 2014

nonn

Every multiple of a member is a member.
Every integer 2^r*m (r>2, m odd) is a member.
Every prime p congruent 1, 9, 11, 13, 17, 19 (mod 20) is a member (see reference).

			16 is a member because A066853(16) = 11 < 16.

A. P. Shah, Fibonacci Sequence Modulo m, Fibonacci Quarterly, Vol.6, No.2 (1968), 139-141.

Cf. A000045, A066853.

Complement of A079002. - Jeppe Stig Nielsen, Dec 11 2017

isok(k) = {if(k<8, return(0)); my(v=List([1, 2])); while(v[#v]!=1 || v[#v-1]!=0, listput(v, (v[#v]+v[#v-1])%k)); #Set(v)Jinyuan Wang, Mar 20 2020

A066853(a(n)) < a(n) in ascending order.

More terms from Jinyuan Wang, Mar 20 2020

cp's OEIS Frontend

A066853 Number of different remainders (or residues) for the Fibonacci numbers (A000045) when divided by n (i.e., the size of the set of F(i) mod n over all i).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

A082116 Fibonacci sequence (mod 5).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A079344 F(n) mod 8, where F(n) = A000045(n) is the n-th Fibonacci number.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

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

A224482 Numbers n for which the Lucas numbers modulo n is nondefective (residue complete).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords