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,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

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.

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

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 *)

Crossrefs

Cf. A091143 (number of solutions to x^2 + y^2 = z^2 mod 2^n).

Cf. A060968, A087687, A002117, A013662.

Number of solutions to x^k + y^k = z^k mod n: this sequence (k=2), A063454 (k=3), A288099 (k=4), A288100 (k=5), A288101 (k=6), A288102 (k=7), A288103 (k=8), A288104 (k=9), A288105 (k=10).

Sequence in context: A270685 A272252 A067801 * A288105 A288101 A320913

Adjacent sequences: A062772 A062773 A062774 * A062776 A062777 A062778

Keyword

nonn,nice,mult

Author

Ahmed Fares (ahmedfares(AT)my-deja.com), Jul 18 2001

Extensions

More terms from Sascha Kurz, Mar 25 2002

Status

approved