### Permutations of maximum period

**Problem:**
Let *p* be a permutation on [*n*] = (1,...,*n*). We are considering operations on the
permutation group of order *n*. Let us define
*p*^{2} as *p* o *p*, and more generally
*p*^{k+1} as *p* o *p*^{k}. For instance,
if *n*=3 and *p* = (3,1,2), then *p*^{2} = (2,3,1)
is obtained by applying *p* twice, and *p*^{3} = (1,2,3) = *I*. We shall use
the letter *I* to denote the identity permutation: *I* = (1,2,...,*n*). Then the period is the minimum integer *k* > 0
such that *p*^{k} = *I*.

For a given *n*, we are interested in finding permutations with maximum period.
Let us note that the permutation (2,3,4,...,*n*-1,*n*,1) always has a period of *n*.
As a consequence, the following permutation with *n*=12 with 3 cycles (sub permutations) defined as
*p*=(2,3,1|5,6,7,4|9,10,11,12,8) has a period 3 x 4 x 5 = 60. This is true because the three
sub-periods - 3, 4 and 5 - are mutually prime. In that case the period is the product of the sub-periods. More generally,
if we had *m* cycles, the period could be as large as *(n/m)*^{m}. This expression attains its
maximum when *m* = 0.368 x *n* (0.368 = 1/e). In other words, the maximum is achieved when we
have about *m*/3 cycles with mutually prime periods, regardless of *n*. The maximum period is then of the order
*e*^{n/e} < *n*!

Is my reasoning correct? I am trying to create random permutations to encrypt a string *s*,
in the context of fraud detection. The idea is that permutations with large periods, if well chosen,
will be very difficult to identify. Let's say that *p* has an even period *v*. Then if you only know
*p*^{v/2} but not *p* nor *v*, it is almost impossible to identify *p* and *v*. Once a
hacker knows *p* and *v*, he can easly retrieve the original string *s*.

**Contributions:**

- From David Bernier:
This is related to Landau's function *g(n)* , *n*
being the number of elements in the set getting permuted.

- From Derek Holt:
I have a C program to identify permutations of
maximum order. For example, for *n*=10000, the maximum order is

317*313*311*307*293*283*281*277*271*269*263*257*251*241*239*233*229*227*
223*211*199*197*193*191*181*179*173*167*163*157*151*149*139*137*131*127*
113*109*107*103*101*97*89*83*79*73*71*67*61*59*53*47*43*41*37*31*29*23*
19*17*169*121*49*25*81*64 =

837248314781153836222627527908638519798608214039954646068895157070382622
91218453286312511300740953193197240510692638318426636506681182400