Project Euler–Problem 6

Description

From Project Euler:

The sum of the squares of the first ten natural numbers is,
1² + 2² + ... + 10² = 385
The square of the sum of the first ten natural numbers is,
(1 + 2 + ... + 10)² = 55² = 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.

Solution

The straight forward solution to this problem is just to loop through the numbers from 1 to 100 and compute both the square of the sum and the sum of the squares. 

class Problem006
 def sum_of_squares(n)
  (1..n).map { |n| n**2 }.reduce(:+)
 end

 def square_of_sum(n)
  (1..n).reduce(:+) ** 2
 end

 def difference(n)
  sum_of_squares(n) - square_of_sum(n)
 end
end

Problem006.new.difference(100)

Of course, this iterative solution works fine on such a small range, but starts to break down as the range gets larger. Fortunately, there is a simple formula for computing the sum of numbers 1 to n.
sum(n) = n x (n + 1) / 2
Using this information we can now calculate the square of the sum in constant time.

class Problem006
 def square_of_sum(n)
  (n * (n + 1) / 2) ** 2
 end
end

Similarly, there is a formula for calculating the sum of squares from 1 to n. The derivation of which can be found here.
sum²(n) = (n x (n + 1) x (2n + 1)) / 6
So finally, we can optimize the sum of squares to also work in constant time. This gives us a fast solution regardless of the size of n.

class Problem006
 def sum_of_squares(n)
  ((2*n+1) * (n+1) * n) / 6
 end
end

The full source and specifications can be seen on github. Next time, finding the 10,001st prime number.