2012 AMC 12B Problems/Problem 24
Problem
Define the function on the positive integers by setting and if is the prime factorization of , then For every , let . For how many s in the range is the sequence unbounded?
Note: A sequence of positive numbers is unbounded if for every integer , there is a member of the sequence greater than .
Solution 1
First of all, notice that for any odd prime , the largest prime that divides is no larger than , therefore eventually the factorization of does not contain any prime larger than . Also, note that , when it stays the same but when it grows indefinitely. Therefore any number that is divisible by or any number such that is divisible by makes the sequence unbounded. There are multiples of within . also works: .
Now let's look at the other cases. Any first power of prime in a prime factorization will not contribute the unboundedness because . At least a square of prime is to contribute. So we test primes that are less than :
works, therefore any number that are divisible by works: there are of them.
could also work if satisfies , but .
does not work.
works. There are no other multiples of within .
could also work if , but already.
For number that are only divisible by , they don't work because none of these primes are such that could be a multiple of nor a multiple of .
In conclusion, there are number of 's ... .
Solution 2
Say a number is if the sequence is bounded; otherwise is .
It is clear that is interesting iff is. For a prime, , . Thus, for a prime, , in the prime factorization of ; if then , so is interesting iff is. Continuing in this manner, we can divide by all such primes for which ; and is interesting iff each of these resulting numbers are. Finally we will end up with a number whose prime factorization contains only exponents . Let be the set of such numbers. It suffices to find all interesting numbers in ; all other interesting numbers will be multiples of these. Note that for all ; so by induction a multiple of an interesting number is also interesting.
The set contains either powers of primes , or a product of two such powers.
We have ; since iff , so and its multiples are interesting; there are such.
We have ; since iff , so and its multiples are interesting; there are such.
Among the remaining prime powers only but it has no other multiples in .
We are now left with numbers that are products of two prime powers, i.e , .
We have , so a number of this form is interesting iff or ; they are already counted above.
If then or or (all boring) or , , but has no other multiples.
If then is or and both are boring.
No larger prime can divide because even .
We have found all the interesting numbers: multiples of , multiples of , , and for a total of ... .
Video Solution by Richard Rusczyk
https://artofproblemsolving.com/videos/amc/2012amc12b/276
~dolphin7
See Also
2012 AMC 12B (Problems • Answer Key • Resources) | |
Preceded by Problem 23 |
Followed by Problem 25 |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | |
All AMC 12 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.