3

I want to calaculate pythagorean triplets(code below) and I want to calculate infinitly how do I do it without using the three for loops? Could I use a for loop in some way? thanks.

import math

def main():
    for x in range (10000, 1000):
        for y in range (10000, 1000):
            for z in range(10000, 1000):
                if x*x == y*y + z*z:
                    print y, z, x
                    print '-'*50

if __name__ == '__main__':
    main()  
2
  • What's wrong with the while statement? Could you provide additional information on why you think this MUST be done with the for statement?
    – S.Lott
    Feb 25, 2009 at 21:54
  • If you're doing it for the project-euler problem then there is a simple pencil-and-paper mathematical solution.
    – jfs
    Feb 25, 2009 at 22:24

12 Answers 12

8

Generally, you can't. Three variables, three loops.

But this is a special case, as nobody pointed out. You can solve this problem with two loops.

Also, there's no point in checking y, z and z, y.

Oh, and range(10000, 1000) = [].

import math

for x in range(1, 1000):
  for y in range(x, 1000):
      z = math.sqrt(x**2 + y**2)
      if int(z) == z:
        print x, y, int(z)
        print '-'*50
2
  • +1: for must use some kind of iterable; sequence or generator.
    – S.Lott
    Feb 25, 2009 at 21:53
  • Yeah, that's what I was getting at, and what I would have written if I knew more Python. Feb 26, 2009 at 0:02
4

You can arrange your code in a single main loop like this:

MIN = 10000
MAX = 10010
a = [MIN, MIN, MIN]
while True:
    print a
    for i in range(len(a)):
        a[i] = a[i] + 1
        if a[i] < MAX:
            break
        a[i] = MIN
        i += 1
    else:
        break

Instead of the print a, you can do your Pythagorean triplet test there. This will work for an arbitrary number of dimensions.

If you really want to do this infinitely, you will have to use a different iteration technique such as diagonalization.

1
  • +1 diagonalization---I wanted to be the one to answer that :( Feb 25, 2009 at 22:39
4

You would only need two loops - just check to see if math.sqrt(x*x+y*y) is an integer. If it is, you've discovered a pythagorean triple.

I'm new to Python, so I don't know what range(10000, 1000) does - where does it start and stop? I ask because you can halve your runtime by having the range for y start at x instead of fixing it, due to the fact that addition is commutative.

edit: This answer is what I was getting at, and what I would have written if I knew more Python.

0
2

Using xrange instead of range should use less memory, especially if you want to try large ranges.

4
  • In recent versions of Python, they're the same
    – DNS
    Feb 25, 2009 at 22:41
  • True, although AFAICT that's in Python 3.0 which I assume most folks aren't using yet. Feb 25, 2009 at 22:50
  • But one shouldn't optimize if it's not necessary. Feb 25, 2009 at 22:58
  • Well, the original poster seemed like he wanted to do larger ranges if he could, hence my suggestion. Take it for what it's worth :-) Feb 25, 2009 at 23:02
2

Here's an efficient version, using iterators, that generates all such triples, in order. The trick here is to iterate up through the sets of (x,y) pairs that sum to N, for all N.

import math
import itertools

def all_int_pairs():
    "generate all pairs of positive integers"
    for n in itertools.count(1):
        for x in xrange(1,n/2+1):
            yield x,n-x

for x,y in all_int_pairs():
    z = math.sqrt(x**2 + y**2)
    if int(z) == z:
        print x, y, int(z)
        print '-'*50
1

This is the same as Can Berk Guder's answer, but done as a generator, just for fun. It's not really useful with the nested loops here, but it can often be a cleaner solution. Your function produces results; you worry later about how many to retrieve.

import math

def triplets(limit):
    for x in range(1, limit):
        for y in range(x, limit):
            z = math.sqrt(x**2 + y**2)
            if int(z) == z:
                yield x, y, int(z)

for x, y, z in triplets(10):
    print x, y, z
    print "-" * 50
1

Using the same algorithm (see the other answers for better approaches), you can use itertools.count to get a loop that runs forever.

import itertools

for x in itertools.count(1):
    for y in xrange(1, x):
         for z in xrange(1, y):
              if x*x == y*y + z*z:
                  print x, y, z
1

Not the most efficient (Python will build an array with a billion tuples), but this is a single loop:

for x, y, z in [(x, y, z) for x in range(10000, 11000) for y in range(10000, 11000) for z in range(10000, 11000)]:
    if x*x == y*y + z*z:
        print y, z, x
        print '-'*50

Or, as suggested by Christian Witts,

for x, y, z in ((x, y, z) for x in xrange(10000, 11000) for y in xrange(10000, 11000) for z in xrange(10000, 11000)):
    if x*x == y*y + z*z:
        print y, z, x
        print '-'*50

(assuming Python >= 2.4) uses generators instead of building a billion-tuple array.

Either way, you shouldn't code like this... Your initial code with nested loops is clearer.

1
  • change that to "for x, y, z in ((x, y, z) for x in xrange(10000, 11000) for y in xrange(10000, 11000) for z in xrange(10000, 11000)):" for a generator expression instead and change range to xrange unless you're already using Py3.0 Feb 26, 2009 at 5:06
0

Besides what has already been posted, people would expect three loops for three collections. Anything else may get very confusing and provide no added benefit.

0

If you want to count to infinity ..

Create a generator function that counts from zero and never stops, and use the for loop on it

def inf():
   i = 0
   while True:
     yield i
     i = i + 1

for i in inf():
    print i  # or do whatever you want!

I don't know if there's already such a builtin function

0
0

At least three loops are needed for infinity. To make something flexible takes a ton of loops. This example is a solution to Project Euler Problem 9 and more.

#!/usr/bin/env python

def fcount(start=1):
    n = float(start)
    while True:
        yield n
        n += 1

def find_triples():
    for c in fcount():
        for b in fcount():
            if b > c:
                break
            for a in fcount():
                if a > b:
                    break
                if a ** 2 + b ** 2 == c ** 2:
                    yield (a, b, c)

def triples_by_sum(targetsum):
    for a, b, c in find_triples():
        if a + b + c == targetsum:
            yield a, b, c
        if c > targetsum:
            break

if __name__ == '__main__':
    # Finds multiple triples
    for a, b, c in triples_by_sum(252):
        print a, b, c
    # Finds single triples
    a, b, c = triples_by_sum(1000).next()
    print a, b, c
    # Goes forever
    for a, b, c in find_triples():
        print a, b, c
0

How about use itertools.product instead?

# range is [10000, 1000)
for x, y, z in itertools.product(range(10000, 1000, -1), repeat=3): 
    if x * x == y * y + z * z:
        print(y, z, x)

with a litter bit optimize:

for x, y, z in itertools.product(range(10000, 1000, -1), repeat=3):
    if y >= x or z >= x or x >= (y + z) or z < y:
        continue
    if x * x == y * y + z * z:
        print(y, z, x)

EDIT:Here I just give a way to use product instead of multiple for loop. And you can find more efficient method in above posts.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.