|
%I #25 Nov 21 2023 05:24:47
%S 1,2,2,4,6,4,8,16,6,12,10,8,14,16,12,32,16,12,18,24,16,20,24,32,30,28,
%T 18,32,30,24,32,64,20,32,48,24,38,36,28,96,40,32,42,40,36,48,48,64,56,
%U 60,32,56,54,36,60,128,36,60,58,48,62,64,48,128,84,40,66,64,48,96
%N Number of solutions to x^2 + 2y^2 == 1 (mod n).
%H Andrew Howroyd, <a href="/A088965/b088965.txt">Table of n, a(n) for n = 1..10000</a>
%H 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 Multiplicative with a(2^e) = 2^e for e <= 2, a(2^e) = 2^(e + 1) 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 13 2018
%F Sum_{k=1..n} a(k) ~ c * n^2, where c = (9/(16*A309710)) = 0.528300880442971272... . - _Amiram Eldar_, Nov 21 2023
%p A088965 := 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 = 1 mod n then a := a+1 ; end if; end do; end do ; a ; end proc:
%p seq(A088965(n),n=1..70) ; # _R. J. Mathar_, Jan 07 2011
%t a[1]=1; a[n_]:=Length@Rest@Union@Flatten@Table[If[Mod[i^2 + 2 j^2, n]==1, i+I j, 0], {i, 0, n-1}, {j, 0, n-1}]; Table[a[n], {n, 1, 80}] (* _Vincenzo Librandi_, Jul 16 2018 *)
%o (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
%o (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(e>2, 2, 1), p^(e-1)*if(abs(p%8-2)==1, p-1, p+1)))} \\ _Andrew Howroyd_, Jul 09 2018
%o (Magma) [n eq 1 select 1 else #[x: x in [1..n], y in [1..n] | (x^2+2*y^2) mod n eq 1]: n in [1..80]]; // _Vincenzo Librandi_, Jul 16 2018
%Y Cf. A087561, A060968, A309710.
%K mult,nonn,easy
%O 1,2
%A Yuval Dekel (dekelyuval(AT)hotmail.com), Oct 28 2003
|
