2019 AIME I Problems/Problem 9

Problem 9

Let $\tau (n)$ denote the number of positive integer divisors of $n$ . Find the sum of the six least positive integers $n$ that are solutions to $\tau (n) + \tau (n+1) = 7$ .

Solution

Essentially, you realize that to get 7 you need an odd amount of divisors + and even amount of divisors. This means that one of our n needs to be a square. Furthermore it must either be a prime squared to get 3 divisors or a prime to the fourth to get 5 divisors. Any more factors in a square would be to large. Thus $n/n+1$ is in the form $p^2$ or $p^4$ . The rest of the solution is bashing left to the reader.

~~ paliwalar.21

Solution 2

In order to obtain a sum of 7, we must have:

either a number with 5 divisors (a fourth power of a prime) and a number with 2 divisors (a prime), or
a number with 4 divisors (a semiprime) and a number with 3 divisors (a square of a prime). (No integer greater than 1 can have fewer than 2 divisors.)

Since both of these cases contain a number with an odd number of divisors, that number must be an even power of a prime. These can come in the form of a square like $3^2$ with 3 divisors, or a fourth power like $2^4$ with 5 divisors. We then find the smallest such values by hand.

$2^2$ has two possibilities: 3 and 4, or 4 and 5. Neither works.
$3^2$ has two possibilities: 8 and 9, or 9 and 10. (8,9) and (9,10) both work.
$2^4$ has two possibilities: 15 and 16, or 16 and 17. Only (16,17) works.
$5^2$ has two possibilities: 24 and 25, or 25 and 26. Only (25,26) works.
$7^2$ has two possibilities: 48 and 49, or 49 and 50. Neither works.
$3^4$ has two possibilities: 80 and 81, or 81 and 82. Neither works.
$11^2$ has two possibilities: 120 and 121, or 121 and 122. Only (121,122) works.
$13^2$ has two possibilities: 168 and 169, or 169 and 170. Neither works.
$17^2$ has two possibilities: 288 and 289, or 289 and 290. Neither works.
$19^2$ has two possibilities: 360 and 361, or 361 and 362. Only (361,362) works.

Having computed the working possibilities, we take the sum of the corresponding values of $n$ : $8+9+16+25+121+361 = \boxed{540}$ . ~Kepy.

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

Page

Toolbox

Search

2019 AIME I Problems/Problem 9

Contents

Problem 9

Solution

Solution 2

See Also