Project Euler — problem 9

Just had supper. My stomach is full of cabbage, carrot and noodle. I’d like to solve the ninth problem to stretch my mind. This one is about Pythagorean theorem.

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which, a² + b² = c². For example, 3² + 4² = 9 + 16 = 25 = 5². There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

I admit this is a hard one for me, based on my almost totally forgotten knowledge in algebra. I was thinking about it all day long, even when I was eating or walking. I could try out each combination of a, b and c less than 1,000 to search for the triplet. However, there is only one right answer, thus it would be like finding a needle in a haystack by using brute force algorithm. So I had to search the internet for some help.
Wikipedia on Pythagorean triple provides me the very clue for this problem. Given a² + b² = c², we have a = m² – n², b = 2*m*n, c = m² + n², in which m > n and both are positive integers. Considering another condition a + b + c = 1000, we get the equation 2*m*(m+n) = 1000. Thus, I know 500 can be evenly divided by m and (m+n), and  250 < m^2 < 500. After the analysis, I write down the solution in R.

1
2
3
4
5
6
7
8
9
10

m.high <- floor(sqrt(500))
m.low <- ceiling(sqrt(250))
m <- m.low:m.high
m <- m[which(500 %% m == 0)]
n <- 500 / m - m
a <- m ^ 2 - n ^ 2
b <- 2 * m * n
c <- m ^ 2 + n ^ 2
result <- a * b * c
cat("The result is:", result, "\n")

After years in experimental research, I realize I have forgotten so much fundanmental knowledge in other disciplines. Mathematics is great for mental exercises. I should schedule some time for it.