A003474 -id:A003474 - cp's OEIS frontend

A094678 a(n) = A003474(n)/n.

1, 2, 6, 8, 32, 54, 208, 256, 1458, 2560, 10648, 17496, 70304, 151424, 629856, 819200, 5064320, 9565938, 40781104, 65536000, 331619184, 623589472, 2728756984, 3673320192, 22315420160, 32127240704, 188286357654, 321009188864, 1577709824480, 2975389355520, 13283298844816, 17626562560000

Offset: 1

Vladeta Jovovic, Jun 07 2004

nonn

Number of normal bases for GF(3^n) over GF(3). - Joerg Arndt, Jul 03 2011
For n>=2, a(n) = f(n)/(2^(n-1)) where f(n) is the number of Hamiltonian cycles in the 3-ary de Bruijn graph (i.e., 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); cf. A192513). - Joerg Arndt, Jul 03 2011.
For details on this correspondence, see A192513. - Dmitrii Pasechnik, Dec 07 2014

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

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

Terms > 5064320 by Joerg Arndt, Jul 03 2011

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

Original entry on oeis.org

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

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

cp's OEIS Frontend

A094678 a(n) = A003474(n)/n.

Views

Author

Keywords

Comments

Programs

Mathematica

PARI

Extensions

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

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