# The Towers of Hanoi

This puzzle dates from 1883 when it was published in Paris by a certain N Claus de Siam of the College of Li-Sou-Stian. The French involvement in IndoChina at that time expalins the names. In fact this name and college are anagrams of Lucas d'Amiens who was teaching at the Lycée Saint-Louis. The inventor of the puzzle was then the French mathematician Eduard Lucas who is best known for his results in number theory. In particuar he studied the Fibonacci sequence and the associated Lucas sequence named after him.

The "legend" which accompanied the game stated that in Benares in the reign of the Emperor Fo Hi there was a temple, with a dome which marked the centre of the world, beneath which priests moved golden discs between diamond needles, a cubit high and as thick as the body of a bee. The discs could be moved between needles, but only on the condition that no disc could be on top of a smaller one.

God placed 64 gold discs on one needle at the creation and it was the priests' task to move all the discs to one of the other needles.

It was claimed that when they had completed the task, needles, tower, temple and Bramins would crumble away into dust and with a thunderclap the Universe would end.

Since it would have taken them at least $2^{64} - 1$ moves, which even at one move a second (and no mistakes!) would take 590 trillion years, that has never been tested.