Searching for hidden treasure

\text{Courtesy of Forrest Fenn}

We want to talk about treasure hunt in mathematics. But first, focus on a treasure hunt that involves a treasure chest that is similar to the one shown above.

An ornate Romanesque 10-inch by 10-inch treasure chest weighing about 40 pounds that is filled with gold coins and other gems is “hidden in the Rocky Mountains, somewhere between Santa Fe and the Canadian border at an elevation above 5,000 feet. It’s not in a mine, a graveyard or near a structure,” according to Forrest Fenn, a millionaire art dealer in his 80s who lives in Sante Fe, New Mexico. His self-published memoir included a cryptic poem that describes the location of the treasure box.

Nobody knows for sure if this is not just a hoax. Eight years after the publication of the poem, tens of thousands of treasure hunters have flocked to locations in the vast Rocky Mountain region looking for Fenn’s treasure box, which is thought to be worth over $1 million. Four of these treasure hunters had died while searching. The most recent death occurred in the summer of 2017.

In fact, the wife of another treasure hunter who died while searching for Fenn’s hidden box told NBC News that the hunt was “ludicrous” and “should be stopped.” Here’s another piece from NPR that profiles Forrest Fenn and his treasure box.

The payout of this treasure hunt, if successful, is only in the one to two million dollars range. The Rocky Mountains stretch more than 3,000 miles (4,800 km) from the northernmost part of British Columbia, in western Canada, to New Mexico, in the Southwestern United States. The odds of finding the treasure seem long. How would that compare with the odds of winning the Powerball jackpot, which are one in 292 millions? The size of the Powerball jackpot winning is usually in the range of hundreds of million dollars. It seems that buying a Powerball ticket may be a better bet – much larger payout, virtually no chance of dying as a result of buying the ticket.

We do not advocate for buying Powerball tickets or other lottery tickets. The comparison serves to illustrate the ludicrousness of searching for Fenn’s box. To some, like the wife of one of the hunters who died, the hunt may seem ludicrous to the point that buying a Powerball ticket makes more sense.

From a financial standpoint and safety standpoint, hunting for the hidden box of Fenn makes no sense. Of course, there is another way to look at the hunt. For some, it is all about the thrill of the chase, as the title of Forrest Fenn’s book suggests.

In mathematics, the most famous chase may well be the one set off by Pierre de Fermat. Pierre de Fermat claimed in 1637 that no positive integers a, b and c satisfies the equation \displaystyle a^n+b^n=c^n for any integer n greater than 2 (this statement was later called Fermat’s Last Theorem). He scribbled in the margin of his own copy of the Greek text Arithmetica by Diophantus commenting that a proof of this statement was too large to fit in the margin. The following image shows the page from the 1670 edition of Diophantus’ Arithmetica.

The page in the 1670 edition of Diophantus’ Arithmetica that shows Observatio Domini Petri de Fermat (Wikipedia)

The above image is from an edition that came after the death of Fermat in 1665. So it is not from the book with Fermat’s scribbles. This 1670 edition did incorporate the commentary by Fermat (see the part that says Observatio Domini Petri de Fermat).

The claim made by Fermat set off a search for a proof that lasted 358 years. The first successful proof was presented by Andrew Wiles in 1994 and formally published in 1995. With the fact that the solution took three and a half centuries to emerge, it would be obvious that this is a very difficult mathematical problem. Indeed, the Guinness Book of World Records made the obvious official by declaring Fermat’s last theorem as the “most difficult mathematical problem”, another reason being that it had the largest number of unsuccessful proofs.

The mathematical treasure hunts, unlike the one for Forrest Fenn’s box, are not in the physical realm but in the realm of ideas. The payout is not in the form of gold coins or gold nuggets. A more appropriate metaphor is the climbing of Mount Everest. Why climb a tall mountain? Because it is there and it is tall. The mathematicians work on hard problems because they are hard and no one else had solved them before.

Andrew Wiles’ proof was built on the work of all the giants that came before (and all the unsuccessful proofs that came before). Fermat’s last theorem, as an unsolved problem throughout the centuries, stimulated the development of algebraic number theory in the 19th century and the proof of the modularity theorem in the 20th century. The mathematical treasure hunts tend to blaze new trails.

