Problem #39 is one of the many problems on Project Euler that involves Pythagorean Triples. In fact, this type of problem is so common that my solution to this problem is nearly identical to my solution for Problem #9. The question reads:
Project Euler Problem 39: Integer right triangles
If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.
{20,48,52}, {24,45,51}, {30,40,50}
For which value of p ≤ 1000, is the number of solutions maximised?
If you look back at my post for Problem #9, you’ll find that these two problems ask for essentially the same thing. Thus, I will not fully explain my solution this time.
Solution #1: Brute Force Approach
We simply use the same method to count Pythagorean Triples with a given perimeter as we did in Problem #9. This involves writing every Pythagorean Triple in the form d(m^2-n^2), d(2mn), d(m^2+n^2) for some integers d, m, and n. By factoring the perimeter, we can count the number of possible triples {d,m,n}. Doing so for every possible perimeter, we can find the perimeter with the maximum number of solutions. Here is an implementation of this method in Python 2.7 that is nearly identical to my solution from Problem #9:
'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #39
'''
import time
from math import sqrt
def listFactors(n):
primes = []
exponents = []
c = 2
while(c<=sqrt(n)):
if(n%c==0):
primes.append(c)
t = 0
while(n%c==0):
n/=c
t+=1
exponents.append(t)
c+=1
if(n>1):
primes.append(n)
exponents.append(1)
return sorted(listFactorsGivenFactorization(primes, exponents))
def listFactorsGivenFactorization(p,e):
total = []
if(len(p) >= 1):
for x in range(e[0]+1):
total.append(p[0]**x)
else:
return [1]
previousTotal = listFactorsGivenFactorization(p[1:], e[1:])
actualTotal = []
for a in total:
for b in previousTotal:
actualTotal.append(a*b)
return actualTotal
def countPythagoreanTriples(n):
if(n%2==1):
return -1
found = []
possibleD = listFactors(n/2)
n/=2
for d in possibleD:
newProduct = n/d
lowerBound = int(sqrt(newProduct/2))
upperBound = int(sqrt(newProduct))
for m in range(lowerBound, upperBound+1):
if(m>0 and newProduct%m == 0):
o = newProduct/m-m
if(0<o<m):
triple = sorted([d*(m*m-o*o), 2*d*m*o, d*(m*m+o*o)])
if triple not in found:
found.append(triple)
return len(found)
def projectEulerProblemThirtyNine(n):
maximum = 1
maxIndex = 12
for c in range(13,n+1):
v = countPythagoreanTriples(c)
if(v>maximum):
maxIndex = c
maximum = v
return maxIndex
start = time.time()
print projectEulerProblemThirtyNine(1000)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
840
--- 0.00754904747009 seconds ---
for input of n = 1000
'''
As shown above, many of the problems on Project Euler are nearly identical to earlier problems, and as a result you can solve new problems by using code written for earlier problems.
Thanks for reading!
The Inner Machinations of Walker 