A086932 Number of non-congruent solutions of x^2 + y^2 == -1 (mod n).

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

Andrew Howroyd, Table of n, a(n) for n = 1..10000

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

Cf. A060968, A006752.

Sequence in context: A140875 A364315 A115368 * A331762 A221255 A341862

Adjacent sequences: A086929 A086930 A086931 * A086933 A086934 A086935

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