# Fibonacci Fun

A Riddler Classic problem gives us an excuse to implement and benchmark Fibonacci calculations in Julia.

This week's Riddler Classic is framed as a curious exchange between a postal worker and a customer. The goal is to encode an integer (a street number) by its place in a Fibonacci sequence. Specifically, if $m$ and $n$ are the first two elements, then our street address should be the number $q$ places in the sequence after $n$, i.e. the $(2 + q)^{\text{th}}$ number in that sequence. For example, the standard Fibonacci sequence ${1, 1, 2, 3, 5, 8, 13, \dots}$ has $m=1$ and $n=1$, and the number $8$ would have $q=4$. Thus, we would encode our street number $8$ as $(m, n, q) = (1, 1, 4)$. However, we wish to further require that the choices of $m$ and $n$ maximize $q$. Our goal is to find the encodings for $81$ and $179$ with maximal values of $q$.

## Coding

Implementing Fibonacci sequences with double recursion is a famously touted microbenchmark for Julia. Still, we'll implement it in a more sane way. This function iterates up the chosen sequence to find the value of $q$ for the given integer `goal`

, and returns $0$ if `goal`

is *not* in the sequence.

```
function qfib(m, n, goal)
m = convert(typeof(goal), m)
n = convert(typeof(goal), n)
q = 0
while true
q += 1
total = m + n
if total == goal
return q
end
if total > goal
return 0
end
m = n
n = total
end
end
```

One note about the first two lines of the function. Why are we converting `m`

and `n`

to have the same type as `goal`

? Fibonacci numbers increase very quickly. For our problem of encoding $81$ and $179$, it's not a big deal, but if we generalize even a little bit to later values, the numbers will not fit in the default `Int64`

. If our goal is an `Int128`

, we will introduce type instability which is ruinous to performance. (When we go beyond `Int128`

, will need `BigInt`

.)

### Benchmarks

Curious about performance? Obviously it doesn't matter at all for values like $81$ and $179$, but how does this implementation fare against very large values? Using this table of Fibonacci numbers, we find:

```
# This is the largest Fibonacci number to fit in Int64
julia> @btime qfib(1, 1, 7540113804746346429)
73.004 ns (0 allocations: 0 bytes)
90
```

This is the $92^{\text{nd}}$ Fibonacci number (so $q = 90$ is correct). Seems fast enough. Let's try something larger. The $167^{\text{th}}$ Fibonacci number should give $q=165$.

```
julia> typeof(35600075545958458963222876581316753)
Int128
julia> @btime qfib(1, 1, 35600075545958458963222876581316753)
315.485 ns (0 allocations: 0 bytes)
165
```

Now for something really big, the $300^{\text{th}}$ Fibonacci number:

```
julia> typeof(222232244629420445529739893461909967206666939096499764990979600)
BigInt
julia> @btime qfib(1, 1, 222232244629420445529739893461909967206666939096499764990979600)
20.770 μs (600 allocations: 16.70 KiB)
298
```

Pretty fast indeed :)

### Back to the coding …

Now that we have a much-faster-than-needed Fibonacci calculator, we should implement the search for the choices of $m$ and $n$ that maximize $q$. This is straightforward. The function `maxq`

returns the triple $(m, n, q)$ that maximizes $q$ for a given `goal`

.

```
function maxq(goal)
best = (0, 0, 0)
for m in 1:(goal - 1)
for n in 1:(goal - m)
q = qfib(m, n, goal)
if q > best[3]
best = (m, n, q)
end
end
end
best
end
```

## Results

For the desired "street numbers" $81$ and $179$ we find:

```
julia> @btime maxq(81)
11.997 μs (0 allocations: 0 bytes)
(3, 2, 7)
julia> @btime maxq(179)
57.371 μs (0 allocations: 0 bytes)
(11, 7, 6)
```

The number $81$ is encoded by $(3, 2, 7)$ and $179$ is encoded by $(11, 7, 6)$. Interestingly, they both maximize $q$ with choices of $m$ and $n$ where $m > n$.