Landau's function for one million billions Marc Deleglise Jean Louis Nicolas and Paul Zimmermann

Landau's function for one million billions Marc Deleglise, Jean-Louis Nicolas and Paul Zimmermann ? February 27, 2008 A Henri Cohen pour son soixantieme anniversaire. Abstract Let Sn denote the symmetric group with n letters, and g(n) the max- imal order of an element of Sn. If the standard factorization of M into primes is M = q?11 q?22 . . . q?kk , we define ?(M) to be q ?1 1 + q?22 + . . .+ q?kk ; one century ago, E. Landau proved that g(n) = max?(M)≤n M and that, when n goes to infinity, log g(n) ? p n log(n). There exists a basic algorithm to compute g(n) for 1 ≤ n ≤ N ; its running time is O “ N3/2/ √ logN ” and the needed memory is O(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 ?-superchampion numbers. Similar numbers, the superior highly composite numbers, were introduced by S. Ramanujan to study large values of the divisor function ? (n) = Pd |n 1.

• abstract let


• called ?-superchampion numbers


• satisfying


• numbers


• qi also


• function ?


• let pk


• large prime


• b? greater than


• minimizes ?