Why isn't my solution to Project Euler 9 working?

Question

Problem 9:

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

a2 + b2 = c2

For example, 3² + 4² = 9 + 16 = 25 = 5².

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

My approach was to generate triplets and then check if they meet the sum a + b + c = d. For that I appliead Dickson's method for generating Pythagorean triplets (Dickson method as explained at Wikipedia: To find integer solutions to x2 + y2 = z2, find positive integers r, s, and t : r2 = 2 * s * t is a square. Then: x = r + s; y = r + t and z = r + s + t. From this we see that r is any even integer and that s and t are factors of r2 / 2.

def problem9(d=12):
  def dickson(r=6):
    factors, triplets, st = [], [], (r**2)/2
    for i in range(1, int( sqrt(st)+1 )): # Sqrt optimization
      if st % i == 0:
        factors += [[r, i, st//i]]
    for i in range(len(factors)):
      r,s,t = factors[i][0], factors[i][1], factors[i][2]
      triplets += [[r+s,r+t,r+s+t]]
    return triplets

  def tripletSumsMyDValue(triplets):
    for tri in triplets:
      a,b,c = tri[0],tri[1],tri[2]
      if d == int(a + b + c):
        return tri
      else:
        return None

  inc = 2
  while True:
    found = tripletSumsMyDValue(dickson(inc))
    if found: return found
    else: print(inc,found,'is not!')
    inc += 1

It's frustrating thinking you're a genius and few seconds after executing your code you realize that you're caught in an infinite loop :P

The while True: loop, it's supposed to stop after hitting the right answer (200, 375, 425) but it turns out to be infinite.

The most upsetting is that next code works fine, so please don't point that out. I just want to know what's wrong in mine.

def problem9b(d = 12):
  inc = 1
  while True:
    for a in range(1, 100 * inc):
      for b in range(1, 100 * inc):
          c = (a ** 2 + b ** 2) ** .5
          if a + b + c == 1000:
              return a, b, c
    inc += 1

Answer 1

for i in range(1,500):
    for j in range(1,500):
        c = (i ** 2 + j ** 2) ** 0.5
        if i+j+c ==1000:
            print(i*j*c)`

I guess this is the shortest code. I use 500 because hypotenuse must be bigger than other edges, and simple math :D

Answer 2

You could have written the program in a simple way as follows:

#function to find the pythagorean triplet
#Using Dickson formula
def pythagorean_triplet_dickson():
 for r in range(1,1000):
  for s in range(1,r):
   if ((r**2)/2)%s == 0:
    t = (r**2/2)/s
    if r+s+r+t+r+t+s == 1000:
     return (r+s)*(r+t)*(r+t+s)

#Printing the result
print pythagorean_triplet_dickson()

You can also use m, n formula which has better execution time compared to Dickson method. Check out the source to see that program also :)

Answer 3

import time
start = time.time()
def isok():
    for a in range(100,1000):
        for b in range(100,1000):
            for c in range(100,1000):
                if a + b + c == 1000 and a ** 2 + b ** 2 == c **2:
                    print("a is {} b is {} c is {}".format(a,b,c))
                    print("anwser is",a * b * c)
                    return True
print(isok())
elapsed = (time.time() - start)
print("This code took: " + str(elapsed) + " seconds")

Answer 4

Since c = 1000 - a - b, this shorter and faster Python code can also be followed:

# i = a, k = b, j = c
for i in range (1 , 1000):
for k in range (i + 1 , 1000):
    j = 1000 - i - k
    if (i ** 2 + k ** 2 == j ** 2) & (i + j + k == 1000):
        print (i * k * j)
        break

Answer 5

There is a much easier way to do this;

If instead of diving straight into the coding of it, you look at the maths, you can simplify the problem significantly.

We have two equations;

a2 + b2 = c2

a + b + c = 1000

So substitute one into the other:

a2 + b2 = (1000 - a - b)2

0 = 10002 - 2000a - 2000b - 2ab

We also know that a, b, and c are all <1000. So, we can get a list of all combinations of a and b which satisfy that equation, and then simply check what sqrt(a**2 + b**2) is.

You can do it in a single (admittedly ugly and not very pythonic) list comprehension, and it takes only a second.

[[a,b, sqrt(a**2 + b**2)] for a,b in combinations(range(1,1000),2) if 1000000-2000*a-2000*b+2*a*b==0]

[[200, 375, 425.0]]

A list comprehension is a quick way of creating a list in python. Any list you create through list comprehension can always be created in a clearer way using loops. You can read about them more here.

Here's a simple one:

a = [i for i in range(10)]

which just does the same as:

a = []
for i in range(10):
  a.append(i)

Here's the example i gave;

[[a,b, sqrt(a**2 + b**2)] for a,b in combinations(range(1,1000),2) if 1000000-2000*a-2000*b+2*a*b==0]

which can be written:

triplets = []
for a,b in combinations(range(1,1000),2):
  if 1000000-2000*a-2000*b+2*a*b==0:
    triplets.append([a, b, sqrt(a**2 + b**2)])

combinations is just a function of the itertools module, you can read about it there.

As is pointed out in the comments below though, there is a way it can be simplified even further;

0 = 10002 - 2000a - 2000b - 2ab

can be rewritten to give b in terms of a.

a = 1000 * 500-b / 1000-a

combinations(range(1,1000), 2) will give a list a million entries long. It scales with n2. By writing b in terms of a, and only iterating over range(1,1000) once, you cut it down to O(n), from O(n2).

Instead, you can do:

from math import sqrt, floor

for a in range(1, 500):
  b = 1000 * (500-a) / (1000-a)
  c = sqrt(a**2 + b**2)
  if int(floor(c)) == c and 0 < a < b < c:
    print a, b, c

You can cast c to an int if you want, but then if it somehow doesn't work, that would mask it.

Answer 6

  def tripletSumsMyDValue(triplets):
    for tri in triplets:
      a,b,c = tri[0],tri[1],tri[2]
      if d == int(a + b + c):
        return tri
      else:
        return None

For each triplet in the group, if it's the answer, you return it; if it isn't, you return None. That means you never look at any triplet after the first in each group. The answer appears in group 150, which has triplets that add up to 22952, 11704, 7956, 4960, 4212, 2968, 2720, 1980, 1736, 1400, 1260, 1040, 1000, 900, 880; since the 22952 is not 1000, you fail that group.

The easiest way to fix that is to just remove the whole else clause. If you never return tri during the loop, you'll fall off the end of the function and return None by default.

However, it's worth noting that, even with this fix, your code will never terminate for a number that has no answers, even though you I'm pretty sure you quickly reach a point where no further values could possibly work. (Without reading it carefully I'm not sure where that point is; maybe inc > d?)

---

As a side note, you could simplify this code a lot. First, if tri always has three members (which it does), the following are equivalent:

a,b,c = tri[0],tri[1], tri[2]
a,b,c = tri

Or you can even do for a,b,c in triplets:. Or, even simpler:

for tri in triplets:
    if d == int(sum(tri)):
        return tri