cp's OEIS Frontend

A079458 Number of Gaussian integers in a reduced system modulo n.

%I A079458 #70 Dec 06 2024 10:24:37
%S A079458 1,2,8,8,16,16,48,32,72,32,120,64,144,96,128,128,256,144,360,128,384,
%T A079458 240,528,256,400,288,648,384,784,256,960,512,960,512,768,576,1296,720,
%U A079458 1152,512,1600,768,1848,960,1152,1056,2208,1024,2352,800,2048,1152,2704
%N A079458 Number of Gaussian integers in a reduced system modulo n.
%C A079458 Number of units in the ring consisting of the Gaussian integers modulo n. - _Jason Kimberley_, Dec 07 2015
%H A079458 Jason Kimberley, <a href="/A079458/b079458.txt">Table of n, a(n) for n = 1..10000</a>
%H A079458 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 A079458 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 A079458 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 A079458 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 A079458 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 A079458 From _Amiram Eldar_, Feb 13 2024: (Start)
%F A079458 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 A079458 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 A079458 a(n) = A204617(n)*A062570(n). - _Ridouane Oudra_, Jun 05 2024
%e A079458 {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 A079458 with(GaussInt): seq(GIphi(n), n=1..100);
%t A079458 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 A079458 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 A079458 (Magma) A079458 := func<n|#UnitGroup(quo<IntegerRing(QuadraticField(-1))|n>)>; // _Jason Kimberley_, Nov 14 2015
%o A079458 (PARI)
%o A079458 a(n)=
%o A079458 {
%o A079458     my(r=1, f=factor(n));
%o A079458     for(j=1, #f[, 1], my(p=f[j, 1], e=f[j, 2]);
%o A079458         if(p==2, r*=2^(2*e-1));
%o A079458         if(p%4==1, r*=(p-1)^2*p^(2*e-2));
%o A079458         if(p%4==3, r*=(p^2-1)*p^(2*e-2));
%o A079458     );
%o A079458     return(r);
%o A079458 } \\ _Jianing Song_, Sep 16 2018
%Y A079458 Equals four times A218147. - _Jason Kimberley_, Nov 14 2015
%Y A079458 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 A079458 Cf. A003557, A007947, A204617, A062570.
%Y A079458 Equivalent of arithmetic functions in the ring of Gaussian integers (the corresponding functions in the ring of integers are in the parentheses): A062327 ("d", A000005), A317797 ("sigma", A000203), this sequence ("phi", A000010), A227334 ("psi", A002322), A086275 ("omega", A001221), A078458 ("Omega", A001222), A318608 ("mu", A008683).
%Y A079458 Equivalent in the ring of Eisenstein integers: A319445.
%K A079458 mult,easy,nonn
%O A079458 1,2
%A A079458 _Vladeta Jovovic_, Jan 14 2003