2012 AMC 12B Problems/Problem 24
Contents
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
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
.
Notice that for all
; an inductive argument leads to the conclusion that multiples of an interesting number are interesting.
We have ; since
iff
, we have
is the least power of
that is interesting. There are
multiples of
that are
.
We have ; since
iff
, we have
is the least power of
that is interesting. There are
multiples of
that are
.
We have , so a number of this form is interesting iff
or
; they are already counted above.
Integer is interesting (resp. boring) iff
is.
A square-free integer is boring, since
.
Let be the subset of
consisting of integers whose prime factorization only contains exponents 2 or higher. It suffices to check
: all interesting numbers in
are multiples of interesting numbers in
.
Let's first look at all the prime powers (these have no other multiples in
). They are:
,
,
, and
. Only
is interesting but it has no other multiples (even in
).
We are left with such that either
or
.
If then
is
or
and both are boring. If
then
(boring) or
(also boring) or
, which is interesting, but, of course, has no other multiples.
We have 12 multiples of , 4 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.