The $k$th move of the Tower of Hanoi 
In the tower of Hanoi $x,y,z$ are the positions and we are to move 10 disks from $x$ to $y$. What are the 128th and 768th moves?
(A) $x\to y$ and $x\to z$
(B) $x\to z$ and $z\to x$
(C) $x\to z$ and $z\to y$
(D) $x\to y$ and $z\to y$

I know the total number of moves is $2^{10}-1=1023$. For move 128 I did $128\bmod3=2$, which gave me nothing at all… please help me out!
 A: Try listing out the moves for one, two and three discs:
1  2  3  4  5  6  7
XY
xz XY zy
xy xz yz XY zx zy xy

There is a pattern here that allows us to get the sequence of moves for the next number of discs:


*

*We copy the whole sequence for the previous number of discs, but replace y with z and vice versa.

*We append xy.

*We append the previous sequence again, but replace x with z and vice versa.


This allows us to find the source and destination pegs of the $k$th move of the $n$-disc sequence:


*

*Initialise the source and destination pegs as x and y respectively. Write out $k$ as an $n$-bit binary word (zero-padded on the left) and place a pointer on the least significant 1.

*Stop and return the source and destination pegs if the pointer is on the most significant bit. Otherwise, move the pointer one place left. If it lands on a 0, replace y with z and vice versa; if it lands on a 1, replace x with z and vice versa. Repeat step 2.



Here, $n=10$, so the set-ups for finding the 128th and 768th moves are as follows:
0010000000 = 128
  ^ xy
 ^ xz
^ xy -> 128th move is x -> y
1100000000 = 768
 ^ xy
^ zy -> 768th move is z -> y

Hence the correct answer is (d).
By the way, here's the algorithm for the 72nd move:
0001001000 = 72
   |  ^ xy
   | ^ xz
   |^ xy
   ^ zy
  ^ yz
 ^ zy
^ yz -> 72nd move is y -> z

