Euler Problem 9

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which, a**2 + b**2 = c**2 For example, 32 + 42 = 9 + 16 = 25 = 52. There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

This problem is actually more of an algebra exercise than an algorithm question. Eliminating C and simplifying:

  • a**2 + b**2 == c**2 AND a + b + c == 1000
  • a**2 + b**2 = (1000 – a – b) * (1000 – a – b)
  • a**2 + b**2 = 1000**2 – 1000a – 1000b – 1000a + a**2 + ab – 1000b + ab + b**2
  • 0 = 1000000 – 2000a – 2000b + 2ab
  • 2a * (1000 – b) = 1000000 – 2000b
  • a = 1000*(500 – b)/(1000 – b)

This gives us the relationship between a and b. To find the integer solution, we try b in range 1..499, and test if a is also an integer.

for b in 1..499
	x = 1000 * (500 - b)
	y = 1000 - b
	if x % y == 0 then
		a = x/y
		c = 1000 - a - b
		puts a, b, c, (a**2 + b**2 == c**2)
	end
end

About this entry