A192037 -id:A192037 - 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

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions