A235715 -id:A235715 - 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

A128924 T(n,m) is the number of m's in the fundamental period of Fibonacci numbers mod n.

Original entry on oeis.org

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

Offset: 1

R. J. Mathar, Apr 25 2007

T(n,m) is the triangle read by rows, 0<=m

A118965 and A066853 give numbers of zeros and nonzeros in n-th row, respectively. - Reinhard Zumkeller, Jan 16 2014

			{F(k) mod 4} has fundamental period (0,1,1,2,3,1), see A079343, with
T(4,0)=1 zero, T(4,1)=3 ones, T(4,2)=1 two's, T(4,3)=1 three's. The triangle starts
1,
1, 2,
2, 3, 3,
1, 3, 1, 1,
4, 4, 4, 4, 4,
2, 6, 3, 4, 3, 6,
2, 4, 2, 1, 1, 2, 4,
2, 3, 2, 1, 0, 3, 0, 1,
2, 5, 2, 2, 2, 2, 2, 2, 5,
4, 8, 4, 8, 4, 8, 4, 8, 4, 8,
1, 3, 2, 1, 0, 1, 0, 0, 1, 0, 1,
2, 5, 2, 2, 1, 5, 0, 1, 1, 2, 2, 1,
4, 4, 2, 2, 0, 4, 0, 0, 4, 0, 2, 2, 4,
2, 8, 2, 2, 1, 4, 4, 4, 4, 4, 1, 2, 2, 8,
2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3, 2, 3, 3,
2, 3, 4, 1, 0, 3, 0, 1, 2, 3, 0, 1, 0, 3, 0, 1,
4, 4, 2, 2, 4, 2, 0, 0, 2, 2, 0, 0, 2, 4, 2, 2, 4,

Reinhard Zumkeller, Rows n = 1..125 of triangle, flattened
G. Darvasi and St. Eckmann, Zur Verteilung der Reste der Fibonacci-Folge modulo 5c, Elemente der Mathematik 50 (1995) pp. 76-80.

Cf. A053029, A053030, A053031, A001175 (row sums), A001176 (1st column).

import Data.List (group, sort)
a128924 n k = a128924_tabl !! (n-1) !! (k-1)
a128924_tabl = map a128924_row [1..]
a128924_row 1 = [1]
a128924_row n = f [0..n-1] $ group $ sort $ g 1 ps where
   f []     _                            = []
   f (v:vs) wss'@(ws:wss) | head ws == v = length ws : f vs wss
                          | otherwise    = 0 : f vs wss'
   g 0 (1 : xs) = []
   g _ (x : xs) = x : g x xs
   ps = 1 : 1 : zipWith (\u v -> (u + v) `mod` n) (tail ps) ps
-- Reinhard Zumkeller, Jan 16 2014

A128924 := proc(m,h)
    local resul,k,M ;
    resul :=0 ;
    for k from 0 to A001175(m)-1 do
        M := combinat[fibonacci](k) mod m ;
        if M = h then
            resul := resul+1 ;
        end if ;
    end do;
    resul ;
end proc:
seq(seq(A128924(m,h),h=0..m-1),m=1..17) ;

A001175[1] = 1; A001175[n_] := For[k = 1, True, k++, If[Mod[Fibonacci[k], n] == 0 && Mod[Fibonacci[k+1], n] == 1, Return[k]]]; T[m_, h_] := Module[{resul, k, M}, resul = 0; For[k = 0, k <= A001175[m]-1, k++, M = Mod[Fibonacci[k], m]; If[ M == h, resul++]]; Return[resul]]; Table[T[m, h], {m, 1, 17}, {h, 0, m-1}] // Flatten (* Jean-François Alcover, Feb 11 2015, after Maple code *)

T(n,n) = A235715(n). - Reinhard Zumkeller, Jan 17 2014

Showing 1-2 of 2 results.

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