## Project Euler 6: Find the difference between the sum of the squares and the square of the sum

#### Project Euler 6 Problem Description

Project Euler 6: The sum of the squares of the first ten natural numbers is,

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

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.

#### Analysis

Solving this problem requires the knowledge of two established formulas:

1. The sum of the first *n* numbers (triangular numbers, used in Project Euler Problem 1):

2. The sum of the first *n* square numbers (square pyramidal numbers):

For a visual example of square pyramidal numbers, imagine stacking cannon balls:

We apply these formulas to our range [1,*n*] and find the difference. These formulas will come in useful for solving other problems.

Now, I guess for the purists one could perform the subtraction of these two summations and derive the following formula:

Avoiding loops to solve these types of problems in favor of formulas and closed-form calculations becomes apparent with the more demanding hackerRank Project Euler 6 version. It requires you to solve up to 10,000 trials with a higher limit of n ≤ 10,000 in a fixed amount of time, typically less than a tenth of a second.

#### Project Euler 6 Solution

Runs < 0.001 seconds in Python 2.7.Use this link to get the Project Euler 6 Solution Python 2.7 source.

#### Afterthoughts

- Reference: The On-Line Encyclopedia of Integer Sequences (OEIS) A000330: Square pyramidal numbers: a(n) = 0^2 + 1^2 + 2^2 + ... + n^2 = n*(n+1)*(2*n+1)/6.

1, {5, 14, 30, 55, 91, 140, 204, 285, 385, 506, 650, 819, … }.

*Project Euler 6 Solution last updated*

#include

using namespace std;

#define ll long long

int main()

{

ll n;

cin>>n;

ll ans1 = (n*(n+1)*(2*n+1))/6;

ll ans2 = (n*(n+1))/2;

ll ans3 = ans2*ans2;

cout<<ans3-ans1<<endl;

}