cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-5 of 5 results.

A106287 Number of orbits of the 5-step recursion mod n.

Original entry on oeis.org

1, 8, 5, 96, 5, 56, 7, 1468, 203, 40, 11, 1312, 13, 56, 25, 23400, 17, 6392, 193, 480, 35, 88, 555, 37180, 2505, 104, 15539, 672, 293, 280, 151, 374292, 55, 136, 35, 199744, 37, 6128, 65, 7340, 41, 392, 1899, 1056, 1015, 6648, 313775, 627280, 14413, 20040, 85
Offset: 1

Views

Author

T. D. Noe, May 02 2005

Keywords

Comments

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 (A106290). For instance, the 1468 orbits mod 8 have lengths of 1, 2, 3, 6, 12 and 24.

Links

Crossrefs

Cf. A015134 (orbits of Fibonacci sequences), A106285 (orbits of 3-step sequences), A106286 (orbits of 4-step sequences), A106290 (number of different orbit lengths), A106309 (n producing a simple orbit structure).

A371566 Primes p such that x^5 - x^4 - x^3 - x^2 - x - 1 is irreducible (mod p).

Original entry on oeis.org

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

Views

Author

Robert Israel, Mar 27 2024

Keywords

Links

Crossrefs

Contained in, but not equal to, A106309. Cf. A370830.

Programs

  • Maple
    P:= x^5 - x^4 - x^3 - x^2 - x - 1:
select(p -> Irreduc(P) mod p, [seq(ithprime(i), i=1..1000)]); # Robert Israel, Mar 13 2024
  • Mathematica
    P = x^5 - x^4 - x^3 - x^2 - x - 1;
Select[Prime[Range[1000]], IrreduciblePolynomialQ[P, Modulus -> #]&] (* Jean-François Alcover, Mar 24 2024, after Robert Israel *)
  • PARI
    a371566(upto) = forprime (p=2, upto, my(f=factormod(x^5 - x^4 - x^3 - x^2 - x - 1, p)); if(#f[,1]==1, print1(p,", "))) \\ Hugo Pfoertner, Mar 22 2024
  • Python
    from itertools import islice
from sympy import Poly, nextprime
from sympy.abc import x
def A371566_gen(): # generator of terms
    p = 2
    while True:
        if Poly(x*(x*(x*(x*(x-1)-1)-1)-1)-1, x, modulus=p).is_irreducible:
            yield p
        p = nextprime(p)
A371566_list = list(islice(A371566_gen(),20)) # Chai Wah Wu, Mar 14 2024

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

Views

Author

T. D. Noe, May 02 2005

Keywords

Comments

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.

Links

Crossrefs

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

Programs

  • Python
    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

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

Views

Author

Robert Israel, Mar 28 2024

Keywords

Comments

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?

Examples

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

Links

Crossrefs

Cf. A106309, A371566.

Programs

  • Maple
    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)]);

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.

Original entry on oeis.org

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

Views

Author

Robert Israel, Mar 28 2024

Keywords

Comments

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

Examples

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

Links

Crossrefs

Cf. A106309.

Programs

  • 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)]);
Showing 1-5 of 5 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.