January 6, 2017
Mathematicians are strange people:
Two people are sharing a plate of nachos. They take turns dividing the nachos, each taking the nth Fibonacci number of nachos on the nth turn. When the number of nachos left is less than the next Fibonacci number, they start the sequence over. What number of nachos (less than 500) requires the most number of restarts?
For instance, if you start with n = 11 nachos, the first person takes 1 nacho (leaving 10), the second person takes 1 nacho (leaving 9), the first person takes 2 nachos (leaving 7), the second person takes 3 nachos (leaving 4), and the process restarts. Then the first person takes 1 nacho (leaving 3), the second person takes 1 nacho (leaving 2), and the first person takes 2 nachos (leaving none). There were two restarts, which we can notate as [1,1,2,3], [1,1,2].
The fibonacho numbers are those starting numbers n that require more restarts than any smaller number. Thus, the first fibonacho number is 1 from , the second fibonacho number is 3 from [1,1], , the third fibonacho number is 10 from [1,1,2,3], [1,1], , and so on.
Your task is to write programs that calculate the number of restarts for a given n, and the sequence of fibonacho numbers. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.