9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @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. $\endgroup$ – Steve D Jan 1 '17 at 19:24
1
$\begingroup$

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:

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

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

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))
$\endgroup$
  • $\begingroup$ 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!) $\endgroup$ – j_random_hacker Jan 1 '17 at 22:13
  • $\begingroup$ @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. $\endgroup$ – Steve D Jan 1 '17 at 22:20
  • $\begingroup$ 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! $\endgroup$ – orlp Jan 1 '17 at 22:32
  • $\begingroup$ 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$. $\endgroup$ – j_random_hacker Jan 2 '17 at 0:12
  • 1
    $\begingroup$ @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$. $\endgroup$ – j_random_hacker Jan 2 '17 at 13:59
-2
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – orlp Dec 25 '16 at 8:17
  • $\begingroup$ That is answered in the last paragraph. $\endgroup$ – gnasher729 Dec 26 '16 at 20:27
  • $\begingroup$ @gnasher729 That's far from being an answer to a question "efficiently compute", or even for "optimal strategy for merging" $\endgroup$ – yo' Dec 26 '16 at 21:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.