Tuesday 27 September 2011

Project Euler: problem 6


The sum of the squares of the first ten natural numbers is,
12 + 22 + ... + 102 = 385
The square of the sum of the first ten natural numbers is,
(1 + 2 + ... + 10)2 = 552 = 3025
Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 - 385 = 2640.
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

This is one quite simple.

# Create a vector with the first hundred natural numbers

x.1 <- (1:100)
# Square each element of the vector of natural numbers, i.e, square each natural number and store in another vector
y.1 <- x.1^2
head(y.1)
# Sum the first hundred natural numbers and the squares of each of the first hundred natural numbers and take the difference of these sums
a.1 <- sum(y.1)
b.1 <- (sum(x.1))^2
b.1 - a.1
b.1


Answer: 25164150



After solving a couple of these problems, and after reading some solutions posted by aatrujillo here and here, I realize that my solutions are not general, i.e., they only cater to the problem at hand and hence their scope is very limited. For example, consider the above problem. Had the question asked to do the same analysis on the first 200 natural numbers, I would have to rewrite the entire loop again. I understand that in this case it does not involve much more than changing the size of the x.1 vector, but for a problem that involves more than one loop, it seems to be very "uncool". As a result, I have decided to orient my results towards general solutions and then solve the problem by specifying the parameters. Let's see how that goes. :)



4 comments:

  1. No need to crunch numbers; there are formulae to help you.

    1 + ... + n = n * (n + 1) / 2

    and

    1^2 + ... + n^2 = n * (n + 1) * (2 * n + 1) / 6

    Rearrange these for a faster, cleaner solution.

    ReplyDelete
  2. Richie makes a good point. As you progress further into PE questions the order of complexity of brute force algorithms to solve the problems will increase quite swiftly. And don't forget that PE expects the code to complete in under a minute. So, it is a good idea to look for ingenious algorithms that reduce problem complexity before you get down to crunching numbers.

    ReplyDelete
  3. That's true Akhil... I realized when I went a bit deeper in PE problems. Thanks for the advice. :-)

    ReplyDelete
  4. This problem can be solved in a single line:

    sum(seq(1:100))^2 - sum(seq(1:100)^2)

    ReplyDelete