# finding a Pythagorean triple of a given size

**URL:** <https://boards.straightdope.com/t/finding-a-pythagorean-triple-of-a-given-size/610335>\
**Category:** Factual Questions\
**Created:** [January 22, 2012, 10:01pm UTC](https://boards.straightdope.com/t/finding-a-pythagorean-triple-of-a-given-size/610335 "2012-01-22T22:01:43Z")\
**Posts on this page:** 12\
**Page:** 2

<div class="post-metadata">

**Author:** ![Omphaloskeptic](https://avatars.discourse-cdn.com/v4/letter/o/bcef8e/32.png) [@Omphaloskeptic](https://boards.straightdope.com/u/Omphaloskeptic)\
**Post date:** [January 24, 2012, 2:52am UTC](https://boards.straightdope.com/t/finding-a-pythagorean-triple-of-a-given-size/610335/21 "2012-01-24T02:52:51Z")

</div>

> [@CalMeacham](#):
>
> You declare that, but is it true? I’ve never seen a proof of it. certainly it’s worked as far as I’ve taken it, but that’ not a proof.

The [Wikipedia page](http://en.wikipedia.org/wiki/Pythagorean_triple#Proof_of_Euclid.27s_formula) has a fairly standard proof.

---

<div class="post-metadata">

**Author:** ![Lumpy](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lumpy/32/446_2.png) [@Lumpy](https://boards.straightdope.com/u/Lumpy)\
**Post date:** [January 24, 2012, 1:48pm UTC](https://boards.straightdope.com/t/finding-a-pythagorean-triple-of-a-given-size/610335/22 "2012-01-24T13:48:25Z")

</div>

> [@Omphaloskeptic](#):
>
> Your question (I think) is, _What constraints does this place on c; and how can I find m and n given c?_  
> \<snip\>Factoring c, if you are not constructing c explicitly by multiplying primes, will eventually get difficult; but at the sizes c~10[sup]15[/sup] you’re interested in, factoring is still easy to do by exhaustive search.

Thank you for your extremely interesting and informative post, but the above is where I’m stuck. How do you factor a number that large?

---

<div class="post-metadata">

**Author:** ![Lumpy](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lumpy/32/446_2.png) [@Lumpy](https://boards.straightdope.com/u/Lumpy)\
**Post date:** [January 24, 2012, 2:05pm UTC](https://boards.straightdope.com/t/finding-a-pythagorean-triple-of-a-given-size/610335/23 "2012-01-24T14:05:33Z")

</div>

> [@Chronos](#):
>
> Do you care at all about the shape of the triangle? The simplest family of primitive Pythagorean triples gives you really long, skinny triangles.

I kind of do care, in that a larger value of C (and B) might be offset by having A be only a much smaller value. Ideally all three sides should be at least somewhat larger than the example I posted in the spoiler section of my first followup post. As to how to rank contending examples? Maybe by the sum of the sides or the resulting area of the triangle?

---

<div class="post-metadata">

**Author:** ![Omphaloskeptic](https://avatars.discourse-cdn.com/v4/letter/o/bcef8e/32.png) [@Omphaloskeptic](https://boards.straightdope.com/u/Omphaloskeptic)\
**Post date:** [January 24, 2012, 5:09pm UTC](https://boards.straightdope.com/t/finding-a-pythagorean-triple-of-a-given-size/610335/24 "2012-01-24T17:09:38Z")

</div>

> [@Lumpy](#):
>
> Thank you for your extremely interesting and informative post, but the above is where I’m stuck. How do you factor a number that large?

“Exhaustive search” just means trying all of the possible prime factors up to the square root of the number, with a simple program in any language you like that allows for arithmetic with numbers of that size. For numbers ~10[sup]15[/sup], this means trying about 3 million factors, which for a modern computer will only take about a second.

I don’t know what programming languages you know (reply and I or someone can help you write such a program). In C, numbers of this size are larger than 32 bits (the typical size for a long int) but will fit in 64 bits (typical for a long long int), so you don’t need to use an arbitrary-precision library. Some languages (like Python) include arbitrary-precision arithmetic natively, so you don’t need to worry about the size.

There are ways to speed up this simple factoring approach, but for numbers much larger than this (say 10[sup]18[/sup] or larger) you would typically switch to a more efficient factoring technique.

* * *

Also, an error in my summary in the earlier post:

> [@](#):
>
> **Just tell me the answer already:**  
> c is the hypotenuse of a [del]primitive[/del] Pythagorean triangle iff it’s of the form c=(product of 3-mod-4 primes)[sup]2[/sup] \* (product of 1-mod-4 primes).  
> _c is the hypotenuse of a primitive triangle if it is a product of 1-mod-4 primes._

(The rest of the post uses the correct result.)

---

<div class="post-metadata">

**Author:** ![Omphaloskeptic](https://avatars.discourse-cdn.com/v4/letter/o/bcef8e/32.png) [@Omphaloskeptic](https://boards.straightdope.com/u/Omphaloskeptic)\
**Post date:** [January 27, 2012, 7:09am UTC](https://boards.straightdope.com/t/finding-a-pythagorean-triple-of-a-given-size/610335/25 "2012-01-27T07:09:53Z")

</div>

> [@Lumpy](#):
>
> I kind of do care, in that a larger value of C (and B) might be offset by having A be only a much smaller value. Ideally all three sides should be at least somewhat larger than the example I posted in the spoiler section of my first followup post. As to how to rank contending examples? Maybe by the sum of the sides or the resulting area of the triangle?

Here’s a ranking for which finding the “best” triangle is straightforward: The best triangle has maximal hypotenuse C (less than your limit of Cmax=10[sup]16[/sup] or whatever). Among triangles with maximal C, the best triangle has maximal area (or perimeter; for fixed C these give the same result). To find the top-ranked triangle this way, just step C down from Cmax, factoring each candidate, until you find a value of C which admits a Pythagorean triangle via the condition already described (requiring that it be primitive if you like). So for example with Cmax=10[sup]16[/sup], the largest value of C if you don’t require primitivity is 10[sup]16[/sup]-11=9999999999999989=7_7_1021_199884067241 (so all sides will have a common factor of 7_7=49); if you require primitivity it is 10[sup]16[/sup]-47=9999999999999953=37_601_18973\*23702153. (The largest 1-mod-4 prime less than Cmax is 10[sup]16[/sup]-63=9999999999999937.)

Now since both of these have several 1-mod-4 factors, each will have several distinct Pythagorean triangles: the Brahmagupta-Fibonacci combination formula gives two distinct ways of writing the product of two sums of squares as a sum of two squares, so for example if there are n distinct 1-mod-4 factors then there will be 2[sup]n-1[/sup] different Pythagorean triples with the given C. So you can just generate all of the different triangles (2 in the first case above, 8 in the second) and check to see which one has maximal area.

If you rank triangles simply according to their area or perimeter (not first ranking according to C) then the search algorithm is simpler (I can describe it if you’re interested; essentially you’re searching a small region of the integer-lattice disk with radius sqrt(C)); but the value of C which gives maximal area, if I’ve done the search right, is substantially smaller than the values above, 9999999999840617.

---

<div class="post-metadata">

**Author:** ![Lumpy](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lumpy/32/446_2.png) [@Lumpy](https://boards.straightdope.com/u/Lumpy)\
**Post date:** [January 27, 2012, 1:58pm UTC](https://boards.straightdope.com/t/finding-a-pythagorean-triple-of-a-given-size/610335/26 "2012-01-27T13:58:05Z")

</div>

So far so good, although I’m still faced with finding the values of M and N for fairly large primes. For example 9,999,999,999,840,617 = 13x 13x 53,717x 1,101,543,229, and I need to already know what perfect squares they’re the sum of before I can use B-F.

---

<div class="post-metadata">

**Author:** ![Omphaloskeptic](https://avatars.discourse-cdn.com/v4/letter/o/bcef8e/32.png) [@Omphaloskeptic](https://boards.straightdope.com/u/Omphaloskeptic)\
**Post date:** [January 27, 2012, 4:44pm UTC](https://boards.straightdope.com/t/finding-a-pythagorean-triple-of-a-given-size/610335/27 "2012-01-27T16:44:54Z")

</div>

> [@Lumpy](#):
>
> So far so good, although I’m still faced with finding the values of M and N for fairly large primes. For example 9,999,999,999,840,617 = 13x 13x 53,717x 1,101,543,229, and I need to already know what perfect squares they’re the sum of before I can use B-F.

Right. These numbers are small enough that if you want you can just do another brute-force exhaustive search (for each prime p, you only have to check squares m\<sqrt(p) to see if p-m[sup]2[/sup] is also a square, so for your largest prime ~10[sup]9[/sup] this only means checking about 30000 values). But if you want to be more efficient you can use Cornacchia’s algorithm (the Wikipedia article is kind of terse; there’s a good pseudocode explanation [here](http://www.schorn.ch/howto.html) (under the heading “Representing a prime as the sum of two squares”). Implementation note: in this algorithm you have to compute the modular exponential b[sup]n[/sup] mod p, for large values of n. This can be done efficiently, without computation of huge numbers, by repeated squaring and modular multiplication. If you’re using a good integer library it may have this built in (Python has pow(b,n,p) for example).

---

<div class="post-metadata">

**Author:** ![Omphaloskeptic](https://avatars.discourse-cdn.com/v4/letter/o/bcef8e/32.png) [@Omphaloskeptic](https://boards.straightdope.com/u/Omphaloskeptic)\
**Post date:** [February 15, 2012, 5:45pm UTC](https://boards.straightdope.com/t/finding-a-pythagorean-triple-of-a-given-size/610335/28 "2012-02-15T17:45:10Z")

</div>

Hey **Lumpy** , just curious–did you find the numbers you were looking for?

---

<div class="post-metadata">

**Author:** ![Lumpy](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lumpy/32/446_2.png) [@Lumpy](https://boards.straightdope.com/u/Lumpy)\
**Post date:** [February 15, 2012, 9:31pm UTC](https://boards.straightdope.com/t/finding-a-pythagorean-triple-of-a-given-size/610335/29 "2012-02-15T21:31:28Z")

</div>

> [@Omphaloskeptic](#):
>
> Hey **Lumpy** , just curious–did you find the numbers you were looking for?

I took it as far as I could without actually writing a program to do the brute force number searches, which would be more work than I was willing to put into it. But thanks again, because I did learn a bit about modular arithmetic.

---

<div class="post-metadata">

**Author:** ![Omphaloskeptic](https://avatars.discourse-cdn.com/v4/letter/o/bcef8e/32.png) [@Omphaloskeptic](https://boards.straightdope.com/u/Omphaloskeptic)\
**Post date:** [February 16, 2012, 4:07am UTC](https://boards.straightdope.com/t/finding-a-pythagorean-triple-of-a-given-size/610335/30 "2012-02-16T04:07:26Z")

</div>

> [@Lumpy](#):
>
> I took it as far as I could without actually writing a program to do the brute force number searches, which would be more work than I was willing to put into it. But thanks again, because I did learn a bit about modular arithmetic.

OK. I can give you some pointers if you want help writing the code. It’s not a bad problem for an introduction to a new programming language.

---

<div class="post-metadata">

**Author:** ![Lumpy](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lumpy/32/446_2.png) [@Lumpy](https://boards.straightdope.com/u/Lumpy)\
**Post date:** [February 16, 2012, 4:24am UTC](https://boards.straightdope.com/t/finding-a-pythagorean-triple-of-a-given-size/610335/31 "2012-02-16T04:24:37Z")

</div>

No need, I’ve discovered there are factorization and sum of squares finders online. I’ll play with those for a while, see what I come up with.

---

<div class="post-metadata">

**Author:** ![gnulinux](https://avatars.discourse-cdn.com/v4/letter/g/6de8d8/32.png) [@gnulinux](https://boards.straightdope.com/u/gnulinux)\
**Post date:** [November 28, 2012, 9:55pm UTC](https://boards.straightdope.com/t/finding-a-pythagorean-triple-of-a-given-size/610335/32 "2012-11-28T21:55:11Z")

</div>

If (a,b,c) is a member of the ‘silver ratio’ sequence of ppt’s then the next one is given by …  
(2a+b+2c,a+2b+2c,2a+2b+3c).

[Previous page](https://boards.straightdope.com/t/finding-a-pythagorean-triple-of-a-given-size/610335.md?page=1)