login
Number of Gaussian integers in a reduced system modulo n.
23

%I #66 Jun 22 2024 16:17:34

%S 1,2,8,8,16,16,48,32,72,32,120,64,144,96,128,128,256,144,360,128,384,

%T 240,528,256,400,288,648,384,784,256,960,512,960,512,768,576,1296,720,

%U 1152,512,1600,768,1848,960,1152,1056,2208,1024,2352,800,2048,1152,2704

%N Number of Gaussian integers in a reduced system modulo n.

%C Number of units in the ring consisting of the Gaussian integers modulo n. - _Jason Kimberley_, Dec 07 2015

%H Jason Kimberley, <a href="/A079458/b079458.txt">Table of n, a(n) for n = 1..10000</a>

%H Jonathan M. Borwein, <a href="https://web.archive.org/web/20190331234618/https://carmamaths.org/resources/jon/OEIStalk.pdf">Adventures with the OEIS: Five sequences Tony may like</a>, Guttmann 70th [Birthday] Meeting, 2015, revised May 2016. [Wayback Machine link]

%H Jonathan M. Borwein, <a href="/A060997/a060997.pdf">Adventures with the OEIS: Five sequences Tony may like</a>, Guttmann 70th [Birthday] Meeting, 2015, revised May 2016. [Cached copy, with permission]

%H Catalina Calderón, Jose Maria Grau, A. Oller-Marcén, and László Tóth, <a href="http://dx.doi.org/10.5486/PMD.2015.7098">Counting invertible sums of squares modulo n and a new generalization of Euler's totient function</a>, Publicationes Mathematicae-Debrecen, Vol. 87 (1-2) (2015), pp. 133-145; <a href="https://arxiv.org/abs/1403.7878">arXiv preprint</a>, arXiv:1403.7878 [math.NT], 2014.

%F Multiplicative with a(2^e) = 2^(2*e-1), a(p^e) = (p^2-1)*p^(2*e-2) if p mod 4=3 and a(p^e) = (p-1)^2*p^(2*e-2) if p mod 4=1.

%F a(n) = A003557(n)^2 * a(A007947(n)), where a(2)=2, a(p)=(p-1)^2 for prime p=1(mod 4), a(p)=p^2-1 for prime p=3(mod 4), and a(n*m)=a(n)*a(m) for n coprime to m. - _Jason Kimberley_, Nov 16 2015

%F From _Amiram Eldar_, Feb 13 2024: (Start)

%F Dirichlet g.f.: zeta(s-2) * (1 - 1/2^(s-1)) * Product_{p prime > 2} (1 - 1/p^(s-1) - (-1)^((p-1)/2)*(p-1)/p^s).

%F Sum_{k=1..n} a(k) = c * n^3 / 3 + O(n^2 * log(n)), where c = (3/4) * Product_{p prime > 2} (1 - 1/p^2 - (-1)^((p-1)/2)*(p-1)/p^3) = (3/4) * A334427 * Product_{p prime == 1 (mod 4)} (1 - 2/p^2 + 1/p^3) = 0.6498027559... (Calderón et al., 2015). (End)

%F a(n) = A204617(n)*A062570(n). - _Ridouane Oudra_, Jun 05 2024

%e {1, i, 1+2i, 2+i, 3, 3i, 3+2i, 2+3i} is the set of eight units in the Gaussian integers modulo 4. - _Jason Kimberley_, Dec 07 2015

%p with(GaussInt): seq(GIphi(n), n=1..100);

%t phi[1]=1;phi[p_, s_] := Which[Mod[p, 4] == 3, p^(2 s - 2) (p^2 - 1), Mod[p, 4] == 1, p^(2 s - 2) ((p - 1))^2, True, 2^(2 s - 1)];phi[n_] := Product[phi[FactorInteger[n][[i, 1]], FactorInteger[n][[i, 2]]], {i, Length[FactorInteger[n]]}];Table[phi[n], {n, 1, 33}] (* _José María Grau Ribas_, Mar 16 2014 *)

%t f[p_, e_] := (p - 1)*p^(2*e - 1) * If[p == 2, 1, 1 - (-1)^((p-1)/2)/p]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* _Amiram Eldar_, Feb 13 2024 *)

%o (Magma) A079458 := func<n|#UnitGroup(quo<IntegerRing(QuadraticField(-1))|n>)>; // _Jason Kimberley_, Nov 14 2015

%o (PARI)

%o a(n)=

%o {

%o my(r=1, f=factor(n));

%o for(j=1, #f[, 1], my(p=f[j, 1], e=f[j, 2]);

%o if(p==2, r*=2^(2*e-1));

%o if(p%4==1, r*=(p-1)^2*p^(2*e-2));

%o if(p%4==3, r*=(p^2-1)*p^(2*e-2));

%o );

%o return(r);

%o } \\ _Jianing Song_, Sep 16 2018

%Y Equals four times A218147. - _Jason Kimberley_, Nov 14 2015

%Y Sequences giving the number of solutions to the equation GCD(x_1^2+...+x_k^2, n) = 1 with 0 < x_i <= n: A000010 (k=1), A079458 (k=2), A053191 (k=3), A227499 (k=4), A238533 (k=5), A238534 (k=6), A239442 (k=7), A239441 (k=8), A239443 (k=9).

%Y Cf. A003557, A007947, A204617, A062570.

%K mult,easy,nonn

%O 1,2

%A _Vladeta Jovovic_, Jan 14 2003