Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.

>> REGISTER NOW TO START POSTING

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

1. ## 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?  Reply With Quote

3. ## Re: A linearithmic (at most) complexity algorithm to generate 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  Reply With Quote

4. ## Re: A linearithmic (at most) complexity algorithm to generate Pythagorean triples

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.  Reply With Quote

5. ## Re: A linearithmic (at most) complexity algorithm to generate Pythagorean 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  Reply With Quote

6. ## The Following User Says Thank You to Zaphod_b For This Useful Post:

angstrem (May 26th, 2013)

7. ## Re: A linearithmic (at most) complexity algorithm to generate Pythagorean triples

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!  Reply With Quote