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