Project Euler — problem 9

June 12, 2012
By

(This article was first published on Tony's bubble universe » R, and kindly contributed to R-bloggers)

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, a2 + b2 = c2. For example, 32 + 42 = 9 + 16 = 25 = 52. 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 a2 + b2 = c2, we have a = m2 – n2, b = 2*m*n, c = m2 + n2, 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.

?View Code RSPLUS
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.

To leave a comment for the author, please follow the link and comment on his blog: Tony's bubble universe » R.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Tags: , ,

Comments are closed.