Some mathematical treasure hunts even have $1 million prize attached. The Millennium Problems are sponsored by the Clay Institute, a list of 6 unsolved problems with a $1 million prize money each (it used to be a list of 7 problems). Also see here. Needless to say, these problems are difficult problems. Riemann hypothesis, one of the problems, was formulated in 1859! Any progress in these problems will expand our views of the mathematical world and the physical world.

The hunt for Fenn’s treasure box could very well take years or even decades. Stepping on a loose stone in a steep hill in the wilderness may be fatal. This hunt will end, if successful, in the retrieval of the treasure box and nothing more. The treasure hunt of the mathematical kind can lead to new vista in the mathematical world as well as new ways of looking at the physical world. The mathematical treasure hunt can be done in the comfort of one’s home or office, or in any other relaxed environment such as a park. The mathematical treasure hunts, in some cases, can also end in a million dollar payout.

\text{ }

\text{ }

\text{ }

Dan Ma math

Daniel Ma mathematics

\copyright 2018 – Dan Ma

Writing digits of a large prime in a highway

A highway of prime digits

The digits in the above picture of a highway are the first digits of the largest prime number discovered almost two weeks ago on December 26, 2017. The number has over 23 million decimal digits (23,249,425 to be precise). If writing 5 digits per inch, all the digits of this prime number would cover a stretch of highway over 73 miles in length! That’s only 5 miles under the distance of three marathons.

The digits would also fill an entire shelf of books for a total of 9,000 pages!

Though the previous largest prime number is plenty large, it digits would only cover a stretch of highway about 70.5 miles long! So the new discovery would cover a further distance of about 2.5 miles.

The brand new largest prime is the number 2 raised to 77,232,917 less 1. Prime numbers that are generated in this fashion are called Mersenne primes, in honor of the French monk Marin Mersenne, who studied these numbers more than 350 years ago. The previous largest known prime number is also a Mersenne prime.

Indeed, there is a large worldwide community of volunteers who devote their free time in hunting for Mersenne primes, called Great Internet Mersenne Prime Search (GIMPS for short). In fact, anyone who has a computer and has Internet access can do it. It does not take special mathematical expertise. It takes patience. The discoverer of this latest record, Jonathan Pace, is a GIMPS volunteer for over 14 years. The GIMPS site would have all the information to get started for anyone who wants to join the search.

Why the fascination with prime numbers? Some people think of finding the next largest known prime number as Climbing Math Everest. The best thing about this Everest is that there is another Everest to conquer after one is successfully scaled. Euclid proved over 2,000 years ago that there are infinitely many such Everest. Theoretically we know there is no such thing as the largest prime. When we speak of the largest prime, it is only the largest prime number verified by the computing resource that is currently available.

Now we know that the current world record of the largest prime number is 2^{77,232,917}-1, which has 23,249,425 decimal digits. This Mount Everest was scaled in December 2017. Volunteers at GIMPS are hard at work in trying to find the next Mount Math Everest.

The theoretical aspects of prime numbers are even taller Math Everest than the computational ones. Many problems involving prime numbers are easy to state but hard to prove. Some have withstood attempts at solving for centuries (twin prime conjecture and Goldbach conjecture come to mind).

Prime numbers have real world practical implications too. Online commerce is made possible by the use of prime numbers in keeping information secure. Though the large prime numbers used in cryptography are much smaller in comparison to the largest prime number discovered recently. Who knows. It could be possible that prime numbers with millions of digits could find practical use in the future.

\text{ }

\text{ }

\text{ }

Dan Ma math

Daniel Ma mathematics

Dan Ma prime numbers

\copyright 2018 – Dan Ma

Making use of Markov chains

A stochastic process describes a system that changes in values over time. Typically in order to predict what state the process will be in in the future, the past states may have to be used as input. A Markov chain is a stochastic process in which the predictions for the future of the process are based solely on its present state. Thus a Markov chain only remembers the current step and not the steps in the past (this is called the memoryless property). Markov chains, and stochastic processes in general, have wide applications in many fields. In this post, we highlight two fun probability problems that can be solved using Markov chains.

Figure 1 – toss a coin until seeing 3 consecutive heads

