3
$\begingroup$

This computational question is based on this question of combinatorics on the Mathematics.SE.

A permutation of a list of $n$ items, $\{ 1, 2, \ldots, n \}$, is of course a reordering of them. If one applies the same permutation again and again, one must ultimately return to the original list. For instance if you have 15 items and permute merely $1 \to 2, 2 \to 1$ (often written as the cycle $(12)$) then the number of permutations (the length of the cycle) is $2$. If instead you have the permutation $1 \to 2, 2 \to 3, 3 \to 1$ or (123), then you need three such steps. Permutations can be written as factored into cycles, for instance for 9 items: $(1345)(26)(78)(9)$, where the lone item $(9)$ is never changed. (Conventional notation omits such lone items.)

The maximum number of steps needed to return to the original ordering over all possible permutations is described by the Landau function of the number of elements $n$. The Landau function is the largest least common multiple (LCM) of any IntegerPartition of $n$:

Landau[n_] := Max[LCM @@@ IntegerPartitions[n]]

(It is sequence A000793 in the OEIS.)

Unfortunately, my simple code is extremely slow, and limits its use to $n<70$ or so depending upon computational resources and time:

Timing[Landau[70]]

(*

{33.4142, 6126120}

*)

Is there a significantly faster algorithm for computing this function in Mathematica that would allow it to be used for much larger $n$?


I urge Wolfram Research to add Landau's function to the function calls in Mathematica.

$\endgroup$
4
$\begingroup$

https://oeis.org/A000793 already provides faster Mathematica code for this sequence:

b[n_, i_] := 
  b[n, i] = Module[{p}, p = If[i < 1, 1, Prime[i]]; 
    If[n == 0 || i < 1, 1, 
     Max[b[n, i - 1], Table[p^j*b[n - p^j, i - 1], {j, Log[p, n]}]]]];

a[n_] := b[n, If[n < 8, 3, PrimePi @ ⌈1.328 * Sqrt[⌊n*Log[n]⌋]⌉ ] ];

a[500]
715657920159093382270800

Credited to Jean-François Alcover, and Alois P. Heinz, with mild reformatting of my own.

$\endgroup$
  • $\begingroup$ Ah... just a matter of finding faster existing code. Thanks so much. Accept. $\endgroup$ – David G. Stork May 31 '17 at 23:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.