Fibonacci Fun

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

Top-down view of a spiral stair case
Photo by Ludde Lorentz / Unsplash

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


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
        if total > goal
            return 0
        m = n
        n = total

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


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)

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)

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

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

julia> typeof(222232244629420445529739893461909967206666939096499764990979600)

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

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)


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