11
$\begingroup$

Given $j \geq 5$, is there a formula for the number of Pythagorean triplets $(a, b, c)$ satisfying the constraint that $a, b, c \leq j$?

There exists at least one Pythagorean triplet for $j\geq5$; the question is how to find the exact number of Pythagorean triplets for large $j$.

$\endgroup$
8
  • 1
    $\begingroup$ What does it mean for a triplet to be between two integers? Do you want the hypotenuse to be between the two integers? There is a tabulation at oeis.org/A224921 $\endgroup$ Jul 17, 2016 at 9:58
  • 3
    $\begingroup$ for example, between 2 and 6, there is one Pythagorean triplet, namely, 3, 4, and 5. Also between 2 and 6, there is only one triplet. However, between 2 and 11, there are two triplets: (3,4,5), (6,8,10). $\endgroup$ Jul 17, 2016 at 11:10
  • 6
    $\begingroup$ @StevenLandsburg Regardless of whether the question is appropriate for MO, I think that the OP's reply to Gerry makes it clear what is meant by the question $\endgroup$
    – Yemon Choi
    Jul 17, 2016 at 15:12
  • 3
    $\begingroup$ I don't understand why this question has been closed, it's perfectly reasonable. $\endgroup$
    – Igor Rivin
    Jul 17, 2016 at 18:26
  • 1
    $\begingroup$ These are the partial sums of OEIS sequence A046080; there is a formula there for $A046080(n)$ in terms of the prime factors of $n$. A "closed-form" formula for $A224921(n)$ would seem unlikely. $\endgroup$ Jul 18, 2016 at 21:09

3 Answers 3

8
$\begingroup$

The question here was studied (in a slightly more generalized version) by Sierpinski (1906) in Polish; asymptotics were found by Fricker (1977, 1982) and Fischer (1979) both in German; and an unconditional upper bound was established by Stronina (1969) in Russian.

As for English, you can find these references (and others) in, for example, the paper:

Nowak, W. G., & Recknagel, W. (1989). The distribution of Pythagorean triples and a three-dimensional divisor problem. Math. J. Okayama Univ, 31, 213-220. Link (no paywall).

Here is an excerpt from the first page:

enter image description here

The reference here comes from backtracking; first:

Benito, M., & Varona, J. L. (2002). Pythagorean triangles with legs less than n. Journal of computational and applied mathematics, 143(1), 117-126. Link (no paywall).

In there, the authors point to an earlier paper (p. 118):

Kühleitner, M. (1993, December). An omega theorem on Pythagorean triples. In Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg (Vol. 63, No. 1, pp. 105-113). Springer Berlin/Heidelberg. Link.

The last paper is, unfortunately, only visible as a preview; but it is written in English (despite the German title) and contains a reference to the Nowak and Recknagel paper excerpted above.

$\endgroup$
5
  • 1
    $\begingroup$ I counted 1216894 triples below 637460, of which 101461 are prime. The latter number seems consistent with $\frac{1}{2\pi}N$ rather than with $\frac{4}{\pi}N$. The number 1216894 for all triples in turn seems consistent with $\frac{1}{2\pi}N \log{N}$ rather than $\frac{4}{\pi} N\log{N}$. The factor of $8$ discrepancy clearly comes from one paper counting integer triples and the other POSITIVE integer triples. $\endgroup$ Jul 20, 2016 at 8:47
  • $\begingroup$ to be precise: $n$ is positive in the paper above, while $r$ and $s$ can be negative and can be switched with each other. $\endgroup$ Jul 20, 2016 at 12:38
  • $\begingroup$ @YaakovBaruch (Perhaps I am missing something obvious but...) shouldn't allowing $r$ and $s$ to be negative create a factor $4$ discrepancy? There is an $n \geq 1$ requirement... $\endgroup$ Jul 21, 2016 at 15:47
  • 1
    $\begingroup$ yes, but as I mentioned in the previous comment, another factor of 2 must come from switching $r$ and $s$. My counting of positive triples assumed $0< r < s < n$. $\endgroup$ Jul 21, 2016 at 18:06
  • $\begingroup$ @YaakovBaruch Ah, yes... something obvious! Thanks. $\endgroup$ Jul 21, 2016 at 18:12
3
$\begingroup$

The problem is equivalent to asking for all Pythagorean triples with bounds on the hypotenuse and a variant of that problem is treated in the article ENUMERATION OF ALL PRIMITIVE PYTHAGOREAN TRIPLES WITH HYPOTENUSE LESS THAN OR EQUAL TO N

