Project Euler 6: Sum Square Difference

The sum of the squares of the first ten natural numbers is:

$$1^2 + 2^2 + \ldots + 10^2 = 385$$

The square of the sum of the first ten natural numbers is:

$$(1 + 2 + \ldots + 10)^2 = 552 = 3025$$

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 a straightforward problem for vector processing capabilities in R.

ProjectEuler

## Project Euler 6: Sum square difference
answer <- sum(1:100)^2 - sum((1:100)^2)
print(answer)

This problem can also be solved arithmetically. When Carl Friedrich Gauss (1777–1855) when he was a child his teacher challenged his students to add all numbers from 1 to 100. All of his friends struggled to add all the 100 numbers one by one, but Carl completed the task in a few seconds. Gauss found that the sum of natural numbers 1 to \(n\) is:

$$\sum_{i=1}^{n} i = \frac{n(n + 1)}{2}$$

The code shown above does what Carl’s classmates would have done, using brute force to count the total. Gauss’ solution only required a straightforward step. Computer scientists use Big O notation to describe the steps it takes to complete an algorithm. In Big-O Notation, the first solution is \(O(n)\) which means that the number of steps in the algorithm grows in direct proportion to the data set. In this case, we only look at 100 numbers. But solving this problem for many billions of numbers would pose some practical issues. The brute-force solution is notated as \(O(n)\) as it takes as many steps as there are elements. Gauss’ solution is \(O(1)\), which means that the solution only requires one step, regardless of the size of the data set.

The sum of the squares of the first \(n\) natural numbers is:

$$\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$$

With these two formulas, a fast solution without having to use loops can be written.

n <- 100
answer <- ((n * (n + 1)) / 2)^2 - (n * (n + 1) * (2 * n + 1)) / 6
print(answer)