180 Follower Problem

Relevant wiki: Number of Factors

Using the divisor count formula, the number $n = p_1^{e_1} p_2^{e_2} p_3^{e_3} \ldots$ has $(1+e_1) (1+e_2) (1+e_3) \ldots$ divisors. (Note that $e_1, e_2, e_3, \ldots$ may be zero, in which case the corresponding $1+e_1, 1+e_2, 1+e_3, \ldots$ are 1 and thus don't contribute anything to the product.) In order to have 180 divisors, we need $1+e_1, 1+e_2, 1+e_3, \ldots$ to multiply to 180. If I'm not mistaken, there are 26 such ways, ignoring order and ignoring 1s:

• $180$
• $90 \cdot 2$
• $60 \cdot 3$
• $45 \cdot 4$
• $45 \cdot 2 \cdot 2$
• $36 \cdot 5$
• $30 \cdot 6$
• $30 \cdot 3 \cdot 2$
• $20 \cdot 9$
• $20 \cdot 3 \cdot 3$
• $18 \cdot 10$
• $18 \cdot 5 \cdot 2$
• $15 \cdot 12$
• $15 \cdot 6 \cdot 2$
• $15 \cdot 4 \cdot 3$
• $15 \cdot 3 \cdot 2 \cdot 2$
• $12 \cdot 5 \cdot 3$
• $10 \cdot 9 \cdot 2$
• $10 \cdot 6 \cdot 3$
• $10 \cdot 3 \cdot 3 \cdot 2$
• $9 \cdot 5 \cdot 4$
• $9 \cdot 5 \cdot 2 \cdot 2$
• $6 \cdot 6 \cdot 5$
• $6 \cdot 5 \cdot 3 \cdot 2$
• $5 \cdot 4 \cdot 3 \cdot 3$
• $5 \cdot 3 \cdot 3 \cdot 2 \cdot 2$

(The only way I can think of to find these is by careful case-by-case analysis.)

Now, given a product $180 = (1+e_1) (1+e_2) (1+e_3) \ldots$ where $e_1 \ge e_2 \ge e_3 \ge \ldots$ , we'd like to find $p_1, p_2, p_3, \ldots$ that makes the resulting number the smallest. It's clearly better to keep $p_1 < p_2 < p_3 < \ldots$ . One simple way to realize this is that if for some $i,j$ where $i < j$ , we have $p_i > p_j$ , then swapping them will multiply the number by $p_i^{e_j-e_i} p_j^{e_i-e_j} = \left( \frac{p_j}{p_i} \right)^{e_i-e_j}$ . Because $e_i \ge e_j$ , the exponent is nonnegative. Because $p_i > p_j$ , the base is less than 1 (and positive). Thus this multiplier is not greater than 1, and so the original unswapped number cannot be the minimum; at best, it's tied for the minimum, and at worst, swapping will give a smaller result. So we can assume $p_i < p_j$ for all $i,j$ where $i < j$ . In other words, $p_1, p_2, p_3, \ldots$ are the prime numbers in that order; $p_1 = 2, p_2 = 3, p_3 = 5, \ldots$ .

Now, we can compute the minimum number given by each product. For example, take the product $10 \cdot 3 \cdot 3 \cdot 2$ . Then $1+e_1 = 10, 1+e_2 = 3, 1+e_3 = 3, 1+e_4 = 2$ , or in other words, $e_1 = 9, e_2 = 2, e_3 = 2, e_4 = 1$ . Thus the number given by this product is $2^9 \cdot 3^2 \cdot 5^2 \cdot 7^1 = 806400$ .

By computing each of the 26 possible smallest numbers, we obtain 26 candidates; simply pick the smallest. In this case, it happens with the last product: $2^4 \cdot 3^2 \cdot 5^2 \cdot 7^1 \cdot 11^1 = \boxed{277200}$ .

---

Note that we do need figuring out at least some of the products; we can't take shortcuts. For example, saying "assign the largest prime factor to the smallest base, then the next largest prime factor to the next smallest base, and so on" doesn't work, because with a product of 8, it would give $2^1 \cdot 3^1 \cdot 5^1 = 30$ and not $2^3 \cdot 3^1 = 24$ . Even if we modify "smallest base" to "smallest base raised to its current exponent" (so that in the above case, the last 2 will get assigned to $2^2 = 4$ instead of $5^1 = 5$ ), we will still stumble for a product of 24, where $2^2 \cdot 3^1 \cdot 5^1 \cdot 7^1 = 420$ is not the optimal solution; $2^3 \cdot 3^2 \cdot 5^1 = 360$ is. That requires us to put the factor 3 to base 3 and not base 2.