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)

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