[seqfan] Reverse Tower of Hanoi

Daniel Joyce hlauk.h.bogart at gmail.com
Sun Oct 19 19:50:30 CEST 2014


Reverse tower of Hanoi

The same number of moves but the rules now are
any smaller disk cannot be put on a larger disk
when moving one stack of disks one at a time
to another peg.


------5|------   |         |
 -----4|-----    |         |
  ----3|----     |         |
   ---2|---      |         |
    --1|--       |         |
--------------------------------
#1     #2     #3
peg    peg    peg


The stack of 5 disks on the first peg can be moved
one at a time to either peg #2 or peg #3 never placing
a smaller disk on a larger disk.

For a 5 stack the number of moves is 2^5-1 but the total
sum of those moves is sequence # A000337 omitting the
first term of (0)

For each stack 1 through 15 the total sum of each stack
moved one at a time is shown below.

1,5,17,49,129,321,769,1793,4097,9217,20481,45057,98305,212993,458753...

For a 5 disk stack the total sum of pieces moved is the
5th term 129 above.

There is no mention of the Tower of Hanoi in A000337.

Just like A000295 is the total sum of moves for each
(n) stack in the Tower of Hanoi only placing smaller on
larger disks for each move --

1,4,11,26,57,120,247,502,1013,2036,4083,8178,16369,32752,65519...

Where 5 stack has a total sum of 57 pieces moved.


More interesting, is there a relation to the two
different sequences?

Cheers,

Dan


More information about the SeqFan mailing list