A003473 -id:A003473 - cp's OEIS frontend

A027362 Number of Hamiltonian cycles in the directed graph with 2n nodes {0..2n-1} and edges from each i to 2i (mod 2n) and to 2i+1 (mod 2n).

1, 1, 1, 2, 3, 4, 7, 16, 21, 48, 93, 128, 315, 448, 675, 2048, 3825, 5376, 13797, 24576, 27783, 95232, 182183, 262144, 629145, 1290240, 1835001, 3670016, 9256395, 11059200, 28629151, 67108864, 97327197, 250675200, 352149525, 704643072, 1857283155, 3616800768

Offset: 1

Clone Lester (aflms(AT)cts1.cats.alaska.edu)

nonn

Also the number of binary normal polynomials of degree n. [Joerg Arndt, Nov 28 2004]. For a proof, see S. H. Chan et al. (2015) and S. V. Duzhin and D. V. Pasechnik (2014) below. [Dmitrii Pasechnik, Dec 05 2014]
Also the number of spanning trees (more precisely, the absolute value of a maximal minor of the Laplacian matrix) of the directed graph G_n with n nodes {0..n-1} and edges from each i to 2i (mod n) and to 2i+1 (mod n). This gives a connection to sandpile groups. The bijection between this and the original description can be obtained by noticing that the line graph of G_n is isomorphic to the graph G_2n (i.e. the graph in the original description of the sequence), thus relating the Hamiltonian cycles in G_2n and the Eulerian cycles in G_n. Finally, the latter are in bijection with directed spanning trees, rooted at a fixed vertex, in G_n by BEST Theorem (see the wikipedia article on it). [Dmitrii Pasechnik, Aug 14 and Nov 13 2011]
Also the number of invertible n x n circulant matrices over GF(2), divided by n. [Joerg Arndt, Aug 15 2011]. For a proof, see S. H. Chan et al. (2015) below. [Dmitrii Pasechnik, Dec 05 2014]

			The solutions for n=1, 2 and 3 are
  0 1;
  0 1 3 2;
  0 1 2 5 4 3.
The 4 solutions for n=6 are
  0 1 2 4 8 5 11 10 9 7 3 6;
  0 1 2 5 11 10 8 4 9 7 3 6;
  0 1 3 7 2 4 8 5 11 10 9 6;
  0 1 3 7 2 5 11 10 8 4 9 6.

Joe McCauley, Posting to sci.math (by jmccaul(AT)iatcmail.ed.ray.com). [Date?]

Joerg Arndt and Alois P. Heinz, Table of n, a(n) for n = 1..1000 (first 130 terms from Joerg Arndt)
Joerg Arndt, Matters Computational (The Fxtbook), p.904.
Swee Hong Chan, Henk D. L. Hollmann and Dmitrii V. Pasechnik, Critical groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields, arXiv: 1312.2114 [math.CO], 2013.
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. [_Dmitrii Pasechnik_, Dec 05 2014]
S. V. Duzhin, D. V. Pasechnik, Groups acting on necklaces and sandpile groups, 2014. See Section 3, History. - _N. J. A. Sloane_, Jun 30 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 1. p. 7.
Lionel Levine, Sandpile groups and spanning trees of directed line graphs, arXiv:0906.2809 [math.CO], 2009-2010.
Lionel Levine, Sandpile groups and spanning trees of directed line graphs, J. Combin. Th. (A) 118(2011), 350-364.
Wikipedia, BEST Theorem.

Cf. A003473.

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]];
a[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]];
Array[a, 40] (* Jean-François Alcover, Jul 21 2018, after Joerg Arndt *)

