|
| |
|
|
A089003
|
|
Number of non-congruent solutions to x^2 - 2y^2 == 1 (mod n).
|
|
2
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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
|
| |
|
|
