← RoseCode

ROSECODE 148

Towers of Hanoi revisited

Philippe_57721 · Programming ·

In a game of Hanoi with n disks, we can consider the layout after m moves as a permutation of {1, ..., n}

For instance, with 15 disks, after 12345 moves the layout is:
  • Peg-1 : 7 8 9 10 11 12 15
  • Peg-2 : 1 4 5 6 13 14
  • Peg-3 : 2 3

corresponding to permutation : 7 8 9 10 11 12 15 1 4 5 6 13 14 2 3

The index of this permutation in lexicographic order is 563569656784

With 70 disks, what is the index of the permutation corresponding to the layout after 123456789101112131415 moves?

[My timing: < 100 ms]