This Kata is a continuation of [Part 1](http://www.codewars.com/kata/the-fusc-function-part-1). The `fusc` function is defined recursively as follows:

    fusc(0) = 0
    fusc(1) = 1
    fusc(2n) = fusc(n)
    fusc(2n + 1) = fusc(n) + fusc(n + 1)
    
Your job is to produce the code for the `fusc` function. In this kata, your function will be tested with large values of `n` more than 1000 bits (in JS and PHP: at most 52 bits), so you should be concerned about stack overflow and timeouts.

Method suggestion:

Imagine that instead of `fusc(n)`, you were to implement `fib(n)`, which returns the n'th Fibonacci number.

The function is recursively defined by:

```
1.    fib(0) = 1
2.    fib(1) = 1
3.    fib(n + 2) = fib(n) + fib(n + 1), if n + 2 > 1
```
If one translates the above definition directly into a recursive function, the result is not very efficient. One can try memoization, but that requires lots of space and is not necessary. So, first step is to try and find a _tail recursive_ definition. In order to do that we try to write both sides of equation 3) on the same form. Currently, the left side of the equation contains a single term, whereas the right side is the sum of two terms. A first attempt is to add `fib(n + 1)` to both sides of the equation:
```
3.    fib(n + 1) + fib(n + 2) = fib(n) + 2 * fib(n + 1)
```
The two sides of the equation look much more alike, but there is still an essential difference, which is the coefficient of the second term of each side. On the left side of the equation, it is `1`  and, on the right, it is `2`. To remedy this, we can introduce a variable `b`:
```
3.    fib(n + 1) + b * fib(n + 2) = b * fib(n) + (b + 1) * fib(n + 1)
```
We notice that the coefficients of the first term are not the same (`1` on the left and `b` on the right), so we introduce a variable `a`:
```
3.    a * fib(n + 1) + b * fib(n + 2) = b * fib(n) + (a + b) * fib(n + 1)
```
Now the two sides have the same form (call it `F`), which we can define as: 

```F(a, b, n) = a * fib(n) + b * fib(n + 1)```

In fact, we can write equation 3) as:
```
3.    F(a, b, n + 1) = F(b, a + b, n)
```
We also have, by definition of `F` and `fib`:
```
4.    F(a, b, 0) = a * fib(0) + b * fib(1) = a + b
```
Also, by definition of `F`: 
```
5.    fib(n) = F(1, 0, n)
```

The next step is to translate the above into code:
```
def fib(n):

    def F(a, b, n):
        if n == 0: return a + b    # see 4. above
        return F(b, a + b, n - 1)  # see 3. above

    return F(1, 0, n)              # see 5. above
```

The final step (optional for languages that support tail call optimization) is to replace the tail recursive function `F` with a loop:
```
def fib(n):
    a, b = 1, 0                    # see 5. above
    while n > 0:
        a, b, n = b, a + b, n - 1  # see 3. above
    return a + b .                 # see 4. above
```
Voila! Now, go do the same with `fusc`.

Source: codewars | Difficulty: MEDIUM_HARD
Tags: Complete search

Starter code: def fusc(n):
	

Solutions:
def fusc(n):
	(a, b) = (1, 0)
	for i in bin(n)[2:]:
		if i == '1':
			b += a
		else:
			a += b
	return b


def fusc(n):
	(a, b) = (0, 1)
	while n > 0:
		if n & 1:
			a += b
		else:
			b += a
		n >>= 1
	return a


def fusc(n):
	(x, y) = (1, 0)
	for i in bin(n)[2:]:
		if i == '1':
			y += x
		else:
			x += y
	return y


def fusc(n):
	s = [1, 0]
	for i in map(int, bin(n)[2:]):
		s[i] += s[1 - i]
	return s[1]


def fusc(n):
	(a, b) = (1, 0)
	while n > 0:
		(a, b, n) = (a + b * (1 - n & 1), a * (n & 1) + b, n >> 1)
	return b


def fusc(n):
	r = 0
	s = 1
	while n > 0:
		if n & 1 == 0:
			n >>= 1
			s += r
			continue
		n = n - 1 >> 1
		r += s
	return r


def fusc(n):
	if n == 0:
		return 0
	(a, b) = (0, 1)
	for i in map(int, reversed(f'{n - 1:b}')):
		if i:
			b += a
		else:
			a += b
	return b