Today’s a Phiday Friday or Φiday Friday or Φriday, so let’s have some more Fibonacci Fun. Here is the famous Fibonacci sequence, where each number (after seeding with “0, 1”) is formed by adding the previous two numbers:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, … — A000045 at the Online Encyclopedia of Integer Sequences (OEIS)

It’s obvious that the numbers get bigger for ever and that no number repeats except 1. But what happens to the final digit of the Fibonacci numbers, as underlined here?:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, …

If you think about it, you’ll realize that the final digit has to repeat. Look for the “0, 1, 1” re-appearing:

0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1, 0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, … — A003893 at the OEIS, “a(n) = Fibonacci(n) mod 10”

As you’ll see, all the numbers 0 to 9 appear in that sequence. But what about the final two digits of the Fibonacci sequence? Do all the numbers 0 to 99 appear before the sequence repeats?

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 44, 33, 77, 10, 87, 97, 84, 81, 65, 46, 11, 57, 68, 25, 93, 18, 11, 29, 40, 69, 9, 78, 87, 65, 52, 17, 69, 86, 55, 41, 96, 37, 33, 70, 3, 73, 76, 49, 25, 74, 99, 73, 72, 45, 17, 62, 79, 41, 20, 61, 81, 42, 23, 65, 88, 53, 41, 94, 35, 29, 64, … — A105471 at the OEIS, “a(n) = Fibonacci(n) mod 100”

---

And what about the the final three digits and the numbers 0 to 999?

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 597, 584, 181, 765, 946, 711, 657, 368, 25, 393, 418, 811, 229, 40, 269, 309, 578, 887, 465, 352, 817, 169, 986, 155, 141, 296, 437, 733, 170, 903, 73, 976, 49, 25, 74, 99, 173, 272 … — A248740 at the OEIS, “a(n) = Fibonacci(n) mod 1000”

---

In fact, some numbers do go missing as the final block of digits gets longer. But all that is based on the representation of the Fibonacci numbers in base 10. What about other bases? I had a look at that question and came up with some interesting patterns when I represented the final-block numbers on an Ulam-like spiral, where numbers are represented as squares on a spiral rotating counter-clockwise. This is the spiral for powers of 2 (the red square marks the center of the spiral and the number 1):

Spiral of final Fib-digits modulo 2^p

---

Fib-spiral mod 2^p (smaller scale)

---

Fib-spiral mod 2^p (smaller scale still)

---

What fraction of numbers are missing from the spiral? Watch this space. In the meantime, here’s the Fib-spiral for powers of 3:

Fib-spiral mod 3^p

---

It’s completely filled, because no numbers are missing (the red square marks “1” at the center of the spiral). What about powers of 4? Well, we’ve already seen that Fib-spiral, because all powers of 4 are also powers of 2:

Fib-spiral mod 4^p

---

The Fib-spiral for powers of 5 is the same as the Fib-spiral for powers of 3: it’s completely filled again. But the Fib-spiral for powers of 6 is interesting:

Fib-spiral mod 6^p

---

Fib-spiral mod 6^p (smaller scale)

---

Fib-spiral mod 6^p (smaller scale still)

---

And here are more Fib-spirals and more interesting patterns:

Fib-spiral mod 7^p

---

Fib-spiral mod 10^p — identical to the Fib-spiral for 2^p

---

Fib-spiral mod 11^p

---

Fib-spiral mod 11^p (smaller scale)

---

Fib-spiral mod 13^p

---

Fib-spiral mod 13^p (smaller scale)

---

Fib-spiral mod 17^p

---

Fib-spiral mod 17^p (smaller scale)

---

Fib-spiral mod 19^p

---

Fib-spiral mod 19^p (smaller scale)

---

Fib-spiral mod 41^p

---

Fib-spiral mod 41^p (smaller scale)

---

Fib-spiral mod 47^p

---

Elsewhere Other-Accessible…

• Friday is Φday — a first look at Phiday on Friday