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,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

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

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

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 *)

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

Cf. A086933, A062775.

Different from A064549.

Sequence in context: A073395 A064549 A304203 * A264090 A345283 A369750

Adjacent sequences: A087684 A087685 A087686 * A087688 A087689 A087690

Keyword

mult,look,nonn

Author

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

Extensions

More terms from Robert Gerbicz, Aug 22 2006

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

Status

approved