Interesting recursive functions -
@MRINMOY_HALDER To be frank, the question is related to that conjecture.
et R={i∣∃j:f(j)=i} be the set of distinct values that... can sum1 explain clearly ???wat is d meaning of dis
R={i∣∃j:f(j)=i} be the set of distinct values that f takes
Someone please explain why is it written "takes" ? R contains the values that f can "give" right?
@MINIPanda it is recursive function. f(x){ if (x==1) return x; //map to "x" else if (x==5) return y; map to "y" // base condition if (x mod 2 == 0) f(x/2) else f(x+5) } Function assign value to it when it terminates. As you can see base value can be either 1 or 5. R = {1,5} PS: Recursive fun calls doesn't provide mapping. A value is mapped when function terminates and return something.
R={i∣∃j:f(j)=i}
even this is ambiguous as everything boils down to f(1) and f(5) it should be mentioned that we can consider f(x)=x coz R contains all values such that there exist at least one value in Domain which should map to this x.
@Divy Kala I have written the code above for the same. Please check it and let me know if you still have doubt.
Answer is 2 Its Saying we have 2 domains N+ → N+
can anyone explain meaning of this plz??
@ Deepesh Kataria .where is f(9)
here the set definition means that
take suppose j=1 then f(1) =6 ,this 6 is i
f(2) = 1 ,this 1 is i
f(3) =8 ,this 8 is i
f(4) = 2 ,this 4 is i
.
this way we get so many values of i which form N+ set only {1 , 2 , 3 ,4 .....}
then why are you doing f(1) =f(6) =f(3) =f(8)...??
the set builder form is not asking this.
@akriti, see defination of function again, it's in recursive form f(n) = f(n/2) ( see the recursion) f(1) = f(6) so in order to cal. f(1) we need to agin cal f(6) now this will give f(3) now again we need to fine f(3) which will be f(8).now f(8)will give f(4) and then f(4) will give f(2) and then f(2) -> f(1) so in this way it repeats itself. see the function again, the catchy thing is the recursion part.
http://math.stackexchange.com/questions/2118739/finding-recursive-function-range/2118749
We will use strong Induction Hypothesis to proof this. Suppose that $f(1) = a$ and $f(5) = b$. It is clear that $$f(5n) = b$$ for all $n$. We'll prove by induction that for all $n \ne 5k$, $f(n) = a$. First note that $$f(2) = f(\frac{2}{2}) = f(1) = a,$$ $$f(3) = f(3+5) = f(8) = f(4) = f(2) = a,$$ $$f(4) = f(2) = a.$$ Now suppose $n = 5k + r$, where $0 \lt r \lt 5$, and for all $k\lt n$, $n$ is not divisible by $5$ bcoz $r \neq 0$ Note that if $n$ is not divisible by $5$ then $n-5$ is also not divisible by $5$. Because $n-5 = 5(k-1) + r$, again $r \neq 0$. And also Note that $\frac{n}{2}$ is not divisible by $5$, bcoz if it were divisible by $5$, this will make $n$ divisible by $5$. Base case: $f(1)=f(2)=f(3)=f(4)=a$ [already solved for base cases above] Incuctive step: Now suppose $n = 5k + r$, where $0 \lt r \lt 5$, and for all $m\lt n$ which are not divisible by $5$, $f(m) = a$. ($m$ already covers $n-5$ and $\frac{n}{2}$) If $n$ is odd, $f(n) = f(n-5)$, and by induction hypothesis, $f(n-5) = a$, so we get $$f(n) = a.$$ If $n$ is even, $f(n) = f(n/2)$, and by induction hypothesis, $f(n/2) = a$, so we get $$f(n) = a.$$
Best solution by using mathematical Induction.Thanks :-)
@Sourav Basu Yes.
$\because f(n)=f(n+5)$.
Putting $n=n-5$ [where $n>5$] will yield $f(n-5)=f(n-5+5)=f(n)$
$\text{let we have f(1) = x. Then, f(2) = f(2/2) = f(1) = x}$
$\text{f(3) = f(3+5) = f(8) = f(8/2) = f(4/2) = f(2/1) = f(1) = x }$ $\text{f(5) = f(5+5) = f(10/2) = f(5) = y. }$
$\text{All $N^+$ except multiples of 5 are mapped to x and multiples}$
$\text{of 5 are mapped to y so ,$\mathbf{Answer\space is\space 2}$}$
thanx @Prince Sindhiya ,the pictorial mapping clears everything.,
choose any number let n=17, then
f(17)=f(22)=f(11)=f(16)=f(8)=f(4)=f(2)=f(1)=f(6)=f(3)=f(8)=f(4)=f(2)=f(1)=f(6)=f(3)=f(8)=f(4)=f(2)=f(1)... <this is one part>
now let n=50
f(50)=f(25)=f(30)=f(15)=f(20)=f(10)=f(5)=f(10)=f(15)=f(20)=f(10)=f(5)=f(10)=f(5)=f(10)=f(5) .....<this is other part>
so we can take any number and that will fall either of any cycle, these are the two types of values that Function f( ) can take.
Let's start with the smallest number. (You can begin at any number)
$f(1) = f(6) = f(3) = f(8) = f(4) = f(2) = \color{red}{f(1)}... $
$f(2)=\color{red}{f(1)}$
$f(3)=\color{red}{f(1)}$
$f(4)=\color{red}{f(1)}$
$f(5) = f(10) = \color{blue}{f(5)}... $
$f(6)=\color{red}{f(1)}$
$f(7) = f(12) = f(6) =\color{red}{f(1)}$
$f(8)=\color{red}{f(1)}$
$f(9) = f(14) = f(7)=\color{red}{f(1)}$
$f(10)=\color{blue}{f(5)}$
$f(11) = f(16) = f(8)=\color{red}{f(1)}$
... so on.
We observe that all the multiples of 5 will have the value of $f(5)$ and every other number will converge to $f(1)$ ultimately.
Let's assume $f(1) = i_1$ and $f(5) = i_2$
$R=\{i∣∃j:f(j)=i\} $
Hence, there are 2 such $i$'s.
