2016 AIME II Problems/Problem 11
For positive integers and
, define
to be
-nice if there exists a positive integer
such that
has exactly
positive divisors. Find the number of positive integers less than
that are neither
-nice nor
-nice.
Solution
We claim that an integer is only
-nice if and only if
. By the number of divisors formula, the number of divisors of
is
. Since all the
s are divisible by
in a perfect
power, the only if part of the claim follows. To show that all numbers
are
-nice, write
. Note that
has the desired number of factors and is a perfect kth power. By PIE, the number of positive integers less than
that are either
or
is
, so the desired answer is
.
Solution by Shaddoll