cp's OEIS Frontend

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

%I A001176 M0165 N0064 #70 Feb 22 2022 23:08:47
%S A001176 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,
%T A001176 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,
%U A001176 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
%N A001176 Number of zeros in fundamental period of Fibonacci numbers mod n.
%C A001176 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
%C A001176 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
%D A001176 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.
%D A001176 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A001176 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A001176 S. Vajda, Fibonacci and Lucas numbers and the Golden Section, Ellis Horwood Ltd., Chichester, 1989.
%H A001176 T. D. Noe, <a href="/A001176/b001176.txt">Table of n, a(n) for n = 1..1000</a>
%H A001176 Brennan Benfield and Michelle Manes, <a href="https://arxiv.org/abs/2202.08986">The Fibonacci Sequence is Normal Base 10</a>, arXiv:2202.08986 [math.NT], 2022.
%H A001176 J. D. Fulton and W. L. Morris, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa16/aa1621.pdf">On arithmetical functions related to the Fibonacci numbers</a>, Acta Arithmetica, 16 (1969), 105-110.
%H A001176 B. H. Hannon and W. L. Morris, <a href="/A001175/a001175.pdf">Tables of Arithmetical Functions Related to the Fibonacci Numbers</a> [Annotated and scanned copy]
%H A001176 M. Renault, <a href="http://webspace.ship.edu/msrenault/fibonacci/fib.htm">Fibonacci sequence modulo m</a>
%H A001176 Review <a href="http://dx.doi.org/10.1090/S0025-5718-69-99644-6">of B. H. Hannon and W. L. Morris tables</a>, Math. Comp., 23 (1969), 459-460.
%F A001176 a(n) = A001175(n)/A001177(n) for n >= 1.
%F A001176 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
%F A001176 a(n) = A128924(n,1). - _Reinhard Zumkeller_, Jan 17 2014
%F A001176 From _Isaac Saffold_, Aug 30 2018: (Start)
%F A001176 With the sole exception of a(8) = 2,
%F A001176   a(p^k) = 1 if A007814(A001175(p^k)) < 2.
%F A001176   a(p^k) = 4 if A007814(A001175(p^k)) = 2.
%F A001176   a(p^k) = 2 if A007814(A001175(p^k)) > 2. (End)
%F A001176 From _Jianing Song_, Sep 01 2018: (Start)
%F A001176 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.
%F A001176 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)
%e A001176 {F(n) mod 1} has fundamental period (0) with 1 zero.
%e A001176 {F(n) mod 2} has fundamental period (0,1,1) with 1 zero.
%e A001176 {F(n) mod 3} has fundamental period (0,1,1,2,0,2,2,1) with 2 zeros.
%e A001176 {F(n) mod 4} has fundamental period (0,1,1,2,3,1), with 1 zero.
%e A001176 {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.
%t A001176 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 *)
%o A001176 (Haskell)
%o A001176 a001176 1 = 1
%o A001176 a001176 n = f 1 ps 0 where
%o A001176    f 0 (1 : xs) z = z
%o A001176    f _ (x : xs) z = f x xs (z + 0 ^ x)
%o A001176    ps = 1 : 1 : zipWith (\u v -> (u + v) `mod` n) (tail ps) ps
%o A001176 -- _Reinhard Zumkeller_, Jan 15 2014
%Y A001176 Cf. A001175, A001177, A053027, A053028, A053029, A053030, A053031, A053032.
%Y A001176 Cf. A235715.
%K A001176 nonn,easy
%O A001176 1,3
%A A001176 _N. J. A. Sloane_
%E A001176 Better description and more terms from _Henry Bottomley_, Feb 01 2000
%E A001176 Examples from _David W. Wilson_, Jan 05 2005
%E A001176 Replaced the old Renault link with a working one. - _Wolfdieter Lang_, Jan 17 2015