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,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^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

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 *)

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-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

Crossrefs

Cf. A088965, A086932, A309710.

Sequence in context: A220217 A220194 A220358 * A097089 A317764 A318075

Adjacent sequences: A088999 A089000 A089001 * A089003 A089004 A089005

Keyword

mult,nonn,easy

Author

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

Status

approved