2020 AMC 12B Problem 24

Question

Let

D(n)

denote the number of ways of writing the positive integer

n

as a product

n = f_1 \cdot f_2 \cdots f_k,

where

k \ge 1,

the

f_i

are integers strictly greater than

1,

and the order in which the factors are listed matters (that is, two representations that differ only in the order of the factors are counted as distinct). For example, the number

6

can be written as

6,

2 \cdot 3,

and

3 \cdot 2,

so

D(6) = 3.

What is

D(96)?

112

128

144

172

184

Answer: A

Concepts:recursive counting factor

Difficulty rating: 2220

Small hint:

Use the recursion

D(n) = \sum_{d \mid n,\, d \gt 1} D(\frac{n}{d}),

with

D(1) = 1

Big hint:

Since

96 = 2^5 \cdot 3,

build up

D

on the divisors

2,

3,

4,

6,

8,

12,

16,

24,

32,

48,

96

Solution:

The first factor

f_1

can be any divisor

d \gt 1,

after which the rest is an ordered factorization of

\frac{n}{d}.

So

D(n) = \sum_{d \mid n,\, d \gt 1} D(\frac{n}{d}),

with

D(1) = 1.

Computing over the divisors of

96 = 2^5\cdot 3:

D(2) = D(3) = 1,

D(4) = 2,

D(6) = 3,

D(8) = 4,

D(12) = 8,

D(16) = 8,

D(24) = 20,

D(32) = 16,

D(48) = 48.

Finally

\begin{gathered} D(96) = D(48) + D(32) \\ {}+ D(24) + D(16) + D(12) \\ {}+ D(8) + D(6) + D(4) \\ {}+ D(3) + D(2) + D(1) \\ = 48 + 16 + 20 + 8 \\ {}+ 8 + 4 + 3 + 2 \\ {}+ 1 + 1 + 1 = 112. \end{gathered}

Thus, the correct answer is A.