A027362 -id:A027362 - cp's OEIS frontend

A003473 Generalized Euler phi function (for p=2).

1, 2, 3, 8, 15, 24, 49, 128, 189, 480, 1023, 1536, 4095, 6272, 10125, 32768, 65025, 96768, 262143, 491520, 583443, 2095104, 4190209, 6291456, 15728625, 33546240, 49545027, 102760448, 268435455, 331776000, 887503681, 2147483648, 3211797501, 8522956800, 12325233375, 25367150592, 68719476735, 137438429184, 206007472125

Offset: 1

N. J. A. Sloane

nonn

a(n) is the number of n X n circulant invertible matrices over GF(2). - Yuval Dekel (dekelyuval(AT)hotmail.com), Aug 20 2003
From Geoffrey Critzer, Oct 13 2024: (Start)
a(n) is the number of units in the ring F_2[x]/.
Let T be the companion matrix of x^n-1 and let M_T be the F_2[x] module induced by T where the action is f*v = f(T)v.  Then a(n) is the number of cyclic vectors in M_T.
a(n) is the number of elements in M_T whose local minimal polynomial is x^n-1.
a(n) is the order of the stabilizer subgroup of T under the action of conjugation.
a(n) is the number of polynomials f(x) in F_2[x] of degree < n such that
 gcd(x^n-1,f(x)) = 1.
a(n) is the number of normal elements in the field F_2^n. (End)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..1000
J. T. B. Beard Jr. and K. I. West, Factorization tables for x^n-1 over GF(q), Math. Comp., 28 (1974), 1167-1168.
Swee Hong Chan, Henk D. L. Hollmann, and Dmitrii V. Pasechnik, Sandpile groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields, arXiv:1405.0113 [math.CO], (1-May-2014).
Gabriele Fici and Estéban Gabory, Generalized De Bruijn Words, Invertible Necklaces, and the Burrows-Wheeler Transform, arXiv:2502.12844 [math.CO], 2025. See Table 2 p. 11.

Cf. A003474 (p=3), A192037 (p=5).

Cf. also A086479, A027362.

p = 2; numNormalp[n_] := Module[{r, i, pp}, pp = 1; Do[r = MultiplicativeOrder[p, d]; i = EulerPhi[d]/r; pp *= (1 - 1/p^r)^i, {d, Divisors[n]}]; Return[pp]]; numNormal[n_] := Module[{t, q, pp }, t = 1;  q = n; While[0 == Mod[q, p], q /= p; t += 1]; pp = numNormalp[q]; pp *= p^n/n; Return[pp]]; a[n_] := n*numNormal[n]; Array[a, 40] (* Jean-François Alcover, Dec 10 2015, after Joerg Arndt *)

p=2; /* global */
num_normal_p(n)=
{
    my( r, i, pp );
    pp = 1;
    fordiv (n, d,
        r = znorder(Mod(p,d));
        i = eulerphi(d)/r;
        pp *= (1 - 1/p^r)^i;
    );
    return( pp );
}
num_normal(n)=
{
    my( t, q, pp );
    t = 1;  q = n;
    while ( 0==(q%p), q/=p; t+=1; );
    /* here: n==q*p^t */
    pp = num_normal_p(q);
    pp *= p^n/n;
    return( pp );
}
a(n)=n * num_normal(n);
v=vector(66,n,a(n))  /* Joerg Arndt, Jul 03 2011 */

a(n) = n * A027362(n). - Vladeta Jovovic, Sep 09 2003

More terms from Vladeta Jovovic, Sep 09 2003

Terms > 331776000 from Joerg Arndt, Jul 03 2011

A107222 Number of primitive normal polynomials of degree n over GF(2).

Original entry on oeis.org

1, 1, 1, 1, 3, 3, 7, 7, 19, 29, 87, 52, 315, 291, 562, 1017, 3825, 2870, 13797, 11255, 23579, 59986, 178259, 103680, 607522, 859849, 1551227, 1815045, 9203747, 5505966, 28629151, 33552327, 78899078, 167112969, 333342388, 267841392, 1848954877, 2411186731

Offset: 1

Joerg Arndt, Jun 08 2005, Oct 15 2005

No formula for the terms is currently known. [Joerg Arndt, Apr 02 2011]

			a(9) = 19 because there are 19 primitive normal polynomials of degree 9 over GF(2).

Joerg Arndt, Matters Computational (The Fxtbook), section 42.6.3 "The number of binary normal bases", pp. 904-907.
Joerg Arndt, C++ program used for computing this sequence

Cf. A027362, A135498.

Three more terms added from the Arndt website by N. J. A. Sloane, Feb 22 2008

Terms a(34)..a(38) from Joerg Arndt, Apr 17 2016

A192513 Number of Hamiltonian cycles in the 3-ary de Bruijn graph.

