

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer


Given some natural number, we can of course split it up into various sums of other naturals (e.g. $7 = 6 + 1 = 1 + 4 + 2 = \ldots$)

More precisely, for $n \in \mathbb{N}$, we can a find distribution sequence (or partition) $s_0,\ldots,s_u \in \mathbb{N}$ with

$$\sum_{i=0}^{u}s_i = n$$

Now how can I find the partition $s$ for which the overall least common multiple of all elements is maximal. Or differently formulated the maximum product of distinct prime factors of all elements.


$$ 7 \mapsto (3, 4); \Pi_{lcm} = 12 $$ $$ 7 \mapsto (1, 2, 4); \Pi_{lcm} = 4$$ $$ \ldots $$

Here, the first solution is the desired one.


The background of my question is: How can I split up a sequence/string into contiguous subsequences that, when repeated and zipped together, will yield the longest possible resulting sequence.

For the above example, I could split up a string of length $7$ in the following way:

7: abcdefg 7:  abcdefg

    I              II
1: aaaa    3: abcabcabcabc
2: bcbc    4: defgdefgdefg
4: defg 

Of course, using the second distribution, the resulting sequence has a much greater period.


What algorithm/approach can I use to solve this problem and maximize the product? Is this some known problem and how complex would calculating a solution be? It's not NP, I hope?!

Edit: Partial solution

As @KennyTM pointed out in the comments, Landau's function $g$ describes the maximum LCM, i.e. $g(7) = 12$.

So this actually becomes: How to actually produce the partition? Does knowledge of $g(x)$ help here, maybe for a dynamic programming solution?

share|cite|improve this question
The LCM values seems to follow A000793. Edit: Well the definition is Landau's function. – kennytm Aug 28 '10 at 19:30
@KennyTM: Cool, thanks - Landau's function. Edited the question from this ... – Dario Aug 28 '10 at 19:48
up vote 4 down vote accepted

The blog post here describes somebody else's efforts at coding this up. He gets an improvement over the naive approach by using some nice internal structure of the problem.

share|cite|improve this answer
Perfect, that was the kind of solution I was looking for. Nice dynamic programming. – Dario Aug 29 '10 at 8:59

Your Answer


