Help me come up with a function

Question

I have some numbers and corresponding numbers:

0 = 0
1 = 0
2 = 1
3 = 0
4 = 2
5 = 1
6 = 3
7 = 0
8 = 4
9 = 2
10 = 5
11 = 1
12 = 6
13 = 3
14 = 7
15 = 0
16 = 8
17 = 4

etc.

Notice that all the even number's corresponding number is the even number divided by 2.

Notice that for all odd numbers, when divided by 2 and floored, you get the same value for both numbers.

Can you help me come up with a function for this relation?

Answer 1

Is it not the recursively defined map $f:\mathbb{N}\to\mathbb{N}$ given by $f(2n) = n$ (halfs the value for even input), and $f(2n+1) = f(n)$ (recursively defines $f$ on an odd number in terms of a value of $f$ at a smaller point)?

Actually I see that dtldarek already said this in a comment. This is OEIS: A025480. Guy (apparently this Guy) writes "These are the nim-values for heaps of $n$ beans in the game where you're allowed to take up to half of the beans in a heap" on that page.

Of course the same recursive definition can be written $$f(n) = \begin{cases} \frac n2 & \text{if $n$ is even} \\ f(\frac{n-1}{2}) & \text{if $n$ is odd} \\ \end{cases}$$ if you prefer. Other formulas are found on the OEIS entry I linked.

Answer 2

For $n\in\mathbb N$ let $$v_2(n):=\max\{\,k\in\mathbb N_0: 2^k|n\,\} $$ be the number of twos in the prime decomposition of $n$. Then $$ f(n) = \left\lfloor\frac n{2^{v_2(n+1)+1}}\right\rfloor.$$