cp's OEIS Frontend

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

%I A087561 #21 Nov 21 2023 05:22:20
%S A087561 1,2,5,4,1,10,1,8,21,2,21,20,1,2,5,16,33,42,37,4,5,42,1,40,25,2,81,4,
%T A087561 1,10,1,32,105,66,1,84,1,74,5,8,81,10,85,84,21,2,1,80,49,50,165,4,1,
%U A087561 162,21,8,185,2,117,20,1,2,21,64,1,210,133,132,5,2,1,168,145,2,125,148,21
%N A087561 Number of solutions to x^2 + 2y^2 == 0 (mod n).
%H A087561 Andrew Howroyd, <a href="/A087561/b087561.txt">Table of n, a(n) for n = 1..10000</a>
%H A087561 László Tóth, <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. 17 (2014), Article 14.11.6.
%F A087561 Multiplicative with a(2^e) = 2^e, a(p^e) = p^(2*floor(e/2)) for p - 2 == +-3 (mod 8), a(p^e) = ((p-1)*e+p)*p^(e-1) for p - 2 == +-1 (mod 8). - _Andrew Howroyd_, Jul 16 2018
%F A087561 Sum_{k=1..n} a(k) ~ c * n^2, where c = Pi/(4*sqrt(2)*A309710) = 0.521595326207... . - _Amiram Eldar_, Nov 21 2023
%t A087561 a[n_] := If[n == 1, 1, Product[{p, e} = pe; Which[p == 2, 2^e, Abs[Mod[p, 8] - 2] != 1, (p^2)^Quotient[e, 2], True, (p + e (p-1)) p^(e-1)], {pe, FactorInteger[n]}]];
%t A087561 a /@ Range[1, 100] (* _Jean-François Alcover_, Sep 20 2019, from PARI *)
%o A087561 (PARI) a(n)={my(v=vector(n)); for(i=0, n-1, v[i^2%n + 1]++); sum(i=0, n-1, v[i+1]*v[(-2*i)%n + 1])} \\ _Andrew Howroyd_, Jul 16 2018
%o A087561 (PARI) a(n)={my(f=factor(n)); prod(i=1, #f~, my(p=f[i, 1], e=f[i, 2]); if(p==2, 2^e, if(abs(p%8-2)<>1, (p^2)^(e\2), (p+e*(p-1))*p^(e-1))))} \\ _Andrew Howroyd_, Jul 16 2018
%Y A087561 Cf. A086933, A088964, A088965, A089002, A309710.
%K A087561 mult,nonn,easy
%O A087561 1,2
%A A087561 Yuval Dekel (dekelyuval(AT)hotmail.com), Oct 24 2003
%E A087561 More terms from _David Wasserman_, Jun 07 2005