A015134 -id:A015134 - cp's OEIS frontend

A179390 Modulus for Fibonacci-type sequence described by A015134.

1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15

Offset: 1

Will Nicholes, Jul 12 2010

First terms of A015134 are 1, 2, 2 and 4, meaning that there are 1, 2, 2 and 4 Fibonacci-type sequences modulo 1, 2, 3 and 4 respectively. These are:
mod 1: 0
mod 2: 0
mod 2: 0,1,1
mod 3: 0
mod 3: 0,1,1,2,0,2,2,1
mod 4: 0
mod 4: 0,1,1,2,3,1
mod 4: 0,2,2
mod 4: 0,3,3,2,1,3

Will Nicholes, Fibonacci numbers and Pisano periods.

Cf. A015134, A179391, A179392, A179393.

A179391 First term in Fibonacci-type sequence described by A015134.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2

Offset: 1

Will Nicholes, Jul 12 2010

First terms of A015134 are 1, 2, 2 and 4, meaning that there are 1, 2, 2 and 4 Fibonacci-type sequences modulo 1, 2, 3 and 4 respectively. These are:
mod 1: 0
mod 2: 0
mod 2: 0,1,1
mod 3: 0
mod 3: 0,1,1,2,0,2,2,1
mod 4: 0
mod 4: 0,1,1,2,3,1
mod 4: 0,2,2
mod 4: 0,3,3,2,1,3

Will Nicholes, Fibonacci numbers and Pisano periods.

Cf. A015134, A179390, A179392, A179393.

A179392 Second term in Fibonacci-type sequence described by A015134.

Original entry on oeis.org

0, 0, 1, 0, 1, 0, 1, 2, 3, 0, 1, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 4, 6, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 5, 3, 6, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 4, 8, 8, 0, 1, 2, 3, 4, 6, 7, 9, 3, 5, 0, 1, 2, 4, 3, 4, 5, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 8, 3, 8, 13, 6, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 12, 3, 4, 5, 11

Offset: 1

Will Nicholes, Jul 12 2010

First terms of A015134 are 1, 2, 2 and 4, meaning that there are 1, 2, 2 and 4 Fibonacci-type sequences modulo 1, 2, 3 and 4 respectively. These are:
mod 1: 0
mod 2: 0
mod 2: 0,1,1
mod 3: 0
mod 3: 0,1,1,2,0,2,2,1
mod 4: 0
mod 4: 0,1,1,2,3,1
mod 4: 0,2,2
mod 4: 0,3,3,2,1,3

Will Nicholes, Fibonacci numbers and Pisano periods.

Cf. A015134, A179390, A179391, A179393.

A179393 Period of the Fibonacci-type sequence described by A015134.

Original entry on oeis.org

1, 1, 3, 1, 8, 1, 6, 3, 6, 1, 20, 4, 1, 24, 8, 3, 1, 16, 16, 16, 1, 12, 6, 12, 3, 6, 12, 12, 1, 24, 24, 8, 24, 1, 60, 20, 3, 12, 4, 1, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 5, 10, 5, 1, 24, 24, 6, 8, 3, 24, 6, 24, 24, 1, 28, 28, 28, 28, 28, 28, 1, 48, 16, 48, 16, 48, 16, 3, 1, 40, 40, 20

Offset: 1

Will Nicholes, Jul 12 2010

First terms of A015134 are 1, 2, 2 and 4, meaning that there are 1, 2, 2 and 4 Fibonacci-type sequences modulo 1, 2, 3 and 4 respectively. These are:
mod 1: 0
mod 2: 0
mod 2: 0,1,1
mod 3: 0
mod 3: 0,1,1,2,0,2,2,1
mod 4: 0
mod 4: 0,1,1,2,3,1
mod 4: 0,2,2
mod 4: 0,3,3,2,1,3
The first sequence for each modulus is the period-1 sequence of 0,0,0... This has the helpful side effect of causing 1 to act as a delimiter between modulus entries: the first 1 indicates the start of modulo-1 sequences, the second 1 indicates the start of modulo-2 sequences, etc.
For each group of sequences (the group start indicated by a 1), the sum of the periods in that group equal the square of the modulus. 1 = 1, (1+3) = 4, (1+8) = 9, (1+6+3+6) = 16, etc.

Will Nicholes, Fibonacci numbers and Pisano periods.

Cf. A015134, A179390, A179391, A179392.

A365519 Moebius inversion of A015134.

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 3, 4, 3, 2, 13, 4, 6, 3, 8, 8, 8, 9, 21, 8, 24, 13, 11, 16, 10, 6, 9, 12, 62, 8, 33, 16, 24, 24, 24, 36, 18, 63, 24, 32, 42, 24, 21, 48, 24, 33, 69, 64, 21, 10, 32, 24, 26, 27, 144, 48, 40, 62, 61, 32, 62, 99, 72, 32, 48, 24, 33, 96, 88, 24

Offset: 1

Jay Anderson, Sep 07 2023

