Browse · MATH
Printjmc
algebra senior
Problem
Let
For how many integers from 1 to 100, inclusive, does for some number of applications of ?
For how many integers from 1 to 100, inclusive, does for some number of applications of ?
Solution
First, we note that if is a positive integer, then is also a positive integer. We claim that for some number of applications of only for and (In other words, must be a power of 2.)
Note that so If is a power of 2, it is easy to see that repeated applications of on eventually reach 1.
Suppose is an odd positive integer, where Write where is a positive integer. Since is odd, Since is always even, is always odd (and greater than 1), so can never be a power of 2 when is odd and greater than 1.
Now, suppose is even. For example, if then which we know is not a power of 2.
More generally, suppose where is nonnegative and is odd. Then If then is a power of 2, and the sequence eventually reaches 1. Otherwise, is not a power of 2. We also know that is odd and greater than 1, is not a power of 2 either, and so on. Thus, the sequence can never reach 1.
Therefore, must be one of the values 1, 2, 4, 8, 16, 32, or 64.
Note that so If is a power of 2, it is easy to see that repeated applications of on eventually reach 1.
Suppose is an odd positive integer, where Write where is a positive integer. Since is odd, Since is always even, is always odd (and greater than 1), so can never be a power of 2 when is odd and greater than 1.
Now, suppose is even. For example, if then which we know is not a power of 2.
More generally, suppose where is nonnegative and is odd. Then If then is a power of 2, and the sequence eventually reaches 1. Otherwise, is not a power of 2. We also know that is odd and greater than 1, is not a power of 2 either, and so on. Thus, the sequence can never reach 1.
Therefore, must be one of the values 1, 2, 4, 8, 16, 32, or 64.
Final answer
7