11
$\begingroup$

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?

  • 2
    The LCM values seems to follow [A000793](http://www.research.att.com/~njas/sequences/A000793). Edit: Well the definition *is* [Landau's function](http://en.wikipedia.org/wiki/Landau%27s_function).2010-08-28
  • 0
    @KennyTM: Cool, thanks - Landau's function. Edited the question from this ...2010-08-28

1 Answers 1

4

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.

  • 0
    Perfect, that was the kind of solution I was looking for. Nice dynamic programming.2010-08-29