Determining Pythagorean triples based on the hypotenuse

Question

Below is my written code to determine if, based on the hypotenuse, a Pythagorean triple is possible, and what are the lengths. I was wondering if there is a more efficient way of doing so.

#Victor C
#Determines if a right triangle with user inputted hypotenuse is capable of being a Pythagorean Triple
import math
triplecheck = True
while True:
 hypotenuse = int(input("Please enter the hypotentuse:")) #Smallest hypotenuse which results in a pythagorean triple is 5.
 if hypotenuse > 4:
 break
c = csqr = hypotenuse**2 #sets two variables to be equivalent to c^^2. c is to be modified to shorten factoring, csqr as a reference to set a value
if c % 2 != 0: #even, odd check of value c, to create an integer when dividing by half.
 c = (c+1)//2
else:
 c = c//2
for b in range(1,c+1): #let b^^2 = b || b is equal to each iteration of factors of c^^2, a is set to be remainder of c^^2 minus length b.
 a = csqr-b
 if (math.sqrt(a))%1 == 0 and (math.sqrt(b))%1 == 0: #if squareroots of a and b are both equal to 0, they are integers, therefore fulfilling conditions
 tripleprompt = "You have a Pythagorean Triple, with the lengths of "+str(int(math.sqrt(b)))+", "+str(int(math.sqrt(a)))+" and "+str(hypotenuse)
 print(tripleprompt)
 triplecheck = False
if triplecheck == True:
 print("Sorry, your hypotenuse does not make a Pythagorean Triple.")

