login
Number of solutions to gcd(u^2 + v^2 + w^2 + x^2 + y^2 + z^2, n) = 1 with u, v, w, x, y, z in [0,n-1].
6

%I #52 Feb 13 2024 02:19:41

%S 1,32,504,2048,12400,16128,101136,131072,367416,396800,1611720,

%T 1032192,4453488,3236352,6249600,8388608,22713088,11757312,44576280,

%U 25395200,50972544,51575040,141611184,66060288,193750000,142511616,267846264,207126528,574288624

%N Number of solutions to gcd(u^2 + v^2 + w^2 + x^2 + y^2 + z^2, n) = 1 with u, v, w, x, y, z in [0,n-1].

%H Robert Israel, <a href="/A238534/b238534.txt">Table of n, a(n) for n = 1..2000</a> (first 100 terms from Giovanni Resta)

%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^(6*e-1), a(p^e) = (p - 1)*p^(6*e - 4)*(p^3 - (-1)^(3*(p-1)/2)) for odd prime p. - _Andrew Howroyd_, Aug 07 2018

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

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

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

%p f:= proc(n) local i, j, k, S1, S2, S4, S6,G;

%p G:= select(t -> igcd(t,n)=1, [$1..n-1]);

%p S1:= Array(0..n-1);

%p for i from 0 to n-1 do j:= i^2 mod n; S1[j]:= S1[j]+1; od;

%p S2:= Array(0..n-1);

%p for i from 0 to n-1 do

%p for j from 0 to n-1 do

%p k:= i^2 + j mod n;

%p S2[k]:= S2[k]+S1[j];

%p od od:

%p S4:= Array(0..n-1);

%p for i from 0 to n-1 do

%p for j from 0 to n-1 do

%p k:= i + j mod n;

%p S4[k]:= S4[k]+S2[i]*S2[j];

%p od od:

%p S6:= Array(0..n-1);

%p for i from 0 to n-1 do

%p for j from 0 to n-1 do

%p k:= i + j mod n;

%p S6[k]:= S6[k]+S4[i]*S2[j];

%p od od:

%p add(S6[i],i=G);

%p end proc:

%p f(1):= 1:

%p map(f, [$1..100]); # _Robert Israel_, Mar 05 2018

%t g[n_, 6] := g[n, 6] = Sum[If[GCD[u^2+v^2+w^2+x^2+y^2+z^2, n] == 1, 1, 0], {u, n}, {v, n}, {w, n}, {x, n}, {y, n}, {z, n}]; Table[g[n, 6], {n, 1, 12}]

%t f[p_, e_] := (p - 1)*p^(6*e - 4)*(p^3 - (-1)^(3*(p - 1)/2)); f[2, e_] := 2^(6*e - 1); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 30] (* _Amiram Eldar_, Sep 07 2023 *)

%o (PARI) a(n)={my(p=lift(Mod(sum(i=0, n-1, x^(i^2%n)), x^n-1)^6)); sum(i=0, n-1, if(gcd(i,n)==1, polcoeff(p,i)))} \\ _Andrew Howroyd_, Aug 06 2018

%o (PARI) a(n)={my(f=factor(n)); prod(i=1, #f~, my([p,e]=f[i,]); if(p==2, 2^(6*e-1), (p - 1)*p^(6*e - 4)*(p^3 - (-1)^(3*(p-1)/2))))} \\ _Andrew Howroyd_, Aug 07 2018

%Y Cf. A227499, A238533, A239441.

%K nonn,easy,mult

%O 1,2

%A _José María Grau Ribas_, Feb 28 2014

%E a(16)-a(29) from _Giovanni Resta_, Mar 05 2014