# Efficiently computing the smallest integer with n divisors

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$$

• @orlp: My suggestion was: fix $n$ (say, $24$), and fix $m$ (say, $2$). Then you're trying to minimize $k_1\log(2)+k_2\log(3)$, subject to $k_1k_2=24$. So by working with a fixed number $m$ (of primes), you can ignore the complications of whether a certain prime should appear in the global minimum or not. You find the minimum for each $m$, then take the min of those. – Steve D Jan 1 '17 at 19:24

Here's a solution, based on my comments above. I make no claims this is optimal.

The idea is to consider $T(n,m)$, which we defines as "the smallest positive integer with exactly $n$ divisors and $m$ distinct prime factors". We make the easy observations:

\begin{align} T(n, 1) &= 2^{n-1}\\ T(2^m, m) &= p_1p_2\cdots p_m \end{align}

And we also have the recurrence:

$$T(n,m) = \min_{d|n} [T\left(\frac{n}{d}, m-1\right)\cdot p_m^{d-1}]$$

Finally, the quantity you're looking for is $$\min_{1\le i\le\lceil\log(n)\rceil} T(n, i)$$

To that end, here is some Python code, which agrees with all the numbers you gave above. Note that it works with the logarithms to keep the numbers smaller: so the actual integer you seek is round(2**smallest(n)).

import functools
import itertools
import math

# All primes less than 100.
PRIMES = [
2, 3, 5, 7, 11,
13, 17, 19, 23, 29,
31, 37, 41, 43, 47,
53, 59, 61, 67, 71,
73, 79, 83, 89, 97,
]

LOG_PRIMES = [math.log2(p) for p in PRIMES]

def smallest(n):
max_factors = math.ceil(math.log2(n))
min_so_far = float('Infinity')
factors = factorize(n)
memo = {}
for i in range(1, max_factors+1):
t = T(n,i, factors, memo)
if 0.0 < t < min_so_far:
min_so_far = t
return min_so_far

def T(n, m, factors=None, memo=None):
if memo is None:
memo = {}
if n < 2 or m < 1:
return 0
elif m == 1:
# Everything on the smallest prime.
return (n-1) * LOG_PRIMES[0]
elif n < 2**m:
return 0
elif n == 2**m:
# Product of first m primes, in log.
return sum(LOG_PRIMES[:m])
elif (n,m) in memo:
return memo[(n,m)]

if factors is None:
factors = factorize(n)
if len(factors) < m:
return 0

smallest = float('Infinity')
for factor_list in powerset(factors):
divisor = product(factor_list)
first = T(divisor, m-1, factor_list, memo)
# No such product.
if first < 1.0:
continue
second = (n/divisor - 1) * LOG_PRIMES[m-1]
total = first + second
if total < smallest:
smallest = total

memo[(n,m)] = smallest
return smallest

def product(nums):
return functools.reduce(lambda x,y: x*y, nums, 1)

def factorize(n):
prime_factors = []
for p in PRIMES:
while n%p == 0:
n //= p
prime_factors.append(p)
if n == 1:
break
return prime_factors

def powerset(lst):
# No empty set.
return itertools.chain.from_iterable(itertools.combinations(lst, r)
for r in range(1, len(lst)+1))

• The comments you refer to seem to have been deleted unfortunately, but this is certainly optimal (in the sense of computing the smallest possible integer with exactly $n$ factors). Is it the optimality of the time complexity that you're unsure about? I don't know a tight bound for the number of divisors of an integer $n$, but even with the very pessimistic bound of $O(n)$ your algorithm is only $O(n^2\log n)$, which should be fast enough for $n$ in the tens of thousands! (BTW: I was writing up the same algorithm (minus some optimisations) but you got there first, well done!) – j_random_hacker Jan 1 '17 at 22:13
• @j_random_hacker: Yes, not sure what happened to those comments: there were many of them, and they are now all gone! I was indeed talking about time complexity; I actually think it is probably closer to $O(n\log n)$, but the number of divisors is a tricky function. Of course, the code above can certainly be optimized better: powerset doesn't account for duplicates, for example. – Steve D Jan 1 '17 at 22:20
• I believe this is easier to implement efficiently using dynamic programming: gist.github.com/orlp/0fbb7784782712bc7c411aa58a188143 I'm really not comfortable with the logarithm trick by the way - floating point limited precision will at some point screw things. That being said, I don't believe this is actually faster than generating all multiplicative partitions. In fact, I believe that's exactly what it's doing in disguise! – orlp Jan 1 '17 at 22:32
• After reading @orlp's comment and your code more closely, I now think it's important for the time complexity (and practical performance) to change for factor_list in powerset(factors) to something that generates each distinct divisor of n exactly once. That way, for, say, $n=2^k3^k$, when you consider solutions containing exactly the first $2k$ primes as their distinct prime factors, you will only do $O(k^2)$ non-recursive work instead of $O({{2k}\choose{k}})$, which is exponential in $k$. – j_random_hacker Jan 2 '17 at 0:12
• @orlp: I misunderstood the term "multiplicative partitions", sorry. Thanks for the Python code. To see why Steve D's algorithm doesn't parallel that code, consider multiplicative_partitions(24), which produces (among others) the partitions [4, 3, 2] and [6, 2, 2], which (after reversing the order in order to give the smallest prime factor the highest exponent) correspond to the solutions $2^3 3^2 5^1$ and $2^5 3^1 5^1$, respectively. Steve D's algorithm will never consider the latter solution, since it has already determined that the subsolution $2^3 3^2 = 72 < 2^5 3^1 = 96$. – j_random_hacker Jan 2 '17 at 13:59

Possible candidates for "smallest integer with n divisors" are the integers of the form $2^a·3^b·5^c...$ where a ≥ b ≥ c ... and (a+1)(b+1)(c+1)... = n.

So you need to find all ways to express n as the product of integers ≥ 2 in non-ascending order, and calculate and check the corresponding candidates. For example, when n = 16, 16 = 8·2 = 4·4 = 4·2·2 = 2·2·2·2, so possibilities are $2^7·3$, $2^3·3^3$, $2^3·3·5$, $2·3·5·7$, and the smallest is $2^3·3·5 = 120$.

If n is the product of two primes p·q, p ≥ q, the only candidates are $2^{pq-1}$ and $2^{p-1}·3^{q-1}$, and the latter is always smaller.

You can figure out some condition when there could be a factor $2^{ab-1}$ for example, by checking whether $2^{ab-1} > 2^{a-1}·x^{b-1}$ for some prime x that isn't a factor. In the example n = 16, there is a factor $2^3$ because $2^3 < 2·7$.

• Forgive me, but this doesn't answer my question at all, it just summarizes what I've found in my question. The title is just that: a title, not the question itself. I feel like you've only read the title before answering. The real question is at the bottom of my question text. – orlp Dec 25 '16 at 8:17
• That is answered in the last paragraph. – gnasher729 Dec 26 '16 at 20:27
• @gnasher729 That's far from being an answer to a question "efficiently compute", or even for "optimal strategy for merging" – yo' Dec 26 '16 at 21:04