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,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 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

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 *)

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[(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
(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

Crossrefs

Cf. A087561, A060968, A309710.

Sequence in context: A318024 A320409 A096466 * A059474 A252828 A208314

Adjacent sequences: A088962 A088963 A088964 * A088966 A088967 A088968

Keyword

mult,nonn,easy

Author

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

Status

approved