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,
    [tex]x-2^0,x-2^1,x-2^2,\ldots[/tex]
    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?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Recursive function equals xmod3 for all x in N
Loading...