# 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

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)


(Source)

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.

(Source)

## 1000th Fibonacci number

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

26863810024485359386146727202142923967616609318986952340123175997617981700247881689338369654483356564191827856161443356312976673642210350324634850410377680367334151172899169723197082763985615764450078474174626


All in all, 209 characters long.