|
|
A062775
|
|
Number of Pythagorean triples mod n: total number of solutions to x^2 + y^2 = z^2 mod n.
|
|
16
|
|
|
1, 4, 9, 24, 25, 36, 49, 96, 99, 100, 121, 216, 169, 196, 225, 448, 289, 396, 361, 600, 441, 484, 529, 864, 725, 676, 891, 1176, 841, 900, 961, 1792, 1089, 1156, 1225, 2376, 1369, 1444, 1521, 2400, 1681, 1764, 1849, 2904, 2475, 2116, 2209, 4032, 2695, 2900
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
a(n) is multiplicative and, for a prime p, a(p) = p^2. Hence a(n) = n^2 if n is squarefree.
|
|
LINKS
|
|
|
FORMULA
|
a(n) is multiplicative. For the powers of primes p, there are four cases. For p=2, there are cases for even and odd powers: a(2^(2k-1)) = 2^(3k-1) (2^k-1) and a(2^(2k)) = 2^(3k) (2^(k+1)-1). Similarly, for odd primes p, a(p^(2k-1)) = p^(3k-2) (p^k+p^(k-1)-1) and a(p^(2k)) = p^(3k-1) (p^(k+1)+p^k-1). - T. D. Noe, Dec 22 2003
If the canonical form of n is n = 2^i * 3^j * 5^k *... * p^q, then it appears that a(n) = n * f(2, i) * f(3, j) * f(5, k) * ... * f(p, q), where f(p, 1) = p for any prime p; f(2, i) = 2^i + 2^i - 2^ceiling(i/2); f(p, i) = p^i + p^(i-1) - p^floor((i-1)/2) for any odd prime p.
For example, a(7) = 49 because a(7) = 7*f(7, 1) = 7*7; a(16) = 448 because a(16) = a(2^4) = 16 * f(2, 4) = 16 * (16+16-4) = 16*28 = 448; a(12) = 216 because a(12) = a(3*2^2) = 12*f(2, 2)*f(3, 1) = 12*(4+4-2)*3 = 216. (End)
Sum_{k=1..n} a(k) ~ c * n^3, where c = (16/45) * Product_{p prime} (1 + 1/(p^3 + p^2 + p)) = (16/45)*zeta(3)/zeta(4) = 0.39488943478263044166... . - Amiram Eldar, Oct 18 2022, Nov 30 2023
|
|
MAPLE
|
a := 1;
for pe in ifactors(n)[2] do
p := op(1, pe) ;
e := op(2, pe) ;
if p = 2 then
if type(e, 'odd') then
a := a*p^((3*e+1)/2)*(2^((e+1)/2)-1) ;
else
a := a*p^(3*e/2)*(2^(e/2+1)-1) ;
end if;
else
if type(e, 'odd') then
a := a*p^((3*e-1)/2)*(p^((e+1)/2)+p^((e-1)/2)-1) ;
else
a := a*p^(3*e/2-1)*(p^(e/2+1)+p^(e/2)-1) ;
end if;
end if;
end do:
a ;
end proc:
|
|
MATHEMATICA
|
Table[cnt=0; Do[If[Mod[x^2+y^2-z^2, n]==0, cnt++ ], {x, 0, n-1}, {y, 0, n-1}, {z, 0, n-1}]; cnt, {n, 50}]
f[p_, e_] := If[OddQ[e], p^(3*(e+1)/2 - 2)*(p^((e+1)/2) + p^((e-1)/2) - 1), p^(3*e/2 - 1) * (p^(e/2 + 1) + p^(e/2) - 1)]; f[2, e_] := If[OddQ[e], 2^(3*(e+1)/2 - 1)*(2^((e+1)/2) - 1), 2^(3*e/2)*(2^(e/2+1)-1)]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 50] (* Amiram Eldar, Oct 18 2022 *)
|
|
CROSSREFS
|
Cf. A091143 (number of solutions to x^2 + y^2 = z^2 mod 2^n).
|
|
KEYWORD
|
nonn,nice,mult
|
|
AUTHOR
|
Ahmed Fares (ahmedfares(AT)my-deja.com), Jul 18 2001
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|