|
| |
|
|
A001176
|
|
Number of zeros in fundamental period of Fibonacci numbers mod n.
(Formerly M0165 N0064)
|
|
26
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
COMMENTS
|
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
|
|
|
REFERENCES
|
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.
|
|
|
LINKS
|
|
|
|
FORMULA
|
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
With the sole exception of a(8) = 2,
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)
|
|
|
EXAMPLE
|
{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.
|
|
|
MATHEMATICA
|
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 *)
|
|
|
PROG
|
(Haskell)
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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Replaced the old Renault link with a working one. - Wolfdieter Lang, Jan 17 2015
|
|
|
STATUS
|
approved
|
| |
|
|
