Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Generating unique, ordered Pythagorean triplets

Tags:

python

math

This is a program I wrote to calculate Pythagorean triplets. When I run the program it prints each set of triplets twice because of the if statement. Is there any way I can tell the program to only print a new set of triplets once? Thanks.

import math  def main():     for x in range (1, 1000):         for y in range (1, 1000):             for z in range(1, 1000):                 if x*x == y*y + z*z:                     print y, z, x                     print '-'*50  if __name__ == '__main__':     main()   
like image 594
marc lincoln Avatar asked Feb 22 '09 16:02

marc lincoln


People also ask

How do you generate Pythagorean triplets?

Get two consecutive whole numbers that add up to a square number. For example, 4 and 5 - 4+5=9 and \sqrt9=3 3,4 and 5 make a Pythagorean triple. 12 and 13 - 12+13=25 \sqrt{25}=5 5,12 and 13 make a Pythagorean triple.

How many unique Pythagorean triples are there?

There are an infinite number of Pythagorean triples. Whenever 2 n +1 is a square, this forms a Pythagorean triple. But 2 n +1 comprises all the odd numbers; every other square numbers is odd; there are an infinite number of odd squares; hence there are an infinite number of Pythagorean triples.

Can you find patterns in what numbers form a Pythagorean triple?

A Pythagorean triple consists of three positive integers a, b, and c, such that a2 + b2 = c2. Such a triple is commonly written (a, b, c), and a well-known example is (3, 4, 5).

What are the 5 Pythagorean triples?

The 5 most common Pythagorean triples are (3, 4, 5), (5, 12, 13), (6, 8, 10), (9, 12, 15), and (15, 20, 25).

How to generate Pythagorean triplets in Python?

Generate Pythagorean Triplets. A Pythagorean triplet is a set of three positive integers a, b and c such that a 2 + b 2 = c 2. Given a limit, generate all Pythagorean Triples with values smaller than given limit. A Simple Solution is to generate these triplets smaller than given limit using three nested loop.

What is the set of primitive Pythagorean triples?

Pythagorean triples [22, 23]. We be gin with the fundamental definition of a generic Pythagorean the length of the hypothenuse. The set of all Pythagorean triples is denoted by P. A Pythagorean triple ( a, b, c) is said to be primitive if a, b and c are relatively prime (co-prime). We denote by P 0 the set of all primitive Pythagorean triples.

Is it possible to parameterise the Pythagorean triples?

Indeed, many existing methods concentrate ongenerating primitive triples but do not cater to non-primitives. By contrast, the approach presentedin this paper to parameterise the Pythagorean triples generates all of the triples in a unique way, i.e.,without repetitions.

Are there other formulas for generating Pythagorean triples Besides Euclid's?

Besides Euclid's formula, many other formulas for generating Pythagorean triples have been developed. Euclid's, Pythagoras' and Plato's formulas for calculating triples have been described here:


1 Answers

Pythagorean Triples make a good example for claiming "for loops considered harmful", because for loops seduce us into thinking about counting, often the most irrelevant part of a task.

(I'm going to stick with pseudo-code to avoid language biases, and to keep the pseudo-code streamlined, I'll not optimize away multiple calculations of e.g. x * x and y * y.)

Version 1:

for x in 1..N {     for y in 1..N {         for z in 1..N {             if x * x + y * y == z * z then {                 // use x, y, z             }         }     } } 

is the worst solution. It generates duplicates, and traverses parts of the space that aren't useful (e.g. whenever z < y). Its time complexity is cubic on N.

Version 2, the first improvement, comes from requiring x < y < z to hold, as in:

for x in 1..N {     for y in x+1..N {         for z in y+1..N {             if x * x + y * y == z * z then {                 // use x, y, z             }         }     } } 

which reduces run time and eliminates duplicated solutions. However, it is still cubic on N; the improvement is just a reduction of the co-efficient of N-cubed.

It is pointless to continue examining increasing values of z after z * z < x * x + y * y no longer holds. That fact motivates Version 3, the first step away from brute-force iteration over z:

for x in 1..N {     for y in x+1..N {         z = y + 1         while z * z < x * x + y * y {             z = z + 1         }         if z * z == x * x + y * y and z <= N then {             // use x, y, z         }     } } 

For N of 1000, this is about 5 times faster than Version 2, but it is still cubic on N.

The next insight is that x and y are the only independent variables; z depends on their values, and the last z value considered for the previous value of y is a good starting search value for the next value of y. That leads to Version 4:

for x in 1..N {     y = x+1     z = y+1     while z <= N {         while z * z < x * x + y * y {             z = z + 1         }         if z * z == x * x + y * y and z <= N then {             // use x, y, z         }         y = y + 1     } } 

which allows y and z to "sweep" the values above x only once. Not only is it over 100 times faster for N of 1000, it is quadratic on N, so the speedup increases as N grows.

I've encountered this kind of improvement often enough to be mistrustful of "counting loops" for any but the most trivial uses (e.g. traversing an array).

Update: Apparently I should have pointed out a few things about V4 that are easy to overlook.

  1. Both of the while loops are controlled by the value of z (one directly, the other indirectly through the square of z). The inner while is actually speeding up the outer while, rather than being orthogonal to it. It's important to look at what the loops are doing, not merely to count how many loops there are.

  2. All of the calculations in V4 are strictly integer arithmetic. Conversion to/from floating-point, as well as floating-point calculations, are costly by comparison.

  3. V4 runs in constant memory, requiring only three integer variables. There are no arrays or hash tables to allocate and initialize (and, potentially, to cause an out-of-memory error).

  4. The original question allowed all of x, y, and x to vary over the same range. V1..V4 followed that pattern.

Below is a not-very-scientific set of timings (using Java under Eclipse on my older laptop with other stuff running...), where the "use x, y, z" was implemented by instantiating a Triple object with the three values and putting it in an ArrayList. (For these runs, N was set to 10,000, which produced 12,471 triples in each case.)

Version 4:           46 sec. using square root:  134 sec. array and map:      400 sec. 

The "array and map" algorithm is essentially:

squares = array of i*i for i in 1 .. N roots = map of i*i -> i for i in 1 .. N for x in 1 .. N     for y in x+1 .. N         z = roots[squares[x] + squares[y]]         if z exists use x, y, z 

The "using square root" algorithm is essentially:

for x in 1 .. N     for y in x+1 .. N         z = (int) sqrt(x * x + y * y)         if z * z == x * x + y * y then use x, y, z 

The actual code for V4 is:

public Collection<Triple> byBetterWhileLoop() {     Collection<Triple> result = new ArrayList<Triple>(limit);     for (int x = 1; x < limit; ++x) {         int xx = x * x;         int y = x + 1;         int z = y + 1;         while (z <= limit) {             int zz = xx + y * y;             while (z * z < zz) {++z;}             if (z * z == zz && z <= limit) {                 result.add(new Triple(x, y, z));             }             ++y;         }     }     return result; } 

Note that x * x is calculated in the outer loop (although I didn't bother to cache z * z); similar optimizations are done in the other variations.

I'll be glad to provide the Java source code on request for the other variations I timed, in case I've mis-implemented anything.

like image 110
joel.neely Avatar answered Sep 27 '22 17:09

joel.neely