CODEWITHSUNDEEP
python-2.7
Yewdent Niedtaknow
Yewdent Niedtaknow

Reputation: 33

Pythagorean triples not being found in code - issue with code or theory?

I'm working on Project Euler's Problem 9 and have been picking at it for some time now.

This problem states:

'A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a^2 + b^2 = c^2
For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.'

I've developed a code that works for the case given of the pythagorean triples of 3,4 and 5. However when extended to try to find the integers a,b and c, it comes up with nothing which makes me think my method must be missing a few pythagorean triples. Here is my code:

def square(list): #makes a function to square values in a list
    return [i**2 for i in list]

list = range(1,333)
list2 = square(list)

i = len(list2) -1    
while i != 1:
    j=0
    k=i
    while j != k:
        lhs = list2[j] + list2[k]
        rhs = list2[i]
        if lhs == rhs:
            #print i+1,j+1,k+1 - included to check the code was working for small values
            if i+1 + j+1 + k+1 == 1000:
                print (i+1)*(j+1)*(k+1)
            break
        if lhs < rhs:
            j += 1
        if lhs > rhs:    
            k -= 1
    i -= 1

Please let me know if you think this is the case, if I can improve the code somehow or how I can find the missing triple!

Upvotes: 2

Views: 48

Answers (2)

blhsing
blhsing

Reputation: 106543

A more optimal solution:

for a in range(1, 1000 / 3 + 1):
    for b in range(a + 1, 1000 / 2 + 1):
        c = 1000 - a - b
        if a * a + b * b == c * c:
            print a * b * c

Explanations for the ranges:

  • a < b < c < 1000, so a has to be no greater than 1000 / 3
  • b < c < 1000, so b has to be no greater than 1000 / 2
  • c is 1000 - a - b

Upvotes: 1

Raphael Facredyn
Raphael Facredyn

Reputation: 186

If you are not particularly interested in efficiency than you co do this

import math

for a in range(1, 1000):
    for b in range(1, 1000):
        c = math.sqrt(a**2 + b**2)
        if a + b + c == 1000:
            print a * b * c

Upvotes: 0

Related Questions