3

Given some permutation P of {1,2,3... N} we want to permute always by the same rule. What can be the largest K (number of permutation steps done) to obtain starting sequence?

Eg. If we do 1->2, 2->3, 3->4 ... N->1, K will be N (as it is the number of how many permutations we need to do to obtain the starting sequence). But this example is just easy. We can have much more intricate and complicated permutations, and I just actually want to find the "most complicated" one (and how much will be K in terms of size of sequence N).

Thanks!

verret
  • 6,691
qwerty_
  • 97

1 Answers1

7

This is Landau's function $g(n)$, the values of which are given at OEIS A000793; see Wikipedia for a description. The number you're looking for is the maximum of the least common multiple of the parts of a partition of $n$. For example, $7 = 4 + 3$ and $lcm(4, 3) = 12$, so a permutation of $7$ with cycles of length $4$ and $3$, such as $(1, 2, 3, 4)(5, 6, 7)$ in the cycle notation, has order 12. None of the other partitions of 7 have larger lcm, so for $n = 7$ you have $g(7) = 12$. For large $n$ we have

$$ \lim_{n \to \infty} {\ln g(n) \over \sqrt{n \ln n}} = 1 $$

which gives a sense of how quickly this function grows, something like $g(n) \approx e^{\sqrt{n \ln n}}$.

Michael Lugo
  • 22,354