DISQUS

[got truncated?] Ah, I used an incorrect constraint of sum(cycle-lengths)=26 instead of sum(cycle-lengths)

Ah, I used an incorrect constraint of sum(cycle-lengths)=26 instead of sum(cycle-lengths)

I believe there is a slight error in your calculations. The problem is right on the "threshold length" of 4. The maximum LCM of a length four partition of 26 is 1155, corresponding to the partition [11,7,5,3], not 1260. The set you specified [4,5,7,9] isn't a partition of 26; it adds up to 25. However, you can insert a 1 in the set, leaving the lcm unaffected which gives you the max lcm of 1260 for length 5 and beyond.

I solved the problem on a lazy afternoon last year, and was curious about its origins and other solutions, and I came across your page. The origin as far as I can tell is an ancient 70s paper entitled "Control Structure Abstractions of the Backtracking Programming Technique". They called the problem "Malicious Secretary" (IMHO, a much better title than the misleading "Korn Shell")