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

Solution:

The first factor $f_1$ can be any divisor $d \gt 1,$ after which the rest is an ordered factorization of $n/d.$ So $D(n) = \sum_{d \mid n,\, d \gt 1} D(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.

2020 AMC 12B Problem 24

Answer: A

Difficulty rating: 2220

Solution:

Problem 24 in Other Years