Friday, March 26, 2021

[forzzcgm] initializing slow-growth generalized Fibonacci

consider a generalized Fibonacci sequence X[n+width] = X[n] + X[n+tap] .  in traditional Fibonacci, width = 2, tap = 1.  we borrow the term "tap" from linear feedback shift registers (LFSR), which are similar except mod 2.  tap can range from 1 to width-1 inclusive, producing different sequences.

to seed the sequence, we need initial values X[1]..X[width].  (indexing from 1 makes things simpler than 0 in this application.)

the most elegant initial state is all zeros, but that will of course produce a boring sequence of only zeros.

the next most elegant start state is one 1 and the rest zeros.  surprisingly, it does not matter where the one 1 goes in the initial state; they will all produce the same sequence.  (in contrast, different initial states will generally produce different sequences; the set of initial states with exactly one 1 is special.)

the initial state with one 1 that takes the longest to get going has X[tap] = 1, and otherwise X[1] = ... = X[width] = 0 .

these sequences are interesting because they exhibit a variety of exponential growth rates between 1 and 2 (future post).

No comments :