# Fibonacci

I have a bit of a trip with Fibonacci numbers lately; here are many things I’ve learnt about them lately.

## Formula

There this thing called Binet’s formula, which allows us to calculate any Fibonacci number.

First we need to calculate these terms:

$$ a_n = \left( \frac{1 + \sqrt{5}}{2} \right)^n = \phi ^ n $$

$$ b_n = \left( \frac{1 - \sqrt{5}}{2} \right)^n = - (\phi - 1) ^ n $$

where $$\phi$$ is the solution to $$x^2-x-1 = 0$$

which gives Binet’s formula:

$$ f_n = \frac{a_n - b_n}{\sqrt{5}} $$

The `a`

term grows substantially faster than `b`

; the contribution of `b`

is negligible after `n ~ 10`

.

n | a(n) | b(n) | diff % | a / sqrt(5) | fib = (a - b) / sqrt(5) |
---|---|---|---|---|---|

0 | 1 | 1 | 0 | 0.45 | 0 |

1 | 1.62 | -0.62 | 61.80% | 0.72 | 1 |

2 | 2.62 | 0.38 | 85.41% | 1.17 | 1 |

3 | 4.24 | -0.24 | 94.43% | 1.89 | 2 |

4 | 6.85 | 0.15 | 97.87% | 3.07 | 3 |

5 | 11.09 | -0.09 | 99.19% | 4.96 | 5 |

6 | 17.94 | 0.06 | 99.69% | 8.02 | 8 |

7 | 29.03 | -0.03 | 99.88% | 12.98 | 13 |

8 | 46.98 | 0.02 | 99.95% | 21.01 | 21 |

## About 1/89

The number $$\frac{1}{89}$$ is weirdly related to the Fibonacci series.

$$ \frac{1}{89} = \sum\limits_{n=1}^\infty F_n 10^{-(n + 1)} $$

where $$F_n$$ is the nth Fibonacci number.

```
.01
.001
.0002
.00003
.000005
.0000008
.00000013
.000000021
.0000000034
.00000000055
.000000000089
.0000000000144
.
.
+ .
----------------
.01123595505... = 1/89
```

## Magazine

There is an entire mathematical magazine dedicated to the Fibonacci series. It has existed since 1963, and is still being published.

## Python

This is one of the weirdest algorithms I’ve come across to calculate Python, with lots of bitwise operators.

```
def fib(n):
return (4 << n*(3+n)) // ((4 << 2*n) - (2 << n) - 1) & ((2 << n) - 1)
```

I had to look up about them, it’s not like I use Python bitwise operators every day:

`x << y == x * (2 ** y)`

Ergo, the code above is roughly the same as:

```
def fib(n):
return (4 * (2 ** (n*(3+n)))) // ((4 * (2 ** (2*n))) - (2 * (2 ** n)) - 1) & ((2 * (2 ** n)) - 1)
```

The `&`

operation is the bitwise AND operation, which, it turns out, is equivalent to the MODULO operation when dealing with powers of two.

In general, if divisor is a power n of two, the modulo operation can be translated to a bitwise AND with divisor-1. Similarly, the integer division value / divisor corresponds to a right shift of n positions: value » n.

## 1000th Fibonacci number

And to close this off, this is the 1000th one:

```
26863810024485359386146727202142923967616609318986952340123175997617981700247881689338369654483356564191827856161443356312976673642210350324634850410377680367334151172899169723197082763985615764450078474174626
```

All in all, 209 characters long.