A128924 -id:A128924 - cp's OEIS frontend

A001176 Number of zeros in fundamental period of Fibonacci numbers mod n.

1, 1, 2, 1, 4, 2, 2, 2, 2, 4, 1, 2, 4, 2, 2, 2, 4, 2, 1, 2, 2, 1, 2, 2, 4, 4, 2, 2, 1, 2, 1, 2, 2, 4, 2, 2, 4, 1, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 4, 2, 2, 4, 2, 2, 2, 2, 1, 1, 2, 4, 1, 2, 2, 4, 2, 2, 2, 2, 2, 1, 2, 4, 4, 2, 1, 2, 2, 1, 2, 2, 2, 2, 2, 4, 2, 2, 2, 4, 2, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 1, 2, 2, 2, 2

Offset: 1

N. J. A. Sloane

If the Fibonacci numbers are indexed so that 3 is the fourth number, then if the modulo base is a Fibonacci number (>= 3) with an even index, the period has 2 zeros. If the base is a Fibonacci number (>= 5) with an odd index, the period has 4 zeros. - Kerry Mitchell, Dec 11 2005

For a proof that A001177(n) divides the period length A001175(n) for n >= 1, see, e.g., the Vajda reference, p. 73. This comment refers to the present first formula. - Wolfdieter Lang, Jan 19 2015

			{F(n) mod 1} has fundamental period (0) with 1 zero.
{F(n) mod 2} has fundamental period (0,1,1) with 1 zero.
{F(n) mod 3} has fundamental period (0,1,1,2,0,2,2,1) with 2 zeros.
{F(n) mod 4} has fundamental period (0,1,1,2,3,1), with 1 zero.
{F(n) mod 5} has fundamental period (0,1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1) with 4 zeros.

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

T. D. Noe, Table of n, a(n) for n = 1..1000
Brennan Benfield and Michelle Manes, The Fibonacci Sequence is Normal Base 10, arXiv:2202.08986 [math.NT], 2022.
J. D. Fulton and W. L. Morris, On arithmetical functions related to the Fibonacci numbers, Acta Arithmetica, 16 (1969), 105-110.
B. H. Hannon and W. L. Morris, Tables of Arithmetical Functions Related to the Fibonacci Numbers [Annotated and scanned copy]
M. Renault, Fibonacci sequence modulo m
Review of B. H. Hannon and W. L. Morris tables, Math. Comp., 23 (1969), 459-460.

Cf. A001175, A001177, A053027, A053028, A053029, A053030, A053031, A053032.

Cf. A235715.

a001176 1 = 1
a001176 n = f 1 ps 0 where
   f 0 (1 : xs) z = z
   f _ (x : xs) z = f x xs (z + 0 ^ x)
   ps = 1 : 1 : zipWith (\u v -> (u + v) `mod` n) (tail ps) ps
-- Reinhard Zumkeller, Jan 15 2014

With[{fibs=Fibonacci[Range[2000]]},Table[Count[FindTransientRepeat[ Mod[ fibs, n], 3][[2]],0],{n,110}]] (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, Dec 26 2016 *)

a(n) = A001175(n)/A001177(n) for n >= 1.
a(n) = ord(n, fibonacci(A001177(n) + 1)), where ord(n, a) is the multiplicative order of a modulo n. - Mircea Merca, Jan 03 2011
a(n) = A128924(n,1). - Reinhard Zumkeller, Jan 17 2014
From Isaac Saffold, Aug 30 2018: (Start)
With the sole exception of a(8) = 2,
  a(p^k) = 1 if A007814(A001175(p^k)) < 2.
  a(p^k) = 4 if A007814(A001175(p^k)) = 2.
  a(p^k) = 2 if A007814(A001175(p^k)) > 2. (End)
From Jianing Song, Sep 01 2018: (Start)
a(2^e) = 1 if e <= 2, otherwise 2. For odd primes p, a(p^e) = 4 if A001177(p) is odd; 1 if A001177(p) is even but not divisible by 4; 2 if A001177(p) is divisible by 4.
a(n) = 2 for n == 0, 3, 7, 8, 12, 15 (mod 20). a(p^e) = 1 if primes p == 11, 19 (mod 20); 4 if p == 13, 17 (mod 20). Conjecture: 1/6 of the primes congruent to 1 or 9 mod 40 satisfy a(p^e) = 1, 2/3 of them satisfy a(p^e) = 2 and 1/6 of them satisfy a(p^e) = 4; also, 1/2 of the primes congruent to 21 or 29 mod 40 satisfy a(p^e) = 1 and 1/2 of them satisfy a(p^e) = 4. (End)

