# Task
 Dudka has `n` details. He must keep exactly 3 of them.

 To do this, he performs the following operations until he has only 3 details left:
```
He numbers them.
He keeps those with either odd or even numbers and throws the others away.```

 Dudka wants to know how many ways there are to get exactly 3 details. Your task is  to help him calculate it.

# Example

 For `n = 6`, the output should be `2`.
 ```
Dudka has 6 details, numbered 1 2 3 4 5 6. 
He can keep either details with numbers 1, 3, 5, 
or with numbers 2, 4, 6. 
Both options leave him with 3 details, 
so the answer is 2.```

 For `n = 7`, the output should be `1`.
 ```
Dudka has 7 details, numbered 1 2 3 4 5 6 7. 
He can keep either details 1 3 5 7, or details 2 4 6. 
If he keeps details 1 3 5 7 , 
he won't be able to get 3 details in the future, 
because at the next step he will number them 1 2 3 4 
and will have to keep either details 1 3, or 2 4, 
only two details anyway. 
That's why he must keep details 2 4 6 at the first step, 
so the answer is 1.```

# Input/Output


 - `[input]` integer `n`

  `3 ≤ n ≤ 10^9`


 - `[output]` an integer

  The number of ways to get exactly 3 details.

Difficulty: introductory

Starter code:

def three_details(n):
	

Solutions:
from functools import lru_cache

@lru_cache(maxsize=None)
def three_details(n):
    if n <= 3: return n==3
    q, r = divmod(n, 2)
    return three_details(q) + three_details(q+r)

from functools import lru_cache

@lru_cache(maxsize=None)
def three_details(n):
    if n in (3,5,7):
        return 1
    elif n < 6:
        return 0
    q, r = divmod(n, 2)
    if r:
        return three_details(q) + three_details(q+1)
    else:
        return three_details(q) * 2

from math import log2

def three_details(n):
    i = int(log2(n))
    return min(abs(n - 2**p) for p in (i, i + 1))

def three_details(n):
    u = 2 ** n.bit_length()
    return n - u // 2 if n <= 3 * u // 4 else u - n

from math import ceil
from functools import lru_cache
three_details = lru_cache(None)(lambda n:int(n==3) if n<=3 else three_details(ceil(n/2)) + three_details(n//2))

three_details=lambda n:(lambda l:min(n%2**l,-n%2**l))(int(__import__('math').log2(n)))

def three_details(n):
    if n==3: return 1
    if n<5: return 0
    if n%2==0:
        return 2*three_details(n//2)
    else:
        return three_details(n//2)+three_details(n//2+1)


def three_details(n):
    p=2**n.bit_length()
    return (p-abs(4*n-3*p))//4


ready = [0,0,0,1]

def f(x):
    if x<len(ready): return ready[x]
    else: return f(x//2) + f(x//2 + x%2)

for i in range(4,100001):
    ready.append(f(i))


def three_details(n):
    if n < 100000: return ready[n]
    else: return three_details(n//2) + three_details(n//2 +n%2)

from functools import lru_cache


@lru_cache()
def three_details(n, count=0):
    even, odd = n//2, n//2 + n%2
    if n == 3:
        return 1
    elif n < 3:
        return 0
    return three_details(n-even) + three_details(n-odd)