Project Euler – Problem 6

Written by on 30 October 2010

Topics: Project Euler

This exercise has a longer problem description than the previous, so lets jump right into it.

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

Lets start with a definition; We define N such that we want to find a solution for all natural numbers from one to N.
Once again I will provide you with two different solutions. A brute force approach which works nicely when N is small (100 is considered small), and an arithmetic approach where we derive analytical expressions for the solution.

Brute force

The brute force algorithm is really straight forward, so without further ado

int sum = 0;
int squared = 0;
int result = 0;
const int N = 100

for (int i = 1; i     sum += i;
    squared += i * i;
}
result = sum * sum - squared;

and the solution

The difference between the square of sum and sum of squares for 1-100 is 25164150
Solution took 0 ms

Until I reach N=10.000.000 I can’t really see a difference in timing, so the solution approach fast enough for this exercise. Using the big-O notation we can analyse the algorithm and assure our self that the algorithm runs in O(N) time, which means the  solution scales linearly with N, which is fairly good already. But lets explore an analytical approach.

Arithmetic approach

Basically we need to find a way to formula which describes the sum of squares and a formula for the sum of natural numbers.

There are a quite a few sites on the net, which gives some very fine proofs for the formulas I am about to give you, so I will cheat a bit today and just provide the formulas and then link to what I find to be a good proof.

We need formulas for two things. The sum of natural numbers, and the sum of squares of natural numbers.

The sum of natural numbers can be expressed as

Over at 9math they provide 3 different proofs for the formula, with the first one being my absolute favourite. Ken Ward provides 11 different ways to derive the formula. I find the latter page a bit harder to read, but the methods provide a good insight.

Regarding the sum of natural numbers, there is a fun little anecdote about Gauss. Which I will cite from A History of Mathematics by Carl B. Boyer the story goes like

Carl Friedrich Gauss (1777–1855), unlike the men discussed in the preceding chapter, was an infant prodigy. His father was an upright but autocratic Brunswick cooper who died shortly before Gauss’s thirty-first birthday. His mother outlived her husband by another thirty-one years, and she resided with Carl Friedrich and his family for most of that time. Gauss enjoyed numerical computation as a child; an anecdote told of his early schooling is characteristic: One day, in order to keep the class occupied, the teacher had the students add up all the numbers from one to a hundred, with instructions that each should place his slate on a table as soon as he had completed the task. Almost immediately Carl placed his slate on the table, saying, “There it is.” The teacher looked at him scornfully while the others worked diligently. When the instructor finally looked at the results, the slate of Gauss was the only one to have the correct answer, 5050, with no further calculation. The ten-year-old boy evidently had computed mentally the sum of the arithmetic progression 1 + 2 + 3 + … + 99 + 100, presumably through the formula m(m+1)/2. His teachers soon called Gauss’s talent to the attention of the Duke of Brunswick….

This one and 108 different version of the anecdote can be found at sigmaxi.

The second formula we need is the sum of squares of natural numbers, and once again Ken Ward provides us with the proof to the fact that the square of sums is

So with the two formulas in place we can program the solution without such that the only limiting factor is the size that a long can hold.
The code becomes

long sum = 0;
long squared = 0;
long result = 0;

const int N = 100;

sum = N * (N+1)/ 2;
squared = (N * (N + 1) * (2 * N + 1)) / 6;

result = sum * sum - squared;

and the result is

The difference between the square of sum and sum of squares for 1-100 is 25164150
Solution took 0 ms

Using the big-O notation again we can analyse the algorithm and see that it runs in O(1), which means the execution time is constant as a function of N.

Closing remarks

As we have seen the brute force approach to the the problem works rather well, and we have to increase N significantly before there is will be problem with the execution time. However, there is a much smarter solution if we dive into an arithmetic approach, which will only be limited by the size of the integer storage we use.

You can download the source code here.

8 Comments For This Post I'd Love to Hear Yours!

  1. Jean-Marie Hachey says:

    Table 1
    Difference between the sum of the squares and the square of the sum for various sequences of natural numbers.
    [Re: Project Euler – Problem 6].

    http://img11.hostingpics.net/pics/998580pe6table1.jpg

    Table 1 shows that an overflow appears at range 1-2000 in the Arithmetic Solution. The overflow occurs at this line:
    squared = (N * (N + 1) * (2 * N + 1) ) / 6
    ___

    Sources:
    1) Project Euler 6
    Kristian’s algorithm
    http://www.mathblog.dk/files/euler/Problem6.cs
    2) Microsoft Visual C# 2010 Express
    3) Microsoft Office Excel (2007)

  2. chi says:

    the brute force loop seems to have bugged or something. for anyone else following along, it should probably read:


    for (int i = 1; i <= N; i++)
    {
    sum += i;
    squared += i * i;
    }

  3. dead_clade_walking says:

    This website is really great. Nice explanations. 🙂

  4. teen_boy says:

    nice one…………can you provide me some other website where such problems are found. 🙂

  5. Kristian says:

    If you are looking for general programming challenges take a look here:
    http://www.mathblog.dk/programming-challenges/

  6. jeras says:

    You didn’t simplify your final equation, sum*sum – squared. If you expand the terms and simplify, you end up with something like this (python):

    #! /usr/bin/env python
    
    def solve(n=100):
        return n * (n+1) * (n-1) * (3*n+2) // 12
    
    if __name__ == '__main__':
        print solve()
    

    That simplification reduces my runtime from about 67usec to 48usec. 🙂

  7. birdlab says:

    static void Main(string[] args)
    {
    int summe = 0;
    int value = 2;
    int preSumme = 0;
    int differenz = 0;
    int quadriert = 0;
    int result2 = 0;

    for (int i = 1; i <= 100; i++)
    {
    quadriert = (int)Math.Pow(i, value);
    summe += quadriert;
    }

    for (int i = 1; i <= 100; i++)
    {
    preSumme += i;
    }

    result2 = (int)Math.Pow(preSumme, value);

    differenz = result2 – summe;

    Console.WriteLine("Summe der Quadrate der ersten 100 Zahlen =" + summe);
    Console.WriteLine("Quadrat der Summe der ersten 100 Zahlen =" + result2);
    Console.WriteLine("Die Differenz ist =" + differenz);
    Console.ReadKey();
    }

  8. RAJames says:

    I know that you posted this years ago, but I would like comment for the sake of anyone visiting this site in the future. In your solution, you calculate sum and squared from the known series expansions. However, in this particular version of the solution, you calculate sum twice. The squared value only needs:

    squared = ( ( 2 * N + 1 ) * sum ) / 3;

    Not that big a deal, but just for thoroughness
    I just found your site and love it!!

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.