login
A087561
Number of solutions to x^2 + 2y^2 == 0 (mod n).
3
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, 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, 162, 21, 8, 185, 2, 117, 20, 1, 2, 21, 64, 1, 210, 133, 132, 5, 2, 1, 168, 145, 2, 125, 148, 21
OFFSET
1,2
LINKS
László Tóth, Counting Solutions of Quadratic Congruences in Several Variables Revisited, J. Int. Seq. 17 (2014), Article 14.11.6.
FORMULA
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
Sum_{k=1..n} a(k) ~ c * n^2, where c = Pi/(4*sqrt(2)*A309710) = 0.521595326207... . - Amiram Eldar, Nov 21 2023
MATHEMATICA
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]}]];
a /@ Range[1, 100] (* Jean-François Alcover, Sep 20 2019, from PARI *)
PROG
(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
(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
CROSSREFS
KEYWORD
mult,nonn,easy
AUTHOR
Yuval Dekel (dekelyuval(AT)hotmail.com), Oct 24 2003
EXTENSIONS
More terms from David Wasserman, Jun 07 2005
STATUS
approved