A389175 - OEIS

%I #60 Nov 02 2025 16:05:56

%S 1,6,72,936,28080,3397680,23783760

%N Period of all n-th order linear recurrence integers sequence with constant integer coefficients mod 9.

%C The linear recurrences of order n considered are f(m) = k_1*f(m-1) + k_2*f(m-2) + ... + k_n*f(m-n) for some set of integer coefficients k_i and initial integer values f(i) for 0 <= i < n.

%C f(m) mod 9 is eventually periodic and a(n) is the least common multiple of the periods over all such recurrences.

%C So f(t) == f(t - a(n)) (mod 9) for t big enough to be in the periodic part of all the recurrences, and nothing smaller than a(n) suffices.

%C Digital root A010888 has the same effect as mod 9 provided coefficients and initial values are >= 0 so as all terms f(m) >= 0.

%C a(n) is a multiple of the n-step Fibonacci period A210456(n) since its recurrence is among those considered here (and goes past the point where digital root differs from mod 9).

%C a(n) is a multiple of a(n-1) since all order n-1 recurrences are included in order n by taking coefficient k_n = 0.

%C a(n) is a multiple of a(1)*n = 6*n since the recurrences k_n = 0,1,...,8 and otherwise k_i = 0, starting from f(n-1) = 1 and otherwise f(i) = 0, are equivalent to the a(1) recurrences spread out to n terms apart.

%H Shixuan Gao, <a href="/A389175/a389175.cpp.txt">C++ program</a>

%e It suffices to consider recurrence coefficients and terms mod 9: for n=1 the combinations in f(m) = k*f(m-1) starting f(0) = b are

%e   k=0: f = b,0,0,..., period 1.

%e   k=1: f = b,b,b,..., period 1.

%e   k=2: f = b,2*b,4*b,8*b,7*b,5*b,b,2*b,..., period 6 (or divisor of).

%e   k=3: f = b,3*b,0,0,..., period 1.

%e   k=4: f = b,4*b,7*b,b,4*b,..., period 3.

%e   k=5: f = b,5*b,7*b,8*b,4*b,2*b,b,5*b,..., period 6 (or divisor of).

%e   k=6: f = b,6*b,0,0,..., period 1.

%e   k=7: f = b,7*b,4*b,b,..., period 3.

%e   k=8: f = b,8*b,b,..., period 2.

%e The least common multiple of these periods is lcm(1,1,6,1,3,6,1,3,2) = 6 = a(1).

%o (C++) // See Links

%Y Cf. A010878, A010888, A210456, A351889.

%K nonn,base,more

%O 0,2

%A _Shixuan Gao_, Oct 23 2025