OFFSET
1,2
COMMENTS
Also, the number of non-congruent solutions to x^2 - 2y^2 == -1 (mod n). - Andrew Howroyd, Jul 16 2018
The comment above is based on the identity -(x^2 - 2y^2) = (x-2y)^2 - 2(x-y)^2. - Jianing Song, Jul 17 2018
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 == +-1 (mod 8), a(p^e) = (p+1)*p^(e-1) for p == +-3 (mod 8). - Andrew Howroyd, Jul 15 2018
Sum_{k=1..n} a(k) ~ c * n^2, where c = 9/(16*A328895) = 0.644804064282100795... . - Amiram Eldar, Nov 21 2023
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 *)
f[2, e_] := If[e < 3, 2^e, 2^(e+1)]; f[p_, e_] := If[MemberQ[{1, 7}, Mod[p, 8]], (p - 1), (p + 1)] * p^(e - 1); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Sep 11 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+1)%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-4)==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
KEYWORD
mult,nonn,easy
AUTHOR
Yuval Dekel (dekelyuval(AT)hotmail.com), Nov 02 2003
STATUS
approved