Find the nth Sequence of a Fibonacci Sum
Tags: python, tutorial
Published: 2019-09-09 00:02:18

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:
```python
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:
```python
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 :shrug:. Also note, the number "Phi" is:
```
Phi = ((5^0.5) + 1)/2
```
Let's put this into a function:
```python
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:
```python
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:

```python
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:

```python
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

```