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

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,2

Comments

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.

Links

Table of n, a(n) for n=1..60.

D. D. Wall, Fibonacci series modulo m, Amer. Math. Monthly, 67 (1960), 525-532.

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

Example

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)}

Crossrefs

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).

Sequence in context: A099377 A121844 A091512 * A240134 A193800 A061727

Adjacent sequences: A106282 A106283 A106284 * A106286 A106287 A106288

Keyword

nonn

Author

T. D. Noe, May 02 2005

Status

approved