login
Number of orbits of the 3-step recursion mod n.
4

%I #13 Mar 24 2024 07:56:04

%S 1,4,3,12,5,12,9,44,21,20,25,36,15,66,15,172,53,84,21,60,27,144,23,

%T 132,105,116,183,482,177,60,91,684,75,420,45,252,109,162,45,220,125,

%U 198,265,520,105,92,2259,516,359,420,159,884,2867,732,125,3714,63,1408,59,180

%N Number of orbits of the 3-step recursion mod n.

%C 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.

%H D. D. Wall, <a href="http://www.jstor.org/stable/2309169">Fibonacci series modulo m</a>, Amer. Math. Monthly, 67 (1960), 525-532.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Fibonaccin-StepNumber.html">Fibonacci n-Step Number</a>.

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

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

%K nonn

%O 1,2

%A _T. D. Noe_, May 02 2005