Recursive function equals xmod3 for all x in N

[ama03630]

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?

 

[gunch]

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.

 

[ama03630]

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?