Skip to main content
OlympiadHQ

Browse · MATH

Print

jmc

algebra senior

Problem

Let

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.
Final answer
7