Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
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
add comment

1 Answer

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|improve this answer
    
Perfect, that was the kind of solution I was looking for. Nice dynamic programming. –  Dario Aug 29 '10 at 8:59
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.