2016 AIME II Problems/Problem 11

For positive integers $N$ and $k$ , define $N$ to be $k$ -nice if there exists a positive integer $a$ such that $a^{k}$ has exactly $N$ positive divisors. Find the number of positive integers less than $1000$ that are neither $7$ -nice nor $8$ -nice.

Solution

We claim that an integer $N$ is only $k$ -nice if and only if $N \equiv 1 \pmod k$ . By the number of divisors formula, the number of divisors of $\prod_{i=1}^n p_i^{a_i}$ is $\prod_{i=1}^n (a_i+1)$ . Since all the $a_i$ s are divisible by $k$ in a perfect $k$ power, the only if part of the claim follows. To show that all numbers $N \equiv 1 \pmod k$ are $k$ -nice, write $N=bk+1$ . Note that $2^{kb}$ has the desired number of factors and is a perfect kth power. By PIE, the number of positive integers less than $1000$ that are either $1 \pmod 7$ or $1\pmod 8$ is $143+125-18=250$ , so the desired answer is $999-250=\boxed{749}$ .

Solution by Shaddoll

2016 AIME II (Problems • Answer Key • Resources)
Preceded by Problem 10	Followed by Problem 12
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search

2016 AIME II Problems/Problem 11

Solution

See also