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

1, 2, 2, 4, 6, 4, 8, 0, 6, 12, 10, 8, 14, 16, 12, 0, 16, 12, 18, 24, 16, 20, 24, 0, 30, 28, 18, 32, 30, 24, 32, 0, 20, 32, 48, 24, 38, 36, 28, 0, 40, 32, 42, 40, 36, 48, 48, 0, 56, 60, 32, 56, 54, 36, 60, 0, 36, 60, 58, 48, 62, 64, 48, 0, 84, 40, 66, 64, 48, 96

Offset: 1

Author

Yuval Dekel (dekelyuval(AT)hotmail.com), Nov 02 2003

Keywords

• mult
• nonn
• easy

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.

Crossrefs

Cf. A088965, A086932, A309710.

Programs

Mathematica

f[2, e_] := If[e < 3, 2^e, 0]; f[p_, e_] := If[MemberQ[{1, 7}, Mod[p - 2, 8]], (p - 1), (p + 1)] * p^(e - 1); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Sep 11 2020 *)

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-2*i)%n + 1])} \\ Andrew Howroyd, Jul 09 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>2, 0, 2^e), p^(e-1)*if(abs(p%8-2)==1, p-1, p+1)))} \\ Andrew Howroyd, Jul 09 2018

Formula

Multiplicative with a(2^e) = 2^e for e <= 2, a(2^e) = 0 for e > 2, a(p^e) = (p-1)*p^(e-1) for p-2 mod 8 = +-1, a(p^e) = (p+1)*p^(e-1) for p-2 mod 8 = +-3. - Andrew Howroyd, Jul 15 2018

Sum_{k=1..n} a(k) ~ c * n^2, where c = 7/(16*A309710) = 0.410900684788977656... . - Amiram Eldar, Nov 21 2023