The first problem is demonstrated by the above diagram – tossing a fair coin until the appearance of k consecutive heads. How many tosses are required on average to accomplish this goal? In Figure 1, it takes 17 tosses to get 3 consecutive heads. The number of tosses is random. Sometimes it takes more tosses and sometimes it takes fewer tosses. In general, what is the expected number of tosses to get k consecutive heads? For 3 consecutive heads, the answer is 14. To get 4 consecutive heads, it takes on average 30 tosses.

How does coin tossing becomes a Markov chain? Let’s take the goal of 4 consecutive heads. As the coin is tossed, we are interested in 5 different states – 0, H, HH, HHH and HHHH. The state 0 refers to the beginning of the experiment or that the current toss is a Tail. The other four states refer to the most recent consecutive heads that have appeared. In each toss of the coin, the process is in one of these 5 states. The next state depends on the current state and does not depend on the past states, making this a Markov chain. The following is the transition probability matrix.

    \mathbf{P} =       \bordermatrix{ & 0 & \text{1=H} & \text{2=HH} & \text{3=HHH} & \text{4=HHHH} \cr        0 & 0.5 & 0.5 & 0  & 0 & 0 \cr        1 & 0.5 & 0 & 0.5 & 0 & 0 \cr        2 & 0.5 & 0 & 0 & 0.5 & 0 \cr        3 & 0.5 & 0 & 0 & 0  & 0.5 \cr        4 & 0 & 0 & 0 & 0  & 1 \cr   } \qquad

The matrix captures the probabilities of how the process transitions from one state to the next. For example, if the current state is H, then the process will go to HH (with probability 0.5) or go to 0 (with probability 0.5). Example 2 in this blog post in a companion blog shows how to use this matrix to compute the expected number of steps it takes to go from state 0 to the state HHHH. The answer is 30.

If the goal is to toss the coin until obtaining 3 consecutive heads, then the states of the process would be 0, H, HH and HHH. Set the the transition probability matrix accordingly and apply the same technique discussed in the companion blog. If the goal is to toss the coin until obtaining k consecutive heads, adjust the states and the matrix accordingly and apply the method.

Though the highlighted problem is about the average number of tosses, a broader problem is about a probability distribution of the number of tosses to get k consecutive heads. For k=4, what is the probability that the goal (4 consecutive heads) can be achieved in 4 tosses of the coin, in 5 tosses, and so on? The method in answering these questions is discussed in this blog post in the same companion blog.

Figure 2 – rolling a die until seeing all 6 faces

The second problem is demonstrated by Figure 2 – rolling a fair die until the appearance of all 6 faces. How many rolls on average are required to achieve this goal? In Figure 2, it takes 11 rolls to get all 6 faces. Example 3 in this blog post shows how to answer this question. The answer is 14.7.

It turns out that Markov chain is not needed to solve this problem since this problem is related to two classic problems in probability – the occupancy problem as well as the coupon collector problem. In fact, the coupon collector problem provides a handy formula to obtain the average number rolls in order to have all faces in a k-sided die appeared once.

As in the first problem, the broader problem is about a probability distribution. What is the probability that all 6 faces appear after 6 rolls, after 7 rolls, and after 8 rolls and so on? This blog post in the same companion blog gives the idea on how to answer such questions.

Introductory discussion on Markov chains is found in the early posts in this companion blog on stochastic processes.


Markov chains

Daniel Ma math

Dan Ma mathematics

\copyright 2017 – Dan Ma

How to use a dictionary to keep you safe

In light of the recent data breach at the credit reporting company Equifax that affects one in two adults in the United States and other instances of security breach in the last several years, many consumers just want to throw up their hands and give up. Systems that store sensitive personal information seem to get hacked on a regular basis. How do we keep our information safe?

It is true that certain aspects of the digital security are out of our hand. Doing this one thing will go a long way to help safe guard our information safe – using a strong password for each of our online accounts. In addition, do not reuse password across multiple accounts and change passwords on a regular basis.

We highlight two ways to create passwords. It is not commonly suggested that dictionary words are used in forming a password. If done right, a dictionary such as the following will be a useful tool for creating strong passwords.

Using familiar words or proper pronouns is a no no. People may get lazy and use proper nouns such as their favorite movies or sport teams. Two examples are:



