A212486 -id:A212486 - cp's OEIS frontend

A059889 a(n) = |{m : multiplicative order of 7 mod m=n}|.

4, 6, 8, 26, 4, 42, 12, 48, 52, 66, 12, 778, 4, 138, 80, 300, 12, 528, 12, 1430, 72, 138, 28, 15216, 24, 66, 1216, 966, 28, 3630, 28, 1344, 360, 58, 108, 16988, 28, 138, 176, 12752, 28, 7398, 12, 4422, 1900, 122, 12, 131028, 240, 536, 744, 1046, 28, 23744, 44

Offset: 1

Vladeta Jovovic, Feb 06 2001

nonn

The multiplicative order of a mod m, gcd(a,m)=1, is the smallest natural number d for which a^d = 1 (mod m).
a(n) = number of orders of degree n monic irreducible polynomials over GF(7).
Also, number of primitive factors of 7^n - 1 (cf. A218358). - Max Alekseyev, May 03 2022

Max Alekseyev, Table of n, a(n) for n = 1..388

Number of primitive factors of b^n - 1: A059499 (b=2), A059885(b=3), A059886 (b=4), A059887 (b=5), A059888 (b=6), this sequence (b=7), A059890 (b=8), A059891 (b=9), A059892 (b=10).
Cf. A000005, A008683, A058946, A053450, A057954, A058946, A074249, A212486, A218358
Column k=7 of A212957.

with(numtheory):
a:= n-> add(mobius(n/d)*tau(7^d-1), d=divisors(n)):
seq(a(n), n=1..40);  # Alois P. Heinz, Oct 12 2012

