The Wikipedia page has a fairly standard proof.
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?
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?
“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:
(The rest of the post uses the correct result.)
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=771021199884067241 (so all sides will have a common factor of 77=49); if you require primitivity it is 10[sup]16[/sup]-47=9999999999999953=3760118973*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.
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 (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).
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.
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.
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.
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).