A371595 - OEIS

%I #15 Mar 30 2024 12:59:39

%S 1,8,781,2801,16105,30941,88741,9,22,14,190861,1926221,2896405,7,23,

%T 8042221,29,10,66,560,18,39449441,6888,88,32,100,34,132316201,108,16,

%U 42,26,68,46,74,7600,4108,81,83,43,178,45,190,32,98,1576159601,70,37,226,13110,2959999381,3276517921,29040

%N a(n) is the least period of the 5-step recurrence x(k) = (x(k-1) + x(k-2) + x(k-3) + x(k-4) + x(k-5)) mod prime(n) for initial conditions (x(0),x(1),x(2),x(3),x(4)) other than (0,0,0,0,0) in [0..prime(n)-1]^5.

%C It appears that a(n) <= (prime(n)^5-1)/(prime(n)-1), with equality in many cases.

%H Robert Israel, <a href="/A371595/b371595.txt">Table of n, a(n) for n = 1..10000</a>

%H Robert Israel, <a href="/A371595/a371595_1.pdf">Minimal Period of Linear Recurrences</a>.

%e a(8) = 9 because prime(3) = 5 and the recurrence has minimal period 9; e.g., with initial values 4, 7, 11, 6, 1 it continues 16, 9, 11, 5, 4, 7, 17, 6, 1, ...

%p minperiod:= proc(p)

%p   local Q, q, F, i, z, d, k, kp, G, alpha;

%p   Q:= z^5  - z^4 - z^3 - z^2 - z - 1;

%p   F:= (Factors(Q) mod p)[2];

%p   k:= infinity;

%p   for i from 1 to nops(F) do

%p      q:= F[i][1];

%p      d:= degree(q);

%p      if d = 1 then kp:= NumberTheory:-MultiplicativeOrder(p+solve(q, z), p);

%p      else

%p          G:= GF(p, d, q);

%p          alpha:= G:-ConvertIn(z);

%p          kp:= G:-order(alpha);

%p      fi;

%p      k:= min(k,kp);

%p   od;

%p   k;

%p end proc:

%p map(minperiod, [seq(ithprime(i),i=1..100)]);

%Y Cf. A106309.

%K nonn,look

%O 1,2

%A _Robert Israel_, Mar 28 2024