A089003 Number of non-congruent solutions to x^2 - 2y^2 == 1 (mod n).
1, 2, 4, 4, 6, 8, 6, 16, 12, 12, 12, 16, 14, 12, 24, 32, 16, 24, 20, 24, 24, 24, 22, 64, 30, 28, 36, 24, 30, 48, 30, 64, 48, 32, 36, 48, 38, 40, 56, 96, 40, 48, 44, 48, 72, 44, 46, 128, 42, 60, 64, 56, 54, 72, 72, 96, 80, 60, 60, 96, 62, 60, 72, 128, 84, 96, 68, 64, 88, 72
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
-
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 *) -
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
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
Comments