Finding shortest sequences of integers whose product is larger than n

Question

Here is the task:

For an integer n, return a list of the k length integers sequences whose product is larger than n but as close to n as possible (i.e. smallest larger than n number), and whose largest member is the smallest possible. For each sequence length k, there is one such sequence, and we want to have the sequences for all possible k's. 1 doesn't count as a valid member. The sequences are ordered from largest to smallest member.

For example, for n=100, the longest non-trivial sequence is with k=7 and is [2, 2, 2, 2, 2, 2, 2]. sequences with k>7 will be just an extension to this sequence (i.e. additional 2's appended to this list) and thus we will disregard them as trivial and will not care for them.

For k=2 the sequence of choice for n=100 is [10, 10]. It is better than [12, 9] since the largest member is smaller. If the largest member is the same in two sequences of the same length then the decision moves to the next largest, etc.

The shortest sequence for n=100 is obviously the trivial [100].

And the full list for n=100 is:

In: productsequences(100)

out:
[[2, 2, 2, 2, 2, 2, 2],
 [3, 3, 2, 2, 2, 2],
 [3, 3, 3, 2, 2],
 [4, 3, 3, 3],
 [5, 5, 4],
 [10, 10],
 [100]]

This is the recursive code I've came up with. It seems to be working well. However for large numbers it becomes slow.

How can I improve it? Can the same be achieved faster for large numbers?

def productsequences(n, maxn=None):
    """
    Returns a list of valid integer sequnces of different lengths whose
    product is the smallest larger than n.
    """
    if n <= 1:
        return []
    if maxn == None:
        maxn = n
    seqlist= []
    for i in range(2, min(maxn, n) + 1):
        if n % i:
            r = productsequences((n // i) + 1, i)
        else:
            r = productsequences(n // i, i)
        if len(r) == 0:
            seqlist.append([i])
        else:
            for k in r:
                seqlist.append([i] + k)
    nontrivial = []
    lim = n # Just a large enough initial value. needs to be larger than
    # log(n, 2) + 1
    for k in seqlist: # keep just one sequnce of every length
        if len(k) < lim:
            nontrivial.append(k)
            lim = len(k)
    return nontrivial

Answer 1

Yes, you can improve that algorithm, by optimizing the following inequation:

$$n \le \prod_{i=1}^{k}{\lfloor\sqrt[k]{n}\rfloor+b_i} \quad \text{with} \quad b_i \in \{0, 1\}\land b_i >= b_{i+1}$$

Just initialize the guess for all factors for a given \$k\$ with \$\lfloor\sqrt[k]{n}\rfloor+1\$, and replace the factors one by one with \$\lfloor\sqrt[k]{n}\rfloor\$ while you are still above \$n\$.

That means you will effectively only need to calculate one root per \$k\$, followed by at most \$k\$ divisions, multiplications and comparisons.

---

Your problem would be far more complicated if being closer to \$n\$ had precedence over using the smallest factors. However, if only smallest factors are demanded, the \$k\$-th root of \$n\$ is the best approaximation you can get. Otherwise the problem would be a derivative of prime number factorization.

Answer 2

Yep. @Ext3h got it right. Here's the revised code:

from math import log
from functools import reduce


def prodseq(n):
    m = []
    if log(n, 2) - int(log(n ,2)) < 1e-10:
        maxk = int(log(n, 2))
    else:
        maxk = int(log(n, 2) + 1)
    for k in range(maxk, 0, -1):
        r = [int(n ** (1 / k))] * k
        i = 0
        while reduce(lambda x, y: x * y, r, 1) < n:
            r[i] += 1
            i += 1
        m.append(r)
    return m