4 discs
After having tried to solve the puzzle with 4 discs I found that the smallest amount of moves possible was 15. (See fig. 1)
5 discs
To try and make things slightly easier for myself I decided to use the first 15 moves I had used for 4 discs and then proceed from there. This method was effective and led me to find that the smallest number of moves was 31. (See fig. 2)
Results and Formulas
When placing all the results into a table I noticed that if you take a certain number of moves for example 3 and then double it you end up with 6. You only then need to add another 1 to make 7, which is the next amount of moves. This works for any number of moves for finding the next amount of moves. To simplify my findings I produced a formula as shown below. This was my first formula.
m = previous number of moves
Next amount of moves = 2m + 1
I also decided to look at the differences between the smallest number of moves for each number of discs and the difference between these numbers. They are as shown is this table.
I noticed that all the differences were powers of 2. From this I predicted that the formula, needed to find the smallest number of moves from any number of discs, would somewhere involve the powers of 2.
From the results in this table where 2 was placed to the power of the number of discs, I could see that the results were the same as the in the previous table.
Then from looking at the results again, I noticed that the difference between the ‘Smallest number moves for each disc’ and the ‘Difference between the number of moves’ was only that of 1.
From these two observations I decided to try and construct a formula to give the smallest number of moves from any number of discs.
d = number of discs m = smallest number of moves
2 d was what I used to start my formula. I then needed to adapt it to find the answers I needed. The adaptation that I needed to make was to find the difference, which I had already found from the previous tables to be 1. So I added this to the formula I already had.
The formula I now had was m = 2 d – 1. This was my second formula.
I found that this rule worked for any number of discs and always produced the smallest amount of moves possible.
For example, if we use 5 discs.
2 d – 1
2 5 – 1 = 31 Smallest number of moves for 5 discs = 31.
Upon revisiting my first formula I discovered that it was a repeating sequence whereby 2m was the first in the sequence. The next term in the sequence would therefore be 2m + 1. This turned out to be an iterative procedure where the output of a calculation would be the input for the next calculation and the sequence could be repeated again and again.
This could be shown using nth terms as well.
The last nth term: U n
The next nth term: U n +1
Conclusion
From the results that I collected I was able to produce two formulas which enabled you to find the next amount of moves using either the previous amounts of moves or the number of discs. The first formula I produced I did so with the help of iterative procedures. The second formula I produce using the powers of 2.
