Problem 6: Sum Square Difference

Problem

• Link to the problem

Notes

We have the following sums:

$$\begin{array}{rl}\sum _{i=1}^{n}i& =\frac{n(n+1)}{2}\\ \sum _{i=1}^n{i}^2& =\frac{n(n+1)(2n+1)}{6}\end{array}$$

We want to find the difference between the square of the sum of the first $n$ integers and the sum of the squares of the first $n$ integers:

$$\begin{array}{rl}{\left(\sum _{i=1}^{n}i\right)}^2-\sum _{i=1}^n{i}^2& ={\left(\frac{n(n+1)}{2}\right)}^2-\frac{n(n+1)(2n+1)}{6}\\ & =\frac{n^2(n+1{)}^2}{4}-\frac{n(n+1)(2n+1)}{6}\\ & =\frac{3n^2(n+1{)}^2-2n(n+1)(2n+1)}{12}\\ & =\frac{n(n+1)(3n(n+1)-2(2n+1))}{12}\\ & =\frac{n(n+1)(3n^2+3n-4n-2)}{12}\\ & =\frac{n(n+1)(3n^2-n-2)}{12}\\ & =\frac{n(n+1)(3n+2)(n-1)}{12}\end{array}$$

Solution

See it on GitHub.

//* Problem 6: Sum Square Difference
//*
//* 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.

//! time complexity: O(1)
// see the book for implementation details
// https://euler.newty.dev/problems/6.html#notes
use euler::prelude::*;

const N: u64 = 100;

fn solve() -> Solution {
    // see the derivation in: notes/p6.rs
    solution!(N * (N + 1) * (3 * N + 2) * (N - 1) / 12)
}

problem!(
    6,
    solve,
    "537942be3eb323c507623a6a73fa87bf5aeb97b7c7422993a82aa7c15f6d9cd6"
);