Analysis of an obfuscated fibonacci function

De-uglify

def f(n):
    a = 4 << n*(3+n)
    b = (4 << 2*n) - (2 << n) - 1
    c = ~-(2 << n)
    return (a // b) & c

~-(2 << n) = 2**(n+1) - 1, so the & c is doing mod 2**(n+1).

Rewrite the shifts with exponents

def f(n):
    a = 4 * 2**(n*(3+n))
    b = 4 * 2**(2*n) - 2**(n+1) - 1
    return (a // b) % 2**(n+1)

Think a while and realize that b = 2**(2n+2)) - 2**(n+1) - 1 is p**2 - p - 1 if
you set p = 2**(n+1), which sets off the Fibonacci-identity detector :) Rewrite

def f(n):
    p = 2**(n+1)
    a = p**(n+2)
    b = p**2 - p - 1
    return (a // b) % p

Look on wikipedia and see s(1/X) = X/(X**2 - X - 1) is the generating function
for Fib, so a/b is p**(n+1) s(1/p), so f(n) is doing

    floor( p**(n+1) (\sum_k Fib(k)/p^k) ) % p

Divide the sum into three parts: k < n+1, k = n+1, k > n+1

    \sum_{k<n+1} Fib(k) p**(n+1-k) +
    Fib(n+1) +
    \sum_{k>n+1} Fib(k) p**(n+1-k)

So probably the mod is killing the first sum, which is big, and the floor is
killing the last sum, which is small, leaving just Fib(n+1).

All the terms in the first sum are divisible by p, so the mod does kill it.

Since Fib(k) < 2**k, the middle term Fib(k+1) < p, so it is unchanged by the
mod.

But showing that the last sum is < 1 is huge pain >:( Both the easy bounds
Fib(k) < 2**k and Fib(k) < 2**(k-1) + 1/2 are too coarse! Using Fib(k) < (phi**k
+ 1)/2 will, after an annoying calculation and special casing the first three or
so values of n, in the end give a good enough bound though, so the floor wipes
out that sum leaving finally just

    f(n) = Fib(n+1)