1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Almost - that reduction costs more than you would expect. It currently needs to recompute the full product for every loop iteration, resulting in a total run time of \$\mathcal{O}(log^3(n))\$, rather than \$\mathcal{O}(log^2(n))\$. Try performing the full reduction only once, and then update the product inside the loop by only dividing and multiplying with the changed factor. \$\endgroup\$ – Ext3h Sep 23 '16 at 12:32

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.