[zljfhron] Lagged Fibonacci digits

Part 1: Two newest taps

The Fibonacci sequence modulo 10 starting with 0 and 1 repeats with a period of 60, the Babylonians' favorite number: 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. One could imagine a very confusing digital clock in which two digits slide by every minute (or second).

Other starting pairs give other periods:
Period 20: 0 2 2 4 6 0 6 6 2 8 0 8 8 6 4 0 4 4 8 2.
Period 12: 2 1 3 4 7 1 8 9 7 6 3 9. (Also usable for a clock.)
Period 4: 4 2 6 8.
Period 3: 0 5 5.
Period 1: 0 0.
These periods sum to 100, which exhausts all possibilities of two starting digits.

Part 2: Lagged Fibonacci, newest and oldest taps

Start with the digits 0 0 0 0 0 0 1 at the top of a 7-column tableau. Fill in the following rows left-to-right by adding modulo-10 the digit to left and the digit immediately above. For the leftmost digit on each row, the digit "to the left" is the last digit on the previous row. This is equivalent to the recurrence a[i] = (a[i-1] + a[i-7]) mod 10. The sequence repeats with an impressively long period of 2480437. The original motivation was a method for a person to produce by hand a page of seemingly random digits with little effort. The tableau begins

0 0 0 0 0 0 1
1 1 1 1 1 1 2
3 4 5 6 7 8 0
3 7 2 8 5 3 3
6 3 5 3 8 1 4

and ends 2480437 digits later:

5 1 7 4 0 4 8
3 4 1 5 5 9 7
0 4 5 0 5 4 1
1 5 0 0 5 9 0
1 6 6 6 1 0 0
1 7 3 9 0 0 0
1 8 1 0 0 0 0
1 9 0 0 0 0 0
1

Periods of other column widths (lag lengths) and their factorizations, starting with 0 0 ... 1:
1 4 = 2*2
2 60 = 2*2*3*5
3 217 = 7*31
4 1560 = 2*2*2*3*5*13
5 168 = 2*2*2*3*7
6 196812 = 2*2*3*3*7*11*71
7 2480437 = 127*19531
8 15624 = 2*2*2*3*3*7*31
9 28515260 = 2*2*5*73*19531
10 1736327236 = 2*2*7*19*31*127*829
11 249032784 = 2*2*2*2*3*7*11*13*71*73
12 203450520 = 2*2*2*3*5*7*13*31*601
13 482322341820 = 2*2*3*5*11*17*31*71*19531

The sequence of periods 4, 60, 217, 1560, 168 does not appear on OEIS. These first four terms I have confirmed are the longest possible period among all start seeds, not just 0 0 0 ... 1. It is curious that the factor 19531 occurs multiple times.

Part 3: Two oldest taps

We consider the recurrence a[i] = (a[i-6] + a[i-7]) mod 10, that is, the two "oldest" values. To calculate the next digit on a seven-column tableau, add the number above to the number above and to the right (northeast). Or, this could also be done with a more compact six-column tableau adding the number above and the number above and to the left (northwest). This recurrence repeats with a period 661416, smaller than the corresponding lag-7 sequence in Part 2.

Periods for lag lengths are given below. The periods seem neither uniformly longer nor shorter than Part 2.

2 60 = 2*2*3*5
3 168 = 2*2*2*3*7
4 1560 = 2*2*2*3*5*13
5 16401 = 3*7*11*71
6 196812 = 2*2*3*3*7*11*71
7 661416 = 2*2*2*3*7*31*127
8 15624 = 2*2*2*3*3*7*31
9 8894028 = 2*2*3*11*13*71*73
10 1736327236 = 2*2*7*19*31*127*829
11 3712686852 = 2*2*3*7*31*73*19531
12 203450520 = 2*2*2*3*5*7*13*31*601
13 25732419240 = 2*2*2*3*5*11*17*31*71*521

The sequence 60, 168, 1560 does not appear in OEIS. But the analogous sequence modulo 2 (instead of modulo 10) is A046932, and curiously, the analogous sequence of Part 2 modulo 2 seems to be the exact same sequence. Also, there's the factor 19531 again. Searching for the number on OEIS gives a hint of what is going on. The VIC cipher used this recurrence in base 10 with width 10.

Source code

Here is a Haskell implementation including Floyd's cycle-detection algorithm. It is only a partial implementation of cycle detection because it does not go back to test that the found period is not a multiple of a shorter period. I'm hoping this second step wasn't necessary.

Because the generated sequences were implemented as giant lists, it was very easy to have catastrophic space leaks. I've left in old versions of code demonstrating a few such failures. Even printing out a list followed by its length required some care. This aspect of Haskell, compared to an imperative programming language, I strongly dislike.

The code is far from optimized, most notably because it was an exercise in learning to use Data.Sequence to hold the state. Unboxed arrays would probably have been better.