Problem 6 in the Project Euler list asks us to:
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
The literal translation of this is:
sumdiff <- function(n) {
sum(c(1:n))^2-sum(c(1:n)^2)
}
However, this is another problem (like Problem #1) that has a closed-form solution, and so can run in constant time.
The closed form expression for the sum of the squares is
\[ sum_{i=1}^{n}i^2 = \frac{1}{6}n(2n+1)(n+1) \]
The closed form expression for the square of the sum is
\[ \left(\sum_{i=1}^{n}i\right)^2 = \left(\frac{n(n+1)}{2}\right)^2 \]
So if we subtract and simplify, we end up with the solution
\[ \frac{1}{12}n(3n^3+2n^2-3n-2) \]
The solution is shown below:
sumdiff2 <- function(n) {
#(1/4)*(n^2)*(1+n)^2 - (1/6)*n*(1+n)*(1+2*n)
(1/12)*(n)*(-2-3*n+2*n^2+3*n^3)
}
We can calculate the answer as shown:
> sumdiff2(100)
[1] 25164150
Needless to say, closed form solutions are preferable where possible.