Fibonacho Numbers

January 6, 2017

ft090208

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 [1], the second fibonacho number is 3 from [1,1], [1], the third fibonacho number is 10 from [1,1,2,3], [1,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.

Advertisements

Pages: 1 2

One Response to “Fibonacho Numbers”

  1. r. clayton said

    A solution in Racket.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: