Project Euler

Problem

This problem comes from Project Euler 6

Problem

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 = 55^2 = 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

We could take the following approach, which is implied by the problem

sum_square = 0
square_sum = 0

for num in range(1, 101):
    sum_square += num**2

for num in range(1, 101):
    square_sum += num

square_sum = square_sum**2

print(square_sum-sum_square)

The problem with this approach is that if we change the range, say from [1 - 100] to [1 - 1 000 000], it would take a much longer time to calculate. What if we could skip all this and have a much faster approach? Well, we have two formulas for the “sum of squares” and “square of sums”!

Sum of Squares

For the “sum of squares”, it is known that

And that’s it. Since $n = 100$ , then

Square of Sums

The sum of all natural numbers from 1 to $n$ is

We just have to use this formula, then square the sum at the end!

Since $n = 100$ , we’ll get

Code

I decided to leave the formulas in the code in case I wished to change $n$ later. And instead of calculating $n(n+1)$ twice, I calculated it once and placed it in the variable " $a$ ".

# Project Euler: Problem 6
# Sum square difference

n = 100

a = n*(n+1)
sum_square = (a*(2*n + 1))/6
square_sum = (a/2)**2

print(square_sum-sum_square)

// Project Euler: Problem 6
// Sum square difference
// Alternate Rust version

fn main() {
    let n = 100;

    let a: i32 = n*(n+1);
    let sum_square: i32 = (a*(2*n + 1))/6;
    let square_sum: i32 = (a/2).pow(2);

    println!("{}", square_sum - sum_square);
}