Split up $n \in \mathbb{N}$ into sum of naturals with maximum LCM

Question

Question:

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.

Example:

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

Here, the first solution is the desired one.

Background:

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.

So:

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?

Answer 1

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.