## recursive function equals xmod3 for all x in N

I have a suspicion that if f(0)=0, and f(x)=min(N\Uf(x-2^i)) where i runs from 0 to i=floor(ln(x)/ln(2)), then f(x)=xmod3 for all natural numbers, x. Can anyone help me prove this inductively?
 I'm not bothering to show the base cases as they are easy. I'm leaving out some detail here and just giving a proof sketch, but the general approach is as follows: Strengthen the induction hypothesis slightly by claiming that $f(y) \in \{0,1,2\}$ in addition to $f(y) \equiv y \pmod 3$. The key observation is that among, $$x-2^0,x-2^1,x-2^2,\ldots$$ no elements are congruent to $x$ modulo 3, but the first two represents the other two residue classes modulo 3. This means that if $x=3k+a$ where $a\in\{0,1,2\}$ and we assume that the hypothesis holds for all natural numbers less than x, then f(x-2^i) is never a, which means, $$a \in \mathbb{N} \setminus \bigcup_{i=0}^{\left\lfloor \log_2(x)\right\rfloor} \{f\left(x-2^i\right)\}$$ For x > 1 we have $\{f(x-2^0),f(x-2^1),a\}=\{0,1,2\}$ by our previous comments. This shows a is actually the minimum when x >1. So if you prove the theorem for x=0 and x =1, then you can inductively show f(3k+a)=a.
 It took me a little while, but I understand this now. Thank you very much for your help. Now, I claim f(x)= min(N\Uf(x-p)) where p is 1 or a prime less than or equal to x. Then, f(x)=xmod4. Do you think I could use a similar style of an inductive proof to prove this?

 Tags gametheory, induction, recursion