cp's OEIS Frontend

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

%I A003473 M0875 #59 Feb 19 2025 01:04:35
%S A003473 1,2,3,8,15,24,49,128,189,480,1023,1536,4095,6272,10125,32768,65025,
%T A003473 96768,262143,491520,583443,2095104,4190209,6291456,15728625,33546240,
%U A003473 49545027,102760448,268435455,331776000,887503681,2147483648,3211797501,8522956800,12325233375,25367150592,68719476735,137438429184,206007472125
%N A003473 Generalized Euler phi function (for p=2).
%C A003473 a(n) is the number of n X n circulant invertible matrices over GF(2). - Yuval Dekel (dekelyuval(AT)hotmail.com), Aug 20 2003
%C A003473 From _Geoffrey Critzer_, Oct 13 2024: (Start)
%C A003473 a(n) is the number of units in the ring F_2[x]/<x^n-1>.
%C A003473 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.
%C A003473 a(n) is the number of elements in M_T whose local minimal polynomial is x^n-1.
%C A003473 a(n) is the order of the stabilizer subgroup of T under the action of conjugation.
%C A003473 a(n) is the number of polynomials f(x) in F_2[x] of degree < n such that
%C A003473  gcd(x^n-1,f(x)) = 1.
%C A003473 a(n) is the number of normal elements in the field F_2^n. (End)
%D A003473 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A003473 Alois P. Heinz, <a href="/A003473/b003473.txt">Table of n, a(n) for n = 1..1000</a>
%H A003473 J. T. B. Beard Jr. and K. I. West, <a href="http://dx.doi.org/10.1090/S0025-5718-1974-0364196-5">Factorization tables for x^n-1 over GF(q)</a>, Math. Comp., 28 (1974), 1167-1168.
%H A003473 Swee Hong Chan, Henk D. L. Hollmann, and Dmitrii V. Pasechnik, <a href="http://arxiv.org/abs/1405.0113">Sandpile groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields</a>, arXiv:1405.0113 [math.CO], (1-May-2014).
%H A003473 Gabriele Fici and Estéban Gabory, <a href="https://arxiv.org/abs/2502.12844">Generalized De Bruijn Words, Invertible Necklaces, and the Burrows-Wheeler Transform</a>, arXiv:2502.12844 [math.CO], 2025. See Table 2 p. 11.
%F A003473 a(n) = n * A027362(n). - _Vladeta Jovovic_, Sep 09 2003
%t 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]]; 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_ *)
%o A003473 (PARI)
%o A003473 p=2; /* global */
%o A003473 num_normal_p(n)=
%o A003473 {
%o A003473     my( r, i, pp );
%o A003473     pp = 1;
%o A003473     fordiv (n, d,
%o A003473         r = znorder(Mod(p,d));
%o A003473         i = eulerphi(d)/r;
%o A003473         pp *= (1 - 1/p^r)^i;
%o A003473     );
%o A003473     return( pp );
%o A003473 }
%o A003473 num_normal(n)=
%o A003473 {
%o A003473     my( t, q, pp );
%o A003473     t = 1;  q = n;
%o A003473     while ( 0==(q%p), q/=p; t+=1; );
%o A003473     /* here: n==q*p^t */
%o A003473     pp = num_normal_p(q);
%o A003473     pp *= p^n/n;
%o A003473     return( pp );
%o A003473 }
%o A003473 a(n)=n * num_normal(n);
%o A003473 v=vector(66,n,a(n))  /* _Joerg Arndt_, Jul 03 2011 */
%Y A003473 Cf. A003474 (p=3), A192037 (p=5).
%Y A003473 Cf. also A086479, A027362.
%K A003473 nonn
%O A003473 1,2
%A A003473 _N. J. A. Sloane_
%E A003473 More terms from _Vladeta Jovovic_, Sep 09 2003
%E A003473 Terms > 331776000 from _Joerg Arndt_, Jul 03 2011