A088965 Number of solutions to x^2 + 2y^2 == 1 (mod n).
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, 18, 32, 30, 24, 32, 64, 20, 32, 48, 24, 38, 36, 28, 96, 40, 32, 42, 40, 36, 48, 48, 64, 56, 60, 32, 56, 54, 36, 60, 128, 36, 60, 58, 48, 62, 64, 48, 128, 84, 40, 66, 64, 48, 96
Offset: 1
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.
Programs
-
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
-
Maple
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: seq(A088965(n),n=1..70) ; # R. J. Mathar, Jan 07 2011
-
Mathematica
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 *) -
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, 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
Formula
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
Sum_{k=1..n} a(k) ~ c * n^2, where c = (9/(16*A309710)) = 0.528300880442971272... . - Amiram Eldar, Nov 21 2023