Fibonacci Fun

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