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 :
Post a Comment