1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Recursive function equals xmod3 for all x in N

  1. Nov 8, 2009 #1
    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?
  2. jcsd
  3. Nov 8, 2009 #2
    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 [itex]f(y) \in \{0,1,2\}[/itex] in addition to [itex]f(y) \equiv y \pmod 3[/itex].
    The key observation is that among,
    no elements are congruent to [itex]x[/itex] modulo 3, but the first two represents the other two residue classes modulo 3. This means that if [itex]x=3k+a[/itex] where [itex]a\in\{0,1,2\}[/itex] and we assume that the hypothesis holds for all natural numbers less than x, then f(x-2^i) is never a, which means,
    [tex]a \in \mathbb{N} \setminus \bigcup_{i=0}^{\left\lfloor \log_2(x)\right\rfloor} \{f\left(x-2^i\right)\}[/tex]
    For x > 1 we have [itex]\{f(x-2^0),f(x-2^1),a\}=\{0,1,2\}[/itex] 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.
  4. Nov 8, 2009 #3
    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?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook