# 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.

na(n)b(n)diff %a / sqrt(5)(a - b) / sqrt(5)
01100.450
11.62-0.6261.80%0.721
22.620.3885.41%1.171
34.24-0.2494.43%1.892
46.850.1597.87%3.073
511.09-0.0999.19%4.965
617.940.0699.69%8.028
729.03-0.0399.88%12.9813
846.980.0299.95%21.0121

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):
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.

(Source)

## 1000th Fibonacci number

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

2686381002448535938614672720214292396761660931898695234012317599761798
1700247881689338369654483356564191827856161443356312976673642210350324
634850410377680367334151172899169723197082763985615764450078474174626


All in all, 209 characters long.