Better description and more terms from Henry Bottomley, Feb 01 2000
Examples from David W. Wilson, Jan 05 2005
Replaced the old Renault link with a working one. - Wolfdieter Lang, Jan 17 2015

A053029 Numbers with 4 zeros in Fibonacci numbers mod m.

Original entry on oeis.org

5, 10, 13, 17, 25, 26, 34, 37, 50, 53, 61, 65, 73, 74, 85, 89, 97, 106, 109, 113, 122, 125, 130, 137, 146, 149, 157, 169, 170, 173, 178, 185, 193, 194, 197, 218, 221, 226, 233, 250, 257, 265, 269, 274, 277, 289, 293, 298, 305, 313, 314, 317, 325, 337, 338, 346

Offset: 1

Henry Bottomley, Feb 23 2000

nonn

Conjecture: m is on this list iff m is an odd number all of whose factors are on this list or m is twice such an odd number.

A001176(a(n)) = A128924(a(n),1) = 4. - Reinhard Zumkeller, Jan 17 2014

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
Brennan Benfield and Michelle Manes, The Fibonacci Sequence is Normal Base 10, arXiv:2202.08986 [math.NT], 2022.
Brennan Benfield and Oliver Lippard, Connecting Zeros in Pisano Periods to Prime Factors of K-Fibonacci Numbers, arXiv:2407.20048 [math.NT], 2024.
M. Renault, Fibonacci sequence modulo m

Let {x(n)} be a sequence defined by x(0) = 0, x(1) = 1, x(n+2) = m*x(n+1) + x(n). Let w(k) be the number of zeros in a fundamental period of {x(n)} modulo k.
                             |   m=1    |   m=2   |   m=3
-----------------------------+----------+---------+---------
The sequence {x(n)}          | A000045  | A000129 | A006190
The sequence {w(k)}          | A001176  | A214027 | A322906
Primes p such that w(p) = 1  | A112860* | A309580 | A309586
Primes p such that w(p) = 2  | A053027  | A309581 | A309587
Primes p such that w(p) = 4  | A053028  | A261580 | A309588
Numbers k such that w(k) = 1 | A053031  | A309583 | A309591
Numbers k such that w(k) = 2 | A053030  | A309584 | A309592
Numbers k such that w(k) = 4 | this seq | A309585 | A309593
* and also A053032 U {2}

a053029 n = a053029_list !! (n-1)
a053029_list = filter ((== 4) . a001176) [1..]
-- Reinhard Zumkeller, Jan 17 2014

A053030 Numbers with 2 zeros in Fibonacci numbers mod m.

Original entry on oeis.org

3, 6, 7, 8, 9, 12, 14, 15, 16, 18, 20, 21, 23, 24, 27, 28, 30, 32, 33, 35, 36, 39, 40, 41, 42, 43, 45, 46, 47, 48, 49, 51, 52, 54, 55, 56, 57, 60, 63, 64, 66, 67, 68, 69, 70, 72, 75, 77, 78, 80, 81, 82, 83, 84, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96, 98, 99, 100, 102, 103, 104

Offset: 1

Henry Bottomley, Feb 23 2000

nonn

m is on this list iff m does not have 1 or 4 zeros in the Fibonacci sequence modulo m.

A001176(a(n)) = A128924(a(n),1) = 2. - Reinhard Zumkeller, Jan 17 2014

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Brennan Benfield and Oliver Lippard, Connecting Zeros in Pisano Periods to Prime Factors of K-Fibonacci Numbers, arXiv:2407.20048 [math.NT], 2024. See p. 2.
Brennan Benfield and Michelle Manes, The Fibonacci Sequence is Normal Base 10, arXiv:2202.08986 [math.NT], 2022.
M. Renault, Fibonacci sequence modulo m

Let {x(n)} be a sequence defined by x(0) = 0, x(1) = 1, x(n+2) = m*x(n+1) + x(n). Let w(k) be the number of zeros in a fundamental period of {x(n)} modulo k.
                             |   m=1    |   m=2   |   m=3
-----------------------------+----------+---------+---------
The sequence {x(n)}          | A000045  | A000129 | A006190
The sequence {w(k)}          | A001176  | A214027 | A322906
Primes p such that w(p) = 1  | A112860* | A309580 | A309586
Primes p such that w(p) = 2  | A053027  | A309581 | A309587
Primes p such that w(p) = 4  | A053028  | A261580 | A309588
Numbers k such that w(k) = 1 | A053031  | A309583 | A309591
Numbers k such that w(k) = 2 | this seq | A309584 | A309592
Numbers k such that w(k) = 4 | A053029  | A309585 | A309593
* and also A053032 U {2}