Original entry on oeis.org

2, 4, 24, 64, 512, 1728, 13312, 32768, 373248, 1310720, 10903552, 35831808, 287965184, 1240465408, 10319560704, 26843545600, 331895275520, 1253826625536, 10690521726976, 34359738368000, 347727917481984, 1307761908383744, 11445236333019136, 30814043149172736

Offset: 1

Joerg Arndt, Jul 03 2011

nonn

The 3-ary de Bruijn graph is the graph with 3*n nodes {0..3*n-1} and edges from each i to 3*i (mod 3*n), 3*i+1 (mod 3*n), and 3*i+2 (mod 3*n).

Correctness of a(n) = A094678(n)*2^(n-1) for all n>1 follows from S. H. Chan et al. below, together with the BEST theorem. [Dmitrii Pasechnik, Dec 07 2014]

Swee Hong Chan, Henk D. L. Hollmann, Dmitrii V. Pasechnik, Sandpile groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields, arXiv:1405.0113 [math.CO], (1-May-2014).
Swee Hong Chan, Henk D. L. Hollmann, Dmitrii V. Pasechnik, Sandpile groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields, Journal of Algebra (2015), pp. 268-295.
Gabriele Fici and Estéban Gabory, Generalized De Bruijn Words, Invertible Necklaces, and the Burrows-Wheeler Transform, arXiv:2502.12844 [math.CO], 2025. See Table 1. p. 7.
Wikipedia, BEST Theorem [_Dmitrii Pasechnik_, Dec 07 2014]

Cf. A003474, A094678.

Cf. A003473, A027362.

p = 3; numNormalp[n_] := Module[{r, i, pp = 1}, Do[r = MultiplicativeOrder[p, d]; i = EulerPhi[d]/r; pp *= (1 - 1/p^r)^i, {d, Divisors[n]}]; Return[pp]];
a[n_] := Module[{t = 1, q = n, pp}, While[0 == Mod[q, p], q /= p; t += 1]; pp = numNormalp[q]; pp *= p^n/n; Return[pp*2^(n - 1)]];
Array[a, 30] (* Jean-François Alcover, Jul 22 2018, after Joerg Arndt *)

a(n)=if(n==1,return(2));my(r,i,t=3^n/n<<(n-1));fordiv(n/3^valuation(n,3), d, r=znorder(Mod(3,d)); i=eulerphi(d)/r; t*=(1-1/3^r)^i);t \\ See comments. Charles R Greathouse IV, Jan 03 2013

a(n) = A094678(n)*2^(n-1) for n > 1. [Joerg Arndt, Dec 07 2014, amended by Georg Fischer, Jun 21 2020]

More terms from Dmitrii Pasechnik, Dec 07 2014

A335804 Number of n X n matrices over GF(2) with minimal polynomial x^n - 1.

Original entry on oeis.org

1, 3, 56, 2520, 666624, 839946240, 3343877406720, 41781748196966400, 3701652434038082764800, 763416952708225267547504640, 750836199529096452135514747699200

Offset: 1

Christof Beierle, Jun 24 2020

nonn

a(n) is the size of the conjugacy class in GL(n,GF(2)) corresponding to the companion matrix of x^n - 1. It can be given by the number of n X n invertible matrices over GF(2) divided by the number of n X n circulant invertible matrices over GF(2) (i.e., the centralizer of the companion matrix of x^n - 1).

If m is odd, x^m-1 has no multiple roots so that every matrix with characteristic polynomial x^m-1 also has x^m-1 as its minimal polynomial. Hence, a(m) = A089035(m). - Geoffrey Critzer, Jul 24 2025

Cf. A002884, A003473, A027362, A089035.

a(n) = A002884(n) / A003473(n). If n is an odd prime, then a(n) = A089035(n).

A191744 Number of Hamiltonian cycles in the 5-ary De Bruijn graph.

Original entry on oeis.org

24, 1152, 110592, 5308416, 995328000

Offset: 1

Joerg Arndt, Jul 03 2011

The 5-ary De Bruijn graph is the graph with 5*n nodes {0..5*n-1} and edges from each i to 5*i + j (mod 5*n), for 0<=j<5.

Cf. A027362 (2-ary graph), A192513 (3-ary graph).

A272033 Number of irreducible normal polynomials of degree n over GF(2) that are not primitive.

Original entry on oeis.org

0, 0, 0, 1, 0, 1, 0, 9, 2, 19, 6, 76, 0, 157, 113, 1031, 0, 2506, 0, 13321, 4204, 35246, 3924, 158464, 21623, 430391, 283774, 1854971, 52648, 5553234, 0, 33556537, 18428119, 83562231, 18807137, 436801680, 8328278, 1205614037

Offset: 1

Joerg Arndt, Apr 18 2016

