GeekDad Puzzle of the Week – Modulo Fibonacci

Reading Time: 1 minute

fibonacci_teaser
The Fibonacci sequence of numbers is well documented and well-researched. Most straightforward puzzles such as “which Fibonacci numbers are perfect squares?” or “which Fibonacci numbers are prime?” have at one point or another been someone’s proof or project, and are easily found via your favorite search engine.

To make an interesting Fibonacci puzzle, I will have to combine the famous set of numbers and a fun math function: modulo. The modulo (or “mod”) function returns the remainder after a division operation takes place. In many language, it is the counterpart to DIV, which gets the quotient or standard division answer.
51 ÷ 8 = 6R3
51 DIV 8 = 6, 51 / 8 = 6
51 MOD 8 = 3, 51 % 8 = 3

This week’s GeekDad Puzzle of the Week deals with the ordinality of position of the Fibonacci number, and how it relates to the sum of the digits after a “mod” operation on a power of 10. How many Fibonacci numbers under f(1000) have the sum of their last few digits equal to their position within the sequence?

A simple example would be f(10) % 100 = 55. The sum of the digits of 55 = 5+5 = 10.

NOTE: For purposes of this puzzle, f(0) = 0, f(1) = 1, and f(n) = f(n-2) + f(n-1).

Additionally, consider that f(1000) has over 200 digits, so tools like your favorite spreadsheet may not have the desired precision.

As always, please send in your responses to GeekDad Central for your chance at this week’s fabulous prize: a $50 Gift Certificate from ThinkGeek.

Good luck, and happy puzzling!

Get the Official GeekDad Books!