// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (8 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 6 Solution

Project Euler 6 Solution

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,

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.

Analysis

Solving this problem requires the knowledge of two established formulas:
1. The sum of the first n numbers (triangular numbers, used in Problem 1):

\sum\limits_{i=1}^n i = \frac{n(n+1)}{2}

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

\sum\limits_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}

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:

\frac{n(n-1)(n+1)(3n+2)}{12}

Avoiding loops to solve these types of problems in favor of formulas and closed-form calculations becomes apparent when you are asked to solve 10,000 problems with much higher limits in a fixed amount of time, typically less than a few seconds.

h_mark_sm-05bceb881aa02b72d688d21db01df5d8
This program and method
solves all test cases
on HackerRank


Project Euler 6 Solution

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

Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
|25164150|

Afterthoughts

Project Euler 6 Solution last updated

Discussion

No comments yet.

Post a comment