Find the nth Sequence of a Fibonacci Sum

The Fibonacci sequence is a recursive function defined as Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2). In other words:

n            | 0  | 1  | 2  | 3  | 4  | 5  | 6  | 7  | 8  | 9  | 10 |
Fibonacci(n) | 0  | 1  | 1  | 2  | 3  | 5  | 8  | 13 | 21 | 34 | 55 |

The Fibonacci sequence is the "Hello World" of recursion because it is relatively easy to grasp. Today though, we're going to break up the monotony and learn how to calculate the n value from the sum. In other words, we'll make a function that takes in the number 55 and spits out 10. We'll also learn how to handle exceptionally large sums where we'll need to use approximation.

Why Would We Need to do This in the Real World?

The Fibonacci sequence has some applications in the fields of mathematics and computer science, but I am neither a mathematician nor a scientist, so to be honest with you, I don't know what real-world purpose something like this might serve. The real point of this is to flex our problem solving muscles by thinking about an old problem in a new way.

Solution 1 - The Easy Way

At first glance, the solution for this problem seems obvious: Make a Fibonacci sequence, then write another function that takes in a number and loops through the Fibonacci function until there's a match.

The Fibonacci function:

def fib(n):
  ar = [0, 1]
  if n < len(ar):
    return ar[n]
  else:
    while n > len(ar) - 1:
    ar.append(
      ar[len(ar)-1] + ar[len(ar) - 2]
    )
  return ar[n]

Easy enough, but let's make sure (I named this file fib.py):

>>> from fib import *
>>> fib(10)
55

Perfect. Now, let's write the function that will give us 10 when we pass it 55:

def find_fib(sum):
  n = 0
  while True:
    if fib(n) > sum:
      return -1 # This is our error code
    elif fib(n):
      n = n+1
    else:
      return n