/* from p.907 of the Fxtbook */
p=2; /* global */
num_normal_p(n)=
{
    local( 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)=
{
    local( 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) = num_normal(n);
vector(66,n,a(n)) /* Joerg Arndt, Jul 03 2011 */

# version 4.7
def dg(n): # this gives the graph in the 3rd description
    g = DiGraph(loops=True)
    for i in range(n): g.add_vertex();
    for i in range(n):
        g.add_edge(i, mod(2*i, n));
        g.add_edge(i, mod(1+2*i, n));
    return g;
def A027362(n): # this gives the number of spanning trees
    return dg(n).laplacian_matrix().submatrix(1, 1).det();
# Dmitrii Pasechnik, Aug 14 2011

a(n) = A003473(n)/n. - Vladeta Jovovic, Sep 09 2003

a(2^k) = 2^(2^k-k-1) from L. Levine 2011, Theorem 1.3.

A086323 Number of n X n circulant invertible (0,1) matrices over the reals.

Original entry on oeis.org

1, 2, 6, 8, 30, 36, 126, 160, 450, 740, 2046, 2592, 8190, 12824, 30030, 48640, 131070, 194508, 524286, 812840, 1987818, 3486824, 8388606, 12400368, 33348150, 56700072, 128800098, 219681672, 536870910, 861181320, 2147483646, 3555730432

Offset: 1

Yuval Dekel (dekelyuval(AT)hotmail.com), Aug 30 2003

nonn

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

Cf. A003473.

a(n) = 2^n - A086328(n).

More terms from Vladeta Jovovic, Sep 08 2003

More terms from Max Alekseyev, Sep 24 2009

A003474 Generalized Euler phi function (for p=3).

Original entry on oeis.org

1, 4, 18, 32, 160, 324, 1456, 2048, 13122, 25600, 117128, 209952, 913952, 2119936, 9447840, 13107200, 86093440, 172186884, 774840976, 1310720000, 6964002864, 13718968384, 62761410632, 88159684608, 557885504000, 835308258304, 5083731656658, 8988257288192, 45753584909920, 89261680665600, 411782264189296, 564050001920000

Offset: 1

N. J. A. Sloane

nonn

For n >= 2, a(n) is the number of n X n circulant invertible matrices over GF(3). - Yuval Dekel (dekelyuval(AT)hotmail.com), Aug 22 2003

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

J. T. B. Beard Jr. and K. I. West, Factorization tables for x^n-1 over GF(q), Math. Comp., 28 (1974), 1167-1168.
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. A003473 (p=2), A192037 (p=5).

p = 3; 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_] := If[n==1, 1, n*numNormal[n]]; Array[a, 40] (* Jean-François Alcover, Dec 10 2015, after Joerg Arndt *)

p=3; /* 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)=if ( n==1, 1, n * num_normal(n) );
v=vector(66,n,a(n))
/* Joerg Arndt, Jul 03 2011 */

Terms > 86093440 from Joerg Arndt, Jul 03 2011

A086324 Number of n X n circulant singular matrices over GF(2).

Original entry on oeis.org

1, 2, 5, 8, 17, 40, 79, 128, 323, 544, 1025, 2560, 4097, 10112, 22643, 32768, 66047, 165376, 262145, 557056, 1513709, 2099200, 4198399, 10485760, 17825807, 33562624, 84672701, 165675008, 268435457, 741965824, 1259979967, 2147483648, 5378137091, 8656912384

Offset: 1

Yuval Dekel (dekelyuval(AT)hotmail.com), Aug 30 2003

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Cf. A003473, A002416.

a(n) = 2^n - A003473(n).

a(10)-a(34) from Alois P. Heinz, Mar 16 2017

A192037 Generalized Euler phi function (for p=5).

Original entry on oeis.org

1, 16, 96, 256, 2500, 9216, 62496, 147456, 1499904, 6250000, 39037504, 84934656, 971882496, 3905750016, 23437500000, 57415827456, 610351562496, 2249712009216, 15258773437504, 39062500000000, 366140629499904, 1523926718550016, 9536743164062496, 16231265527136256, 238418579101562500

Offset: 1

Joerg Arndt, Jul 03 2011

nonn

For n>=2 a(n) is the number of n X n circulant invertible matrices over GF(5)

Cf. A003473 (p=2), A003474 (p=3).

PARI
```
/* see A003473, there set p=5 */
```

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

A086479 Number of invertible circulant (0,1) matrices over the reals that have even determinant.

Original entry on oeis.org

0, 0, 3, 0, 15, 12, 77, 32, 261, 260, 1023, 1056, 4095, 6552, 19905, 15872, 66045, 97740, 262143, 321320, 1404375, 1391720, 4198397, 6108912, 17619525, 23153832, 79255071, 116921224, 268435455, 529405320, 1259979965, 1408246784

Offset: 1

Yuval Dekel (dekelyuval(AT)hotmail.com), Sep 09 2003

nonn

Cf. A003473, A086323, A086324.

a(n) = A086323(n) - A003473(n)

More terms from Max Alekseyev, Sep 25 2009

A330694 Triangular array read by rows. T(n,k) is the number of k-normal elements in GF(2^n), n >= 1, 0 <= k <= n-1.

Original entry on oeis.org

1, 2, 1, 3, 3, 1, 8, 4, 2, 1, 15, 15, 0, 0, 1, 24, 12, 18, 3, 5, 1, 49, 49, 0, 14, 14, 0, 1, 128, 64, 32, 16, 8, 4, 2, 1, 189, 189, 63, 63, 0, 0, 3, 3, 1, 480, 240, 240, 0, 30, 15, 15, 0, 2, 1, 1023, 1023, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1536, 768, 768, 384, 384, 96, 96, 24, 26, 7, 5, 1, 4095, 4095, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1

Offset: 1

Geoffrey Critzer, Dec 25 2019

Let g(x) = Sum_{i=0..n-1} g_i x^i in GF(q)[x]. Define an action on the algebraic closure of GF(q) by g*a = Sum_{i=0..n-1} g_i a^(q^i). The annihilator of a is an ideal and is generated by a polynomial g of minimum degree. If deg(g) = n-k then a is k-normal.

An element a in GF(q^n) is 0-normal if {a, a^q, a^(q^2), ..., a^(q^(n-1))} is a basis for GF(q^n) over GF(q).

			Triangle begins
     1;
     2,    1;
     3,    3,   1;
     8,    4,   2,   1;
    15,   15,   0,   0,   1;
    24,   12,  18,   3,   5,  1;
    49,   49,   0,  14,  14,  0,  1;
   128,   64,  32,  16,   8,  4,  2,  1;
   189,  189,  63,  63,   0,  0,  3,  3,  1;
   480,  240, 240,   0,  30, 15, 15,  0,  2, 1;
  1023, 1023,   0,   0,   0,  0,  0,  0,  0, 0, 1;
  1536,  768, 768, 384, 384, 96, 96, 24, 26, 7, 5, 1;
  4095, 4095,   0,   0,   0,  0,  0,  0,  0, 0, 0, 0, 1;

S. Huczynska, G. Mullen, D. Panario, and D. Thomson, Existences and properties of k-normal elements over finite fields, Finite Fields and Their Applications, 24 (2013), 170-183.
Zülfükar Saygi, Ernist Tilenbaev, Çetin Ürtiş, On the number of k-normal elements over finite fields, Turk J Math., (2019) 43.795.812.
David Thompson, Something about normal bases over finite fields, Existence and properties of k-normal elements over finite fields, Slides, (2013).

Column k=0 gives A003473.

Needs["FiniteFields`"];Table[b = Map[GF[2^n][#] &, Tuples[{0, 1}, n]];
  Table[Count[Table[MatrixRank[Table[b[[i]]^(2^k), {k, 0, n - 1}][[All, 1]],
       Modulus -> 2], {i, 2, 2^n}], k], {k, 1, n}] // Reverse, {n, 1, 8}] // Grid

T(n, k) = Sum_{h | x^n-1, deg(h) = n-k} phi_2(h) where phi_2(h) is the generalized Euler phi function and the polynomial division is in GF(2)[x].

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

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

A027362 Number of Hamiltonian cycles in the directed graph with 2n nodes {0..2n-1} and edges from each i to 2i (mod 2n) and to 2i+1 (mod 2n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Sage

Formula

A086323 Number of n X n circulant invertible (0,1) matrices over the reals.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A003474 Generalized Euler phi function (for p=3).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A086324 Number of n X n circulant singular matrices over GF(2).

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A192037 Generalized Euler phi function (for p=5).

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A086479 Number of invertible circulant (0,1) matrices over the reals that have even determinant.

Views

Author

Keywords

Crossrefs

Formula

Extensions

A330694 Triangular array read by rows. T(n,k) is the number of k-normal elements in GF(2^n), n >= 1, 0 <= k <= n-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica