2 - Even Fibonacci

Problem

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, \dots$$ By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Short aside. I prefer the Fibonacci sequence as $F_0=1$ and $F_1=1.$ Since we're asked to consider only the even terms and cap by magnitude, this won't matter. You can simply redefine these as $1$ and $2$ if you prefer.

Foundations and research before we begin

Recursion and tree explosion

The Fibonacci sequence, you can think of as being the base cases $$F_0 = 1$$ $$F_1 = 1$$

and then the recursive definition

$$F_k = F_{k-1} + F_{k-2}$$

Let's analyze the recursive definition. We'll start with $F_4$ as an example. The recursive definition yields $$F_4 = F_3 + F_2$$

Since $F_3$ and $F_2$ aren't base cases we have to continue $$F_3 = F_2 + F_1$$ $$F_2 = F_1 + F_0$$

We keep going until all terms have been reduced to the base cases. Since each term consists of two lower terms we'll visualize them as a binary tree. For each node we drill down $F_{k-1}$ to the left and $F_{k-2}$ to the right. Please enjoy and respect my art:

That's a lot of nodes for just $F_4$. If we would start from $F_5$ then this entire $F_4$ tree is just the left node from $F_5$ while the right node is $F_3$. Larger terms will quickly explode into a big hecking tree and computing higher and higher terms will rapidly become unfeasible. See function calls in appendix

Towards a solution

Recursive consideration

Let's try our hand at recursion in Uiua. Looking at the recursive definition first, we can fork function calls and add them, something like: add fork(fibo sub 2|fibo sub 1)

On the whole we want to return 1 for base cases, but for $F_k$ where $k > 1$ we use the recursive fork addition. To manage this, we can use a switch statement that checks whether the incoming argument is less or equal to 1

# Read these from bottom to top
⨬(+⊃(fibo -2|fibo -1)  #Otherwise add terms recursively
| 1                    #If yes, return 1
)⊸≤1                   #Is less or equal to 1?

Since we are creating a recursive function, we need to specify its signature. We will be returning a single element, given a number, so the signature is |1.1 or simply |1.

Let's call this recursive function BFH and use it to generate a range of Fibonacci numbers. I'll be saving this file as p2-bad.ua and running uiua natively.

# file: p2-bad.ua

# Bad Fibonacci Helper
BFH ← |1 (
  ⨬(+⊃(BFH -2|BFH -1)|1)⊸≤1
)
BF ← ≡BFH⇡
BF 30

The reason I'm not doing this in the pad is because the recursion tree explodes in size and hits the recursion limit. If running natively, you can override this limit.

time UIUA_RECURSION_LIMIT=1000 uiua run p2-bad.ua
[1 1 2 3 5 8 13 21 34 55 89 ... and so on]
uiua run p2-bad.ua  4,97s

Getting the first thirty numbers takes around 5 seconds on my laptop. That's slow.

Memoization to the rescue

Notice that whenever we calculate a term for Fibonacci it relies on the outcomes of the numbers in the sequence before it. $F_9 = F_8 + F_7$. In the range context, we would've already calculated $F_8$ and $F_7$ before $F_9$. Wouldn't it speed things up considerably if we could cache the result of the previous function calls? This is exactly what the memo modifier does. See memo docs

# Better Fibonacci Helper
BFH ← |1 memo(
  ⨬(+⊃(BFH -2|BFH -1)|1)⊸≤1
)
BF ← ≡BFH⇡
BF 30

After memo-izing the recursive call, this program finishes in less than 10 milliseconds. A far cry from 5 seconds. You can even run it in the pad.

However, if you change BF = BFH range to BF = BFH rev range you will end up having a recursion limit error since going backwards doesn't calculate the lower Fibonacci numbers first.

How do you do do?

What we need to do now is to gather sequential Fibonacci numbers until they exceed the $4000000$ threshold. Later we will drop the odd ones and sum up the even ones.

The basics of do is do(do_this|while_condition).

How should we iterate then? One thing we could do is to take in one number, k, and do two things to it. First, we calculate the k-th Fibonacci term and then we increment k by 1. With our memoized BFH function above, we could define this iterative body as X = fork add,1 BFH.

BFH ← |1 memo(
  ⨬(+⊃(BFH -2|BFH -1)|1)⊸≤1
)
X ← ⊃+₁ BFH

Testing a couple of values of X yields

X 5
### 8
### 6

X 14
### 610
### 15

X 20
### 10946
### 21

So, we end up with

X k
### k-th fibonacci number
### k + 1

How will this interact with the do body? According to the do documentation

The net signature of the two functions, minus the condition, is called the composed signature. A composed signature with a positive net signature will collect the outputs into an array.

X consumes 1 argument but outputs 2. We will be overproducing on elements so the extra output should be collected into an array.

Let's try setting this up. Let's get all Fibonacci numbers less than 10. We set the loop function to X the condition to <10 and pass the iterator 0 as an argument to the do function.

    ⍢(X|<10) 0
[1 1 2 3 5 8 13 21 34 55]

Huh, that's not quite right. It looks like it is collecting 10 Fibonacci numbers instead of Fibonacci numbers less than 10. This implies that the condition body is acting on the iterator instead of the Fibonacci numbers. Let's try debugging for clues anyway, what does the condition see?

    ⍢(X|<6?) 1
# Note: Compacted debug for brevity
┌╴?
├╴1
├╴2
├╴3
├╴4
├╴5
├╴6
└╴╴
[1 2 3 5 8]

Yes, the condition body is acting on the iterator whereas we want it to act on the Fibonacci number.

Let's manually prop up some X calls to simulate what gets collected.

# Snapshot of 7 runs
    [X X X X X X X 0]
[8 13 8 5 3 2 1 1]

Sequential calls of X do indeed leave behind a trail of Fibonacci numbers but at its front is the iterator.

Why is the snapshot reversed?

To show the snapshot we have to chain X calls. This is processed from right to left. When overproducing in loops, it is collected into an array instead, resulting in an array that runs left to right.

So, for the condition body we'll just pop the iterator out of the way and then consume the Fibonacci number with our condition check. That should be okay because the do documentation says

If the condition function consumes its only arguments to evaluate the condition, then those arguments will be implicitly copied.

    ⍢(X|<10◌) 0
"Error: Missing argument 2"

Ah, but of course. The condition function is the first thing to run. We're supplying only one argument. We need another one. We should just put the horse before the cart and pretend that this has run once. With X 0 or 1 1.

    ⍢(X|<10◌) X 0
[1 1 2 3 5 8]

That seems to work. Let's try this now, with the 4 million limit

    ⍢(X|<4000000◌) 1 1
[1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597
2584 4181 6765 10946 17711 28657 46368 75025
121393 196418 317811 514229 832040 1346269
2178309 3524578]

Great!

An iterative solution

What we observe from the do loop is that at each iteration, if we overproduce on output then something is pushed off and collected. This is not the official way to think about it but it certainly helps me understand. Here's an annotated version of the loop snapshot from the previous section

# Snapshot of 7 runs
    [X X X X X X X 0]

# At the start of the 8th run
 8 is consumed, replaced by 9 21
 |
 | 13 joins the pushed off elements
 | |
 V V
[8 13 8 5 3 2 1 1]

# After the 8th run
Arguments to next X
  |
 / \  Collected so far
 | |         |
 | |        / \
 | |       /   \
 | |      |     |
 | |     / \   / \
 | |    |   |  |  |
 | |   / \ / \ | / \
 | |   | | | | | | |
 V V   V V V V V V V
[9 21 13 8 5 3 2 1 1]

Can we make a non recursive X such that it pushes off elements as it goes along? Such a function would look and behave something like this:

[X a b]      <-Takes 2 inputs : a b
[(a+b) a b]  <-Gives 3 outputs: (a+b) a b

Of course, add is our main function of choice but we need something that preserves the arguments. Both by and on will do something with either the first or last argument. So will with and off for that matter. Searching for more modifiers we find that above and below operate on all arguments. Since below keeps all arguments after the outputs it is the correct choice. See below docs

[below add a b]
[(a+b) a b]