Hackers may use a prebuilt list of common words and familiar proper pronouns to hack such passwords. Such list may be just 20,000 words long, not long enough to offer security. In this blog post in the All Math Considered blog (a companion blog), we show how to randomly select 5 words in the dictionary shown above. The following is the example demonstrated in that blog post.


The above example is a 41-character password. How much better are such passwords? The dictionary in question has about 65,000 words. There would be over 1 septillion 5-word strings that can be formed out of this dictionary. One septillion is 1 trillion times 1 trillion. If a computer or a network of computers can check 1,000 of the 1 septillion possibilities per second, it would take over 1 million years to exhaust all the possibilities. So a brute force attack is not a feasible approach. The hacker will have to find other ways. In this case, the safety of large numbers is on your side.

Remember, for dictionary words to work as passwords, the words must be randomly chosen. See this blog post to see how to select words at random.

Another approach is to use a sentence or sentences that are memorable. Then use the first letter from each word. For example,


The above string is taken from the first letters of the sentence “My favorite movie is Pirate of the Caribbean and I am a die hard LA Lakers fan”. So the same two familiar proper nouns mentioned above can be turned into a memorable phrase for a strong password. See the discussion in this blog post in the companion blog called Talking about Numbers.


strong passwords

Cyber Security


Daniel Ma


\copyright 2017 – Dan Ma

A normal bell curve that is made with humans

A picture was found at the website of the department of statistics and actuarial science at Simon Fraser University.

Figure 1 – Normal Bell Curve of Heights of Students (found here)

Though this normal bell curve is not the work of nature, the idea is clever. A picture of a normal distribution should never go to waste. So we write about it in our introductory statistics blog (see here). Indeed, it is an excellent opportunity to discuss properties of normal distribution.

\text{ }

\text{ }

\text{ }

\copyright 2017 – Dan Ma

Probability and actuarial science

Consider this scenario. Both a thirty-year old man and a seventy-year old man purchase identical annuity contracts. The costs of the contracts are the same to both men. The benefits are also the same – both men receive the same monthly payment till death. What is wrong with this picture?

The life expectancy of a thirty-year old is four times longer than that of a seventy-year old. So such an annuity contract would be a good deal for the thirty-year old as he can stand to collect four times more payments than a seventy-year old (but with time value of money the differential is more than 4 times).

Such contracts sold to a thrity-year old would be a bad deal for the insurance company. In fact if the insurance company had sold such contracts to a sufficient number of thirty-year old, it almost certainly would go out of business long before the thirty-year old can live to an old age. Though good deal for the young folks, such practices are simply not sustainable both as a business practice and as a matter of public policy.

Yet back in the seventeenth century, during the reign of William III of England, this was what commonly happened – annuity contracts with the same prices and the same payouts were routinely sold to both thirty-year old and seventy-year old (see Karl Pearson, The History of Statistics In the 17th and 18th Centuries against the Changing Background of Intellectual, Scientific and Religious Thought).

Why? People back in those days did not have any conceptualization of probability or statistics. For example, they did not know that the length of someone’s life, though unpredictable on an individual basis, could be predicted statistically based on empirical observations over time and across a large group of people. The prevailing mentality was that God controlled every minute detail of the universe. Such belief ruled out any kind of conceptualization of chance as phenomena that can be studied and predicted in the aggregate.

Fast forward to the present. We now take probability seriously (and the seriousness had been steadily growing since the eighteenth century). Probability tools are widely available. Here’s a life expectancy calculator from Social Security. According to this calculator, the additional life expectancy of a man who is currently thirty-year old is 51.4 years. A man who is currently seventy-year old is expected to live 14.8 more years. So a thirty-year old man can expect to live three and a half times longer than a seventy-year old man.

With a strong foundation of probability and statistics, which was not available in the seventeenth century, annuity contracts are priced based on the probability of living a long life and the life insurance policies are priced based on the probability of dying prematurely.

Actuaries are specially-trained professionals who use their knowledge of probability, statistics, and specific models to evaluate and price risks, e.g. risks of living too long, the risks of dying too soon, the risks of property damages, the risks of becoming sick and a whole host of other risks that are quantifiable. As a result, actuaries are generally employed in life, health, and property and casualty insurance companies, consulting firms, and government.

In fact the actuarial profession grew out of the effort to put the pricing of life insurance and annuity contracts on a sound scientific and business basis in the early eighteenth century England.

