A062775 Number of Pythagorean triples mod n: total number of solutions to x^2 + y^2 = z^2 mod n.
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
Offset: 1
Links
- Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe, terms 1001..5000 from Seiichi Manyama)
- Gottfried Helms, Pythagorean triples mod n / Solution enhanced, newsgroup sci.math.research, 2003.
- László Tóth, Counting solutions of quadratic congruences in several variables revisited,arXiv:1404.4214 [math.NT], 2014.
- László Tóth, Counting Solutions of Quadratic Congruences in Several Variables Revisited, J. Int. Seq. 17 (2014), Article 14.11.6.
- Index to sequences related to sums of squares.
Crossrefs
Programs
-
Maple
A062775 := proc(n) 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: seq(A062775(n),n=1..100) ; # R. J. Mathar, Jun 25 2018
-
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 *)
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
From Gottfried Helms, May 13 2004: (Start)
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
Extensions
More terms from Sascha Kurz, Mar 25 2002
Comments