So, we set X = below add and do something similar to the do loop above. Let's try getting all Fibonacci numbers below 200.

    X ← ◡+

    ⍢(X|<200) 1 1
[1 1 2 3 5 8 13 21 34 55 89]

Hmm, this is off by one. $55+89=144$ is missing. Let's stop and think about it a little. What would it take for 144 to be pushed off and collected? Well, when we have the arguments 233 144 the loop would stop at that point, evaluating 233 < 200 as false, and 144 isn't pushed off. So, we just pop off the first argument in the condition body like we did in the previous section.

    ⍢(X|<200◌) 1 1
[1 1 2 3 5 8 13 21 34 55 89 144]

Solution

Pick your favourite X, iterative

    X ← ◡+

or recursive

BFH ← |1 memo(
  ⨬(+⊃(BFH -2|BFH -1)|1)⊸≤1
)
X ← ⊃+₁ BFH

We'll use X to generate all Fibonacci numbers below the threshold.

For brevity I'll use threshold 200 until the end.

We should start with by mod 2 since we want to target only even Fibonacci numbers.

    ⊸◿2 ⍢(X|<200◌) 1 1
[1 1 2 3 5 8 13 21 34 55 89 144]
[1 1 0 1 1 0 1  1  0  1  1  0]

We only want to keep the even ones, therefore we can flip the mask array with not.

    ¬ ⊸◿2 ⍢(X|<200◌) 1 1
[1 1 2 3 5 8 13 21 34 55 89 144]
[0 0 1 0 0 1 0  0  1  0  0  1]

then keep those

    ▽ ¬ ⊸◿2 ⍢(X|<200◌) 1 1
[2 8 34 144]

and finally we sum them up with reduce add

    /+ ▽ ¬ ⊸◿2 ⍢(X|<4000000⋅) ∩1
4613732

Extra credit

Do you notice any patterns about what numbers are even for the Fibonacci sequence? Turns out every third number is. There is a formula, or a relationship we can use to generate them.

Look at the first 4 even numbers in the sequence

   [2 8 34 144]

What are their ratios?

I'll use stencil for the ratios. You can look at chapter eight for a short discussion on stencil or simply go to the docs.

    ⧈÷ [2 8 34 144]
[4 4.25 4.235294117647059]

Seems to be four and a little something.

$$ 2 * 4 = 8$$ $$ 8 * 4 = 32$$

Well, $32$ is $2$ away from the next even Fibonacci number, $34.$

$$ 34 * 4 = 136$$

And here, $136$ is $8$ away from the next even Fibonacci number. It seems awfully suspicious.

Is it possible that the even numbers keep following this pattern?

Let's define a new recursive relationship, let's call it G, and use it to predict the even numbers.

$$ G_1 = 2,\ G_2 = 8 $$ $$ G_k = 4 \times G_{k-1} + G_{k-2}$$

We can modify our iterative solution, run it under 4 million and compare with the mod filtered results.

X ← ◡(+×₄)
    ⍢(X|<4000000◌) 8 2
[2 8 34 144 610 2584 10946 46368 196418 832040 3524578]

    Y ← ◡+
    ▽ ¬⊸◿ 2⍢(Y|<4000000◌) 1 1
[2 8 34 144 610 2584 10946 46368 196418 832040 3524578]

Yup. That's the same. So an alternative solution is

    /+⍢(◡(+×₄)|<4000000◌) 8 2
4613732

Appendix

Function calls

I wanted to plot the amount of function calls for a naive implementation so I wrote a little script. It calculates the n-th Fibonacci term and keeps track of how many function calls it makes. It outputs how many function calls are made for each of the first 15 terms.

def fibo n
  $GLOBAL_CALLS += 1
  return 1 if n <= 1
  fibo(n-1) + fibo(n-2)
end

(1..15).each do |n|
  $GLOBAL_CALLS = 0
  fibo n
  puts $GLOBAL_CALLS
end

This spits out $$1\ 3\ 5\ 9\ 15\ 25\ 41\ 67 ...and\ so\ on$$

The fourth term here is 9 which agrees with our binary tree drawing for $F_4$ which has that many nodes.

We can plot these with a chart plotter. Crikey, that's an exponential one.