Landau's function for one million billions (Q1026978)

The maximal order \(g(n)\) of an element of the symmetric group over \(n\) elements has been considered by \textit{E. Landau} in [Arch. Math. Phys. (3) 5, 92--103 (1903; JFM 34.0233.02)] and has been subsequently the subject of several investigations. This excellent paper treats very efficiently the problem of computing \(g(n)\). The algorithm produced is practically extremely fast, though the authors do not know how to bound its maximal complexity. It relies on a very refined combinatorial analysis of the structure of the numbers \(g(n)\). Getting the average complexity of this algorithm is an open question, and not an obvious one as this algorithm relies of \textit{\(\ell\)-superchampion numbers} that may resist to this kind of analysis.