Pensieve Header: Computing the maximal order of a permutation in S_n.

$RecursionLimit  = 10000;
MaxOrder[n_] := MaxOrder[n, 2];
MaxOrder[n_, p_] /; p>n := 1;
MaxOrder[n_, p_] := MaxOrder[n, p] = Max[Table[
p^k*MaxOrder[n-(p^k /. 1 -> 0), NextPrime[p]],
{k, 0, Floor[Log[p,n]]}
]]

Print[# -> {m=MaxOrder[#], FactorInteger[m]}]& /@ Range[20];

Timing[{m=MaxOrder[1000], FactorInteger[m]}]

ListPlot[Log[10, MaxOrder[#]]& /@ Range[1000]]

ListPlot[(Log[MaxOrder[#]] / (Sqrt[#]Log[#]))& /@ Range[2,1000]]

Log[2]/2 // N

n=1000; Log[MaxOrder[n]] / (Sqrt[n]Log[n]) // N