A371566 -id:A371566 - cp's OEIS frontend

A106309 Primes p such that for all initial conditions (x(0),x(1),x(2),x(3),x(4)) in [0..p-1]^5 except [0,0,0,0,0], the 5-step recurrence x(k) = x(k-1) + x(k-2) + x(k-3) + x(k-4) + x(k-5) (mod p) has the same period.

5, 7, 11, 13, 17, 31, 37, 41, 53, 79, 107, 199, 233, 239, 311, 331, 337, 389, 463, 523, 541, 547, 557, 563, 577, 677, 769, 853, 937, 971, 1009, 1021, 1033, 1049, 1061, 1201, 1237, 1291, 1307, 1361, 1427, 1453, 1543, 1657, 1699, 1723, 1747, 1753, 1759, 1787, 1801, 1811, 1861, 1877, 1997, 1999

Offset: 1

T. D. Noe, May 02 2005, revised May 12 2005

nonn

The first term not in A371566 is a(105) = 4259.

			a(3) = 11 is a term because the recurrence has period 16105 for all initial conditions except (0,0,0,0,0).

Robert Israel, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Fibonacci n-Step Number
Robert Israel, Linear Recurrences With a Single Minimal Period

Cf. A106287 (orbits of 5-step sequences). Contains A371566.

filter:= proc(p) local Q,q,F,i,z,d,k,kp,G,alpha;
  Q:= z^5  - z^4 - z^3 - z^2 - z - 1;
  if Irreduc(Q) mod p then return true fi;
  F:= (Factors(Q) mod p)[2];
  if ormap(t -> t[2]>1, F) then return false fi;
  for i from 1 to nops(F) do
    q:= F[i][1];
    d:= degree(q);
    if d = 1 then
       kp:= numtheory:-order(solve(q,z),p);
    else
       G:= GF(p,d, q);
       alpha:= G:-ConvertIn(z);
       kp:= G:-order(alpha);
    fi;
    if i = 1 then k:= kp
    elif kp <> k then return false
    fi;
  od;
  true
end proc:
select(filter, [seq(ithprime(i),i=1..1000)]);

4259 found by D. S. McNeil.

Edited by Robert Israel, Mar 27 2024

A371569 Primes p such that for all initial conditions (x(0),x(1),x(2),x(3),x(4)) in [0..p-1]^5 except [0,0,0,0,0], the 5-step recurrence x(k) = x(k-1) + x(k-2) + x(k-3) + x(k-4) + x(k-5) (mod p) has the same period, but x^5 - x^4 - x^3 - x^2 - x - 1 is reducible (mod p).

Original entry on oeis.org

4259, 61643, 94307, 110063, 118171, 348149, 1037903, 1872587, 2149403, 2331859, 2450807, 2490263, 2500847, 2521823, 2534659, 2772179, 2788367, 2789939, 3271883, 3399707, 3550751, 3577487, 3640859, 3861899, 3904309, 4016219, 4063211, 4236719, 4245239, 4368739, 4441007, 4542779, 5033477, 5446283

Offset: 1

Robert Israel, Mar 28 2024

nonn

Terms of A106309 that are not in A371566.

In each of the first 2000 terms, x^5 - x^4 - x^3 - x^2 - x - 1 splits into linear factors (mod p). Are there any where it does not?

			a(3) = 94307 is a term because 94307 is prime, z^5  - z^4 - z^3 - z^2 - z - 1 = (z + 11827)*(z + 78583)*(z + 54610)*(z + 14536)*(z + 29057) (mod 94307), and the recurrence has period 47153 for all initial conditions except (0,0,0,0,0), as -11827, -78583, -54610, -14536, and -29057 all have multiplicative order 47153 (mod 94307).

Robert Israel, Table of n, a(n) for n = 1..2000
Robert Israel, Linear Recurrences with a Single Minimal Period

Cf. A106309, A371566.

filter:= proc(p) local Q, q, F, i, z, d, k, kp, G, alpha;
  if not isprime(p) then return false fi;
  Q:= z^5  - z^4 - z^3 - z^2 - z - 1;
  if Irreduc(Q) mod p then return false fi;
  F:= (Factors(Q) mod p)[2];
  if ormap(t -> t[2]>1, F) then return false fi;
  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;
     if i = 1 then k:= kp
     elif kp <> k then return false
     fi;
  od;
  true
end proc:
select(filter, [seq(i, i=3 .. 10^7,2)]);

cp's OEIS Frontend

A106309 Primes p such that for all initial conditions (x(0),x(1),x(2),x(3),x(4)) in [0..p-1]^5 except [0,0,0,0,0], the 5-step recurrence x(k) = x(k-1) + x(k-2) + x(k-3) + x(k-4) + x(k-5) (mod p) has the same period.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Extensions