A088964 Number of solutions to x^2 == 2y^2 (mod n).

1, 2, 1, 4, 1, 2, 13, 8, 9, 2, 1, 4, 1, 26, 1, 16, 33, 18, 1, 4, 13, 2, 45, 8, 25, 2, 9, 52, 1, 2, 61, 32, 1, 66, 13, 36, 1, 2, 1, 8, 81, 26, 1, 4, 9, 90, 93, 16, 133, 50, 33, 4, 1, 18, 1, 104, 1, 2, 1, 4, 1, 122, 117, 64, 1, 2, 1, 132, 45, 26

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, a(p^e) = p^(2*floor(e/2)) for p mod 8 = +-3, a(p^e) = ((p-1)*e+p)*p^(e-1) for p mod 8 = +-1. - Andrew Howroyd, Jul 13 2018

Sum_{k=1..n} a(k) ~ c * n^2, where c = (64/Pi^4) * A328895 * A196525 = 0.35720726027165235652... . - Amiram Eldar, Nov 21 2023

Maple

A088964 := proc(n) local a, x, y ; a := 0 ; for x from 0 to n-1 do for y from 0 to n-1 do if (x^2-2*y^2) mod n = 0 then a := a+1 ; end if; end do; end do ; a ; end proc:
seq(A088964(n), n=1..70) ; # R. J. Mathar, Jan 07 2011

Mathematica

a[n_] := Product[{p, e} = pe; Which[p == 2, 2^e, Abs[Mod[p, 8] - 4] == 1, (p^2)^Quotient[e, 2], True, (p+e(p-1))p^(e-1)], {pe, FactorInteger[n]}];
Array[a, 100] (* Jean-François Alcover, Apr 08 2020, after Andrew Howroyd *)
f[2, e_] := 2^e; f[p_, e_] := If[MemberQ[{1, 7}, Mod[p, 8]], ((p-1)*e + p)*p^(e-1), p^(2*Floor[e/2])]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Sep 20 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[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, 2^e, if(abs(p%8-4)==1, (p^2)^(e\2), (p+e*(p-1))*p^(e-1))))} \\ Andrew Howroyd, Jul 09 2018

Crossrefs

Cf. A087561, A062803, A196525, A328895.

Sequence in context: A030652 A224065 A077904 * A326721 A243792 A124331

Adjacent sequences: A088961 A088962 A088963 * A088965 A088966 A088967

Keyword

mult,nonn,easy

Author

Yuval Dekel (dekelyuval(AT)hotmail.com), Oct 28 2003

Status

approved