Project Euler: Problem 6

This is problem 6 on Project Euler:

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

1^(2) + 2^(2) + … + 10^(2) = 385

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

(1 + 2 + … + 10)^(2) = 55^(2) = 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.

This is another problem which has a nice elegant solution, if you are prepared for the mathematics involved.

The formula for the sum of the squares of first n integers is n(n + 1)(2n + 1)/6 and the formula for the sum of the first n numbers is n(n + 1)/2. The answer we are looking for is therefore (n(n + 1)(n)(n + 1)/4) – (n(n + 1)(2n + 1)/6). Factoring for n(n + 1) we get n(n + 1)(n-1)(3n + 2)/12. Solving this for n = 100 we get 100(101)(99)(302)/12. Evaluating this gives us the correct answer.

However, relying on a brute-force approach we can code the problem in Delphi as this:

procedure TfrmMain.Problem6;
var
sum, sumOfSquares, squareOfSum: int64;
  i: integer;
begin
  sum := 0;
sumOfSquares := 0;
  for i := 1 to 100 do begin
    inc(sum, i);
inc(sumOfSquares, i * i);
  end;
squareOfSum := sum * sum;
ShowMessage(IntToStr(squareOfSum - sumOfSquares));
end;

Lines 6 and 7 initialise the variables to hold the sum and the sum of the squares. The loop at line 8 updates the current values of these variables. Line 12 calculates the square of the sum of the first 100 numbers. The difference is then calculated and displayed at line 13. On my PC this code takes less then a second to run.

Tags: , ,

Comments are closed.