login
A088964
Number of solutions to x^2 == 2y^2 (mod n).
3
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
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
KEYWORD
mult,nonn,easy
AUTHOR
Yuval Dekel (dekelyuval(AT)hotmail.com), Oct 28 2003
STATUS
approved