a[n_] := DivisorSum[n, MoebiusMu[n/#] * DivisorSigma[0, 7^#-1] &]; Array[a, 60] (* Amiram Eldar, Jan 25 2025 *)

a(n) = sumdiv(n, d, moebius(n/d) * numdiv(7^d-1)); \\ Amiram Eldar, Jan 25 2025

a(n) = Sum_{d|n} mu(n/d)*tau(7^d-1), (mu(n) = Moebius function A008683, tau(n) = number of divisors of n A000005).

A212737 Square array A(n,k), n>=1, k>=1, read by antidiagonals, where column k lists the orders of degree-d irreducible polynomials over GF(prime(k)); listing order for each column: ascending d, ascending value.

Original entry on oeis.org

1, 1, 3, 1, 2, 7, 1, 2, 4, 5, 1, 2, 4, 8, 15, 1, 2, 3, 3, 13, 31, 1, 2, 5, 6, 6, 26, 9, 1, 2, 3, 10, 4, 8, 5, 21, 1, 2, 4, 4, 3, 8, 12, 10, 63, 1, 2, 3, 8, 6, 4, 12, 24, 16, 127, 1, 2, 11, 6, 16, 12, 6, 16, 31, 20, 17, 1, 2, 4, 22, 9, 3, 7, 8, 24, 62, 40, 51

Offset: 1

Alois P. Heinz, Jun 02 2012

			For k=1 the irreducible polynomials over GF(prime(1)) = GF(2) of degree 1-4 are: x, 1+x; 1+x+x^2; 1+x+x^3, 1+x^2+x^3; 1+x+x^2+x^3+x^4, 1+x+x^4, 1+x^3+x^4. The orders of these polynomials p (i.e., the smallest integer e for which p divides x^e+1) are 1; 3; 7; 5, 15. (Example: (1+x^3+x^4) * (1+x^3+x^4+x^6+x^8+x^9+x^10+x^11) == x^15+1 (mod 2)). Thus column k=1 begins: 1, 3, 7, 5, 15, ... .
Square array A(n,k) begins:
    1,  1,  1,  1,  1,  1,  1,  1,  1,  1, ...
    3,  2,  2,  2,  2,  2,  2,  2,  2,  2, ...
    7,  4,  4,  3,  5,  3,  4,  3, 11,  4, ...
    5,  8,  3,  6, 10,  4,  8,  6, 22,  7, ...
   15, 13,  6,  4,  3,  6, 16,  9,  3, 14, ...
   31, 26,  8,  8,  4, 12,  3, 18,  4, 28, ...
    9,  5, 12, 12,  6,  7,  6,  4,  6,  3, ...
   21, 10, 24, 16,  8,  8,  9,  5,  8,  5, ...
   63, 16, 31, 24, 12, 14, 12,  8, 12,  6, ...
  127, 20, 62, 48, 15, 21, 18, 10, 16,  8, ...

Alois P. Heinz, Antidiagonals n = 1..141, flattened
Eric Weisstein's World of Mathematics, Irreducible Polynomial
Eric Weisstein's World of Mathematics, Polynomial Order

Columns k=1-10 give: A059912, A212906, A212485, A212486, A218336, A218337, A218338, A218339, A218340, A218341.

with(numtheory):
M:= proc(n, i) M(n, i):= divisors(ithprime(i)^n-1) minus U(n-1, i) end:
U:= proc(n, i) U(n, i):= `if`(n=0, {}, M(n, i) union U(n-1, i)) end:
b:= proc(n, i) b(n, i):= sort([M(n, i)[]])[] end:
A:= proc() local l; l:= proc() [] end;
      proc(n, k) local t;
        if nops(l(k))

m[n_, i_] := Divisors[Prime[i]^n-1] ~Complement~ u[n-1, i]; u[n_, i_] := u[n, i] = If[n == 0, {}, m[n, i] ~Union~ u[n-1, i]]; b[n_, i_] := Sort[m[n, i]]; a = Module[{l}, l[] = {}; Function[{n, k}, Module[{t}, If [Length[l[k]] < n, l[k] = {}; For[t = 1, Length[l[k]] < n, t++, l[k] = Join[l[k], b[t, k]]]]; l[k][[n]]]]]; Table[Table[a[n, 1+d-n], {n, 1, d}], {d, 1, 15}] // Flatten (* _Jean-François Alcover, Dec 20 2013, translated from Maple *)

Formulae for the column sequences are given in A059912, A212906, ... .

A213224 Minimal order A(n,k) of degree-n irreducible polynomials over GF(prime(k)); square array A(n,k), n>=1, k>=1, read by antidiagonals.

Original entry on oeis.org

1, 1, 3, 1, 4, 7, 1, 3, 13, 5, 1, 4, 31, 5, 31, 1, 3, 9, 13, 11, 9, 1, 7, 7, 5, 11, 7, 127, 1, 3, 9, 16, 2801, 7, 1093, 17, 1, 4, 307, 5, 25, 36, 19531, 32, 73, 1, 3, 27, 5, 30941, 9, 29, 32, 757, 11, 1, 3, 7, 16, 88741, 63, 43, 64, 19, 44, 23

Offset: 1

Alois P. Heinz, Jun 06 2012

Maximal order of degree-n irreducible polynomials over GF(prime(k)) is prime(k)^n-1 and thus A(n,k) < prime(k)^n.

			A(4,1) = 5: The degree-4 irreducible polynomials p over GF(prime(1)) = GF(2) are 1+x+x^2+x^3+x^4, 1+x+x^4, 1+x^3+x^4. Their orders (i.e., the smallest integer e for which p divides x^e+1) are 5, 15, 15, and the minimal order is 5. (1+x+x^2+x^3+x^4) * (1+x) == x^5+1 (mod 2).
Square array A(n,k) begins:
    1,    1,     1,    1,   1,       1,        1,   1, ...
    3,    4,     3,    4,   3,       7,        3,   4, ...
    7,   13,    31,    9,   7,       9,      307,  27, ...
    5,    5,    13,    5,  16,       5,        5,  16, ...
   31,   11,    11, 2801,  25,   30941,    88741, 151, ...
    9,    7,     7,   36,   9,      63,        7,   7, ...
  127, 1093, 19531,   29,  43, 5229043, 25646167, 701, ...
   17,   32,    32,   64,  32,      32,      128,  17, ...

Alois P. Heinz, Antidiagonals n = 1..45, flattened
Eric Weisstein's World of Mathematics, Irreducible Polynomial
Eric Weisstein's World of Mathematics, Polynomial Order

Columns k=1-10 give: A212953, A218356, A218357, A218358, A218359, A218360, A218361, A218362, A218363, A218364.
Columns k=1-10 are first columns of: A059912, A212906, A212485, A212486, A218336, A218337, A218338, A218339, A218340, A218341.
Cf. A212737 (all orders).

with(numtheory):
M:= proc(n, i) option remember;
      divisors(ithprime(i)^n-1) minus U(n-1, i)
    end:
U:= proc(n, i) option remember;
      `if`(n=0, {}, M(n, i) union U(n-1, i))
    end:
A:= (n, k)-> min(M(n, k)[]):
seq(seq(A(n, d+1-n), n=1..d), d=1..14);

M[n_, i_] := M[n, i] = Divisors[Prime[i]^n - 1] ~Complement~ U[n-1, i]; U[n_, i_] := U[n, i] = If[n == 0, {}, M[n, i] ~Union~ U[n-1, i]]; A[n_, k_] := Min[M[n, k]]; Table[Table[A[n, d+1-n], {n, 1, d}], {d, 1, 14}] // Flatten (* Jean-François Alcover, Dec 13 2013, translated from Maple *)

A(n,k) = min(M(n,k)) with M(n,k) = {d : d|(prime(k)^n-1)} \ U(n-1,k) and U(n,k) = M(n,k) union U(n-1,k) for n>0, U(0,k) = {}.

A059912 Triangle T(n,k) of orders of n degree irreducible polynomials over GF(2) listed in ascending order, k=1..A059499(n).

Original entry on oeis.org

1, 3, 7, 5, 15, 31, 9, 21, 63, 127, 17, 51, 85, 255, 73, 511, 11, 33, 93, 341, 1023, 23, 89, 2047, 13, 35, 39, 45, 65, 91, 105, 117, 195, 273, 315, 455, 585, 819, 1365, 4095, 8191, 43, 129, 381, 5461, 16383, 151, 217, 1057, 4681, 32767, 257, 771, 1285, 3855

Offset: 1

Vladeta Jovovic, Feb 09 2001

A permutation of the odd positive numbers; namely, order each odd number d by the multiplicative order of 2 modulo d (in case of a tie, smaller d go first). - Jeppe Stig Nielsen, Feb 13 2020

			There are 18 (cf. A001037) irreducible polynomials of degree 7 over GF(2) which all have order 127.
Triangle T(n,k) begins:
    1;
    3;
    7;
    5,   15;
   31;
    9,   21,  63;
  127;
   17,   51,  85, 255;
   73,  511;
   11,   33,  93, 341, 1023;
  ...

Alois P. Heinz, Rows n = 1..71, flattened
Eric Weisstein's World of Mathematics, Irreducible Polynomial
XIAO Gang, Polynomial order: computes the order of an irreducible polynomial over a finite field GF(p), WIMS.

Cf. A058943, A059478, A059499, A001037, A059913.
Cf. A212906, A212485, A212486.
Column k=1 of A212737.
Column k=1 gives: A212953.
Last elements of rows give: A000225.
Cf. A108974.

with(numtheory):
M:= proc(n) option remember;
      divisors(2^n-1) minus U(n-1)
    end:
U:= proc(n) option remember;
      `if`(n=0, {}, M(n) union U(n-1))
    end:
T:= n-> sort([M(n)[]])[]:
seq(T(n), n=1..20);  # Alois P. Heinz, May 31 2012

m[n_] := m[n] = Complement[ Divisors[2^n - 1], u[n - 1]]; u[0] = {}; u[n_] := u[n] = Union[ m[n], u[n - 1]]; t[n_, k_] := m[n][[k]]; Flatten[ Table[t[n, k], {n, 1, 16}, {k, 1, Length[ m[n] ]}]] (* Jean-François Alcover, Jun 14 2012, after Alois P. Heinz *)

maxDegree=26;for(n=1,maxDegree,forstep(d=1,2^n,2,znorder(Mod(2,d))==n&&print1(d,", "))) \\ inefficient, Jeppe Stig Nielsen, Feb 13 2020

T(n,k) = k-th smallest element of M(n) = {d : d|(2^n-1)} \ U(n-1) with U(n) = M(n) union U(n-1) if n>0, U(0) = {}. - Alois P. Heinz, Jun 01 2012

A218358 Minimal order of degree-n irreducible polynomials over GF(7).

Original entry on oeis.org

1, 4, 9, 5, 2801, 36, 29, 64, 27, 11, 1123, 13, 16148168401, 113, 31, 17, 14009, 108, 419, 55, 261, 23, 47, 73, 2551, 53, 81, 145, 59, 99, 311, 256, 3631, 56036, 81229, 135, 223, 1676, 486643, 41, 83, 1017, 166003607842448777, 115, 837, 188, 13722816749522711

Offset: 1

Alois P. Heinz, Oct 27 2012

nonn

a(n) < 7^n.

Max Alekseyev, Table of n, a(n) for n = 1..430
Eric Weisstein's World of Mathematics, Irreducible Polynomial
Eric Weisstein's World of Mathematics, Polynomial Order

Cf. A057954, A074249, A212486, A213224.

with(numtheory):
M:= proc(n) M(n):= divisors(7^n-1) minus U(n-1) end:
U:= proc(n) U(n):= `if`(n=0, {}, M(n) union U(n-1)) end:
a:= n-> min(M(n)[]):
seq(a(n), n=1..42);

M[n_] := M[n] = Divisors[7^n - 1]~Complement~U[n - 1];
U[n_] := U[n] = If[n == 0, {}, M[n]~Union~U[n - 1]];
a[n_] := Min[M[n]];
Table[a[n], {n, 1, 47}] (* Jean-François Alcover, Oct 24 2022, after Alois P. Heinz *)

a(n) = min(M(n)) with M(n) = {d : d|(7^n-1)} \ U(n-1) and U(n) = M(n) union U(n-1) for n>0, U(0) = {}.

a(n) = A212486(n,1) = A213224(n,4).

cp's OEIS Frontend

A059889 a(n) = |{m : multiplicative order of 7 mod m=n}|.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A212737 Square array A(n,k), n>=1, k>=1, read by antidiagonals, where column k lists the orders of degree-d irreducible polynomials over GF(prime(k)); listing order for each column: ascending d, ascending value.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A213224 Minimal order A(n,k) of degree-n irreducible polynomials over GF(prime(k)); square array A(n,k), n>=1, k>=1, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A059912 Triangle T(n,k) of orders of n degree irreducible polynomials over GF(2) listed in ascending order, k=1..A059499(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A218358 Minimal order of degree-n irreducible polynomials over GF(7).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula