Skip to content

Problem 2: Even Fibonacci numbers

Link to the problem: https://projecteuler.net/problem=2.

Problem 2

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, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

A simple solution

A straightfoward implementation would look like this.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
(defwire main-wire
  0 >= .sum
  1 >= .a >= .b

  (Repeat
   (-> (When
        (-> .b (Math.Mod 2) (Is 0))
        (-> .sum (Math.Add .b) > .sum))
       .a (Math.Add .b) >= .h
       .b > .a
       .h > .b)
   :Forever true
   :Until (-> .b (IsMore 4000000)))

  .sum (Assert.Is 4613732 true)
  (Log "Answer"))

(defmesh root)
(schedule root main-wire)
(run root)

[info] [2023-02-24 14:01:39.355] [T-1300] [logging.cpp::62] [main-wire] Answer: 4613732

A better solution

We can get rid of the testing of even values: since the first two numbers of the sequence are odd, it is easy to see that only every third number is even:

1  1  2  3  5  8 13 21 34
o  o  e  o  o  e  o  o  e

In other words, we can calculate the next 3 numbers during a single iteration and only sum that last one (which is even).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
(defwire main-wire
  0 >= .sum
  1 >= .a >= .b
  .a (Math.Add .b) >= .c

  (Repeat
   (-> .sum (Math.Add .c) > .sum
       .b (Math.Add .c) > .a
       .c (Math.Add .a) > .b
       .a (Math.Add .b) > .c)
   :Forever true
   :Until (-> .c (IsMore 4000000)))

  .sum (Assert.Is 4613732 true)
  (Log "Answer"))

(defmesh root)
(schedule root main-wire)
(run root)

[info] [2023-02-24 14:01:39.434] [T-2348] [logging.cpp::62] [main-wire] Answer: 4613732

More details on the Project Euler's website: https://projecteuler.net/overview=002.