What's the smallest $n$ for which $S_n$ has an element of order $30?$

Question

This is Gallian 5.22.

According to the manual the answer is $10$, but it's not clear what combination of cycles from $S_{10}$ would give an ${\rm lcm}$ of $30$ (and as such an element of order $30$).

If I take a cycle of $5$ and a cycle of $6$, they have ${\rm lcm}(5, 6) = 30$ which would mean $S_{11}$, or?

Answer 1

Factor $6 = 2 \times 3$, and notice that $2 + 3 < 2 \times 3$.

Answer 2

The optimal way to split up $30$ is as a sum of prime powers $2^1 + 3^1 + 5^1 = 10$ an described in this earlier answer.

I was curious what the solution to this problem was for all natural numbers and found a general formula. I asked a question about it here.

We are interested in finding a partition $\lambda$ of a fixed number $n$ such that $\lambda$ is a partition of a number $k$ where $k$ is as small as possible. Call $k$ $f(n)$.

The optimal $\lambda$ is a mutually coprime sum of prime powers such that the least common multiple of $\lambda$ is $k$.

As proof, I'll show how to take any $\lambda$ not of that form and construct a strictly better $\lambda$ that is a partition of a strictly smaller integer.

Let $\lambda$ be a partition whose least common multiple is $\pi$.

Suppose $\lambda$ contains two parts $a$ and $b$ such that $(a, b) \neq 1$. Then we can produce a partition of a smaller number with the same least common multiple by replacing $b$ with $b/(a,b)$.

Suppose $\lambda$ contains a number that is a multiple of a prime power $p^k$ and another number $a > 1$ such that $(a, p) = 1$. $\lambda$ contains $ap^k$. Let $\lambda'$ be the partition obtained by taking $\lambda$, removing $ap^k$, and adding $a$ and $p^k$. The least common multiple of $\lambda'$ is the same as the least common multiple of $\lambda$, but $\lambda'$ is a partition of a strictly smaller number.

In order to prove that $a + p^k$ is strictly smaller than $ap^k$.

Suppose $p$ is $2$, $a$ must then be at least $3$ and so $a + p^k$ is strictly less than $ap^k$.

Suppose $p$ is greater than $2$, then $a$ must be at least $3$ and so $a + p^k$ is strictly less than $ap^k$.

So, our function, $f(n)$ is equal to $\sum_i p_i^{a_i}$ where $\prod p_i^{a_i}$ is the prime factorization of $n$.

As Qiaochu Yuan points out in this comment, $f$ is additive.