cp's OEIS Frontend

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

%I A088964 #30 Nov 21 2023 03:29:55
%S A088964 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,
%T A088964 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,
%U A088964 1,2,1,4,1,122,117,64,1,2,1,132,45,26
%N A088964 Number of solutions to x^2 == 2y^2 (mod n).
%H A088964 Andrew Howroyd, <a href="/A088964/b088964.txt">Table of n, a(n) for n = 1..10000</a>
%H A088964 László Tóth, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Toth/toth12.html">Counting Solutions of Quadratic Congruences in Several Variables Revisited</a>, J. Int. Seq. 17 (2014), Article 14.11.6.
%F A088964 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
%F A088964 Sum_{k=1..n} a(k) ~ c * n^2, where c = (64/Pi^4) * A328895 * A196525 = 0.35720726027165235652... . - _Amiram Eldar_, Nov 21 2023
%p A088964 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:
%p A088964 seq(A088964(n),n=1..70) ; # _R. J. Mathar_, Jan 07 2011
%t A088964 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]}];
%t A088964 Array[a, 100] (* _Jean-François Alcover_, Apr 08 2020, after _Andrew Howroyd_ *)
%t A088964 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 *)
%o A088964 (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
%o A088964 (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
%Y A088964 Cf. A087561, A062803, A196525, A328895.
%K A088964 mult,nonn,easy
%O A088964 1,2
%A A088964 Yuval Dekel (dekelyuval(AT)hotmail.com), Oct 28 2003