Thread: A linearithmic (at most) complexity algorithm to generate Pythagorean triples

I've been working on ProjectEuler's Problem 75 for about 4 days already, and it completely burns my brain. It's easy to generate Pythagorean triples with Euler's or Dickson's methods, but they're all of quadratic complexity, not something you want to use when aiming for ~million triples. I just can't figure any better method. So, can anybody suggest me an algorithm of at most linearithmic complexity to generate all the Pythagorean triples?

An approach that worked for me: A couple of comments from my Java source:

//
// To generate all triples of interest up to a given number:
//
// Generate all primitive triples and their multiples up to the
// maximum number.
//
// For each generated triple, increment an array counter for
// that triple's perimeter measurement.
//
// After all have been generated, count the number of array
// elements that have value = 1
//

A reference on how I generated all primitive triples:

                //   http://en.wikipedia.org/wiki/Pythagorean_triple

Elapsed time to get the (Java implementation) result for Problem 75 on a really old (creaky like me, but not as cranky) Linux system: under a second. This with array size (for the triangle perimeters) of 1500000.


Cheers!

Z

Thank you for an answer. It turns out, that by now I'm able to generate all the required primitive triples and their perimeters really fast. But that's not the case for their multiples - it's really slow to expand a set of all primitives to a set of primitives-and-non-primitives. So I've started to search some tricks to avoid it. The first idea that comes to mind is to find the number of all possible multiples simply as BOUND_VALUE / PERIMETER. But it yields collisions - there may exist so peremiters p1 != p2 and so integers k1, k2 that p1 * k1 == p2 * k2 < BOUND_VALUE. And trying to identify all such collisions yields a quadratic complexity algorithm. So far, I have no other idea of where to move after generating all possible primitive triples.

From the wikipedia article:

Originally Posted by Emphasis added by davekw7x

Despite generating all primitive triples, Euclid's formula does not produce all triples. This can be remedied by inserting an additional parameter k to the formula. The following will generate all Pythagorean triples uniquely:

a = k*(m^2 - n^2) ,b = k*(2mn) ,c = k*(m^2 + n^2)

where m, n, and k are positive integers with m > n, m − n odd, and with m and n coprime.

You don't really need a separate explicit parameter for k; you can just let m and n get suitably large and test

                if ((((m - n) % 2) == 1) && (gcd(n, m) == 1))

Then, if it passes the test, apply m, n to formulas for a, b, c, and calculate the perimeter.

Cheers!

Z

YEEEES I DID IT FINALLY!!!!
Zaphod_b, thanks very much for help!
Actually, I've used a Triple Tree algorithm, who can generate 3 primitive triples from 1.
And once I had all the perimeters generated, it was wrong trying to use linear Lists, so I've used logarithmic (I believe) TreeMap, and everything computed fast enough!
That's my first problem solved in Scala!