A simple estimate for the number of primitive Pythagorean triples is due to Lehmer: it is less than $N/2\pi$

Turning to the original problem of enumerating all triples, the following observation helps:

$a^2+b^2=c^2 \implies a=2uv, b=v^2-u^2, c=u^2+v^2; u\le v$
which leads to the problem of finding $\frac{1}{8}\sum_{i=1}^{n}r(i)$, where $r(i)$ is the number of ways to write $i$ as the sum of two squares of signed integers (cf e.g. wolfram ).

The answer is then the aforementioned sum $\frac{1}{8}\sum_{i=1}^{n}r(i)$

$\endgroup$
5
  • $\begingroup$ is there a simple asymptotic for the latter number? $\endgroup$ Jul 19, 2016 at 7:03
  • $\begingroup$ on the wolfram page the asymptotic formula $\sum_{i=1}^{n}r(i) = \pi n + O(\sqrt{n})$ is given $\endgroup$ Jul 19, 2016 at 11:20
  • 1
    $\begingroup$ Yes, the equivalence to "all Pythagorean triples with bounds on the hypotenuse" makes it straightforward to search for (I posted a few example references after using such a query) ... But I'm [somewhat] wary about the reference you provide as it exists only on vixra ... $\endgroup$ Jul 19, 2016 at 17:30
  • 2
    $\begingroup$ Your parametrization of Pythagorean triples is inaccurate in the details: it requires $u$ and $v$ to be relatively prime and of opposite parity, and then the formula parametrizes all primitive Pythagorean triples, not all Pythagorean triples. In other words, as stated, your method double-counts some triples and omits other triples. $\endgroup$ Jul 19, 2016 at 18:12
  • $\begingroup$ Also, the seeming uniform distribution of primitive triples would seem, euristically, to imply an asymptotic of $\frac{1}{2 \pi} \int_1^N \lfloor \frac{N}{x}\rfloor dx \simeq \frac{1}{2 \pi} N\log(N)$ for all triples. Or am I wrong? $\endgroup$ Jul 19, 2016 at 20:24
1
$\begingroup$

It is an old question but I recently solved a programming problem regarding this question, the article was shared above but the method was not explicitly shared here.

Following this article: Pythagorean triangles with legs less than n there is quite a nice solution

We know that each primitive Pythagorean triple can be represented by \begin{align*} a &= x^2 - y^2 \\ b &= 2xy \\ c &= x^2 + y^2 \end{align*} Following the paper lets define a few sets. \begin{align*} R(n) &= \{(x, y) \in \mathbb{Z} \times \mathbb{Z} \mid x^2 + y^2 \leq n, 0 < x < y\}\\ P(n) &= \{(x, y) \in R(n) \mid \gcd(x, y) = 1, x + y \equiv 1 \pmod{2}\} \\ Q(n) &= \{(x, y) \in R(n) \mid \gcd(x, y) = 1\} \end{align*} Note that $|P(n)|$ is exactly the amount of Pythagorean triples with hypotenuse less than or equal to $n$, which is what we are trying to find. Now according to the paper Lemma 3 states \begin{equation*} |P(n)| = \sum_{k \geq 0} (-1)^k|Q(\frac{n}{2^k})| \end{equation*} Note that we changed the region but the proof is the same.

Now all that is left is to calculate $Q(n)$. I define a few equations which are identical to the article, but easier to read. \begin{align*} L(t) &= |\{(x, y) \in R(t^2)\}| = |R(t^2)| \\ L'(t) &= |\{(x, y) \in R(t^2) \mid \gcd(x, y) = 1\}| = |Q(t^2)| \end{align*} Following the exact same proof as the article we have \begin{align*} L(t) &= \sum_{1 \leq d \leq t} L'(\frac{t}{d}) \\ L'(t) &= \sum_{1 \leq d \leq t} \mu(d) L(\frac{t}{d}) \end{align*} Therefore we have, \begin{align*} |Q(n)| &= L'(\sqrt{n}) \\ &= \sum_{1 \leq d \leq \sqrt{n}} \mu(d) L(\frac{\sqrt{n}}{d}) \\ &= \sum_{1 \leq d \leq \sqrt{n}} \mu(d) |R(\frac{n}{d^2})| \end{align*}

Now, using brute force a computer can easily find all the lattice points in $R(n)$, and with a good Möbius sieve we can get a nice easy solution.

I have a python package where I add functions like these if anyone is interested to see the code.

  1. Mobius Sieve
  2. Number of primitve Pythagorean triples with hypotenuse less than n
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.