recursive function equals xmod3 for all x in N

**ama03630** · Nov8-09, 02:53 PM

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** · Nov8-09, 05:29 PM

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 $LaTeX Code: f(y) \\in \\{0,1,2\\}$ in addition to $LaTeX Code: f(y) \\equiv y \\pmod 3$ .
The key observation is that among,
$LaTeX Code: x-2^0,x-2^1,x-2^2,\\ldots$
no elements are congruent to

modulo 3, but the first two represents the other two residue classes modulo 3. This means that if

where $LaTeX Code: 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,
$LaTeX Code: 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 $LaTeX Code: \\{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** · Nov8-09, 09:37 PM

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?