The entry point into the actuarial profession is an exam on probability. It is called Exam P and is jointly administered by the Society of Actuaries (SOA) and the Casualty Actuarial Society (CAS). Here’s what SOA says about Exam P:

    The purpose of the syllabus for this examination is to develop knowledge of the fundamental probability tools for quantitatively assessing risk. The application of these tools to problems encountered in actuarial science is emphasized. A thorough command of the supporting calculus is assumed. Additionally, a very basic knowledge of insurance and risk management is assumed.

In its current incarnation, it is a three-hour exam that consists of 30 multiple-choice questions and is administered as a computer-based test.

To be an actuary, a candidate must pass a series of exams (see here for the exam requirements from SOA). Exam P is the first of many exams. It is not surprising that Exam P is the first exam since the probability is part of the foundation of actuarial science.

How difficult is Exam P? The pass rates are typically low. Exam P is administered six times a year at test locations throughout the country. Less than 45% of the candidates earn a passing score. Often times, the pass rates dip below 40%.

Exam P is an entry point of of the actuarial exam system. It is the first of many exams in the pathway to becoming an actuary. We have a companion blog for studying Exam P.

A blog for Exam P practice problems

This blog has viewership on a daily basis from every continent. In fact, some aspiring actuaries passed Exam P as a result of using this blog. Here’s two practice problems.

Sample practice problem
Sample practice problem

\text{ }

\text{ }

\text{ }

\copyright 2017 – Dan Ma

Jimmy Kimmel Asks People Their Passwords

On Friday Jimmy Kimmel asked people passing by the theater where his show is taped their passwords for the Internet (see the YouTube video below). This is part entertainment and part public service to time with the data breach at EquiFax that was reported two days ago.

A huge security breach at credit reporting company Equifax has exposed sensitive information, such as date of birth, Social Security numbers and addresses and in some cases driver license numbers, of up to 143 million Americans. The data breach is among the worst in U.S. history. The number of people affected is well over half of the adult population in the United States. According to Equifax, the data breach happened between mid-May and July. The hack was discovered on July 29, but Equifax did not inform the public until September 7.

The first person on the video was asked, “We are talking to people about the cyber-security breach at Equifax, and in light of that, we’re asking people how secure their Internet passwords are. What do you use for an internet password?” Without hesitation, the young man responded, “Um, I usually stick to my last name. That’s probably not the best thing to do, but usually it’s my last name, a few digits, um, maybe like a hashtag or something.” The interviewer then asked what his last name is. The young man readily gave out the last name. The interviewer even spelled out the last name for him to confirm. The young man also confirmed, upon asking, that the digits that go with the last name are his birthday.

The video is funny. I am amazed at the laziness and carelessness of the people in the video. First of all, the same password should not be used across multiple accounts. A password certainly should not consist of the name of the person with a few digits such as date of birth or the zip code. Everyone in the video is using the same type of passwords. Of course, it could just be a “manipulated” sample (it only includes password stories that have entertainment value).

The same stunt was done previously after the data hack at Sony two years earlier (see the YouTube video below).

There are various strategies one can use to create strong passwords that are easy (or easier) to keep track of. For example, come up with a memorable phrase and the password would be created from using the first letter in each word. Example: The first house I ever lived in was 613 Fake Street. Rent was $400 per month. The resulting password is


(example found here). This is a 22-character password that is based on memorable phrase consisting of two sentences. The beauty is that the password has upper case and lower case letters and numeric characters and special symbols. It is arranged in such a way that people not in the know cannot guess easily. Of course, you who know the memorable phrase can remember. The same password should not be reused for other accounts (don’t be lazy). So come up with a memorable phrase for each account.

There is another way to generate passwords that are strong. The passwords generated in this scheme are 26-character passwords with the first character being the first letter of the English alphabets, the second character being the second letter of the English alphabets and the third character being the third letter of the English alphabets and so on. In fact, this should be given in the Jimmy Kimmel’s video mentioned above. Though all the letters are known, the scheme produces over 67 million possible passwords (67,108,864 to be exact). Read this blog post to know more. Once someone understands how this scheme works, he or she understands the binomial distribution.

\text{ }

\text{ }

\text{ }

\copyright 2017 – Dan Ma