• Bitwise: please format your code in a readable format
• inspectorG4dget: () Change if math.sqrt(a)%1 == 0` to if not math.sqrt(a)%1. (2) Put everything inside while True in a function and call that function inside while True. Otherwise, this is a better fit for codereview.SE
• Hugh Bothwell: There is a significantly more mathematically advanced method called the Hermite-Serret method; you can find details at math.stackexchange.com/questions/5877/…

Answer 1

First, let's write this with a little style, and go from there:

import math
def is_triple(hypotenuse):
 """return (a, b, c) if Pythagrean Triple, else None"""
 if hypotenuse < 4:
 return None
 c = hypotenuse ** 2
 for a in xrange(3, hypotenuse):
 b = math.sqrt(c - (a ** 2)) 
 if b == int(b):
 return a, int(b), hypotenuse
 return None

Now, I'll walk you through it, line by line, and show you how I got this.

I have no idea if this is more efficient, but it is written in better style, which is an important thing to consider.

import math

Always put your imports at the top of the module.

def is_triple(hypotenuse):

Here is say 'let's define some functionality, and encase a repeatable, reusable pattern of logic within it. The rest of my answer revolves around this, and is a major first step to programming in Python.

def is_triple(hypotenuse):
 """return (a, b, c) if Pythagrean Triple, else None"""

Note the """ triple quotes. That's your docstring, something that reminds you later what you were thinking when you wrote something. Try to keep it under 65 characters or so.

if hypotenuse < 4:
 return None

In the first line, def is_triple(hypotenuse):, I ask the user to give me something; a variable that I can use later. If I later call this function in the manner is_triple(5), I am basically telling the function that my hypotenuse is 5, and for the rest of the time here, we'll call it hypotenuse.

c = hypotenuse ** 2

That's really all you need for this calculation right now.

for a in xrange(3, hypotenuse):
 b = math.sqrt(c - (a ** 2)) 
 if b == int(b):
 return a, int(b), hypotenuse

for a in xrange(3, hypotenuse) basically says for each whole number between 3 and the hypotenuse, do the stuff I'm about to write.

Following the previous example,

>>> range(3, hypotenuse) #hypotenuse is == 5
[3, 4]

Nevermind that I call xrange(), it functions the same as far as we're concerned here, and importantly, is more efficient.

So now that we've made a loop, a will act as though it is each number in [3, 4], so first, it's 3:

b = math.sqrt(c - (a ** 2))
b = math.sqrt(25 - (3 ** 2))
b = math.sqrt(25 - (9))
b = math.sqrt(16)
b = 4.0

Just like you would on pencil and paper. Notice I put a .0 after, the four. That's important here:

if b == int(b):

Basically, int puts the number b from a decimal to a whole number. We just check if they're the same.

>>> int(4.0)
4
>>> int(4.0) == 4
True

So, if the number we got for b is the same as the whole number representation of b, do the next part:

return a, int(b), hypotenuse

Which maps a value back to whatever you called as an assignment for the function call.

>>> values = is_triple(5)
>>> values
(3, 4, 5)
>>> wrong = is_triple(7)
>>> wrong
>>> #it didn't print anything, because it gave me back None

Finally, at the bottom:

return None

That's the last thing to catch, in case nothing else happens. Obviously, if you've gone through this loop and you haven't gotten an answer? Well, looks like you don't have a match. Give back a None to denote this.

To see this work in action, try this:

>>> import pprint
>>> pprint.pprint([{x: is_triple(x)} for x in xrange(101)])

• Victor C: Thank you to everybody that replied with an answer. I am in grade 11, and have been getting into coding from september. I appreciate all the feedback!

Answer 2

A simple optimisation

Riding on Droogan's very good answer, you can add a simple optimisation. Indeed, instead of doing for a in xrange(3, hypotenuse):, you can try a smaller range.

Also, I took this chance to remove the (premature?) optimisation about if hypotenuse < 4.

The point is to limit yourself to solutions with a <= b (which is what Droogan is doing anyway because this is the first solution you'd find).

Then, you can dive into simple maths and get :

def is_triple(hypotenuse):
 """return (a, b, c) if Pythagrean Triple, else None"""
 # We have :
 # 0 < a < c and 0 < b < c (egality corresponds to uninteresting solutions).
 # If a = b, 2 * a^2 = c^2, impossible in |N
 # Therefore a != b.
 # We can assume a < b
 # 0 < a^2 < c^2/2 < b^2 < c^2
 c_sqr = hypotenuse ** 2
 for a in xrange(1, int(math.ceil(hypotenuse / math.sqrt(2)))):
 b = math.sqrt(c_sqr - (a ** 2))
 if b == int(b):
 return a, int(b), hypotenuse
 return None

One can easily check that :

• you have the same results

• it is faster.

A more subtle optimisation

This is inspired by Joel's solution. He noticed that somehow, factors of 2 can be removed out of the problem and used as a multiplying factor when we find the solution. In fact, it is even better than this as other prime numbers have the same property.

Indeed, according to the properties of primitive Pythagorean triples :

All prime factors of c are primes of the form 4n + 1.

Therefore, we can go through the prime factors of the hypothenuse and if they can't be written 4*n + 1, then they must be part of the multiplicative factor.

Thus, one can write something like :

def prime_factors(n):
 """Yields prime factors of a positive number."""
 assert n > 0
 d = 2
 while d * d <= n:
 while n % d == 0:
 n //= d
 yield d
 d += 1
 if n > 1: # to avoid 1 as a factor
 assert d <= n
 yield n
def is_triple(hypotenuse):
 """return (a, b, c) if Pythagrean Triple, else None"""
 # We have :
 # 0 < a < c and 0 < b < c.
 # If a = b, 2 * a^2 = c^2, impossible in |N
 # Therefore a != b.
 # We can assume a < b
 # 0 < a^2 < c^2/2 < b^2 < c^2
 if hypotenuse:
 factor = 1
 for prime, power in collections.Counter(prime_factors(hypotenuse)).iteritems():
 if prime % 4 != 1:
 factor *= prime ** power
 c = hypotenuse / factor
 c_sqr = c ** 2
 for a in xrange(1, int(math.ceil(c / math.sqrt(2)))):
 b = math.sqrt(c_sqr - (a ** 2))
 if b == int(b):
 return factor * a, factor * int(b), factor * c

This seems to be at least 10 times faster than the code I started with.

Faster faster

According to Wikipedia:

Euclid's formula1 is a fundamental formula for generating Pythagorean triples given an arbitrary pair of positive integers m and n with m> n. The formula states that the integers

a = m^2 - n^2 , b = 2mn , c = m^2 + n^2

form a Pythagorean triple. The triple generated by Euclid's formula is primitive if and only if m and n are coprime and m − n is odd. If both m and n are odd, then a, b, and c will be even, and so the triple will not be primitive; however, dividing a, b, and c by 2 will yield a primitive triple if m and n are coprime.2

Thus, you can write a faster code (O(sqrt(c)) instead of O(c)). Please note that it can give different results than the original code. Also, this optimisation makes the factorising trick somewhat less impressive and you get easily get rid of it.

def is_triple(hypotenuse):
 """return (a, b, c) if Pythagrean Triple, else None"""
 # We have :
 # a = m^2 - n^2, b = 2mn , c = m^2 + n^2 with m > n > 0
 # c >= 2 * n^2
 # 0 < n <= sqrt(c/2)
 if hypotenuse:
 factor = 1
 for prime, power in collections.Counter(prime_factors(hypotenuse)).iteritems():
 if prime % 4 != 1:
 factor *= prime ** power
 c = hypotenuse / factor
 c_sqr = c ** 2
 for n in xrange(1, int(math.ceil(math.sqrt(c/2)))):
 m = math.sqrt(c - n ** 2)
 if m == int(m):
 m = int(m)
 return factor*(m*m - n*n), 2*m*n*factor, hypotenuse
 return None

This seems to be 100 times faster than your code for values up to 20000 (and the bigger the values your consider, the more dramatic the improvement is).

• RubberDuck: Merry WinterBash! Have a HAT!

Answer 3

I'm going to point to one thing that is a potential big source of confusion. Imagine you come back to this a year from now, and you've seen some error on one line of this code. You want to fix that line of code, and you're in a rush. You're not going to read the whole function if you can get away with it. Quick - what do a, b, andc mean?

Usually a, b, and c are the lengths of the sides. Here you've got them as the square of the lengths of the sides. That's going to confuse you when you try to revisit this code.

You've even got some of that confusion going on already - you've set

c=csqr

So you're thinking of c as something, and at the same time you're thinking of that same thing as being csquared. You've got two different concepts of c. Similarly, your comment #let b^^2 = b. That's just asking for trouble. In your comments you clearly think of b as something different from what the code thinks of it as. So somewhere else where your comments might refer to b - is that the same b you meant in your comment earlier, or is it the version of b now in the code? (and note it's really b**2, not b^^2). You don't get any bonus for just having 3 one letter variable names.

If you want to do your calculations in the squared variable, use asq, bsq, and csq. (and consider writing out aSquared etc to make it clear).

I wrote my own version without looking at the other solution, but in Python there should be one and only one obvious way to do things (though you may have to be Dutch to see it). The solutions are almost identical:

def test(hypotenuse):
 factor = 1
 while hypotenuse %2 == 0:
 factor *=2
 hypotenuse/= 2
 hsq = hypotenuse**2
 success = False
 for b in xrange(1,hypotenuse):
 a = math.sqrt(hsq-b**2)
 if a == int(a):
 return sorted([factor*int(a), factor*b, factor*hypotenuse])
 return (None,None,None)
hypotenuse = int(input("Please enter the hypotentuse:"))
(a,b,c) = test(hypotenuse)
if a is None:
 print "failure, utter, utter failure"
else:
 print a, b, c

The only real difference is that I took advantage of the fact that one can prove it we have a pythagorean triple with an even hypotenuse, then dividing by 2 yields a new pythagorean triple.

• RubberDuck: "Quick - what do a, b, and c mean?" +50