GeekDad Puzzle of the Week Solution – Modulo Fibonacci

Reading Time: 2 minutes

This past week’s GeekDad Puzzle of the Week, as presented earlier:

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.

This week’s puzzle was straightforward if you were familiar with programming languages that had a “bigint” or other variable type that could handle numbers with 200+ digits. One (correct!) solution presented was spreadsheet-only, with 200+ cells representing each number, and had just one digit per cell.

It turns out that there were some 40 numbers in the Fibonacci sequence that were able to produce their ordinal value by a sum of a subset (or complete subset) of their least significant digits. For a surprising 17 of them, the entire set of digits was required!

Here they are, ranging from f(0) to f(985):

f(0):1 of 1 digits
f(1):1 of 1 digits
f(5):1 of 1 digits
f(10):2 of 2 digits
f(14):2 of 3 digits
f(31):7 of 7 digits
f(35):7 of 7 digits
f(58):9 of 12 digits
f(62):13 of 13 digits
f(72):15 of 15 digits
f(74):12 of 16 digits
f(99):20 of 21 digits
f(122):23 of 26 digits
f(175):37 of 37 digits
f(180):38 of 38 digits
f(184):35 of 39 digits
f(216):45 of 45 digits
f(251):53 of 53 digits
f(252):53 of 53 digits
f(289):57 of 61 digits
f(300):56 of 63 digits
f(342):68 of 72 digits
f(360):75 of 75 digits
f(398):82 of 83 digits
f(415):81 of 87 digits
f(447):93 of 94 digits
f(477):99 of 100 digits
f(494):103 of 103 digits
f(504):105 of 105 digits
f(512):100 of 107 digits
f(540):113 of 113 digits
f(550):110 of 115 digits
f(589):116 of 123 digits
f(591):121 of 124 digits
f(602):125 of 126 digits
f(829):172 of 173 digits
f(843):170 of 176 digits
f(946):198 of 198 digits
f(977):199 of 204 digits
f(985):201 of 206 digits

The largest “reasonable” Fibonacci number with this property is f(3182), which requires 657 of its 665 digits to add up to 3182. In all of its glory, here is f(3182): 44,584,
743,583,574,008,097,098,511,361,924,543,588,462,250,812,746,399,484,939,462,340,345,691,
735,890,336,390,632,434,664,436,991,399,199,388,191,894,774,273,577,434,079,930,019,763,
567,807,244,474,154,726,388,474,301,464,938,664,791,481,973,731,681,870,353,725,040,451,
538,891,977,327,543,517,535,453,389,186,487,944,954,704,973,989,692,558,032,819,269,662,
302,734,939,871,198,631,791,936,979,822,392,031,955,976,880,583,822,655,687,095,874,777,
737,396,239,805,437,939,410,996,736,308,915,876,333,636,203,843,763,115,521,418,037,315,
115,606,842,502,996,349,549,680,651,387,597,262,485,888,558,020,289,990,672,492,377,118,
583,473,722,053,865,743,367,622,787,965,750,058,901,117,445,254,130,146,248,049,407,670,
736,093,775,693,376,815,979,153,647,367,196,390,518,246,308,668,680,888,611,375,670,549,
886,847,919,658,942,306,899,255,672,193,114,647,005,710,436,676,913,402,829,609,091,641

Congratulations to Jaime Santana, winner of this week’s fabulous prize from ThinkGeek! Jaime not only answered the puzzle correctly, but was also drawn at random from among all of the correct (or at least reasonably well reasoned) solutions. A $50 Gift Certificate from the team at ThinkGeek will be on its way soon!

Thanks to everyone to sent in a solution, that reads GeekDad, and that shops at ThinkGeek.

Happy puzzling!

Get the Official GeekDad Books!