Newsgroups: sci.math
From: hoey@AIC.NRL.Navy.Mil (Dan Hoey)
Date: 9 Sep 1994 15:40:39 GMT
Subject: Re: Tower of Hanoi Formula

micha...@ix.netcom.com (Michael O'Connor) asked for a formula for
which disc to move on a given turn K in the Towers of Hanoi.
Yesterday I gave it as:

  D(K) = Log[2] ( 1 + ((K-1) XOr K ))

and I gave expressions (mod 3) for the discs to move:

  From peg (K (-2)^(1-D(K)) + (-1)^D(K))/2
    To peg (K (-2)^(1-D(K)) - (-1)^D(K))/2.

Thinking about it, I was able to see that the last is much too
complicated.  Using the fact that 2==-1 (mod 3), and swapping pegs 1
and 2, the rule is:

  From peg K + (-1)^D(K)
    To peg K - (-1)^D(K).

This allows us to express the Hanoi algorithm extremely simply: Move a
disc between pegs K+1 and K+2 (mod 3) in the unique legal direction.

Also, this can be used to prove the alternating-color property, by
noticing that after move K the top disc of peg k+2 (mod 3) will be
even, and the others will be odd (counting the peg number if there is
no disc on it).

Dan Hoey
Hoey@AIC.NRL.Navy.Mil