Interesting recursive functions -

The Gateway to Computer Science Excellence

+61 votes

A function $f: \Bbb{N^+} \rightarrow \Bbb{N^+}$ , defined on the set of positive integers $\Bbb{N^+}$,satisfies the following properties:

$f(n)=f(n/2)$ if $n$ is even

$f(n)=f(n+5)$ if $n$ is odd

Let $R=\{ i \mid \exists{j} : f(j)=i \}$ be the set of distinct values that $f$ takes. The maximum possible size of $R$ is ___________.

$f(n)=f(n/2)$ if $n$ is even

$f(n)=f(n+5)$ if $n$ is odd

Let $R=\{ i \mid \exists{j} : f(j)=i \}$ be the set of distinct values that $f$ takes. The maximum possible size of $R$ is ___________.

+139 votes

Best answer

0

et *R*={*i*∣∃*j*:*f*(*j*)=*i*} be the set of distinct values that...

can sum1 explain clearly ???wat is d meaning of dis

+5

R={i∣∃j:f(j)=i} be the set of distinct values thatftakes

Someone please explain why is it written "takes" ? R contains the values that f can "give" right?

0

@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.

+1

@Divy Kala I have written the code above for the same. Please check it and let me know if you still have doubt.

+36 votes

Answer is 2

Its Saying we have 2 domains

N^{+} → N^{+}

- So F(1) = F(6) = F(3) = F(8) = F(4) = F(2) = F(1)....It Repeats... Now F(7) = F(12) = F(6)...Again repeats both above are same...Since F(6) matches in both so same both belongs to same value.We are not getting F(5) above
- Now F(5) = F(10) = F(5)..Repeats ...We can see we have different value for multiples of 5 and other natural numbers.

+6

can you please explain what is the meaning of this statement

$R = \{i | \exists j : f(j) = i \}$

f(5) and f(10) is multiple of 5, that is true. But how they are equal, as we can see f(5) = 10 and f(10) = 5.

Also the problem doesn't want to know about the multiple of x, isn't it??

Problem is very much unclear to me..? If you explain a bit more it will be helpful.

$R = \{i | \exists j : f(j) = i \}$

f(5) and f(10) is multiple of 5, that is true. But how they are equal, as we can see f(5) = 10 and f(10) = 5.

Also the problem doesn't want to know about the multiple of x, isn't it??

Problem is very much unclear to me..? If you explain a bit more it will be helpful.

+16 votes

0

can you please explain what is the meaning of this statement

$R = \{i | \exists j : f(j) = i \}$

f(5) and f(10) is multiple of 5, that is true. But how they are equal, as we can see f(5) = 10 and f(10) = 5.

Also the problem doesn't want to know about the multiple of x, isn't it??

Problem is very much unclear to me, that is why I am unable to understand the answer ? If you explain a bit more it will be helpful.

$R = \{i | \exists j : f(j) = i \}$

f(5) and f(10) is multiple of 5, that is true. But how they are equal, as we can see f(5) = 10 and f(10) = 5.

Also the problem doesn't want to know about the multiple of x, isn't it??

Problem is very much unclear to me, that is why I am unable to understand the answer ? If you explain a bit more it will be helpful.

+15

i.e., set notation. Here we are defining a set R and we include all i in R such that there exists j such that f(j) = i. Here, j is from natural number set. f(5) = f(10) = f(15) = f(20) = ... = say x. Also, f(2) = f(3) = f(4) = f(6) = ... say y. So, to maximize the number of elements in R, we can take $x \neq y$ making 2 possible elements in R.

0

@arjun sir,f(5) = 10

then why r u again finding f(10) and then again finding function of f(10)

what you are doing is f(f(f(......f(5)))) =5

whya re you doing this??

the set definition does not ask for this..

pls explain

then why r u again finding f(10) and then again finding function of f(10)

what you are doing is f(f(f(......f(5)))) =5

whya re you doing this??

the set definition does not ask for this..

pls explain

0

R={i∣∃j:f(j)=i}

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.

+6

@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.

+8 votes

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.$$

0

@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)$

+8 votes

$\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}$}$

+4 votes

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.

+1 vote

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.

52,345 questions

60,503 answers

201,899 comments

95,335 users