Permutation Power

This is Landau's function $g(100)$ . See e.g. here or here .

As already very well explained by Ivan, any permutation of $n$ objects can be decomposed in cycles. The sum of the lengths of the cycles must give $n$ and each cycle gives the identity if repeated as many times as its length. For example, consider the following permutation:

$\sigma = {{1\;2\;3\;4\;5}\choose{2\;5\;4\;3\;1}} = (1\;2\;5)(3\;4)$

It is made up of a 3-cycle and a 2-cycle. The 3-cycle must be applied 3 times in order to give the identity whereas the 2-cycle has to be applied 2 times, as can be easily checked. Therefore, the full permutation $\sigma$ must be applied 6 times, i.e. the LCM of 2 and 3, in order to give the identity.

Therefore, let's find a set of number which summed give 100 and whose LCM is the maximum possible. Using prime numbers is a good start, because their LCM is their product. Indeed, it can be shown that the product of the first $m$ primes (the primorial) is a lower bound of Landau's function (for a suitable $m$ ). Note that:

$2+3+5+7+11+13+17+19+23 = 100$

And thus

$\mbox{LCM}(2,3,5,7,11,13,17,19,23) = 2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23 = 223092870$

This was my first guess, and it is wrong because it can be improved. Indeed, what counts in order to maximize the LCM is to have coprime numbers, not necessarily primes. We can improve the above result substituting $2 + 23$ by $16 + 9$ because in this case we have a factor $9\cdot 16 = 144$ in the LCM rather than $2\cdot 3\cdot 23 = 138$ . This gives:

$\mbox{LCM}(3,5,7,9,11,13,16,17,19) = 5\cdot 7\cdot 9\cdot 11\cdot 13\cdot 16\cdot 17\cdot 19 = 232792560$

which is the correct answer.

Relevant wiki: Dynamic Programming

A permutation $\sigma$ is a product of disjoint cycles. Suppose the cycles of $\sigma$ have length $a_1, a_2, a_3, \ldots, a_n$ . Then $f(\sigma) = \text{lcm} \{a_1, a_2, a_3, \ldots, a_n\}$ , because in order to set the $i$ -th cycle to be the identity, we need to raise $\sigma$ to the $a_i$ -th power. Thus our goal is to maximize $\text{lcm} \{a_1, a_2, a_3, \ldots, a_n\}$ , given the constraint that $a_1+a_2+a_3+\ldots+a_n = 100$ (because the cycles are disjoint).

Suppose $a_i = pq$ where $p, q > 1$ are relatively prime (that is, $a_i$ is not the power of a prime). Then $p+q \le a_i$ and $\text{lcm} \{p,q\} = a_i$ , so we may substitute the cycle with length $a_i$ with several cycles: one of length $p$ , one of length $q$ , and remaining cycles of length 1 to make the number of elements equal. For example, if $\sigma$ has a cycle of length 12, then we can split it off into a cycle of length 4, another cycle of length 3, and five cycles of length 1. This will give the same LCM, and hence same value of $f$ . Thus doing this will never make $f$ to decrease, and so we may assume that all $a_i$ 's are powers of prime.

Now, if there are $a_i, a_j$ such that $a_i | a_j$ and $a_i > 1$ , then we may replace the cycle with length $a_i$ with $a_i$ cycles of length 1, because the LCM is not changed ( $\text{lcm} \{a_i, a_j\} = a_j$ ). Thus we may also assume all $a_i$ 's are relatively prime. Now, we have several powers of primes, all relatively prime, which add up to 100. The LCM is simply the product of all of them, so we need to maximize this product.

We can now use dynamic programming to solve this. Label the primes $p_0, p_1, p_2, \ldots$ in increasing order. We generalize the problem: let $\mathtt{solve}(s,k)$ to be the maximum product of $a_1, a_2, \ldots, a_n$ , given that $a_1+a_2+\ldots+a_n = s$ , each $a_i$ is the perfect power of a prime $p \ge p_k$ , and any two $a_i$ 's are relatively prime. For example, $\mathtt{solve}(5,0) = 6$ , with $a_1 = 2, a_2 = 3$ , but $\mathtt{solve}(5,1) = 5$ with $a_1 = 5$ , because we may not use $p_0 = 2$ . (And $\mathtt{solve}(5,3) = 1$ , since we may not use any of the primes 2, 3, 5, so we're stuck with setting $a_1 = a_2 = \ldots = a_5 = 1$ .) Our goal is to compute $\mathtt{solve}(100,0)$ .

The base case is if $s < p_k$ . We cannot use any prime at all, so we can immediately conclude $\mathtt{solve}(s,k) = 1$ by setting all $a_i$ to 1. We can now make use of recursion: in order to compute $\mathtt{solve}(s,k)$ , we will take the maximum among the following:

• Ignore $p_k$ , so take the value of $\mathtt{solve}(s,k+1)$ .
• Let $a_1 = p_k^e$ for some $e$ (and then all other $a_i$ 's may not use $p_k$ ), so take the value of $p_k^e \cdot \mathtt{solve}(s - p_k^e, k+1)$ . We don't need to find the "right" value of $e$ ; simply iterate over all possible $e$ , as long as $p_k^e \le s$ .

The correctness is easily seen, because this recursion is actually testing all possible combinations: either we ignore $p_k$ , or one of the $a_i$ 's is a power of $p_k$ . This recursion will end, because each successive call increases $k$ and never increases $s$ ; thus at some point, we will compute $\mathtt{solve}(s',k')$ where $p_{k'} > s \ge s'$ and thus we hit the base case. Finally, this will take at most $O \left( \frac{s^2}{\log s} \right)$ time: there are $O \left( \frac{s}{\log s} \right)$ primes below $s$ , so there are that many values for $k$ , and there are $O(s)$ values for $s$ . By memoizing computation, no call will be computed more than once.

The following is a Python 3 implementation of the above algorithm.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

# Primes up to 100, plus one more
primes = [ 2,  3,  5,  7, 11, 13, 17, 19, 23, 29,
          31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
          73, 79, 83, 89, 97, 101]

# Memoized computation
computed_solve = dict()

# solve function as defined
def solve(s,k):
    # If p_k > s, this is base case
    if primes[k] > s: return 1
    # If already computed, return it
    if (s,k) in computed_solve: return computed_solve[s,k]
    # Otherwise, this is a new call

    # Answer candidates
    candidates = []
    # 1. Ignore p_k
    candidates.append(solve(s, k+1))
    # 2. Take a_1 = p_k^e, try all possible e
    e = 1
    while primes[k]**e <= s:
        a1 = primes[k]**e
        candidates.append(a1 * solve(s-a1, k+1))
        e += 1

    # Find maximum among all candidates
    answer = max(candidates)
    # Add to memoized computation and return
    computed_solve[s,k] = answer
    return answer

# Actual problem
solve(100, 0)
# Returns 232792560