In order to tackle this problem I first observed that
$$\phi(p_1^{e_1} \space p_2^{e_2} \cdots \space p_k^{e_k}) = (e_1 + 1)(e_2 + 1)\cdots(e_k +1)$$
Where $\phi(m)$ is the number of (not necessarily prime) divisors of $m$. If $m$ is the smallest integer such that $\phi(m) = n$, then
$$\phi(m) = n$$ $$(e_1 + 1)(e_2 + 1)\cdots(e_k +1) = n$$
Now we must choose $e_i$ such that $\prod_{i} p_i^{e_i}$ is minimal. The choices for $p$ are trivial - they are just the primes in ascending order.
However, my first thought for choosing $e_i$ was incorrect. I thought you could simply factor $n$, sort the factors in descending order and subtract 1. Most of the time this works fine, e.g. the smallest integer with $n = 15$ divisors is:
$$15 = 5 \cdot 3$$ $$15 = (4 + 1)(2 + 1)$$ $$m = 2^4 3^2 = 144$$
But this is incorrect for $n = 16$:
$$16 = 2 \cdot 2\cdot 2 \cdot 2$$ $$16 = (1 + 1)(1 + 1)(1 + 1)(1 + 1)$$ $$m = 2^1 3^1 5^1 7^1 = 210$$
Whereas the correct answer is:
$$16 = (3 + 1)(1 + 1)(1 + 1)$$ $$m = 2^3 3^1 5^1 = 120$$
So it's clear sometimes we need to merge factors. In this case because $7^1 > 2^2$. But I don't exactly see a clean and direct merging strategy. For example, one might think we must always merge into the $2$ power, but this is not true:
$$1552 = (96 + 1)(1 + 1)(1 + 1)(1 + 1)(1 + 1)$$ $$m = 2^{96} 3^1 5^1 7^1 11^1 > 2^{96} 3^3 5^1 7^1$$
I can't immediately think of an example, but my instinct says that some greedy approaches can fail if they merge the wrong powers first.
Is there a simple optimal strategy for merging these powers to get the correct answer?
Addendum. A greedy algorithm that checks every possible merge and performs the best one on a merge-by-merge basis, fails on $n = 3072$. The series of one-by-one merges is:
$$2^2 3^1 5^1 7^1 11^1 13^1 17^1 19^1 23^1 29^1 31^1$$
$$2^3 3^2 5^1 7^1 11^1 13^1 17^1 19^1 23^1 29^1$$
$$2^5 3^3 5^1 7^1 11^1 13^1 17^1 19^1 23^1$$
However the optimal solution is:
$$2^7 3^3 5^2 7^1 11^1 13^1 17^1 19^1$$