GATE IT 2007 | Question: 27

Question

The function f is defined as follows:

int f (int n) {
    if (n <= 1) return 1;
    else if (n % 2  ==  0) return f(n/2);
    else return f(3n - 1);
}

Assuming that arbitrarily large integers can be passed as a parameter to the function, consider the following statements.

1. The function $f$ terminates for finitely many different values of $n \geq 1$.
2. The function $f$ terminates for infinitely many different values of $n \geq 1$.
3. The function $f$ does not terminate for finitely many different values of $n \geq 1$.
4. The function $f$ does not terminate for infinitely many different values of $n \geq 1$.

Which one of the following options is true of the above?

• A. i and iii
• B. i and iv
• C. ii and iii
• D. ii and iv

Comments

actually collatz conjecture is 3n+1 for odd numbers, in that case the function will terminate for all n>=1

---

for 3n-1 it will never reach to 1,checkout the video:- https://www.youtube.com/watch?v=O2_h3z1YgEU

---

https://www.youtube.com/watch?v=nKoqc753Sd8

Answer 1

The function terminates for all powers of $2$ (which is infinite), hence (i) is false and (ii) is TRUE.

Let $n = 5. $
Now, recursive calls will go like $5 - 14 - 7 - 20 - 10 - 5 -$

And this goes into infinite recursion. And if we multiply $5$ with any power of $2$, also result will be infinite recursion. Since, there are infinite powers of $2$ possible, there are infinite recursions possible (even considering this case only). So, (iv) is TRUE and (iii) is false.

So, correct answer is (D).

Comments

Question is not saying that length of integer is  infinite.It is saying number of integers are infinite.

---

Recursion looks like as infinite recursion so simply option (ii) and (iv) Option D

For self checking take function value f(5).

---

@rahul sharma 5 if the int is of size 16 bits then numbers possible in signed integer range is -32768 to 32767….which is in finite range. But no where  told that it is C program.

Answer 2

The function is terminated for any value of n which is in power of 2. There are infinite nos, which are power of 2. Therefore (ii) is correct.

Now, take n= 10 , the function call will go in loop for value of n = 5, 14,7,20,10,5,14.......so on.

The above pattern will repeat for numbers 10, 20,40,80,160,320,640.... Infinity.

Therefore (iv) is also true.

Hence, answer is D

Answer 3

Recursion looks like as infinite recursion so simply option (ii) and (iv) Option D

For self checking take function value f(5).

Answer 4

For power of 2 option (ii) is true and for other No's option (iv) is correct so answer is D