Challenge 6: Sum Square Difference

andrew-field commented 6 years ago

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)² = 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.

andrew-field commented 6 years ago

Pretty easy.

andrew-field commented 6 years ago

My first solution was a simple brute force attack calculating the two values and finding the difference between them. The code is here which you can also see in the file history:

// Square of sum of numbers.
squareSum := 0

// Sum of square of numbers.
sumSquare := 0

for i := 1; i < 101; i++ {
    squareSum += i
    sumSquare += i * i
    }
// Square of sum.
squareSum *= squareSum

fmt.Println("Difference:", squareSum-sumSquare)

However, by doing the algebra of expanding and simplifying (w + x + y + z + ...)² - w² - x² - y² - z² - ... you are left with a calculation which will lead straight to the answer without doing the inbetween steps.

andrew-field commented 3 years ago

Complete rewrite and made function more general.

1+2+...+n = n(n+1)/2 1²+2²+...+n² = n(n+1)(2n+1)/6

So for xₖ₊₁ = xₖ + 1, (x₁ + ... +xₙ)² = n²x₁² + n²(n-1)x₁ + (n²(n-1)²)/4 x₁² + ... + xₙ² = nx₁² + n(n-1)x₁ + (n(n-1)(2n-1))/6 (x₁ + ... +xₙ)² - (x₁² + ... + xₙ²) = nx₁(x₁+n-1)(n-1) + (n(3n³-10n²+9n-2))/12

andrew-field / projecteuler-go

Challenge 6: Sum Square Difference #9