Newsgroups: sci.math
From: hoey@AIC.NRL.Navy.Mil (Dan Hoey)
Date: 8 Sep 94 21:01:27 GMT
Subject: Re: Tower of Hanoi Formula

micha...@ix.netcom.com (Michael O'Connor) asks:

> I know the algorithm for determining what disc in the Tower of
> Hanoi puzzle to move on a certain turn, but is there a way to find
> an algebraic formula, given the number of the turn, to find the
> number of the disc (where the lightest one is 1, second lightest is
> 2 so forth) for an infinite Tower of Hanoi puzzle, and if so, what
> is it?

I don't know if you consider this algebraic, but on turn K you move
disc

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

where Log[2] is the logarithm to the base 2, and XOr is the bitwise
exclusive Or of the two numbers written in binary.  This is just
another way of writing "one plus the number of trailing zeroes in the
binary representation of K", as simen.ga...@math.uio.no (Simen Gaure)
noted.

As pet...@cco.caltech.edu (Peter T. Wang) pointed out, each
odd-numbered turn moves disc 1 clockwise.  That is, you move it from
peg (K-1)/2 to peg (K+1)/2, modulo 3.  In general, odd-numbered discs
will be moved clockwise and even-numbered discs will be moved
anticlockwise, so on move K you move disc D(K) from peg
(K (-2)^(1-D(K)) + (-1)^D(K))/2 to peg (K (-2)^(1-D(K)) -
(-1)^D(K))/2,
modulo 3.

Does anyone have a proof that if you put disc I on disc J, then J-I is
odd?  It's funny, I watched a demonstration in which the even and odd
discs were colored differently, and colors alternated in each pile
throughout the procedure.  It took me a long time to just to notice
the phenomenon, but it's quite surprising when you think about it.

Dan Hoey
Hoey@AIC.NRL.Navy.Mil