cp's OEIS Frontend

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

%I A003474 M3541 #37 Feb 19 2025 01:07:12
%S A003474 1,4,18,32,160,324,1456,2048,13122,25600,117128,209952,913952,2119936,
%T A003474 9447840,13107200,86093440,172186884,774840976,1310720000,6964002864,
%U A003474 13718968384,62761410632,88159684608,557885504000,835308258304,5083731656658,8988257288192,45753584909920,89261680665600,411782264189296,564050001920000
%N A003474 Generalized Euler phi function (for p=3).
%C A003474 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
%D A003474 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A003474 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 A003474 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.
%t A003474 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_ *)
%o A003474 (PARI)
%o A003474 p=3; /* global */
%o A003474 num_normal_p(n)=
%o A003474 {
%o A003474     my( r, i, pp );
%o A003474     pp = 1;
%o A003474     fordiv (n, d,
%o A003474         r = znorder(Mod(p,d));
%o A003474         i = eulerphi(d)/r;
%o A003474         pp *= (1 - 1/p^r)^i;
%o A003474     );
%o A003474     return( pp );
%o A003474 }
%o A003474 num_normal(n)=
%o A003474 {
%o A003474     my( t, q, pp );
%o A003474     t = 1;  q = n;
%o A003474     while ( 0==(q%p), q/=p; t+=1; );
%o A003474     /* here: n==q*p^t */
%o A003474     pp = num_normal_p(q);
%o A003474     pp *= p^n/n;
%o A003474     return( pp );
%o A003474 }
%o A003474 a(n)=if ( n==1, 1, n * num_normal(n) );
%o A003474 v=vector(66,n,a(n))
%o A003474 /* _Joerg Arndt_, Jul 03 2011 */
%Y A003474 Cf. A003473 (p=2), A192037 (p=5).
%K A003474 nonn
%O A003474 1,2
%A A003474 _N. J. A. Sloane_
%E A003474 Terms > 86093440 from _Joerg Arndt_, Jul 03 2011