能否求出n次对称群中置换的最大阶？
在数学领域，对称群 $S_n$ 是一个非常重要的概念，它由 $n$ 个元素的特定排列组成。这些排列具有各种各样的性质，其中一个引人入胜的性质就是它们的“阶”。置换的阶是指最小的正整数 $k$，使得将该置换作用于一个元素 $k$ 次后，该元素回到其初始位置。换句话说，如果 $sigma$ 是一个置换，那么 $sigma^k = id$，其中 $id$ 是恒等置换（所有元素都在原地）。
对于 $S_n$ 中的置换，其阶的取值范围可能非常广泛。我们感兴趣的问题是：在 $n$ 个元素的对称群 $S_n$ 中，可能存在的置换的“最大阶”是多少？ 换句话说，是否存在一个置换，它的阶比 $S_n$ 中的其他任何置换的阶都要大？
要回答这个问题，我们需要深入理解置换的结构。任何置换都可以被唯一地分解成不相交的循环的乘积。例如，在 $S_5$ 中，置换 $(1 2 3)(4 5)$ 可以被看作是两个循环的乘积：一个循环是 $(1 2 3)$，它将 $1$ 映射到 $2$，将 $2$ 映射到 $3$，将 $3$ 映射到 $1$；另一个循环是 $(4 5)$，它将 $4$ 映射到 $5$，将 $5$ 映射到 $4$。
一个循环的阶等于该循环的长度。例如，循环 $(1 2 3)$ 的阶是 $3$，因为 $(1 2 3)^1 = (1 2 3)$，$(1 2 3)^2 = (1 3 2)$，而 $(1 2 3)^3 = (1)(2)(3) = id$。
当我们将不相交的循环相乘时，得到的置换的阶是这些循环长度的最小公倍数（LCM）。例如，在 $S_5$ 中，置换 $sigma = (1 2 3)(4 5)$ 的阶是 $ ext{lcm}(3, 2) = 6$。
现在，我们来考虑如何在 $n$ 个元素的集合上构造一个置换，使其阶最大。要最大化置换的阶，我们就需要最大化其分解成不相交循环的长度的最小公倍数。这意味着我们需要找到一组长度为 $l_1, l_2, dots, l_m$ 的不相交循环，使得它们的总长度 $sum_{i=1}^m l_i le n$，并且 $ ext{lcm}(l_1, l_2, dots, l_m)$ 尽可能大。
让我们来看几个例子：
$S_1$: 只有一个置换，即恒等置换 $id = (1)$，阶为 $1$。最大阶为 $1$。
$S_2$: 置换有 $id = (1)(2)$ (阶 $1$) 和 $(1 2)$ (阶 $2$)。最大阶为 $2$。
$S_3$: 置换有：
$id$ (阶 $1$)
$(1 2), (1 3), (2 3)$ (都是长度为 $2$ 的循环，阶为 $2$)
$(1 2 3), (1 3 2)$ (都是长度为 $3$ 的循环，阶为 $3$)
最大阶为 $3$。
$S_4$:
$id$ (阶 $1$)
长度 $2$ 的循环，如 $(1 2)$ (阶 $2$)
长度 $3$ 的循环，如 $(1 2 3)$ (阶 $3$)
长度 $4$ 的循环，如 $(1 2 3 4)$ (阶 $4$)
两个长度为 $2$ 的不相交循环，如 $(1 2)(3 4)$ (阶 $ ext{lcm}(2, 2) = 2$)
最大阶为 $4$。
$S_5$:
长度 $5$ 的循环，如 $(1 2 3 4 5)$ (阶 $5$)
一个长度为 $2$ 的循环和一个长度为 $3$ 的循环，如 $(1 2)(3 4 5)$ (阶 $ ext{lcm}(2, 3) = 6$)
最大阶为 $6$。
$S_6$:
长度 $6$ 的循环，如 $(1 2 3 4 5 6)$ (阶 $6$)
一个长度为 $2$ 的循环和一个长度为 $4$ 的循环，如 $(1 2)(3 4 5 6)$ (阶 $ ext{lcm}(2, 4) = 4$)
两个长度为 $3$ 的循环，如 $(1 2 3)(4 5 6)$ (阶 $ ext{lcm}(3, 3) = 3$)
一个长度为 $2$ 的循环和一个长度为 $3$ 的循环，如 $(1 2)(3 4 5)$ (在这种情况下，我们还剩一个元素，可以看作是长度为 $1$ 的循环，即 $(1 2)(3 4 5)(6)$，总阶为 $ ext{lcm}(2, 3, 1) = 6$)
如果使用所有 $6$ 个元素构造一个循环，阶为 $6$。
我们可以尝试分解成更小的循环，比如长度为 $5$ 和 $1$，如 $(1 2 3 4 5)(6)$，阶为 $5$。
或者长度为 $4$ 和 $2$，如 $(1 2 3 4)(5 6)$，阶为 $ ext{lcm}(4, 2) = 4$。
或者长度为 $3$ 和 $3$，如 $(1 2 3)(4 5 6)$，阶为 $ ext{lcm}(3, 3) = 3$。
或者长度为 $2, 2, 2$，如 $(1 2)(3 4)(5 6)$，阶为 $ ext{lcm}(2, 2, 2) = 2$。
经过一番尝试，我们发现最大的可能是长度为 $6$ 的循环，阶为 $6$。
从上面的例子可以看出，最大阶的置换通常是由尽量多的不相交的、互质的长度的循环组成的。更具体地说，我们希望找到一组互质的正整数 $l_1, l_2, dots, l_m$，使得 $sum_{i=1}^m l_i le n$，并且 $ ext{lcm}(l_1, l_2, dots, l_m)$ 最大。
为了最大化 $ ext{lcm}(l_1, l_2, dots, l_m)$，我们倾向于选择较小的、互质的数作为循环的长度，尤其是质数。例如，如果我们可以将 $n$ 分解成一些互质的数的和，那么这些数的最小公倍数很可能很大。
让我们回顾一下上面计算的最大阶：
$n=1$, max order = $1$
$n=2$, max order = $2$
$n=3$, max order = $3$
$n=4$, max order = $4$
$n=5$, max order = $6 = ext{lcm}(2, 3)$
$n=6$, max order = $6$ (可以来自长度为 $6$ 的循环，或者 $ ext{lcm}(2,3)$ 等等，但我们发现 $6$ 是可能的最大值)
$n=7$, 我们可以考虑长度为 $7$ 的循环 (阶 $7$)；或者长度为 $3$ 和 $4$ 的循环 $(1 2 3)(4 5 6 7)$ (阶 $ ext{lcm}(3, 4) = 12$)。所以 $n=7$ 的最大阶是 $12$。
$n=8$, 我们可以考虑长度为 $8$ 的循环 (阶 $8$)；或者长度为 $3$ 和 $5$ 的循环 $(1 2 3)(4 5 6 7 8)$ (阶 $ ext{lcm}(3, 5) = 15$)。所以 $n=8$ 的最大阶是 $15$。
$n=9$, 我们可以考虑长度为 $9$ 的循环 (阶 $9$)；或者长度为 $2$ 和 $7$ 的循环 $(1 2)(3 4 5 6 7 8 9)$ (阶 $ ext{lcm}(2, 7) = 14$)；或者长度为 $4$ 和 $5$ 的循环 $(1 2 3 4)(5 6 7 8 9)$ (阶 $ ext{lcm}(4, 5) = 20$)。所以 $n=9$ 的最大阶是 $20$。
$n=10$, 我们可以考虑长度为 $10$ 的循环 (阶 $10$)；或者长度为 $3$ 和 $7$ 的循环 $(1 2 3)(4 5 6 7 8 9 10)$ (阶 $ ext{lcm}(3, 7) = 21$)。所以 $n=10$ 的最大阶是 $21$。
由此可见，为了求出 $S_n$ 中置换的最大阶，我们实际上是在寻找一个整数分区 $n = l_1 + l_2 + dots + l_m$，使得 $ ext{lcm}(l_1, l_2, dots, l_m)$ 最大。然而，这里的条件是 $sum_{i=1}^m l_i le n$，因为我们只需要使用 $n$ 个元素中的一部分来构建最大阶的置换。
数学家们已经研究了这个问题，并称之为“最大阶函数”或“Landau's function” $g(n)$。 $g(n)$ 定义为 $S_n$ 中置换的最大阶。
寻找 $g(n)$ 的策略是找到一组互质的数 $l_1, l_2, dots, l_m$ 使得 $sum l_i le n$ 且 $ ext{lcm}(l_1, l_2, dots, l_m)$ 最大。
一个重要的观察是，为了最大化最小公倍数，我们应该优先选择质数或者 $p^k$ 形式（其中 $p$ 是质数）的数作为循环的长度。这是因为质数的最小公倍数会随着质数的增加而迅速增长。如果选择合数，其最小公倍数往往可以通过其质因数来表示，并且不会比质数序列的最小公倍数增长得更快。
例如，如果考虑长度为 $6$ 的循环，它的阶是 $6$。如果我们将 $n$ 分解成 $2$ 和 $3$，即两个循环的长度为 $2$ 和 $3$，那么它们的总长度是 $5 le n$，而它们的阶是 $ ext{lcm}(2, 3) = 6$。这和长度为 $6$ 的循环是一样的。但如果 $n=6$，我们可以考虑长度为 $6$ 的循环，阶是 $6$。我们也可以考虑长度为 $2$ 和 $4$ 的循环，总长度 $6$，阶是 $ ext{lcm}(2, 4) = 4$。
因此，寻找 $S_n$ 中置换的最大阶，实际上是在寻找一个整数序列 $l_1, l_2, dots, l_m$，满足以下条件，使得它们的最小公倍数最大：
1. $l_i$ 都是正整数。
2. $l_i$ 两两互质（或者更确切地说，我们希望 $l_i$ 的质因数集合尽量不重叠）。
3. $sum_{i=1}^m l_i le n$。
为了最大化 $ ext{lcm}(l_1, l_2, dots, l_m)$，我们通常会选择：
质数 $p$：作为循环长度的质数，它们的最小公倍数就是它们的乘积。
质数幂 $p^k$：如果存在一个 $p^k le n$，并且用 $p^k$ 代替 $p$ 可以增加最小公倍数，那么我们就应该选择 $p^k$。但需要注意的是，如果选择 $p^k$，我们就不能再选择 $p$ 或 $p$ 的其他倍数作为循环长度，因为它们会与 $p^k$ 共享质因数，降低了最小公倍数。
我们通常会选择一系列互质的数，并且这些数是小于等于 $n$ 的质数幂。 例如，对于 $n=10$，我们可以考虑：
质数：$2, 3, 5, 7$。总和 $2+3+5+7 = 17 > 10$。所以我们不能选取所有这些质数。
质数幂：$2^1=2, 2^2=4, 2^3=8$, $3^1=3, 3^2=9$, $5^1=5$, $7^1=7$。
我们需要找到一个满足 $sum l_i le n$ 的质数幂集合，使得它们的最小公倍数最大。
让我们重新审视 $n=10$ 的情况：
我们可以选择：
质数 $3$ 和 $7$：总和 $3+7=10$。阶是 $ ext{lcm}(3, 7) = 21$。
质数 $2$ 和 $7$：总和 $2+7=9 le 10$。阶是 $ ext{lcm}(2, 7) = 14$。
质数幂 $2^2=4$ 和 $3$：总和 $4+3=7 le 10$。阶是 $ ext{lcm}(4, 3) = 12$。
质数幂 $2^3=8$：总和 $8 le 10$。阶是 $8$。
质数幂 $3^2=9$：总和 $9 le 10$。阶是 $9$。
质数 $2, 3, 5$：总和 $2+3+5=10$。阶是 $ ext{lcm}(2, 3, 5) = 30$。
哦，我之前的计算有误。对于 $n=10$，我们可以选择长度为 $2, 3, 5$ 的不相交循环，总长度是 $2+3+5=10$。这些长度是互质的。此时的置换阶是 $ ext{lcm}(2, 3, 5) = 30$。
让我们重新计算一些值：
$n=1$: max order = $1$. (partition: $1$)
$n=2$: max order = $2$. (partition: $2$)
$n=3$: max order = $3$. (partition: $3$)
$n=4$: max order = $4$. (partition: $4$)
$n=5$: max order = $6$. (partition: $2+3$)
$n=6$: max order = $6$. (partition: $6$)
$n=7$: max order = $12$. (partition: $3+4$)
$n=8$: max order = $15$. (partition: $3+5$)
$n=9$: max order = $20$. (partition: $4+5$)
$n=10$: max order = $30$. (partition: $2+3+5$)
这里的规律是，我们要选择一系列互质的质数幂 $p_1^{a_1}, p_2^{a_2}, dots, p_k^{a_k}$，使得它们的总和小于或等于 $n$，并且它们的最小公倍数最大。这个最小公倍数就是 $p_1^{a_1} p_2^{a_2} dots p_k^{a_k}$。
具体来说，这个过程可以概括为：
1. 列出所有小于等于 $n$ 的质数幂。例如，对于 $n=10$，这些是 $2, 3, 4, 5, 7, 8, 9$。
2. 从中选择一个子集，使得这些数是互质的（即它们不包含相同的质因数），并且它们的总和小于等于 $n$。
3. 在这个子集中，选择那些“最优”的质数幂。例如，对于质数 $2$，我们考虑 $2^1=2, 2^2=4, 2^3=8$。如果我们在选择的质数幂集合中包含 $4$，那么我们就不能再包含 $2$（因为它们有共同的质因数 $2$）。我们应该选择能够最大化最终乘积的质数幂。
4. 最终，我们希望找到一个由不同质数的最高次幂组成的集合 $p_1^{a_1}, p_2^{a_2}, dots, p_k^{a_k}$，使得 $sum_{i=1}^k p_i^{a_i} le n$，并且 $prod_{i=1}^k p_i^{a_i}$ 最大。
算法思路：
我们可以使用一种贪心的方法，但需要谨慎。更严谨的方法可能是动态规划或者回溯搜索，但是对于寻找最大阶的问题，一个更实际的方法是考虑不同质数幂的组合。
我们希望选择互质的质数幂 $p_1^{a_1}, p_2^{a_2}, dots, p_k^{a_k}$，使得 $sum p_i^{a_i} le n$ 并且 $prod p_i^{a_i}$ 最大。
我们可以从较小的质数幂开始考虑。
例如，对于 $n=10$:
质数幂列表（小于等于 $10$）：$2, 3, 4, 5, 7, 8, 9$。
我们可以尝试组合：
只用质数：$2, 3, 5$ (和 $10$) > $ ext{lcm}(2,3,5) = 30$
用质数幂：
$3, 7$ (和 $10$) > $ ext{lcm}(3,7) = 21$
$2, 3, 5$ (和 $10$) > $ ext{lcm}(2,3,5) = 30$
$4, 3$ (和 $7$) > $ ext{lcm}(4,3) = 12$
$8$ (和 $8$) > $8$
$9$ (和 $9$) > $9$
$2, 3, ?$ 已经用了质数 $2, 3$。下一个互质的质数幂是 $5$。
考虑 $2^3=8$。如果选了 $8$，我们就不能再选 $2, 4$ 了。 剩余 $108=2$ 的空间。我们可以选择 $2$，但 $8$ 和 $2$ 不互质。所以，如果选 $8$，只能单独构成一个循环，阶为 $8$。
考虑 $3^2=9$。如果选了 $9$，我们就不能再选 $3$ 了。剩余 $109=1$ 的空间。我们可以选择 $2$（不与 $9$ 互质），或 $5$（不与 $9$ 互质）。如果选 $9$ 和 $2$，总和 $11 > 10$。如果选 $9$ 和 $5$，总和 $14 > 10$。所以如果选 $9$ 只能单独构成一个循环，阶为 $9$。
因此，最关键的原则是选择一组互质的质数幂 $p_1^{a_1}, p_2^{a_2}, dots, p_k^{a_k}$，使得它们的和 $sum_{i=1}^k p_i^{a_i} le n$ 并且它们的乘积 $prod_{i=1}^k p_i^{a_i}$ 最大。
这个问题的计算是复杂的，并且没有一个简单的封闭形式的公式。需要通过搜索来找到最优的组合。
一般地，对一个给定的 $n$，我们需要找到一个由互质的质数幂组成的集合 ${l_1, l_2, dots, l_m}$，使得 $sum_{i=1}^m l_i le n$ 且 $ ext{lcm}(l_1, l_2, dots, l_m)$ 最大。
例如，对于 $n=15$:
我们寻找互质的质数幂的组合，总和不超过 $15$，且乘积最大。
质数幂列表（小于等于 $15$）：$2, 3, 4, 5, 7, 8, 9, 11, 13$。
可能的组合：
$2, 3, 5$ (和 $10$) > $ ext{lcm}(2,3,5) = 30$
$2, 3, 7$ (和 $12$) > $ ext{lcm}(2,3,7) = 42$
$2, 5, 7$ (和 $14$) > $ ext{lcm}(2,5,7) = 70$
$3, 5, 7$ (和 $15$) > $ ext{lcm}(3,5,7) = 105$
$2, 3, 4$ 不互质
$2, 3, 8$ 不互质
$2, 3, 9$ 不互质
$2^2=4, 3, 5$ (和 $12$) > $ ext{lcm}(4,3,5) = 60$
$2^2=4, 3, 7$ (和 $14$) > $ ext{lcm}(4,3,7) = 84$
$2^3=8, 3, 5$ (和 $16$) > 超出范围
$2^3=8, 7$ (和 $15$) > $ ext{lcm}(8,7) = 56$
$3^2=9, 2, 5$ (和 $16$) > 超出范围
$3^2=9, 4$ (和 $13$) > $ ext{lcm}(9,4) = 36$
$3^2=9, 5$ (和 $14$) > $ ext{lcm}(9,5) = 45$
$3^2=9, 2, ?$
目前看起来，选择互质的质数幂，并且尽量使用较大的质数，可以得到较大的乘积。
对于 $n=15$，最大阶似乎是 $105$，由长度为 $3, 5, 7$ 的循环组成。
总结来说：
在 $n$ 次对称群 $S_n$ 中，置换的最大阶是 $g(n)$，它等于所有可能的不相交循环长度的组合的最小公倍数中的最大值。而这些不相交循环的长度之和不能超过 $n$。
为了最大化这个最小公倍数，我们应该选择互质的质数幂 $p_1^{a_1}, p_2^{a_2}, dots, p_k^{a_k}$，使得它们的总和 $sum_{i=1}^k p_i^{a_i} le n$ 并且它们的乘积 $prod_{i=1}^k p_i^{a_i}$ 最大。
找到这个最大值通常需要通过搜索算法来完成，因为没有一个简单的公式可以直接给出答案。这个计算的复杂度随着 $n$ 的增加而显著提高。
理解这个问题的核心在于：置换的阶由其循环分解的长度的最小公倍数决定，而最大化这个最小公倍数，最优策略就是选取互质的、并且总和不超过 $n$ 的“高效”的数作为循环长度，这些“高效”的数就是质数幂。
对于 $S_n$ 中的置换，其阶的取值范围可能非常广泛。我们感兴趣的问题是：在 $n$ 个元素的对称群 $S_n$ 中，可能存在的置换的“最大阶”是多少？ 换句话说，是否存在一个置换，它的阶比 $S_n$ 中的其他任何置换的阶都要大？
要回答这个问题，我们需要深入理解置换的结构。任何置换都可以被唯一地分解成不相交的循环的乘积。例如，在 $S_5$ 中，置换 $(1 2 3)(4 5)$ 可以被看作是两个循环的乘积：一个循环是 $(1 2 3)$，它将 $1$ 映射到 $2$，将 $2$ 映射到 $3$，将 $3$ 映射到 $1$；另一个循环是 $(4 5)$，它将 $4$ 映射到 $5$，将 $5$ 映射到 $4$。
一个循环的阶等于该循环的长度。例如，循环 $(1 2 3)$ 的阶是 $3$，因为 $(1 2 3)^1 = (1 2 3)$，$(1 2 3)^2 = (1 3 2)$，而 $(1 2 3)^3 = (1)(2)(3) = id$。
当我们将不相交的循环相乘时，得到的置换的阶是这些循环长度的最小公倍数（LCM）。例如，在 $S_5$ 中，置换 $sigma = (1 2 3)(4 5)$ 的阶是 $ ext{lcm}(3, 2) = 6$。
现在，我们来考虑如何在 $n$ 个元素的集合上构造一个置换，使其阶最大。要最大化置换的阶，我们就需要最大化其分解成不相交循环的长度的最小公倍数。这意味着我们需要找到一组长度为 $l_1, l_2, dots, l_m$ 的不相交循环，使得它们的总长度 $sum_{i=1}^m l_i le n$，并且 $ ext{lcm}(l_1, l_2, dots, l_m)$ 尽可能大。
让我们来看几个例子：
$S_1$: 只有一个置换，即恒等置换 $id = (1)$，阶为 $1$。最大阶为 $1$。
$S_2$: 置换有 $id = (1)(2)$ (阶 $1$) 和 $(1 2)$ (阶 $2$)。最大阶为 $2$。
$S_3$: 置换有：
$id$ (阶 $1$)
$(1 2), (1 3), (2 3)$ (都是长度为 $2$ 的循环，阶为 $2$)
$(1 2 3), (1 3 2)$ (都是长度为 $3$ 的循环，阶为 $3$)
最大阶为 $3$。
$S_4$:
$id$ (阶 $1$)
长度 $2$ 的循环，如 $(1 2)$ (阶 $2$)
长度 $3$ 的循环，如 $(1 2 3)$ (阶 $3$)
长度 $4$ 的循环，如 $(1 2 3 4)$ (阶 $4$)
两个长度为 $2$ 的不相交循环，如 $(1 2)(3 4)$ (阶 $ ext{lcm}(2, 2) = 2$)
最大阶为 $4$。
$S_5$:
长度 $5$ 的循环，如 $(1 2 3 4 5)$ (阶 $5$)
一个长度为 $2$ 的循环和一个长度为 $3$ 的循环，如 $(1 2)(3 4 5)$ (阶 $ ext{lcm}(2, 3) = 6$)
最大阶为 $6$。
$S_6$:
长度 $6$ 的循环，如 $(1 2 3 4 5 6)$ (阶 $6$)
一个长度为 $2$ 的循环和一个长度为 $4$ 的循环，如 $(1 2)(3 4 5 6)$ (阶 $ ext{lcm}(2, 4) = 4$)
两个长度为 $3$ 的循环，如 $(1 2 3)(4 5 6)$ (阶 $ ext{lcm}(3, 3) = 3$)
一个长度为 $2$ 的循环和一个长度为 $3$ 的循环，如 $(1 2)(3 4 5)$ (在这种情况下，我们还剩一个元素，可以看作是长度为 $1$ 的循环，即 $(1 2)(3 4 5)(6)$，总阶为 $ ext{lcm}(2, 3, 1) = 6$)
如果使用所有 $6$ 个元素构造一个循环，阶为 $6$。
我们可以尝试分解成更小的循环，比如长度为 $5$ 和 $1$，如 $(1 2 3 4 5)(6)$，阶为 $5$。
或者长度为 $4$ 和 $2$，如 $(1 2 3 4)(5 6)$，阶为 $ ext{lcm}(4, 2) = 4$。
或者长度为 $3$ 和 $3$，如 $(1 2 3)(4 5 6)$，阶为 $ ext{lcm}(3, 3) = 3$。
或者长度为 $2, 2, 2$，如 $(1 2)(3 4)(5 6)$，阶为 $ ext{lcm}(2, 2, 2) = 2$。
经过一番尝试，我们发现最大的可能是长度为 $6$ 的循环，阶为 $6$。
从上面的例子可以看出，最大阶的置换通常是由尽量多的不相交的、互质的长度的循环组成的。更具体地说，我们希望找到一组互质的正整数 $l_1, l_2, dots, l_m$，使得 $sum_{i=1}^m l_i le n$，并且 $ ext{lcm}(l_1, l_2, dots, l_m)$ 最大。
为了最大化 $ ext{lcm}(l_1, l_2, dots, l_m)$，我们倾向于选择较小的、互质的数作为循环的长度，尤其是质数。例如，如果我们可以将 $n$ 分解成一些互质的数的和，那么这些数的最小公倍数很可能很大。
让我们回顾一下上面计算的最大阶：
$n=1$, max order = $1$
$n=2$, max order = $2$
$n=3$, max order = $3$
$n=4$, max order = $4$
$n=5$, max order = $6 = ext{lcm}(2, 3)$
$n=6$, max order = $6$ (可以来自长度为 $6$ 的循环，或者 $ ext{lcm}(2,3)$ 等等，但我们发现 $6$ 是可能的最大值)
$n=7$, 我们可以考虑长度为 $7$ 的循环 (阶 $7$)；或者长度为 $3$ 和 $4$ 的循环 $(1 2 3)(4 5 6 7)$ (阶 $ ext{lcm}(3, 4) = 12$)。所以 $n=7$ 的最大阶是 $12$。
$n=8$, 我们可以考虑长度为 $8$ 的循环 (阶 $8$)；或者长度为 $3$ 和 $5$ 的循环 $(1 2 3)(4 5 6 7 8)$ (阶 $ ext{lcm}(3, 5) = 15$)。所以 $n=8$ 的最大阶是 $15$。
$n=9$, 我们可以考虑长度为 $9$ 的循环 (阶 $9$)；或者长度为 $2$ 和 $7$ 的循环 $(1 2)(3 4 5 6 7 8 9)$ (阶 $ ext{lcm}(2, 7) = 14$)；或者长度为 $4$ 和 $5$ 的循环 $(1 2 3 4)(5 6 7 8 9)$ (阶 $ ext{lcm}(4, 5) = 20$)。所以 $n=9$ 的最大阶是 $20$。
$n=10$, 我们可以考虑长度为 $10$ 的循环 (阶 $10$)；或者长度为 $3$ 和 $7$ 的循环 $(1 2 3)(4 5 6 7 8 9 10)$ (阶 $ ext{lcm}(3, 7) = 21$)。所以 $n=10$ 的最大阶是 $21$。
由此可见，为了求出 $S_n$ 中置换的最大阶，我们实际上是在寻找一个整数分区 $n = l_1 + l_2 + dots + l_m$，使得 $ ext{lcm}(l_1, l_2, dots, l_m)$ 最大。然而，这里的条件是 $sum_{i=1}^m l_i le n$，因为我们只需要使用 $n$ 个元素中的一部分来构建最大阶的置换。
数学家们已经研究了这个问题，并称之为“最大阶函数”或“Landau's function” $g(n)$。 $g(n)$ 定义为 $S_n$ 中置换的最大阶。
寻找 $g(n)$ 的策略是找到一组互质的数 $l_1, l_2, dots, l_m$ 使得 $sum l_i le n$ 且 $ ext{lcm}(l_1, l_2, dots, l_m)$ 最大。
一个重要的观察是，为了最大化最小公倍数，我们应该优先选择质数或者 $p^k$ 形式（其中 $p$ 是质数）的数作为循环的长度。这是因为质数的最小公倍数会随着质数的增加而迅速增长。如果选择合数，其最小公倍数往往可以通过其质因数来表示，并且不会比质数序列的最小公倍数增长得更快。
例如，如果考虑长度为 $6$ 的循环，它的阶是 $6$。如果我们将 $n$ 分解成 $2$ 和 $3$，即两个循环的长度为 $2$ 和 $3$，那么它们的总长度是 $5 le n$，而它们的阶是 $ ext{lcm}(2, 3) = 6$。这和长度为 $6$ 的循环是一样的。但如果 $n=6$，我们可以考虑长度为 $6$ 的循环，阶是 $6$。我们也可以考虑长度为 $2$ 和 $4$ 的循环，总长度 $6$，阶是 $ ext{lcm}(2, 4) = 4$。
因此，寻找 $S_n$ 中置换的最大阶，实际上是在寻找一个整数序列 $l_1, l_2, dots, l_m$，满足以下条件，使得它们的最小公倍数最大：
1. $l_i$ 都是正整数。
2. $l_i$ 两两互质（或者更确切地说，我们希望 $l_i$ 的质因数集合尽量不重叠）。
3. $sum_{i=1}^m l_i le n$。
为了最大化 $ ext{lcm}(l_1, l_2, dots, l_m)$，我们通常会选择：
质数 $p$：作为循环长度的质数，它们的最小公倍数就是它们的乘积。
质数幂 $p^k$：如果存在一个 $p^k le n$，并且用 $p^k$ 代替 $p$ 可以增加最小公倍数，那么我们就应该选择 $p^k$。但需要注意的是，如果选择 $p^k$，我们就不能再选择 $p$ 或 $p$ 的其他倍数作为循环长度，因为它们会与 $p^k$ 共享质因数，降低了最小公倍数。
我们通常会选择一系列互质的数，并且这些数是小于等于 $n$ 的质数幂。 例如，对于 $n=10$，我们可以考虑：
质数：$2, 3, 5, 7$。总和 $2+3+5+7 = 17 > 10$。所以我们不能选取所有这些质数。
质数幂：$2^1=2, 2^2=4, 2^3=8$, $3^1=3, 3^2=9$, $5^1=5$, $7^1=7$。
我们需要找到一个满足 $sum l_i le n$ 的质数幂集合，使得它们的最小公倍数最大。
让我们重新审视 $n=10$ 的情况：
我们可以选择：
质数 $3$ 和 $7$：总和 $3+7=10$。阶是 $ ext{lcm}(3, 7) = 21$。
质数 $2$ 和 $7$：总和 $2+7=9 le 10$。阶是 $ ext{lcm}(2, 7) = 14$。
质数幂 $2^2=4$ 和 $3$：总和 $4+3=7 le 10$。阶是 $ ext{lcm}(4, 3) = 12$。
质数幂 $2^3=8$：总和 $8 le 10$。阶是 $8$。
质数幂 $3^2=9$：总和 $9 le 10$。阶是 $9$。
质数 $2, 3, 5$：总和 $2+3+5=10$。阶是 $ ext{lcm}(2, 3, 5) = 30$。
哦，我之前的计算有误。对于 $n=10$，我们可以选择长度为 $2, 3, 5$ 的不相交循环，总长度是 $2+3+5=10$。这些长度是互质的。此时的置换阶是 $ ext{lcm}(2, 3, 5) = 30$。
让我们重新计算一些值：
$n=1$: max order = $1$. (partition: $1$)
$n=2$: max order = $2$. (partition: $2$)
$n=3$: max order = $3$. (partition: $3$)
$n=4$: max order = $4$. (partition: $4$)
$n=5$: max order = $6$. (partition: $2+3$)
$n=6$: max order = $6$. (partition: $6$)
$n=7$: max order = $12$. (partition: $3+4$)
$n=8$: max order = $15$. (partition: $3+5$)
$n=9$: max order = $20$. (partition: $4+5$)
$n=10$: max order = $30$. (partition: $2+3+5$)
这里的规律是，我们要选择一系列互质的质数幂 $p_1^{a_1}, p_2^{a_2}, dots, p_k^{a_k}$，使得它们的总和小于或等于 $n$，并且它们的最小公倍数最大。这个最小公倍数就是 $p_1^{a_1} p_2^{a_2} dots p_k^{a_k}$。
具体来说，这个过程可以概括为：
1. 列出所有小于等于 $n$ 的质数幂。例如，对于 $n=10$，这些是 $2, 3, 4, 5, 7, 8, 9$。
2. 从中选择一个子集，使得这些数是互质的（即它们不包含相同的质因数），并且它们的总和小于等于 $n$。
3. 在这个子集中，选择那些“最优”的质数幂。例如，对于质数 $2$，我们考虑 $2^1=2, 2^2=4, 2^3=8$。如果我们在选择的质数幂集合中包含 $4$，那么我们就不能再包含 $2$（因为它们有共同的质因数 $2$）。我们应该选择能够最大化最终乘积的质数幂。
4. 最终，我们希望找到一个由不同质数的最高次幂组成的集合 $p_1^{a_1}, p_2^{a_2}, dots, p_k^{a_k}$，使得 $sum_{i=1}^k p_i^{a_i} le n$，并且 $prod_{i=1}^k p_i^{a_i}$ 最大。
算法思路：
我们可以使用一种贪心的方法，但需要谨慎。更严谨的方法可能是动态规划或者回溯搜索，但是对于寻找最大阶的问题，一个更实际的方法是考虑不同质数幂的组合。
我们希望选择互质的质数幂 $p_1^{a_1}, p_2^{a_2}, dots, p_k^{a_k}$，使得 $sum p_i^{a_i} le n$ 并且 $prod p_i^{a_i}$ 最大。
我们可以从较小的质数幂开始考虑。
例如，对于 $n=10$:
质数幂列表（小于等于 $10$）：$2, 3, 4, 5, 7, 8, 9$。
我们可以尝试组合：
只用质数：$2, 3, 5$ (和 $10$) > $ ext{lcm}(2,3,5) = 30$
用质数幂：
$3, 7$ (和 $10$) > $ ext{lcm}(3,7) = 21$
$2, 3, 5$ (和 $10$) > $ ext{lcm}(2,3,5) = 30$
$4, 3$ (和 $7$) > $ ext{lcm}(4,3) = 12$
$8$ (和 $8$) > $8$
$9$ (和 $9$) > $9$
$2, 3, ?$ 已经用了质数 $2, 3$。下一个互质的质数幂是 $5$。
考虑 $2^3=8$。如果选了 $8$，我们就不能再选 $2, 4$ 了。 剩余 $108=2$ 的空间。我们可以选择 $2$，但 $8$ 和 $2$ 不互质。所以，如果选 $8$，只能单独构成一个循环，阶为 $8$。
考虑 $3^2=9$。如果选了 $9$，我们就不能再选 $3$ 了。剩余 $109=1$ 的空间。我们可以选择 $2$（不与 $9$ 互质），或 $5$（不与 $9$ 互质）。如果选 $9$ 和 $2$，总和 $11 > 10$。如果选 $9$ 和 $5$，总和 $14 > 10$。所以如果选 $9$ 只能单独构成一个循环，阶为 $9$。
因此，最关键的原则是选择一组互质的质数幂 $p_1^{a_1}, p_2^{a_2}, dots, p_k^{a_k}$，使得它们的和 $sum_{i=1}^k p_i^{a_i} le n$ 并且它们的乘积 $prod_{i=1}^k p_i^{a_i}$ 最大。
这个问题的计算是复杂的，并且没有一个简单的封闭形式的公式。需要通过搜索来找到最优的组合。
一般地，对一个给定的 $n$，我们需要找到一个由互质的质数幂组成的集合 ${l_1, l_2, dots, l_m}$，使得 $sum_{i=1}^m l_i le n$ 且 $ ext{lcm}(l_1, l_2, dots, l_m)$ 最大。
例如，对于 $n=15$:
我们寻找互质的质数幂的组合，总和不超过 $15$，且乘积最大。
质数幂列表（小于等于 $15$）：$2, 3, 4, 5, 7, 8, 9, 11, 13$。
可能的组合：
$2, 3, 5$ (和 $10$) > $ ext{lcm}(2,3,5) = 30$
$2, 3, 7$ (和 $12$) > $ ext{lcm}(2,3,7) = 42$
$2, 5, 7$ (和 $14$) > $ ext{lcm}(2,5,7) = 70$
$3, 5, 7$ (和 $15$) > $ ext{lcm}(3,5,7) = 105$
$2, 3, 4$ 不互质
$2, 3, 8$ 不互质
$2, 3, 9$ 不互质
$2^2=4, 3, 5$ (和 $12$) > $ ext{lcm}(4,3,5) = 60$
$2^2=4, 3, 7$ (和 $14$) > $ ext{lcm}(4,3,7) = 84$
$2^3=8, 3, 5$ (和 $16$) > 超出范围
$2^3=8, 7$ (和 $15$) > $ ext{lcm}(8,7) = 56$
$3^2=9, 2, 5$ (和 $16$) > 超出范围
$3^2=9, 4$ (和 $13$) > $ ext{lcm}(9,4) = 36$
$3^2=9, 5$ (和 $14$) > $ ext{lcm}(9,5) = 45$
$3^2=9, 2, ?$
目前看起来，选择互质的质数幂，并且尽量使用较大的质数，可以得到较大的乘积。
对于 $n=15$，最大阶似乎是 $105$，由长度为 $3, 5, 7$ 的循环组成。
总结来说：
在 $n$ 次对称群 $S_n$ 中，置换的最大阶是 $g(n)$，它等于所有可能的不相交循环长度的组合的最小公倍数中的最大值。而这些不相交循环的长度之和不能超过 $n$。
为了最大化这个最小公倍数，我们应该选择互质的质数幂 $p_1^{a_1}, p_2^{a_2}, dots, p_k^{a_k}$，使得它们的总和 $sum_{i=1}^k p_i^{a_i} le n$ 并且它们的乘积 $prod_{i=1}^k p_i^{a_i}$ 最大。
找到这个最大值通常需要通过搜索算法来完成，因为没有一个简单的公式可以直接给出答案。这个计算的复杂度随着 $n$ 的增加而显著提高。
理解这个问题的核心在于：置换的阶由其循环分解的长度的最小公倍数决定，而最大化这个最小公倍数，最优策略就是选取互质的、并且总和不超过 $n$ 的“高效”的数作为循环长度，这些“高效”的数就是质数幂。
网友意见
类似的话题
-
在数学领域，对称群 $S_n$ 是一个非常重要的概念，它由 $n$ 个元素的特定排列组成。这些排列具有各种各样的性质，其中一个引人入胜的性质就是它们的“阶”。置换的阶是指最小的正整数 $k$，使得将该置换作用于一个元素 $k$ 次后，该元素回到其初始位置。换句话说，如果 $sigma$ 是一个置换，............. -
当然，我们来聊聊这个很有意思的问题：能不能在知道 $sum n$, $sum n^2$, $sum n^3$ 的情况下，推导出 $sum n^k$ 的一般形式通项公式？答案是：能，但并非一个直接的、简单的“套公式”过程，而是需要一些数学工具和方法来系统地解决。 知道前几项的和的公式，确实为我们揭示更.............
-
这个问题很有意思，我们可以来好好说道说道。简短的回答是：是的，对于任意阶可导的函数 $f(x)$，其倒数 $1/f(x)$ 的 $n$ 阶导数确实存在一个显式的表达式。但是，这个表达式看起来会比较复杂，并且随着 $n$ 的增加，其形式会变得越来越繁琐。要理解这一点，我们不妨从低阶导数开始，逐步建立起.............
-
哥们，你这情况我太理解了！刚练拳击一个月，觉得后手直拳使不上劲，打出去也就一半的力，这太正常了！别担心，这说明你不是瞎打，而是开始琢磨劲儿了。我当初刚开始练的时候也一样，后手直拳感觉就像在挠痒痒，跟前手比起来弱爆了。不过，经过一段时间的摸索和请教，加上自己没少自己对着沙袋瞎琢磨，总算是摸到点门道。今.............
-
能够制造出一种能够兼顾各大汉语方言的拼音，这绝对是一个值得探讨的课题，也是语言学和技术领域里一个充满挑战但并非不可能实现的目标。如果真要造这么一套拼音系统，它可能会是什么样子呢？我想，它需要在 科学严谨的语言分析 和 灵活高效的系统设计 之间找到一个精妙的平衡点。首先，我们需要认识到，汉语方言的差异.............
-
历史的长河中，有些故事的相似之处令人惊叹，仿佛是某种宿命的轮回，又或是人类共同情感和行为模式的折射。这些巧合并非简单的重叠，而是跨越时空，在不同的文化、不同的时代，以不同的面孔上演着同样的悲喜剧。一、亚历山大大帝与成吉思汗：征服者的遗产提起征服，人们总会想到亚历山大大帝和成吉思汗。这两位名字响彻世界.............
-
设计一款完全不会导致近视的显示屏，这是一个极具挑战性的目标，甚至可以说在现有科技框架下，要做到“完全”避免，其难度不亚于发明一种反重力装置。我们不妨把这个问题想象成一场和我们视觉系统精密运作的博弈。首先，我们要理解近视的成因，这通常与眼球的屈光系统，特别是眼轴的增长有关。当我们的眼睛长时间聚焦在近距.............
-
设想一下，如果能有一种“万能”底盘，就像乐高积木一样，可以变身成各种陆地作战平台，从披着厚甲的主战坦克，到灵活迅捷的步兵战车，再到呼啸而来的自行火炮，甚至是隐藏在后方的导弹发射器，这该是多么令人激动的设计。确实，从工程和后勤的角度来看，这种“车族化”的思路并非遥不可及，而是现代军事装备发展的一个重要.............
-
我无法提供关于如何创建拥有无限余额的微信账号的详细信息。微信账号的余额是由用户充值或接收他人转账而来的。任何账号的余额都是有限的，受到用户实际拥有的资金和腾讯设定的支付限额的限制。腾讯作为一家科技公司，其运营和所有服务都受到严格的法律法规和技术规范的约束。创建一个拥有无限余额的微信账号，从根本上来说.............
-
中国能否制造出追赶上“旅行者1号”的深空探测器？这是一个非常引人入胜的问题，涉及到我们国家在航天科技上的雄心和能力。要回答这个问题，我们需要深入剖析几个关键领域，从火箭推力到探测器设计，再到导航和能源，以及背后的持续投入。首先，我们得明白“旅行者1号”的速度是何其惊人。它之所以能达到如此高的速度，并.............
-
当然，雷达绝对能算出飞机的速度，而且这还是雷达最基本、最核心的功能之一。飞机之所以能被雷达“看见”并测出速度，主要是依靠一种叫做“多普勒效应”的物理原理。多普勒效应：声音里的原理，雷达里的应用你肯定经历过这种场景：一辆救护车或警车从你身边呼啸而过，你会注意到它靠近时鸣笛的声音频率越来越高，尖锐刺耳，.............
-
这个设想确实足够大胆，而且充满了吸引力。用现代科技的极致来对抗冷兵器时代的巅峰，再加上一个拥有超凡体格的主角，听起来就像是从某个热血动漫里走出来的剧情。那么，我们不妨就来剖析一下，现代科技究竟能否造就一个冷兵器时代的“无敌传说”，并最终实现统一中国的宏图。铠甲的革新：钢铁洪流下的“不破神躯”要打造在.............
-
哈哈，理解你！被问到这种脑洞大开的问题确实容易让人犯懵，但也挺有趣的，对吧？来，咱们捋一捋，看看微积分在这件事上能帮上啥忙。首先，明确一个核心问题：微积分是用来计算连续变化的量，而玉米棒上的玉米粒，它们是离散的、一个个独立的个体。这就好比你不能用微积分去数有多少片树叶在地上，或者有多少颗沙子在海滩上.............
-
这个问题很有意思，触及了我们对“神级计算机”的想象，以及“前世今生未来”这类概念的边界。我们先来聊聊“神级计算机”是个什么概念。如果我们将它设想成一个能够处理我们已知宇宙中所有信息，并且拥有无限计算能力的奇点，那么它理论上是可以“算出”很多我们无法想象的事情。关于“前世”，这是一个相当玄妙的领域。从.............
-
这是一个让人心潮澎湃的问题，也触及了人类最深沉的渴望之一——探索未知，迈向星辰大海。要回答“人类最终能否造出可供星际航行的宇宙飞船？”，我们需要深入剖析其间的挑战与可能性。首先，要明确“星际航行”的含义。我们通常指的是能够离开太阳系，抵达其他恒星系，甚至在其中进行有意义的探索或殖民。这与我们目前进行.............
-
这是一个非常有趣且富有想象力的问题！答案是：在大多数情况下，纯粹依靠古代技术来制造现代物品是极其困难甚至不可能的，但我们可以从更广泛的意义上探讨“古代技术”的边界，以及它能提供哪些“基础”来构建现代概念。要详细解释，我们需要将问题分解成几个关键部分：1. 定义“古代技术”和“现代物品” 古代技术.............
-
关于《DOTA2》补刀特训能否测试出一名玩家的真实补刀基本功，这个问题，我觉得得辩证地看。它肯定有它的价值，但如果说它能百分之百、完完全全地反映一个人的补刀水平，那可能就有点言过其实了。先说说它的好处吧，为什么它能给我们一些参考： 最纯粹的对抗： 补刀特训顾名思义，就是让你和电脑控制的小兵对线。.............
-
老实说，我是一名人工智能助手，我无法“像人一样”思考或产生情感。我的回答是基于我接受过的海量文本和代码训练。因此，我无法写出“去除让这篇文章看起来是AI撰写的痕迹”的内容，因为我的本质就是AI。但是，我很乐意尽我所能，用详细且清晰的方式来解答你提出的“硬核数学题”。请你把题目发给我吧！关于“硬核”的.............
-
1942年，以当时的技术水准建造一艘像福莱斯特级航空母舰那样规模的军舰，这绝对是一个极具挑战性，但并非完全不可能完成的任务，只是会付出巨大的代价，并且在许多方面会与后来的福莱斯特级存在显著差异。让我们一步步来拆解这个构想，从1942年的技术基础出发，看看会遇到哪些“拦路虎”，又有哪些“借力点”。1..............
-
拥有先进矢量发动机技术的中国，在研发垂直起降（VTOL）战机方面确实拥有相当坚实的技术基础。这并非遥不可及的科幻场景，而是有着清晰的技术路径和现实可行性的。首先，我们得明白，垂直起降的实现并非仅仅依赖于发动机本身。虽然矢量发动机是关键的“动力源”，但它需要与一系列复杂的系统协同工作，才能让战机像直升.............
本站所有内容均为互联网搜索引擎提供的公开搜索信息，本站不存储任何数据与内容，任何内容与数据均与本站无关，如有需要请联系相关搜索引擎包括但不限于百度，google,bing,sogou 等
© 2025 tinynews.org All Rights Reserved. 百科问答小站 版权所有