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

1, 8, 781, 2801, 16105, 30941, 88741, 9, 22, 14, 190861, 1926221, 2896405, 7, 23, 8042221, 29, 10, 66, 560, 18, 39449441, 6888, 88, 32, 100, 34, 132316201, 108, 16, 42, 26, 68, 46, 74, 7600, 4108, 81, 83, 43, 178, 45, 190, 32, 98, 1576159601, 70, 37, 226, 13110, 2959999381, 3276517921, 29040

Offset

1,2

Comments

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

Links

Robert Israel, Table of n, a(n) for n = 1..10000

Robert Israel, Minimal Period of Linear Recurrences.

Example

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

Maple

minperiod:= proc(p)
  local Q, q, F, i, z, d, k, kp, G, alpha;
  Q:= z^5  - z^4 - z^3 - z^2 - z - 1;
  F:= (Factors(Q) mod p)[2];
  k:= infinity;
  for i from 1 to nops(F) do
     q:= F[i][1];
     d:= degree(q);
     if d = 1 then kp:= NumberTheory:-MultiplicativeOrder(p+solve(q, z), p);
     else
         G:= GF(p, d, q);
         alpha:= G:-ConvertIn(z);
         kp:= G:-order(alpha);
     fi;
     k:= min(k, kp);
  od;
  k;
end proc:
map(minperiod, [seq(ithprime(i), i=1..100)]);

Crossrefs

Cf. A106309.

Sequence in context: A262353 A268148 A145415 * A260032 A332178 A204464

Adjacent sequences: A371592 A371593 A371594 * A371596 A371597 A371598

Keyword

nonn,look

Author

Robert Israel, Mar 28 2024

Status

approved