nonn

			For n=4, the a(4) = 2 cycles counted are
  {0 1 1 2 3 1} repeating
  {0 3 3 2 1 3} repeating
There are 2 other cycles {0} and {0 2 2} mod 4 which are not counted because they are multiples of cycles counted at earlier n (n=1 for {0} and n=2 for {0 1 1}*2 = {0 2 2}).

Cf. A008683, A015134.

a[n_]:=Sum[MoebiusMu[d]Part[ResourceFunction["OEISSequence"]["A015134"],n/d],{d,Divisors[n]}]; Array[a,70] (* Stefano Spezia, Sep 27 2023 *)

a(n) = Sum_{d|n} moebius(d)*A015134(n/d).

A015134(n) = Sum_{d|n} a(d).

A106285 Number of orbits of the 3-step recursion mod n.

Original entry on oeis.org

1, 4, 3, 12, 5, 12, 9, 44, 21, 20, 25, 36, 15, 66, 15, 172, 53, 84, 21, 60, 27, 144, 23, 132, 105, 116, 183, 482, 177, 60, 91, 684, 75, 420, 45, 252, 109, 162, 45, 220, 125, 198, 265, 520, 105, 92, 2259, 516, 359, 420, 159, 884, 2867, 732, 125, 3714, 63, 1408, 59, 180

Offset: 1

T. D. Noe, May 02 2005

nonn

Consider the 3-step recursion x(k)=x(k-1)+x(k-2)+x(k-3) mod n. For any of the n^3 initial conditions x(1), x(2) and x(3) in Zn, the recursion has a finite period. Each of these n^3 vectors belongs to exactly one orbit. In general, there are only a few different orbit lengths (A106288) for each n. For instance, the orbits mod 8 have lengths of 1, 2, 4, 8, 16. Interestingly, for n=2^k and n=3^k, the number of orbits appear to be A039301 and A054879, respectively.

			Orbits for n=2: {(0,0,0)}, {(1,1,1)}, {(0,1,0), (1,0,1)} and {(0,0,1), (0,1,1), (1,1,0), (1,0,0)}

D. D. Wall, Fibonacci series modulo m, Amer. Math. Monthly, 67 (1960), 525-532.
Eric Weisstein's World of Mathematics, Fibonacci n-Step Number.

Cf. A015134 (orbits of Fibonacci sequences), A106286 (orbits of 4-step sequences), A106287 (orbits of 5-step sequences), A106288 (number of different orbit lengths), A106307 (n producing a simple orbit structure).

A106286 Number of orbits of the 4-step recursion mod n.

Original entry on oeis.org

1, 4, 6, 28, 3, 24, 10, 220, 91, 12, 130, 240, 343, 40, 168, 1756, 19, 364, 22, 132, 81, 2068, 26, 1968, 253, 1372, 2336, 448, 2557, 672, 16, 14044, 1143, 76, 108, 4612, 1411, 88, 3084, 1860, 11815, 324, 22, 32092, 13213, 104, 50, 15792, 2467, 4012, 168, 17812

Offset: 1

T. D. Noe, May 02 2005

nonn

Consider the 4-step recursion x(k)=x(k-1)+x(k-2)+x(k-3)+x(k-4) mod n. For any of the n^4 initial conditions x(1), x(2), x(3) and x(4) in Zn, the recursion has a finite period. Each of these n^4 vectors belongs to exactly one orbit. In general, there are only a few different orbit lengths (A106289) for each n. For instance, the 220 orbits mod 8 have lengths of 1, 5, 10 and 20.

D. D. Wall, Fibonacci series modulo m, Amer. Math. Monthly, 67 (1960), 525-532.
Eric Weisstein's World of Mathematics, Fibonacci n-Step Number.

Cf. A015134 (orbits of Fibonacci sequences), A106285 (orbits of 3-step sequences), A106287 (orbits of 5-step sequences), A106289 (number of different orbit lengths), A106308 (n producing a simple orbit structure).

A106287 Number of orbits of the 5-step recursion mod n.

Original entry on oeis.org

1, 8, 5, 96, 5, 56, 7, 1468, 203, 40, 11, 1312, 13, 56, 25, 23400, 17, 6392, 193, 480, 35, 88, 555, 37180, 2505, 104, 15539, 672, 293, 280, 151, 374292, 55, 136, 35, 199744, 37, 6128, 65, 7340, 41, 392, 1899, 1056, 1015, 6648, 313775, 627280, 14413, 20040, 85

Offset: 1

T. D. Noe, May 02 2005

nonn

Consider the 5-step recursion x(k)=x(k-1)+x(k-2)+x(k-3)+x(k-4)+x(k-5) mod n. For any of the n^5 initial conditions x(1), x(2), x(3), x(4) and x(5) in Zn, the recursion has a finite period. Each of these n^5 vectors belongs to exactly one orbit. In general, there are only a few different orbit lengths (A106290). For instance, the 1468 orbits mod 8 have lengths of 1, 2, 3, 6, 12 and 24.

D. D. Wall, Fibonacci series modulo m, Amer. Math. Monthly, 67 (1960), 525-532.
Eric Weisstein's World of Mathematics, Fibonacci n-Step Number.

