login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001176 Number of zeros in fundamental period of Fibonacci numbers mod n.
(Formerly M0165 N0064)
24

%I M0165 N0064

%S 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 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 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 Number of zeros in fundamental period of Fibonacci numbers mod n.

%C 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 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 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 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D S. Vajda, Fibonacci and Lucas numbers and the Golden Section, Ellis Horwood Ltd., Chichester, 1989.

%H T. D. Noe, <a href="/A001176/b001176.txt">Table of n, a(n) for n = 1..1000</a>

%H 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 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 M. Renault, <a href="http://webspace.ship.edu/msrenault/fibonacci/fib.htm">Fibonacci sequence modulo m</a>

%H 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 a(n) = A001175(n)/A001177(n) for n >= 1.

%F 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 a(n) = A128924(n,1). - _Reinhard Zumkeller_, Jan 17 2014

%F From _Isaac Saffold_, Aug 30 2018: (Start)

%F With the sole exception of a(8) = 2,

%F a(p^k) = 1 if A007814(A001175(p^k)) < 2.

%F a(p^k) = 4 if A007814(A001175(p^k)) = 2.

%F a(p^k) = 2 if A007814(A001175(p^k)) > 2. (End)

%F From _Jianing Song_, Sep 01 2018: (Start)

%F 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 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 {F(n) mod 1} has fundamental period (0) with 1 zero.

%e {F(n) mod 2} has fundamental period (0,1,1) with 1 zero.

%e {F(n) mod 3} has fundamental period (0,1,1,2,0,2,2,1) with 2 zeros.

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

%e {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 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 (Haskell)

%o a001176 1 = 1

%o a001176 n = f 1 ps 0 where

%o f 0 (1 : xs) z = z

%o f _ (x : xs) z = f x xs (z + 0 ^ x)

%o ps = 1 : 1 : zipWith (\u v -> (u + v) `mod` n) (tail ps) ps

%o -- _Reinhard Zumkeller_, Jan 15 2014

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

%Y Cf. A235715.

%K nonn,easy

%O 1,3

%A _N. J. A. Sloane_

%E Better description and more terms from _Henry Bottomley_, Feb 01 2000

%E Examples from _David W. Wilson_, Jan 05 2005

%E Replaced the old Renault link with a working one. - _Wolfdieter Lang_, Jan 17 2015

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 12 22:57 EST 2018. Contains 318081 sequences. (Running on oeis4.)