a053030 n = a053030_list !! (n-1)
a053030_list = filter ((== 2) . a001176) [1..]
-- Reinhard Zumkeller, Jan 17 2014

A053031 Numbers with 1 zero in Fibonacci numbers mod m.

Original entry on oeis.org

1, 2, 4, 11, 19, 22, 29, 31, 38, 44, 58, 59, 62, 71, 76, 79, 101, 116, 118, 121, 124, 131, 139, 142, 151, 158, 179, 181, 191, 199, 202, 209, 211, 229, 236, 239, 242, 251, 262, 271, 278, 284, 302, 311, 316, 319, 331, 341, 349, 358, 359, 361, 362, 379, 382, 398

Offset: 1

Henry Bottomley, Feb 23 2000

nonn

Conjecture: m is on this list iff m is an odd number all of whose factors are on this list or m is 2 or 4 times such an odd number.
A001176(a(n)) = A128924(a(n),1) = 1. - Reinhard Zumkeller, Jan 16 2014
Also numbers n such that A001175(n) = A001177(n). - Daniel Suteu, Aug 08 2018

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
Brennan Benfield and Michelle Manes, The Fibonacci Sequence is Normal Base 10, arXiv:2202.08986 [math.NT], 2022.
Brennan Benfield and Oliver Lippard, Connecting Zeros in Pisano Periods to Prime Factors of K-Fibonacci Numbers, arXiv:2407.20048 [math.NT], 2024.
M. Renault, Fibonacci sequence modulo m

Let {x(n)} be a sequence defined by x(0) = 0, x(1) = 1, x(n+2) = m*x(n+1) + x(n). Let w(k) be the number of zeros in a fundamental period of {x(n)} modulo k.
                             |   m=1    |   m=2   |   m=3
-----------------------------+----------+---------+---------
The sequence {x(n)}          | A000045  | A000129 | A006190
The sequence {w(k)}          | A001176  | A214027 | A322906
Primes p such that w(p) = 1  | A112860* | A309580 | A309586
Primes p such that w(p) = 2  | A053027  | A309581 | A309587
Primes p such that w(p) = 4  | A053028  | A261580 | A309588
Numbers k such that w(k) = 1 | this seq | A309583 | A309591
Numbers k such that w(k) = 2 | A053030  | A309584 | A309592
Numbers k such that w(k) = 4 | A053029  | A309585 | A309593
* and also A053032 U {2}

a053031 n = a053031_list !! (n-1)
a053031_list = filter ((== 1) . a001176) [1..]
-- Reinhard Zumkeller, Jan 16 2014

With[{s = {1}~Join~Table[Count[Drop[NestWhile[Append[#, Mod[Total@ Take[#, -2], n]] &, {1, 1}, If[Length@ # < 3, True, Take[#, -2] != {1, 1}] &], -2], 0], {n, 2, 400}]}, Position[s, 1][[All, 1]] ] (* Michael De Vlieger, Aug 08 2018 *)

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]>1e14, 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, Dec 14 2016

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

Original entry on oeis.org

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

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

A235715 a(n) = number of times (n-1) occurs in the fundamental period of Fibonacci numbers modulo n.

Original entry on oeis.org

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

Offset: 1

Reinhard Zumkeller, Jan 17 2014

nonn

a(n) = A128924(n,n).

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A001176, A001175.

a235715 1 = 1
a235715 n = f 1 ps 0 where
   f 0 (1 : xs) z = z
   f _ (x : xs) z = f x xs (z + 0 ^ (n - 1 - x))
   ps = 1 : 1 : zipWith (\u v -> (u + v) `mod` n) (tail ps) ps

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.

cp's OEIS Frontend

A001176 Number of zeros in fundamental period of Fibonacci numbers mod n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

Extensions

A053029 Numbers with 4 zeros in Fibonacci numbers mod m.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

A053030 Numbers with 2 zeros in Fibonacci numbers mod m.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

A053031 Numbers with 1 zero in Fibonacci numbers mod m.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

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

A118965 Number of missing residues in Fibonacci sequence mod n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

Extensions

A235715 a(n) = number of times (n-1) occurs in the fundamental period of Fibonacci numbers modulo n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

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