35. Let N be the set of natural numbers and let f : N → N be defined by:
Let fn(x) denote the n-fold composition of f(x). What is the smallest integer n such that:
fn(13) = 1?
Understanding the Given Function Iteration Problem
This question is based on repeated composition, or iteration, of a piecewise-defined function. The function behaves differently depending on whether the input is even or odd. Whenever the current value is even, it is divided by 2. Whenever the current value is odd, it is multiplied by 3 and then increased by 1.
The function is:
f(x) = x/2 when x is even
and:
f(x) = 3x + 1 when x is odd
We begin with x = 13 and apply the function repeatedly. Each application of f counts as one composition. Our goal is to count the minimum number of applications required to reach the value 1.
The notation fn(13) does not mean [f(13)]n. Instead, it represents applying the same function n times in succession. Therefore, careful counting of every function application is essential.
Meaning of n-Fold Composition of a Function
The notation fn(x) represents the n-fold composition of f with itself. The first few iterations are:
f1(x) = f(x)
f2(x) = f(f(x))
f3(x) = f(f(f(x)))
and the process continues in the same manner.
Therefore, to calculate fn(13), we start with 13, apply f once, take the resulting value as the next input, and continue until the output becomes 1.
Step-by-Step Solution
Step 1: Calculate f(13)
The starting value is:
x = 13
Since 13 is odd, we must use the odd-number rule:
f(x) = 3x + 1
Therefore:
f(13) = 3(13) + 1
= 39 + 1
= 40
Hence:
f1(13) = 40
The value 1 has not yet been reached, so the function must be applied again.
Step 2: Calculate f²(13)
From the first iteration:
f1(13) = 40
Since 40 is even, we use:
f(x) = x/2
Therefore:
f(40) = 40/2 = 20
Thus:
f2(13) = 20
Step 3: Calculate f³(13)
The current value is 20, which is even. Therefore:
f(20) = 20/2
= 10
Hence:
f3(13) = 10
Step 4: Calculate f⁴(13)
The current value 10 is also even. Applying the even-number rule:
f(10) = 10/2
= 5
Therefore:
f4(13) = 5
Step 5: Calculate f⁵(13)
The current value is now 5. Since 5 is odd, the rule changes to:
f(x) = 3x + 1
Therefore:
f(5) = 3(5) + 1
= 15 + 1
= 16
Hence:
f5(13) = 16
Step 6: Calculate f⁶(13)
The value 16 is even. Therefore:
f(16) = 16/2
= 8
Thus:
f6(13) = 8
Step 7: Calculate f⁷(13)
The value 8 is even, so:
f(8) = 8/2
= 4
Therefore:
f7(13) = 4
Step 8: Calculate f⁸(13)
The current value 4 is even. Therefore:
f(4) = 4/2
= 2
Hence:
f8(13) = 2
Step 9: Calculate f⁹(13)
The current value is 2, which is even. Applying the function once more:
f(2) = 2/2
= 1
Therefore:
f9(13) = 1
This is the first time the sequence reaches 1. Hence, the smallest required integer is:
n = 9
Complete Function Iteration Sequence
The entire sequence generated by repeatedly applying the function is:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
It is important to distinguish between the number of values shown in the sequence and the number of function applications. The sequence contains ten values when the starting number 13 is included, but the function is applied only nine times.
The iterations are:
f1(13) = 40
f2(13) = 20
f3(13) = 10
f4(13) = 5
f5(13) = 16
f6(13) = 8
f7(13) = 4
f8(13) = 2
f9(13) = 1
Therefore, nine applications of the function are required.
Why the Starting Value 13 Is Not Counted as an Iteration
The starting value 13 is the input to the process. Before applying the function, we simply have:
f0(13) = 13
The first application of the function changes 13 into 40:
f1(13) = 40
Therefore, the number of arrows in the sequence represents the number of function applications:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
There are nine transitions from the starting value 13 to the final value 1. Hence:
n = 9
Understanding the Even and Odd Rules in the Sequence
The sequence begins with 13, which is odd. Therefore, the function produces:
3(13) + 1 = 40
The number 40 is even, so repeated division by 2 gives:
40 → 20 → 10 → 5
The value 5 is odd, so the odd-number rule is used again:
3(5) + 1 = 16
Since 16 is a power of 2, repeated application of the even-number rule gives:
16 → 8 → 4 → 2 → 1
Combining both parts produces the complete path:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
Alternative Solution by Grouping the Iterations
The calculation can also be organized into two stages. Starting from 13:
13 → 40 → 20 → 10 → 5
This requires four function applications.
From 5:
5 → 16 → 8 → 4 → 2 → 1
This requires five additional function applications.
Therefore, the total number of applications is:
4 + 5 = 9
Hence:
n = 9
Why n = 9 Is the Smallest Integer
To establish that 9 is the smallest possible integer, we must verify that the function does not reach 1 at any earlier iteration.
The values obtained before the ninth iteration are:
40, 20, 10, 5, 16, 8, 4, and 2
None of these values is equal to 1. The value 1 appears for the first time only after the ninth application:
f9(13) = 1
Therefore, no positive integer smaller than 9 satisfies the required condition.
Connection with the Collatz-Type Iteration
The given piecewise function follows the well-known pattern in which an even number is divided by 2 and an odd number is transformed into 3x + 1. In this question, however, we do not need to study the general long-term behavior of all natural numbers.
The task is limited to the specific starting value 13. Therefore, the correct approach is to apply the function repeatedly and count the exact number of compositions required to reach 1.
For the starting value 13, the sequence reaches 1 after exactly nine function applications.
Complete Solution in Compact Form
The function is:
f(x) = x/2, if x is even
and:
f(x) = 3x + 1, if x is odd.
Starting from 13:
f1(13) = 40
f2(13) = 20
f3(13) = 10
f4(13) = 5
f5(13) = 16
f6(13) = 8
f7(13) = 4
f8(13) = 2
f9(13) = 1
Therefore:
n = 9
Final Answer
Starting from 13 and repeatedly applying the given function produces the sequence 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1. The value 1 is reached for the first time after nine applications of the function.
Answer: 9
