Project Euler: Problem 2

Problem 2 of Project Euler is:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

This code (in Delphi 2007) finds the solution in under a second:

procedure TfrmMain.Problem2;
var
  term1, term2, nextTerm :int64;
  numTotal :int64;
begin
  term1 := 1;
  term2 := 2;
  numTotal := 2;
  nextTerm := term1 + term2;
  while nextTerm <= 4000000 do begin
    term1 := term2;
    term2 := nextTerm;
    if not odd(nextTerm) then inc(numTotal, nextTerm);
    nextTerm := term1 + term2;
  end;
  ShowMessage(IntToStr(numTotal));
end;

numTotal is initialised to the value 2 at line 8. The while loop calcualates each term of the series which is then tested to see whether it is even (the Delphi function odd(integer) returns true if the integer being tested is odd). If the current term is even it is added to numTotal. This loop is repeated while the term is less than or equal to 4 000 000.

As stated above, this code produces the correct result in under a second. However, it can be optimised; all the terms are tested for being even as they are calculated. A little thought reveals that every third term is even so we could just add every third term to the total without having to test it. This is because the first term is odd, the second term is even. The sum of an odd integer with an even integer is odd; the sum is only even when both operands are odd or both are even. The sequence follows this order: o, e, o, o, e, o, o, e, o, o, e…

The amended code is:

procedure TfrmMain.Problem2;
var
  term1, term2, nextTerm :int64;
  numTotal :int64;
begin
  term2 := 1;
  numTotal := 0;
  nextTerm := 2;
  while nextTerm <= 4000000 do begin
    inc(numTotal, nextTerm);
    term1 := term2;
    term2 := nextTerm;
    nextTerm := term1 + term2;   // this will be odd
    term1 := term2;
    term2 := nextTerm;
    nextTerm := term1 + term2;   // this will be odd
    term1 := term2;
    term2 := nextTerm;
    nextTerm := term1 + term2;   // this will be even
  end;
  ShowMessage(IntToStr(numTotal));
end;

Tags: ,

Comments are closed.