OFFSET
1,2
COMMENTS
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]/<x^n-1>.
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)
REFERENCES
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
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).
FORMULA
a(n) = n * A027362(n). - Vladeta Jovovic, Sep 09 2003
MATHEMATICA
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 *)
PROG
(PARI)
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 */
CROSSREFS
KEYWORD
nonn
AUTHOR
EXTENSIONS
More terms from Vladeta Jovovic, Sep 09 2003
Terms > 331776000 from Joerg Arndt, Jul 03 2011
STATUS
approved