nonn

Joerg Arndt, Matters Computational (The Fxtbook), section 42.6.3 "The number of binary normal bases", pp. 904-907.
Joerg Arndt, C++ program used for computing this sequence

Cf. A027362 (primitive normal polynomials), A107222.

a(n) = A027362(n) - A107222(n).

a(n) = 0 if 2^n - 1 is prime.

A375729 Irregular triangular array read by rows. T(n,k) is the number of monic irreducible polynomials of degree n in F_2[x] that are k-normal, n>=1, k>=0 .

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 3, 3, 4, 2, 3, 7, 7, 0, 2, 2, 16, 8, 4, 2, 21, 21, 7, 7, 48, 24, 24, 0, 3, 93, 93, 128, 64, 64, 32, 32, 8, 6, 1, 315, 315, 448, 224, 224, 112, 56, 56, 23, 8, 8, 2, 675, 675, 225, 225, 135, 135, 45, 45, 9, 9, 2, 2, 2048, 1024, 512, 256, 128, 64, 32, 16, 3825, 3825, 0, 0, 0, 0, 0, 0, 30, 30

Offset: 1

Geoffrey Critzer, Aug 25 2024

A monic irreducible polynomial of degree n in F_q[x] is k-normal if the span of its roots (expressed as a q-ary word with respect to any normal basis) in F_q^n has dimension n-k. For a more detailed definition of a k-normal polynomial see the abstract of the Alizadeh, Darafsheh, Mehrabi link below.

Conjecture: Let alpha be in F_q^n. Write alpha as a q-ary word w with respect to the standard polynomial basis (1,x,x^2,x^3,...,x^(n-1)). Let beta in F_q^n be the q-ary word w interpreted with respect to any normal basis. Then beta is a root of a k-normal polynomial iff the period of w = n and deg(gcd(alpha,x^n-1))=k.

			 Triangle begins ...
    1,     1;
    1;
    1,     1;
    2,     1;
    3,     3;
    4,     2,   3;
    7,     7,   0,   2,   2;
   16,     8,   4,   2;
   21,    21,   7,   7;
   48,    24,  24,   0,   3;
   93,    93;
  128,    64,  64,  32,  32,   8,  6,  1;
  315,   315;
  448,   224, 224, 112,  56,  56, 23,  8,  8,  2;
  675,   675, 225, 225, 135, 135, 45, 45,  9,  9, 2, 2;
  2048, 1024, 512, 256, 128,  64, 32, 16;
  3825, 3825,   0,   0,   0,   0,  0,  0, 30, 30;
  ...
 T(6,1) = 2 because we have 1+X+X^6 and 1+X+X^3+X^4+X^6.

M. Alizadeh, M Darafsheh, and S. Mehrabi, On the k-normal elements and polynomials over finite fields, Italian Journal of Pure and Applied Mathematics, 39 (2018), 451-464.
S. Huczynska, G. Mullen, D. Panario, and D. Thomson, Existences and properties of k-normal elements over finite fileds, Finite Fields and Their Applications, 24 (2013), 170-183.

Cf. A001037 (row sums), A027362 (column k=0), A330694, A003473.

knormalcy[lyndonword_, n_] := n - MatrixRank[Table[RotateRight[lyndonword, k], {k, 0, n - 1}], Modulus -> 2]; Map[Table[Count[#, i], {i, 0, Max[#]}] &,Table[orbit[word_] := Table[RotateLeft[word, k], {k, 0, nn - 1}]; c = Select[DeleteDuplicates[Map[Sort, Map[orbit, Tuples[{0, 1}, nn]] /. Table[Tuples[{0, 1}, nn][[i]] -> i - 1, {i, 1, 2^nn}]]], Length[DeleteDuplicates[#]] == nn &][[All, 1]]; Map[knormalcy[#, nn] &, Table[Tuples[{0, 1}, nn][[i]], {i, 1, 2^nn}][[c + 1]]], {nn, 1, 5}]]

cp's OEIS Frontend

A003473 Generalized Euler phi function (for p=2).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A107222 Number of primitive normal polynomials of degree n over GF(2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A192513 Number of Hamiltonian cycles in the 3-ary de Bruijn graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A335804 Number of n X n matrices over GF(2) with minimal polynomial x^n - 1.

Views

Author

Keywords

Comments

Crossrefs

Formula

A191744 Number of Hamiltonian cycles in the 5-ary De Bruijn graph.

Views

Author

Keywords

Comments

Crossrefs

A272033 Number of irreducible normal polynomials of degree n over GF(2) that are not primitive.

Views

Author

Keywords

Links

Crossrefs

Formula

A375729 Irregular triangular array read by rows. T(n,k) is the number of monic irreducible polynomials of degree n in F_2[x] that are k-normal, n>=1, k>=0 .

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica