A087687 Number of solutions to x^2 + y^2 + z^2 == 0 (mod n).

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

Offset: 1

Author

Yuval Dekel (dekelyuval(AT)hotmail.com), Sep 27 2003

Keywords

• mult
• look
• nonn

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

• Alois P. Heinz, Table of n, a(n) for n = 1..20000 (first 80 terms from Robert Gerbicz)
• C. Calderón and M. J. De Velasco, On divisors of a quadratic form, Boletim da Sociedade Brasileira de Matemática, Vol. 31, No. 1 (2000), pp. 81-91; alternative link.
• László Toth, Counting Solutions of Quadratic Congruences in Several Variables Revisited, J. Int. Seq., Vol. 17 (2014), Article # 14.11.6; arXiv preprint, arXiv:1404.4214 [math.NT], 2014.
• Index to sequences related to sums of squares

Crossrefs

Cf. A086933, A062775.

Different from A064549.

Programs

Maple

A087687 := proc(n)
    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:
seq(A087687(n),n=1..100) ; # R. J. Mathar, Jun 25 2018

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];
Array[a, 100] (* Jean-François Alcover, Jul 10 2018, after R. J. Mathar *)

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

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

Extensions

More terms from Robert Gerbicz, Aug 22 2006

Edited by Steven Finch, Feb 06 2009, Feb 12 2009