2019 AIME I Problem 9

Attempt Problem 9 of the 2019 AIME I below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2019 AIME I solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

9.

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

Answer: 540
Concepts:factor countingperfect squarecasework
Difficulty rating: 2740
Solution:

The case n=1n = 1 gives τ(1)+τ(2)=3,\tau(1) + \tau(2) = 3, so any solution has n2n \ge 2 and both divisor counts are at least 2.2. Thus 7=2+5=3+4,7 = 2 + 5 = 3 + 4, so one of τ(n),τ(n+1)\tau(n), \tau(n+1) equals 33 or 5.5. Now τ=3\tau = 3 means a prime square p2,p^2, while τ=5\tau = 5 means a prime fourth power p4.p^4. So one of n,n+1n, n+1 lies in {4,9,25,49,121,\{4, 9, 25, 49, 121, 169,289,361,}169, 289, 361, \ldots\} {16,81,625,},\cup \{16, 81, 625, \ldots\}, and its neighbor must have τ=4\tau = 4 (for a square) or be prime (for a fourth power).

Checking neighbors in increasing order: n=8n = 8 works (τ(8)=4,(\tau(8) = 4, τ(9)=3);\tau(9) = 3); n=9n = 9 works (τ(10)=4);(\tau(10) = 4); n=16n = 16 works (τ(16)=5,(\tau(16) = 5, 1717 prime);); n=25n = 25 works (τ(26)=4).(\tau(26) = 4). Then 49,81,169,49, 81, 169, and 289289 all fail: τ(48)=10,\tau(48) = 10, τ(50)=6,\tau(50) = 6, τ(80)=10,\tau(80) = 10, 8282 is not prime, τ(168)=16,\tau(168) = 16, τ(170)=8,\tau(170) = 8, τ(288)=18,\tau(288) = 18, τ(290)=8.\tau(290) = 8. Next, n=121n = 121 works (τ(122)=4)(\tau(122) = 4) and n=361n = 361 works (τ(362)=4).(\tau(362) = 4).

The six least solutions are 8,9,16,25,121,361,8, 9, 16, 25, 121, 361, with sum 540.540.

← Problem 8#8
Full Exam

Problem 9 in Other Years