Skip to main content

2020 AMC 12B Problem 24

Problem 24 of 25HarderNumber TheoryCounting & Probability

Let D(n)D(n) denote the number of ways of writing the positive integer nn as a product n=f1f2fk,n = f_1 \cdot f_2 \cdots f_k, where k1,k \ge 1, the fif_i are integers strictly greater than 1,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 66 can be written as 6,6, 23,2 \cdot 3, and 32,3 \cdot 2, so D(6)=3.D(6) = 3. What is D(96)?D(96)?

Answer choices

Show solution

Solution

The first factor f1f_1 can be any divisor d>1,d \gt 1, after which the rest is an ordered factorization of nd.\frac{n}{d}. So D(n)=dn,d>1D(nd),D(n) = \sum_{d \mid n,\, d \gt 1} D(\frac{n}{d}), with D(1)=1.D(1) = 1. Computing over the divisors of 96=253:96 = 2^5\cdot 3: D(2)=D(3)=1,D(2) = D(3) = 1, D(4)=2,D(4) = 2, D(6)=3,D(6) = 3, D(8)=4,D(8) = 4, D(12)=8,D(12) = 8, D(16)=8,D(16) = 8, D(24)=20,D(24) = 20, D(32)=16,D(32) = 16, D(48)=48.D(48) = 48. Finally 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. \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.

More practice

Concepts: recursive counting · factor

Problem text and solution from the LIVE past-contest archive. See also the AoPS wiki page for community solutions.