login
A086932
Number of non-congruent solutions of x^2 + y^2 == -1 (mod n).
5
1, 2, 4, 0, 4, 8, 8, 0, 12, 8, 12, 0, 12, 16, 16, 0, 16, 24, 20, 0, 32, 24, 24, 0, 20, 24, 36, 0, 28, 32, 32, 0, 48, 32, 32, 0, 36, 40, 48, 0, 40, 64, 44, 0, 48, 48, 48, 0, 56, 40, 64, 0, 52, 72, 48, 0, 80, 56, 60, 0, 60, 64, 96, 0, 48, 96, 68, 0, 96, 64, 72, 0, 72, 72, 80, 0, 96, 96
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 if e = 1 or 0 if e > 1, a(p^e) = (p-1)p^(e-1) if p == 1 (mod 4), a(p^e) = (p+1)p^(e-1) if p == 3 (mod 4). - Vladeta Jovovic, Sep 24 2003
Sum_{k=1..n} a(k) ~ c * n^2, where c = 3/(8*G) = 0.409404..., where G is Catalan's constant (A006752). - Amiram Eldar, Oct 18 2022
MATHEMATICA
a[n_] := If[n == 1, 1, Module[{p, e}, Product[{p, e} = pe; Which[p == 2 && e == 1, 2, p == 2 && e > 1, 0, Mod[p, 4] == 1, (p - 1) p^(e - 1), Mod[p, 4] == 3, (p + 1) p^(e - 1)], {pe, FactorInteger[n]}]]];
a /@ Range[1, 100] (* Jean-François Alcover, Sep 14 2019 *)
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[(-1-i)%n + 1])} \\ Andrew Howroyd, Jul 15 2018
(PARI) a(n)={my(f=factor(n)); prod(i=1, #f~, my(p=f[i, 1], e=f[i, 2]); if(p==2, if(e>1, 0, 2), p^(e-1)*if(p%4==1, p-1, p+1)))} \\ Andrew Howroyd, Jul 15 2018
CROSSREFS
Sequence in context: A140875 A364315 A115368 * A331762 A221255 A341862
KEYWORD
mult,nonn
AUTHOR
Yuval Dekel (dekelyuval(AT)hotmail.com), Sep 21 2003
EXTENSIONS
More terms from John W. Layman, Sep 25 2003
STATUS
approved