Cf. A015134 (orbits of Fibonacci sequences), A106285 (orbits of 3-step sequences), A106286 (orbits of 4-step sequences), A106290 (number of different orbit lengths), A106309 (n producing a simple orbit structure).

A088551 Fibonacci winding number: the number of 'mod n' operations in one cycle of the Fibonacci sequence modulo n.

Original entry on oeis.org

1, 3, 2, 8, 11, 7, 4, 11, 28, 3, 9, 12, 23, 19, 9, 16, 11, 7, 28, 5, 12, 23, 9, 48, 40, 35, 19, 4, 59, 12, 19, 15, 16, 39, 9, 36, 6, 27, 28, 19, 19, 43, 11, 59, 23, 15, 9, 55, 148, 35, 38, 52, 35, 6, 21, 31, 16, 26, 57, 28, 12, 21, 43, 68, 51, 67, 14, 19, 119, 32, 7, 72, 112, 99, 5, 33

Offset: 2

R C Johnson (bob.johnson(AT)dur.ac.uk), Nov 19 2003

If pi(n) is the n-th Pisano number (A001175) then a(n) is usually about pi(n)/2 - and in any case a(n) > pi(n)/4.

			a(8)=4 because one cycle of the Fibonacci numbers modulo 8 is 0, 1, 1, 2, 3, 5; 0, 5, 5; 2, 7; 1; - including 4 'mod 8' operations, each marked with a semi-colon.

T. D. Noe, Table of n, a(n) for n=2..10000
R. C. Johnson, Fibonacci Numbers and Resources.
M. Merca, Inequalities and Identities Involving Sums of Integer Functions, J. Int. Seq. 14 (2011) # 11.9.1.

Cf. A001175, A015134, A214300.

(* pp = Pisano period = A001175 *) pp[1] = 1;
pp[n_] := For[k = 1, True, k++, If[Mod[Fibonacci[k], n] == 0 && Mod[Fibonacci[k + 1], n] == 1, Return[k]]];
a[n_] := Sum[Mod[Fibonacci[k], n], {k, 1, pp[n]}]/n;
Table[a[n], {n, 2, 77}] (* Jean-François Alcover, Sep 05 2017 *)

n*a(n) = sum{k=1..A001175(n)} fibonacci(k) mod n. [Mircea Merca, Jan 03 2011]

More terms from T. D. Noe

Edited by Ray Chandler, Oct 26 2006

A106306 Primes that yield a simple orbit structure in 2-step recursions.

Original entry on oeis.org

2, 3, 7, 13, 17, 23, 37, 41, 43, 47, 53, 61, 67, 73, 83, 89, 97, 103, 107, 109, 113, 127, 137, 149, 157, 163, 167, 173, 193, 197, 223, 227, 233, 241, 257, 263, 269, 277, 281, 283, 293, 307, 313, 317, 337, 347, 353, 367, 373, 383, 389, 397, 401, 409, 421, 433

Offset: 1

T. D. Noe, May 02 2005

nonn

Consider the 2-step recursion x(k)=x(k-1)+x(k-2) mod n. For any of the n^2 initial conditions x(1) and x(2) in Zn, the recursion has a finite period. When n is a prime in this sequence, all of the orbits, except the one containing (0,0), have the same length.
Except for 5, this appears to be the complement of A053032, odd primes p with one 0 in Fibonacci numbers mod p. - T. D. Noe, May 03 2005
A prime p is in this sequence if either (1) the polynomial x^2-x-1 mod p has no zeros for x in [0,p-1] (see A086937) or (2) the polynomial has zeros, but none is a root of unity mod p. The first few primes in the second category are 41, 61, 89 and 109. - T. D. Noe, May 12 2005

Eric Weisstein's World of Mathematics, Fibonacci n-Step Number.

Cf. A015134 (orbits of 2-step sequences).

cp's OEIS Frontend

A179390 Modulus for Fibonacci-type sequence described by A015134.

Views

Author

Keywords

Comments

Links

Crossrefs

A179391 First term in Fibonacci-type sequence described by A015134.

Views

Author

Keywords

Comments

Links

Crossrefs

A179392 Second term in Fibonacci-type sequence described by A015134.

Views

Author

Keywords

Comments

Links

Crossrefs

A179393 Period of the Fibonacci-type sequence described by A015134.

Views

Author

Keywords

Comments

Links

Crossrefs

A365519 Moebius inversion of A015134.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A106285 Number of orbits of the 3-step recursion mod n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A106286 Number of orbits of the 4-step recursion mod n.

Views

Author

Keywords

Comments

Links

Crossrefs

A106287 Number of orbits of the 5-step recursion mod n.

Views

Author

Keywords

Comments

Links

Crossrefs

A088551 Fibonacci winding number: the number of 'mod n' operations in one cycle of the Fibonacci sequence modulo n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A106306 Primes that yield a simple orbit structure in 2-step recursions.

Views

Author

Keywords

Comments

Links

Crossrefs