Towers of Hanoi

I wanted to rant about recursion but apparently I have to save my pent-up anger about that until week 7.

Let's talk about that damn assignment Towers of Anne Hoy (or Reve's Puzzle).

It was pretty quick to design a fast algorithm (called Hanoi4):
For 1 cheese, just move it.
For 2 cheeses, operate move one to an intermediary, move the second, move the first back.
Then for n>2 cheeses, recursive, operate the 2 cheeses method, recursive again.

I found the optimal move counts up until ~20 cheeses on the internet, and found that this quickly-designed, rough algorithm only displayed the optimal number of moves up to about 5 cheeses.  Not very effective.

Refining the algorithm was not very difficult when I decided to actually look at the method stated in the problem: actually using the original code for the Towers of Hanoi in the algorithm.  Thus it was simple to perform:
Hanoi3 - if 1 cheese, move straight to destination
              else Hanoi3 (cheeses - 1) to an intermediary, move from source to destination, Hanoi3 again.
Hanoi4 - if 1 cheese, move straight to destination
              else Hanoi4 (cheeses/2) to an intermediary, Hanoi3(rest of cheeses on that stack), Hanoi4 again.
This solution displayed optimal move counts up to about 8 cheeses, but upon getting 9 cheeses, the solution would start being non-optimal again.

It was obvious that the proper number of cheeses to move to the intermediary, i, was not half the number of cheeses.  This prompted me to re-read the question once more for the clue.  Turns out it is ABSOLUTELY NECESSARY TO HAVE A FULL UNDERSTANDING OF THE PROBLEM BECAUSE THE ANSWER IS STARING YOU IN THE FACE.

FRAAAAAAAA-

How do you find the optimal solution?  Use the optimal moves.  How do you find the optimal number of moves? IT'S GIVEN TO YOU.

Then having found the optimal number of moves using an algorithm it's simple to find to optimal i number.  This turned out to be:
1,1,2,2,2,3,3,3,3,4,4,4,4,4...

Doesn't even take a cryptographer to figure out the pattern on that one.

FRAAAAAAA-