A212906 Triangle T(n,k) of orders of degree-n irreducible polynomials over GF(3) listed in ascending order.

1, 2, 4, 8, 13, 26, 5, 10, 16, 20, 40, 80, 11, 22, 121, 242, 7, 14, 28, 52, 56, 91, 104, 182, 364, 728, 1093, 2186, 32, 41, 82, 160, 164, 205, 328, 410, 656, 820, 1312, 1640, 3280, 6560, 757, 1514, 9841, 19682, 44, 61, 88, 122, 244, 484, 488, 671, 968, 1342

Offset: 1

Author

Boris Putievskiy, May 29 2012

Keywords

• easy
• nonn
• look
• tabf

Comments

The elements m of row n, are also solutions to the equation: multiplicative order of 3 mod m = n, with gcd(m,3) = 1, cf. A053446.

Examples

			Triangle T(n,k) begins:
1,   2;
4,   8;
13, 26;
5,  10,  16,  20, 40, 80;
11, 22, 121, 242;
7,  14,  28,  52, 56, 91, 104, 182, 364, 728;
		

References

• R. Lidl and H. Niederreiter, Finite Fields, 2nd ed., Cambridge Univ. Press, 1997, Table C, pp. 555-557.
• V. I. Arnol'd, Topology and statistics of formulas of arithmetics, Uspekhi Mat. Nauk, 58:4(352) (2003), 3-28

Links

• Alois P. Heinz, Rows n = 1..47, flattened (first 13 rows from Boris Putievskiy)
• Eric Weisstein's World of Mathematics, Irreducible Polynomial
• XIAO, Polynomial order (computes the order of an irreducible polynomial over a finite field GF(p))

Crossrefs

Cf. A053446, A059912, A059885, A058944, A059499, A059886-A059892.

Column k=2 of A212737.

Column k=1 gives: A218356.

Programs

Maple

with(numtheory):
M:= proc(n) option remember;
      divisors(3^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..15);  # Alois P. Heinz, Jun 02 2012

Mathematica

M[n_] := M[n] = Divisors[3^n - 1] ~Complement~ U[n - 1];
U[n_] := U[n] = If[n == 0, {}, M[n] ~Union~ U[n - 1]];
T[n_] := Sort[M[n]]; Array[T, 15] // Flatten (* Jean-François Alcover, Jun 10 2018, after Alois P. Heinz *)

Formula

T(n,k) = k-th smallest element of M(n) with M(n) = {d : d | (3^n-1)} \ (M(1) U M(2) U ... U M(i-1)) for n>1, M(1) = {1,2}.

|M(n)| = Sum_{d|n} mu(n/d)*tau(3^d-1) = A059885(n).