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.
Solving this problem requires the knowledge of two established formulas:
1. The sum of the first n numbers (triangular numbers, used in Problem 1):
2. The sum of the first n square numbers (square pyramidal numbers):
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 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.
solves all test cases
Project Euler 6 SolutionRuns < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 6 Solution Python 2.7 source.
AnswerSlowly 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.
- 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, …
- For a visual example of pyramidal numbers, imagine stacking cannon balls