Powerball and the lottery curse

The recent winner of the Powerball jackpot is Mavis Wanczyk, a hospital worker from Chicopee, Massachusetts.

The Largest Undivided Lottery Jackpot in North American History

The drawing was on 8/23/2017 and the winning numbers are 6, 7, 16, 23, 26, and Powerball number 4. The size of the jackpot was $758.7 million, the largest undivided lottery jackpot in North American history. Instead of having the winnings being paid out over a 30-year period (the annuity option), Wanczyk took a lump-sum payment of $480 million and took home $336 million after taxes. This recent winning is widely reported. Here’s are one instance and another instance of reporting.

We wish Ms. Wanczyk well, hoping that she will manage the unexpected windfall in ways that add to her happiness. For lottery winners of giant jackpot, sometimes the winning is the easy part. Google “the curse of the lottery”, you will see plenty of stories of lottery winners who lost big – breaking up of marriages, going bankrupt, getting robbed, being swindled and in some cases committing suicide or being murdered.

In some states, by law the lottery winners must make public appearances holding a giant publicity check in front of camera. For the states that have no such requirements, where the public appearances are voluntary, wise winners would skip any photo ops (their identity would still be revealed) and head immediately to an undisclosed location. They know that plenty of slings and arrows (in some cases bullets) would come their ways – from swindlers, fraudsters and robbers as well as from the long lost friends and relatives who want to share the wealth. Just like one famous line in the movie Forrest Gump, ‘run, Forrest, run!” That would be the best advice for a winner of a giant and sudden windfall of cash. Of course, it is also important to hire a reputable and trustworthy financial adviser.