This function takes in a sum, say 55, and then starts to calculate a Fibonacci number for 0 through infinity. The first line after the while loop checks to see if Fibonacci(n) is greater than the sum passed (I'll tell you why in a second). If it's not, we increment n by one so that in the next loop, we calculate the next Fibonacci number. Finally, if fib(n) is neither greater than nor less than sum, it must be equal, meaning we've found our n and thus return it.

We check to see if fib(n) is greater than the sum because it's possible that the number passed is not a Fibonacci number at all. Suppose we passed this function the number 25. In the 8th iteration, fib(n) will be 21, and in the next, it will be 34, skipping 25. We return -1 to show that the sum passed to this function is not a Fibonacci number.

I like to pass -1 in this function instead of an error message like "This is not a Fibonacci number" because I don't think mathy functions should return words. That is just a personal design choice and the actual implementation is up to you :)

Let's go ahead and test this function out:

>>> from fib import *
>>> fib(20)
6725
>>> find_fib(6725)
20
>>> find_fib(25)
-1

Awesome. There is one thing I don't like about this solution though: it's slow. Suppose for some reason, the sum you were looking for was the 2000th sequence. Go ahead and try it:

>>> x = fib(2000)
>>> find_fib(x)
2000

It still works, but did your IDLE take a second to figure it out? Mine sure did, I wonder if there's a way to speed it up (spoiler alert, there is).

Solution 2 - The Math Way

Guess what? There is actually a formula for finding the approximate value of a Fibonacci number without calculating all the numbers before:

Fibonacci(n) = (Phi^n)/5^0.5

So if we actually wanted to find n, we would use:

n = log base Phi of (5^0.5 * Fibonacci(n))

Please note that a number to the 0.5 power is a square root, I don't know how to write the radical in markdown 🤷. Also note, the number "Phi" is:

Phi = ((5^0.5) + 1)/2

Let's put this into a function:

import math
def find_fib_formula(sum):
  Phi = (math.sqrt(5) + 1)/2
  formula_result = round(math.log((sum * math.sqrt(5)), Phi))
  return formula_result

Cool, let's try it out

>>> from fib import *
>>> x = fib(1000)
>>> find_fib_formula(x)
1000

It works! There's a problem though. Since we are using round to return the result, we might run into an issue where a non-Fibonacci number is passed, but one is returned. For example, we know that Fibonacci(1000) - 1 is not a Fibonacci number, but look:

>>> x = fib(1000)
>>> find_fib_formula(x - 1)
1000

This is returning the wrong value, so we need to throw in something that double checks. Rewrite your function to check if fib(formula_result) == sum and return an error code (-1) if not:

def find_fib_formula(sum):
  Phi = (math.sqrt(5) + 1)/2
  formula_result = round(math.log((sum * math.sqrt(5)), Phi))
  if fib(formula_result) == sum:
    return formula_result
  else:
    return -1

And let's test it one more time:

>>> from fib import *
>>> x = fib(1000)
>>> find_fib_formula(x)
1000
>>> find_fib_formula(x - 1)
-1

Awesome! But once again, this function isn't exactly perfect, can you guess why? Try to use it with the result of fib(2000). Did you get an error saying the int is too big to convert to float? That's because these numbers are getting really big as we get higher and part of our equation is multiplying that big ol' integer by the square root of five, which is about 2.23. Python can't turn that big an integer into a decimal number, so we'll have to find a way around that.

Solution 3 - Approximation

Since the problem is that we can't turn these big integers into floats, we're just not going to. When we want to multiply the sum by Phi, we're actually just going to multiply it by 2, and then find the log base Phi of that number. Since this way is less precise, we'll also double check to make sure the results of our formula are accurate, and if not, we'll try a few other numbers around our result. It'll look like this:

def find_big_fib(sum):
  Phi = (math.sqrt(5) + 1)/2
  possible_solution = round(math.log(sum*2, Phi))
  if fib(possible_solution) == sum:
    return possible_solution
  else:
    possible_solutions = [
      possible_solution - 1,
      possible_solution - 2,
      possible_solution - 3,
      possible_solution + 1,
      possible_solution + 2,
      possible_solution + 3,
    ]
    for i in possible_solutions:
      if fib(i) == sum:
        return i
    return -1

Can you tell what's happening here? Just like last time, we first calculate the value of Phi. Then, we run the same formula as the previous function, but this time, we use 2 instead of the square root of 5, avoiding the need for turning an impossibly giant integer into a float. To make sure we didn't lose too much accuracy by approximating, we check and see if the number we came up equals the number we were passed when put through the Fibonacci function. If not, we try plus or minus 1, 2, and 3 the number we came up. If none of those are right, we conclude that the sum passed to us is not a Fibonacci sequence and return -1.

>>> from fib import *
>>> x = fib(3000)
>>> find_big_fib(x)
3000

Conclusion

In this tutorial you learned not only how to find the nth value of a Fibonacci number, but also how to work around the limitations of your computer. This is a good thing to think about because sometimes the obvious solution to a problem only works for a small scale. You can almost always find workarounds like this, but make sure to keep in mind the trade-offs you are making.

I added some conditionals to the Python script so that you can always use the find_fib function, and it will decide if it needs to use the find_fib_formula, who will decide if it needs to use find_big_fib. Here is the code in full:

import math

def fib(n):
  ar = [0, 1]
  if n < len(ar):
    return ar[n]
  else:
    while n > len(ar)-1:
      ar.append(
        ar[len(ar)-1] + ar[len(ar)-2]
      )
    return ar[n]

def find_fib(sum):
  if sum < fib(500):
    n = 0
    while True:
      if fib(n) > sum:
        return -1 # This is an error code
      elif fib(n) < sum:
        n = n+1
      else:
        return n
  else:
    return find_fib_formula(sum)

def find_fib_formula(sum):
  if sum <= fib(1000):
    Phi = (math.sqrt(5) + 1)/2
    formula_result = round(math.log((sum * math.sqrt(5)), Phi))
    if fib(formula_result) == sum:
      return formula_result
    else:
      return -1
  else:
    return find_big_fib(sum)

def find_big_fib(sum):
  Phi = (math.sqrt(5) + 1)/2
  possible_solution =  round(math.log(sum * 2, Phi))
  if fib(possible_solution) == sum:
    return possible_solution
  else:
    possible_solutions = [
      possible_solution - 1,
      possible_solution - 2,
      possible_solution - 3,
      possible_solution + 1,
      possible_solution + 2,
      possible_solution + 3,
    ]
    for i in possible_solutions:
      if fib(i) == sum:
        return i
    return -1