THE EQUATION FOR SOLVING LUCAS' TOWER

THE EQUATION FOR SOLVING LUCAS' TOWER

One of the many interesting things about Lucas’ Tower is that there is an equation that will tell you the minimum number of steps you can take to complete the puzzle - the optimal solution. Since you can make a Lucas’ tower with any number of disks (in theory), that number is determined by an explicit equation: 2^n-1, with n being the number of disks. In your case, with eight disks, that means the fewest number of moves possible to complete the puzzle is 2^8-1, or 255. 


That formula is actually what ties the Tower to the legendary Hitchhiker’s Guide to the Galaxy. It has to do with the number 42, which as anyone who’s read, seen, or listened to an adaptation of the Guide knows, is the answer to the Ultimate Question of Life, The Universe, And Everything! 

We’ve found that eight disks make for a satisfying but solvable puzzle, but do you remember the number in the mythical temple of the tower’s origin story? (just so you don’t have to go back and look that up, it’s 64). Now, as computer scientist Ian Parberry discovered, if you plug 64 disks into the solution equation, you find that according to that story, the puzzle that will bring about the end of the world when solved will take the monks 2^64−1 moves to complete. If they move a disk once per second (they’re monks who have spent their lives moving the disks, so they’re probably pretty good at it), that will take them 5.85x1011 (585 billion) years. While the precise age of the universe isn’t known, cosmologists believe it’s around 13.77 billion years old. And if you divide 585 billion by 13.77 billion you’re in the ballpark of - you guessed it! - 42. Maybe Douglas Adams was onto something after all.


How about the strange death of Édouard Lucas, inventor of the puzzle? Lucas was a renowned French mathematician, known for his work on number theory; among other things, he coined the term “Fibonacci sequence.” But poor Édouard died in what’s been called an “absurd accident,” all because he picked the wrong place to eat dinner. 


One night in 1891, Lucas was enjoying a fancy banquet at the French Society for the Advancement of Science, when a passing waiter dropped an armful of plates. As the crockery shattered, a fragment rocketed up and scratched Édouard Lucas on the cheek. A minor cut, no problem, right? A few days later, the scratch became infected, and one of the greatest mathematical minds of the 19th century passed away, from what is now an easily curable case of erysipelas.


Poor Édouard is gone, but his legacy lives on! Our Lucas’ Tower is a classic, compelling puzzle, with a clever but achievable solution. We hope you enjoy it.

Back to blog