2008/03/14 by Marc Deléglise, Deleglise, Marc, Jean-Louis Nicolas +3
Computer Science · Mathematics · #Advanced Mathematical Identities #Analytic Number Theory Research #Coding theory and cryptography #FOS: Mathematics #Number Theory (math.NT)
paper · doi:10.48550/arxiv.0803.2160
openalex publication_date 2008/03/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let \mathfrak Sn denote the symmetric group with n letters, and g(n) the maximal order of an element of \mathfrak Sn. If the standard factorization of M into primes is M=q1\al1q2\al2... qk\alk, we define ℓ(M) to be q1\al1+q2\al2+... +qk\alk; one century ago, E. Landau proved that g(n)=maxℓ(M)≤ n M and that, when n goes to infinity, log g(n) ∼ √(nlog(n)). There exists a basic algorithm to compute g(n) for 1 ≤ n ≤ N; its running time is \co(N3/2/√(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 1015. The main idea is to use the so-called \it ℓ-superchampion numbers. Similar numbers, the \it superior highly composite numbers, were introduced by S. Ramanujan to study large values of the divisor function τ(n)=∑d\dv n 1.