Q.44 Let N be the set of natural numbers and f: N↦N be defined by
3x+1, if x odd }
Let fn(x) denote the n-fold composition of f(x). What is the smallest integer n such that fn(13) = 1?
The smallest integer n such that f^n(13)=1 is 9.
Problem statement
Let N be the set of natural numbers and define a function
f: N → N, f(x) = { x/2, x even; 3x+1, x odd }
Let f^n(x) denote the n-fold composition of f. The task is to find the least n for which f^n(13)=1.
Step-by-step solution
Starting with x_0 = 13 (odd):
- x_1 = f(13) = 3·13 + 1 = 40
- x_2 = f(40) = 40/2 = 20
- x_3 = f(20) = 20/2 = 10
- x_4 = f(10) = 10/2 = 5
- x_5 = f(5) = 3·5 + 1 = 16
- x_6 = f(16) = 16/2 = 8
- x_7 = f(8) = 8/2 = 4
- x_8 = f(4) = 4/2 = 2
- x_9 = f(2) = 2/2 = 1
Thus the sequence of iterates is 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.
Here, x_9 = 1 and none of x_1, …, x_8 equals 1, so the smallest n with f^n(13)=1 is n=9.
How to analyse options in an MCQ
If the question is multiple-choice with options like 5, 7, 9, 11 (typical pattern), check them systematically.
For any option n < 9, we only look up to x_8 = 2; the value 1 has not appeared, so those options are incorrect.
At n=9 the value becomes 1 for the first time, so the option 9 is correct.
Any option n > 9 is wrong because minimality is violated, even though f^n(13)=1 will also hold for all larger n obtained by continuing the iteration along the known Collatz orbit beyond 1 (for example, applying f to 1 gives 4, then 2, then 1 again).
This reasoning explains why exactly one option (the one equal to 9) must be chosen.
Introduction
The functional equation defined by f(x)=x/2 for even x and f(x)=3x+1 for odd x generates what is known as a Collatz sequence, a famous object of study in number theory. For exam aspirants, mastering questions that ask for the smallest integer n such that f^n(13)=1 builds confidence in handling iterative functions and composition-based problems.
