A106287 -id:A106287 - 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

A106285 Number of orbits of the 3-step recursion mod n.

Original entry on oeis.org

1, 4, 3, 12, 5, 12, 9, 44, 21, 20, 25, 36, 15, 66, 15, 172, 53, 84, 21, 60, 27, 144, 23, 132, 105, 116, 183, 482, 177, 60, 91, 684, 75, 420, 45, 252, 109, 162, 45, 220, 125, 198, 265, 520, 105, 92, 2259, 516, 359, 420, 159, 884, 2867, 732, 125, 3714, 63, 1408, 59, 180

Offset: 1

T. D. Noe, May 02 2005

nonn

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.

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

D. D. Wall, Fibonacci series modulo m, Amer. Math. Monthly, 67 (1960), 525-532.
Eric Weisstein's World of Mathematics, Fibonacci n-Step Number.

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

A106286 Number of orbits of the 4-step recursion mod n.

Original entry on oeis.org

1, 4, 6, 28, 3, 24, 10, 220, 91, 12, 130, 240, 343, 40, 168, 1756, 19, 364, 22, 132, 81, 2068, 26, 1968, 253, 1372, 2336, 448, 2557, 672, 16, 14044, 1143, 76, 108, 4612, 1411, 88, 3084, 1860, 11815, 324, 22, 32092, 13213, 104, 50, 15792, 2467, 4012, 168, 17812

Offset: 1

T. D. Noe, May 02 2005

nonn

Consider the 4-step recursion x(k)=x(k-1)+x(k-2)+x(k-3)+x(k-4) mod n. For any of the n^4 initial conditions x(1), x(2), x(3) and x(4) in Zn, the recursion has a finite period. Each of these n^4 vectors belongs to exactly one orbit. In general, there are only a few different orbit lengths (A106289) for each n. For instance, the 220 orbits mod 8 have lengths of 1, 5, 10 and 20.

D. D. Wall, Fibonacci series modulo m, Amer. Math. Monthly, 67 (1960), 525-532.
Eric Weisstein's World of Mathematics, Fibonacci n-Step Number.

Cf. A015134 (orbits of Fibonacci sequences), A106285 (orbits of 3-step sequences), A106287 (orbits of 5-step sequences), A106289 (number of different orbit lengths), A106308 (n producing a simple orbit structure).

A106290 Number of different orbit lengths of the 5-step recursion mod n.

Original entry on oeis.org

1, 3, 4, 4, 2, 9, 2, 6, 7, 6, 2, 11, 2, 6, 8, 8, 2, 9, 3, 8, 8, 6, 4, 12, 3, 6, 10, 8, 3, 18, 2, 10, 8, 6, 4, 11, 2, 6, 8, 12, 2, 18, 4, 8, 14, 9, 4, 16, 3, 9, 8, 8, 2, 12, 4, 12, 10, 6, 3, 22

Offset: 1

T. D. Noe, May 02 2005

Consider the 5-step recursion x(k) = (x(k-1)+x(k-2)+x(k-3)+x(k-4)+x(k-5)) mod n. For any of the n^5 initial conditions x(1), x(2), x(3), x(4) and x(5) in Zn, the recursion has a finite period. Each of these n^5 vectors belongs to exactly one orbit. In general, there are only a few different orbit lengths for each n. For n=8, there are 6 different lengths: 1, 2, 3, 6, 12 and 24. The maximum possible length of an orbit is A106303(n), the period of the Fibonacci 5-step sequence mod n.

Eric Weisstein's World of Mathematics, Fibonacci n-Step Number.

Cf. A106287 (orbits of 5-step sequences), A106309 (primes that yield a simple orbit structure in 5-step recursions).

from itertools import count,product
def A106290(n):
    bset, tset = set(), set()
    for t in product(range(n),repeat=5):
        t2 = t
        for c in count(1):
            t2 = t2[1:] + (sum(t2)%n,)
            if t == t2:
                bset.add(c)
                tset.add(t)
                break
            if t2 in tset:
                tset.add(t)
                break
    return len(bset) # Chai Wah Wu, Feb 22 2022

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

A106285 Number of orbits of the 3-step recursion mod n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A106286 Number of orbits of the 4-step recursion mod n.

Views

Author

Keywords

Comments

Links

Crossrefs

A106290 Number of different orbit lengths of the 5-step recursion mod n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python