Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
63 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 ___________.
in Set Theory & Algebra 7.8k views

Interesting recursive functions - 



@MRINMOY_HALDER To be frank, the question is related to that conjecture.

7 Answers

142 votes
Best answer
Let us assume: $f(1) = x.$

Then, $f(2) = f(2/2) = f(1) = x$
$ f(3) = f(3+5) = f(8) = f(8/2) = f(4/2) = f(2/1) = f(1) = x.$

Similarly, $f(4) = x$
$f(5) = f(5+5) = f(10/2) = f(5) = y.$

So, it will have two values. All multiples of $5$ will have value $y$ and others will have value $x.$

selected by
serioulsy this was best explnation :)
best answer...
why only y values are counted...y not x values ???

et R={i∣∃j:f(j)=i} be the set of distinct values that...
can sum1 explain clearly ???wat is d meaning of dis

bookish explanations eveywhere on this page...
Nice Explanation Boss..
Kya baat hai, amazing bro!

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.


if (x==1)

   return x;   //map to "x"

else if (x==5)

 return y; map to "y"   // base condition

if (x mod 2 == 0)





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.


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. 

@sunita24 Actually, answers written from book are copied from here!
We just checked first few cases.. how to prove there are only 2 equivalence classes?

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

  1. 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
  2. Now F(5) = F(10) = F(5)..Repeats ...We can see we have different value for multiples of 5 and other natural numbers.

edited by

can anyone explain meaning of this plz??

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.
its f(n)=f(n/2) , and not f(n)=n/2, and similarly for the other one, read carefully
doubt 1> if i = 1,2,3,4,6,7,8,12 have calling each other then why size of R is not 9 as i can have values 1,2,3,4,6,7,8,12  and 5 too.

doubt 2> what is about 9. 9 is not comming in 1,2,3,4,6,7,8,12.

please clear these doubts
Thank you for so nice explanation.

Deepesh Kataria .where is f(9)

f(9) = f(9+5)= f(14)= f(14/2)= f(7)

now f(7) = f(7+5)= f(12)=f(12/2)= f(6)=f(3)=f(8) etc.
16 votes
Answer 2..

for multiples of 5.. f(5)=f(10)...
and one for rest of the numbers in N.
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.
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.
please explain in detail


@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


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.

ooh..i missed the recursion part..thanks @mohit..:-)
8 votes

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

edited by
How to think like this in exam??
Take i= 1,2,3,,...10 and solve it. then you will see a pattern in it then generalize it.

Best solution by using mathematical Induction.Thanks :-)

Hi Sachin,

How "If n is odd, f(n)=f(n−5)" this is true?

@Sourav Basu

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



edited by

thanx @Prince Sindhiya  ,the pictorial mapping clears everything., 

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(5) = f(10) = \color{blue}{f(5)}... $


$f(7) = f(12) = f(6) =\color{red}{f(1)}$


$f(9) = f(14) = f(7)=\color{red}{f(1)}$


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


Related questions

41 votes
8 answers
Consider the weighted undirected graph with $4$ vertices, where the weight of edge $\{i,j\}$ is given by the entry $W_{ij}$ in the matrix $W$. W=$\begin{bmatrix} 0&2 &8 &5 \\ 2&0 &5 &8 \\ 8&5 &0 &x \\ 5& 8 &x &0 \end{bmatrix}$ The largest possible integer value of $x$, for which at least one shortest path between some pair of vertices will contain the edge with weight $x$ is ___________.
asked Feb 12, 2016 in DS Sandeep Singh 9.7k views
56 votes
15 answers
Let $G$ be a complete undirected graph on $4$ vertices, having $6$ edges with weights being $1, 2, 3, 4, 5,$ and $6$. The maximum possible weight that a minimum weight spanning tree of $G$ can have is __________
asked Feb 12, 2016 in Algorithms Sandeep Singh 13.9k views
69 votes
16 answers
For a host machine that uses the token bucket algorithm for congestion control, the token bucket has a capacity of $1$ $\text{megabyte}$ and the maximum output rate is $20$ $\text{megabytes}$ per $\text{second}$. Tokens arrive at a rate to sustain output at a ... machine needs to send $12$ $\text{megabytes}$ of data. The minimum time required to transmit the data is _____________ $\text{seconds}$.
asked Feb 12, 2016 in Computer Networks Sandeep Singh 15.7k views
36 votes
7 answers
Cylinder a disk queue with requests for $I/O$ to blocks on cylinders $47, 38, 121, 191, 87, 11, 92, 10.$ The C-LOOK scheduling algorithm is used. The head is initially at cylinder number $63$, moving towards larger cylinder numbers on its ... The cylinders are numbered from $0$ to $199$. The total head movement (in number of cylinders) incurred while servicing these requests is__________.
asked Feb 12, 2016 in Operating System Sandeep Singh 9.6k views