Let ${ \mathfrak S}_n$ denote the symmetric group with $n$ letters, and $g(n)$ the maximal order of an element of ${ \mathfrak S}_n$. If the standard factorization of $M$ into primes is $M=q_1^{ \al_1}q_2^{ \al_2}... q_k^{ \al_k}$, we define $\ell(M)$ to be $q_1^{ \al_1}+q_2^{ \al_2}+... +q_k^{ \al_k}$; one century ago, E. Landau proved that $g(n)=\max_{ \ell(M)\le n} M$ and that, when $n$ goes to infinity, $\log g(n) \sim \sqrt{ n\log(n)}$. There exists a basic algorithm to compute $g(n)$ for $1 \le n \le N$; its running time is $\co(N^{ 3/2}/\sqrt{ \log N})$ and the needed memory is $\co(N)$; it allows computing $g(n)$ up to, say, one million. We describe an algorithm to calculate $g(n)$ for $n$ up to $10^{ 15}$. The main idea is to use the so-called { \it $\ell$-superchampion numbers}. Similar numbers, the { \it superior highly composite numbers}, were introduced by S. Ramanujan to study large values of the divisor function $\tau(n)=\sum_{ d\dv n} 1$.
Categories: math.NT