cp's OEIS Frontend

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

%I A087687 #49 Mar 04 2021 07:03:51
%S A087687 1,4,9,8,25,36,49,32,99,100,121,72,169,196,225,64,289,396,361,200,441,
%T A087687 484,529,288,725,676,891,392,841,900,961,256,1089,1156,1225,792,1369,
%U A087687 1444,1521,800,1681,1764,1849,968,2475,2116,2209,576,2695,2900,2601
%N A087687 Number of solutions to x^2 + y^2 + z^2 == 0 (mod n).
%C A087687 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
%H A087687 Alois P. Heinz, <a href="/A087687/b087687.txt">Table of n, a(n) for n = 1..20000</a> (first 80 terms from Robert Gerbicz)
%H A087687 C. Calderón and M. J. De Velasco, <a href="https://doi.org/10.1007/BF01377596">On divisors of a quadratic form</a>, Boletim da Sociedade Brasileira de Matemática, Vol. 31, No. 1 (2000), pp. 81-91; <a href="http://emis.icm.edu.pl/journals/em/docs/boletim/vol311/v31-1-a6-2000.pdf">alternative link</a>.
%H A087687 László Toth, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Toth/toth12.html">Counting Solutions of Quadratic Congruences in Several Variables Revisited</a>, J. Int. Seq., Vol. 17 (2014), Article # 14.11.6; <a href="http://arxiv.org/abs/1404.4214">arXiv preprint</a>, arXiv:1404.4214 [math.NT], 2014.
%H A087687 <a href="/index/Su#sums_of_squares">Index to sequences related to sums of squares</a>
%F A087687 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
%F A087687 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
%p A087687 A087687 := proc(n)
%p A087687     a := 1;
%p A087687     for pe in ifactors(n)[2] do
%p A087687         p := op(1,pe) ;
%p A087687         e := op(2,pe) ;
%p A087687         if p = 2 then
%p A087687             a := a*p^(e+ceil(e/2)) ;
%p A087687         elif type(e,'odd') then
%p A087687             a := a*p^((3*e-1)/2)*(p^((e+1)/2)+p^((e-1)/2)-1) ;
%p A087687         else
%p A087687             a := a*p^(3*e/2-1)*(p^(e/2+1)+p^(e/2)-1) ;
%p A087687         end if;
%p A087687     end do:
%p A087687     a ;
%p A087687 end proc:
%p A087687 seq(A087687(n),n=1..100) ; # _R. J. Mathar_, Jun 25 2018
%t A087687 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];
%t A087687 Array[a, 100] (* _Jean-François Alcover_, Jul 10 2018, after _R. J. Mathar_ *)
%o A087687 (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_
%o A087687 (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
%Y A087687 Cf. A086933, A062775.
%Y A087687 Different from A064549.
%K A087687 mult,look,nonn
%O A087687 1,2
%A A087687 Yuval Dekel (dekelyuval(AT)hotmail.com), Sep 27 2003
%E A087687 More terms from _Robert Gerbicz_, Aug 22 2006
%E A087687 Edited by _Steven Finch_, Feb 06 2009, Feb 12 2009