Sudden windfall cash usually does not last long. About 70 percent of the time, the cash will be gone in a few years, according to the National Endowment for Financial Education (see this piece from

The Time piece also mentions several stories of lottery winnings gone wrong. One winner mentioned is Abraham Shakespeare, who won a $30 million jackpot in Florida. He told his brother, “‘I’d have been better off broke.” Shakespeare (the lottery winner) has his own page in Wikipedia. His eventual fate: he was murdered by a swindler named Dee-Dee Moore 3 years after winning the big prize. The Wikipedia page of Abraham Shakespeare is more like a posthumous monument of his notoriety as a murdered lottery winner, rather than for highlighting achievements.

The Time piece also mentions a “success” story. Richard Lustig is a 65-year-old Florida man who is a seven-time lottery game grand-prize winner. He had the wisdom of hiring a good financial planner and a good accountant. With the right mindset and the foresight of financial planning, he and his family are enjoying the good life made possible by the lottery winnings two decades earlier.

Shakespeare and Lustig are from two opposite extremes in post lottery winning experiences. In between these two extremes, there are plenty of nightmarish stories with most of them being ended up in poverty, some in drug addiction (stories are here and here).

The Google search for “the curse of the lottery” turns up plenty of advice too. Here’s a piece from Forbes. Another article is a piece from Wired. The piece from Lotto Report has sad stories and other information that can shed more light on the lottery curse. Here’s home page of the Lotto Report.

As horrendous as some of the lottery curse stories are, the odds of incurring such fate are extremely rare. The odds for winning the Mega Millions jackpot is 1 in over 175 million (see here for the calculation). The odds of winning the Powerball jackpot is one in over 292 million (see here for the calculation). The odds of being struck by lightning is 1 in 700,000 according to a piece from National Geographic (significantly below 1 in a million odds). The odds of lightning strike would be more similar to the odds for winning the jackpot in a smaller lottery, e.g. Fantasy 5 in California Lottery (1 in 575,757).

Of course, the longer the odds, the larger the potential jackpot. In fact, some of the most viewed articles in a companion blog called Talking about Numbers are about lotteries. The articles deal with California Lottery. But the ideas and observations would apply to other lotteries as well.

One way to calculate the odds of winning the top prize in a lottery is through math (done here for various games in California Lottery and here for Powerball). Another way is to look at data.

In this piece in Talking about Numbers, I showed that there are only 257 winning tickets with payouts of $1 million or more in the 26-year period from 1985 (the founding of California Lottery) to August 2011, averaging 10 “$1 million plus” winning tickets a year. Of these 257 winning tickets, 247 are in the first 25 years and 10 in the last year.

Naturally, I would like to update the study but California Lottery had since then made it hard to gather the data in their website. But the essential fact remains the same. There are on average about 10 winning tickets a year that pay out $1 million or more. These 257 winning tickets are out of over 9 billion purchased tickets! This means the odds for winning a “million dollar plus” prize in California prize are about one in 36 million (calculated here).

Of course, California Lottery will try their best to give the impression that winning is more commonplace. Lottery authorities are in the business of selling tickets. They do not want to provide a picture reflecting the true odds of winning big. The odds of 1 in 36 million are much better odds than the Powerball odds for sure. But the prizes are not as mega as Powerball (the average of 247 winning tickets from 1985 to 2010 for California Lottery is $18 million).

This piece has more information on the study. Here’s another frequently viewed post on lottery topics.

\text{ }

\text{ }

\text{ }

\copyright 2017 – Dan Ma

Tower of Hanoi

The tower of Hanoi is a game that works on multiple levels. It is a challenging game that test the agility and organization skills of the player. It is also a game mathematicians would love since the game is an excellent illustration of math concepts such as mathematical induction and exponential growth. It is also a concrete illustration of a recursive algorithm.

The game of tower of Hanoi involves moving disks from one rod into another rod. The following is a tower of Hanoi game with 8 disks and three rods.

8-disk Tower of Hanoi (Wikipedia)

The goal of the game is to move all the disks from the left most rod to the right most rod, one disk at a time. Only the uppermost disk on a rod can be moved. In addition, you can only place a smaller disk on top of a larger disk.

Tower of Hanoi sets such as the one shown above are available from Amazon. A home made tower of Hanoi set can also be created. For example, use paper to mark three spots (to serve as rods). Then stack books of varying sizes in one spot and proceed to move the books to another spot according to the rules described above. Kitchen plates can also be used in place of books.

There are also many online versions of the game. Tow examples: version from Math is Fun (from 3-disk to 8-disk game) and 3-disk game to 9-disk game are available in this version. Both sites are easy to use. I prefer the Math is Fun version since the disks are in different colors. Of course, there are many others to choose from (simply Google tower of Hanoi game).

Obviously, the more disks there are in the game, the more difficult it is to successfully to transfer the disks. It is possible that the player may make more moves than necessary if the player is not organized or gets lost.

A 3-disk game can be played in 7 moves and no less than 7 moves. A 4-disk game can be played in a minimum of 15 moves. For a player who gets lost may end up taking more than 15 moves in a 4-disk game. Any player in the know can finish the 4-disk game in 15 moves. The 5-disk game can be played in 31 moves. For 6-disk games, 63 moves. For 7-disk game, 127 moves. To see these for yourself, explore the game using a home made set or play online. The game is also discussed here in a companion blog.

Notice that whenever an additional disk is added to the game, the minimum number of moves is doubled, e.g. from 7 moves to 15 moves (from 3 disks to 4 disks), from 15 to 31 (from 4 disks to 5 disks) and so on. In general, the n-disk game requires a minimum of 2^n-1 moves. Thus the tower of Hanoi is a concrete example of an illustration of exponential growth – increasing the size of the game by one disk doubles the time required to play the game.

In general exponential growth is a phenomenon such that increasing the input by one unit increases the output by a constant multiple (e.g. doubling, tripling, or multiplying with other constant). In contrast, linear growth (or growing linearly) means that increasing the input by one unit increases the output by a constant but as an additive amount.

The exponential growth is even easier to see if the moves are converted into time. Assume that it takes one second to move a disk. It would take 63 seconds to play the 6-disk game, roughly one minute. It would take 127 seconds to play the 7-disk game, roughly 2 minutes. In that two minutes, the play would need to know exactly what the moves should be. Otherwise it would be easy to make a mistake and hence taking more moves than necessary. So converting the moves to seconds further illustrates the exponential growth inherent in the tower of Hanoi game.

A more subtle aspect of the tower of Hanoi game is that in order to play it successfully (i.e. in the minimum number of moves), the game must be played recursively. Take the 4-disk game as example. Imagine that the 4 disks are at first in the left rod. The goal is to move them to the right rod (the destination rod). The rod in the middle is the intermediate rod. The strategy is to move the first 3 disk to the middle rod. Then move the 4th disk (the largest disk) from the left rod to the right rod. The remaining moves will be to move the three disks in the middle rod to the right rod.

With n disks, move the top n-1 disks into the intermediate rod (by following the rules of course). Then move the largest disk in the starting rod into the destination rod. To finish off the game, move the n-1 disks in the intermediate rod into the destination rod. So the n-disk game is executed by playing two (n-1)-disk games with the move of the largest disk in between. So the tower of Hanoi is a great introduction to a recursive algorithm. The tower of Hanoi game would be a great computer programming exercise.

Because of the recursive nature of the game, it would be a challenge to keep track of the moves when the number of disks is large. In a 4-disk game, you would play 3-disk games twice with one move of the largest disk in between. This can be managed with ease after some minimal practice. Say, you want to play the 8-disk game, you would need to play 7-disk game twice with one move of the largest disk in between. For each of the two 7-disk games, you would need to play 6-disk game twice with one more move in between. That would mean four 6-disk games. Then in each of the 6-disk game, you need to play 5-disk game twice with one more move in between. The recursion can get complicated fast! It will be helpful to use diagrams to keep track of all the sub games that are required in the recursive algorithm. This is discussed here in a companion blog.

Now that we know adding one disk to the game of tower of Hanoi doubles the number of moves, hence doubling the time it takes to play. What about doubling the number of disks?

The 8-disk game only requires a minimum of 255 moves (about 4 minutes with one second per move). The 16-disk game would require 65,535 moves, over 1,000 minutes (assuming one second per move) or over 18 hours! The following shows a 32-disk tower of Hanoi set, which is located in a museum in Mexico.

32-disk Tower of Hanoi (Wikipedia)

A 32-disk game would require 2^{32}-1 moves, which is 4,294,967,295. Assuming one second per move, this would be over 136 years! If the workers in the museum is required to move the disks from one rod to another rod by following the rules of the game, that’s would be job security!

The game of Tower of Hanoi is a deceptively simple game. Yet the effect of doubling the number of disks is very dramatic. What about doubling the number of disks to 64, twice as many disks as the one shown above? The following is an interesting tale of the origin of the game of Tower of Hanoi [1].

    In the Temple of Benares, beneath the dome which marks the centre of the world, rests a brass-plate in which are fixed three diamond needles, each a cubit high and as thick as the body of a bee. On one of these needles, at the creation, God placed sixty-four discs of pure gold, the largest disc resting on the brass plate, and the others getting smaller and smaller up to the top one. This is the Tower of Bramah! Day and night unceasingly the priests transfer the discs from one diamond needle to another according to the fixed and immutable laws of Bramah, which require that the priest must not move more than one disc at a time and that he must place this disc on a needle so that there is no smaller disc below it. When the sixty-four discs shall have been thus transferred from the needle on which at the creation God placed them to one of the other needles, tower, temple and Brahmins alike will crumble into dust, and with a thunderclap the world will vanish.

The game of the tower of Hanoi was invented by the French mathematician Édouard Lucas in 1883. A year later, an author called Henri de Parville told of the above interesting tale about the origin of the tower of Hanoi.

It is not known whether Lucas, the inventor of the game, invented this legend or was inspired by it. One thing is clear. The legend accurately describes the enormity of the 64-disk game of the tower of Hanoi.

The least number of moves that are required to play the 64-disk game is 2^{64}-1, which is 18,446,744,073,709,551,615, when converted to years would be 585 billion years (again, assuming one second per disk). In contrast, the age of the universe is believed to be 13.82 billion years. The age of the sun is believed to be 4.6 billion years. The remaining lifetime of the sun is believed to be around 5 billion years. So by the time the sun dies out the game is still not finished!

Back to the question about what happens when the number of disks is doubled. For the 8-disk game, the number of moves is 255. For the 16-disk game, the number of moves is 65,535. Note that the square of 255 is 65,025. So doubling the number of disks has the effect of squaring the number of moves. This is another demonstration of exponential growth.


  1. Hinz Andreas M., Kla. Dzar Sandi, Milutinovic Uros, Ciril Petr, The Tower of Hanoi – Myths and Maths, Springer Basel, Heidelberg, New York, Dordrecht, London, 2013.

\copyright 2017 – Dan Ma