|
|
A087687
|
|
Number of solutions to x^2 + y^2 + z^2 == 0 (mod n).
|
|
5
|
|
|
1, 4, 9, 8, 25, 36, 49, 32, 99, 100, 121, 72, 169, 196, 225, 64, 289, 396, 361, 200, 441, 484, 529, 288, 725, 676, 891, 392, 841, 900, 961, 256, 1089, 1156, 1225, 792, 1369, 1444, 1521, 800, 1681, 1764, 1849, 968, 2475, 2116, 2209, 576, 2695, 2900, 2601
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
To show that a(n) is multiplicative is simple number theory. If gcd(n,m)=1, then any solution of x^2 + y^2 + z^2 == 0 (mod n) and any solution (mod m) can combined to a solution (mod nm) using the Chinese Remainder Theorem and any solution (mod nm) gives solutions (mod n) and (mod m). Hence a(nm) = a(n)*a(m). - Torleiv Kløve, Jan 26 2009
|
|
LINKS
|
|
|
FORMULA
|
a(2^k) = 2^(k + ceiling(k/2)). For odd primes p, a(p^(2k-1)) = p^(3k-2)*(p^k + p^(k-1) - 1) and a(p^(2k)) = p^(3k-1)*(p^(k+1) + p^k - 1). - Martin Fuller, Jan 26 2009
Sum_{k=1..n} a(k) ~ (4*zeta(3))/(15*zeta(4)) * n^3 + O(n^2 * log(n)) (Calderón and de Velasco, 2000). - Amiram Eldar, Mar 04 2021
|
|
MAPLE
|
a := 1;
for pe in ifactors(n)[2] do
p := op(1, pe) ;
e := op(2, pe) ;
if p = 2 then
a := a*p^(e+ceil(e/2)) ;
elif type(e, 'odd') then
a := a*p^((3*e-1)/2)*(p^((e+1)/2)+p^((e-1)/2)-1) ;
else
a := a*p^(3*e/2-1)*(p^(e/2+1)+p^(e/2)-1) ;
end if;
end do:
a ;
end proc:
|
|
MATHEMATICA
|
a[n_] := Module[{k=1}, Do[{p, e} = pe; k = k*If[p == 2, p^(e + Ceiling[ e/2]), If[OddQ[e], p^((3*e-1)/2)*(p^((e+1)/2) + p^((e-1)/2) - 1), p^(3*e/2 - 1)*(p^(e/2 + 1) + p^(e/2) - 1)]], {pe, FactorInteger[n]}]; k];
|
|
PROG
|
(PARI) a(n)=local(v=vector(n), w); for(i=1, n, v[i^2%n+1]++); w=vector(n, i, sum(j=1, n, v[j]*v[(i-j)%n+1])); sum(j=1, n, w[j]*v[(1-j)%n+1]) \\ Martin Fuller
(PARI) a(n)={my(f=factor(n)); prod(i=1, #f~, my([p, e]=f[i, ]); if(p==2, 2^(e+(e+1)\2), p^(e+(e-1)\2)*(p^(e\2)*(p+1) - 1)))} \\ Andrew Howroyd, Aug 06 2018
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
Yuval Dekel (dekelyuval(AT)hotmail.com), Sep 27 2003
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|