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] = (
++it;
Max[Table[
p^k*MaxOrder[n-(p^k /. 1 -> 0), NextPrime[p]],
{k, 0, Floor[Log[p,n]]}
]]
)

it=0; {MaxOrder[10000], it}

FactorInteger[83724831478115383622262752790863851979860821403995464606889515707038262291218453286312511300740953193197240510692638318426636506681182400]

Table[Prime[k], {k, 70}]

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

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=10000; Log[MaxOrder[n]] / (Sqrt[n]Log[n]) // N

Table[MaxOrder[n], {n, 20}]