I have a bit of a trip with Fibonacci numbers lately; here are many things I’ve learnt about them lately.
Formula
There’s 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_n$ term grows substantially faster than $b_n$; the contribution of $b_n$ is negligible when $n$ is bigger than 10.
| $n$ | $a_n$ | $b_n$ | diff % | $\frac{a_n}{\sqrt{5}}$ | $f_n$ |
|---|---|---|---|---|---|
| 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):
a = (4 * (2 ** (n*(3+n))))
b = ((4 * (2 ** (2*n))) - (2 * (2 ** n)) - 1)
c = ((2 * (2 ** n)) - 1)
return a // b & c
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:
2686381002448535938614672720214292396761660931898695234012317599761798
1700247881689338369654483356564191827856161443356312976673642210350324
634850410377680367334151172899169723197082763985615764450078474174626
All in all, 209 characters long.