Register to reply

Recursive function equals xmod3 for all x in N

by ama03630
Tags: gametheory, induction, recursion
Share this thread:
ama03630
#1
Nov8-09, 01:53 PM
P: 2
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?
Phys.Org News Partner Mathematics news on Phys.org
Researcher figures out how sharks manage to act like math geniuses
Math journal puts Rauzy fractcal image on the cover
Heat distributions help researchers to understand curved space
gunch
#2
Nov8-09, 04:29 PM
P: 54
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.
ama03630
#3
Nov8-09, 08:37 PM
P: 2
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?


Register to reply

Related Discussions
If integral equals zero, then function equals zero Calculus & Beyond Homework 17
Recursive function Calculus & Beyond Homework 1
Even summation with recursive function in c++ Programming & Computer Science 1
Simplifying a recursive function Calculus & Beyond Homework 10
Recursive Function Computing & Technology 4