12
$\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?

$\endgroup$
2
  • 2
    $\begingroup$ The LCM values seems to follow A000793. Edit: Well the definition is Landau's function. $\endgroup$
    – kennytm
    Aug 28, 2010 at 19:30
  • $\begingroup$ @KennyTM: Cool, thanks - Landau's function. Edited the question from this ... $\endgroup$
    – Dario
    Aug 28, 2010 at 19:48

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Perfect, that was the kind of solution I was looking for. Nice dynamic programming. $\endgroup$
    – Dario
    Aug 29, 2010 at 8:59

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.