2021 AMC 12A Problem 25

Let

d(n)

denote the number of positive integers that divide

n,

including

1

and

n.

For example,

d(1) = 1,

d(2) = 2,

and

d(12) = 6.

(This function is known as the divisor function.) Let

f(n) = \frac{d(n)}{\sqrt[3]{n}}.

There is a unique positive integer

N

such that

f(N) \gt f(n)

for all positive integers

n \ne N.

What is the sum of the digits of

N?

Show solution

Solution

Since

f(n) = \dfrac{d(n)}{n^{\frac{1}{3}}}

is multiplicative, its value factors over prime powers as a product of terms

\dfrac{e + 1}{p^{\frac{e}{3}}}

for each prime power

p^e\ \|\ n.

We maximize each term separately. If

g_p(e)=\dfrac{e+1}{p^{\frac{e}{3}}},

then

\dfrac{g_p(e+1)}{g_p(e)}=\dfrac{e+2}{e+1}p^{-\frac{1}{3}}.

This ratio decreases with

e,

so checking where it first falls below

1

finds the unique maximum. It gives

e=3

for

p=2,

e=2

for

p=3,

e=1

for

p=5,7,

and

e=0

for every prime

p\ge11.

Hence

N = 2^3\cdot 3^2\cdot 5\cdot 7 = 2520,

whose digit sum is

2 + 5 + 2 + 0 = 9.

Thus, the correct answer is E.

Tagged: factor counting · prime factorization · optimization