What is the mean maximal cycle length of the permutations in S(n)?

Question

Pseudo-random number generators with large periods can be constructed by XORing the outputs of the orbits of several distinct permutations of, say, 16-bit numbers. One would seed each orbit with an element lying in a long cycle to achieve a large total period with as few distinct permutations as possible. The mean maximal cycle length provides a rough measure of how many 16-bit permutations on average would be needed to achieve, say, a 256-bit total period if we seed each orbit with a number lying in a cycle of the maximal length for the permutation. We disregard total period reduction caused by cycle lengths not being coprime.

Answer 1

The maximal cycle length of a permutation follows the same statistic as the maximal prime divisor of an integer (suitable scaled): The probability that the largest cycle of a random permutation in $S_n$ is $\leq n/\alpha$ is $\sim\rho(\alpha)$, where $\rho$ is the solution of the difference-differential equation $$ u\rho'(u) = -\rho(u-1),\quad \rho(u)=1\mbox{ for }u\in[0,1]. $$ This was essentially proven by Gontcharov in 1944, but being written in Russian and having a non-descript title ("On the field of combinatory analysis"), this article has been largely ignored.

Answer 2

The mean length $L_n$ of the longest cycle in a random permutation uniformly chosen from $S_n$ is asymptotically $$\sim \lambda n$$ where $\lambda \approx 0.62433\cdots$.

The references are (thanks to Gerry Myerson):

(1) Solomon W. Golomb, Research Problem 11: Random permutations, Bull. Amer. Math. Soc. 70 (1964), p. 747.

(2) MR0195117 (33 #3320), Shepp, L. A.; Lloyd, S. P., Ordered cycle lengths in a random permutation, Trans. Amer. Math. Soc. 121 1966 340–357.

A wonderful reference for questions of this type is Flajolet and Sedgewick's Analysis of Algorithms text.