[qxjnommp] initializing generalized Fibonacci for monotonic growth

we consider a generalized Fibonacci sequence generated by a state vector.  the next term is the sum of the two oldest elements of the state vector, then, the oldest element is discarded.  here is a demonstration of the evolution of an initial state vector [3,20,100] for 3 iterations.  the oldest elements are on the left; the newest element is added to the right, shifting everything to the left.

[3,20,100]
[20,100,23]
[100,23,120]
[23,120,123]

the simplest possible initial state vector is all zeros, but that generates only zeros.

the next simplest initial state vector has one 1 and the rest zeros.  this family of initial states, in particular putting the 1 at the oldest slot, is discussed in previous posts.  for such a state vector of width W, it takes (W-1)^2+1 iterations until the state vector has no zeros.  (this is the first of many conjectures in this post inspired by experimental verification for small sizes.)  in the example below, we can see rows of Pascal's triangle shift along the state vector.

[1,0,0,0,0]
[0,0,0,0,1]
[0,0,0,1,0]
[0,0,1,0,0]
[0,1,0,0,0]
[1,0,0,0,1]
[0,0,0,1,1]
[0,0,1,1,0]
[0,1,1,0,0]
[1,1,0,0,1]
[1,0,0,1,2]
[0,0,1,2,1]
[0,1,2,1,0]
[1,2,1,0,1]
[2,1,0,1,3]
[1,0,1,3,3]
[0,1,3,3,1]
[1,3,3,1,1]

the sequence initially oscillates.  it takes many iterations before the sequence becomes monotonically strictly increasing.

the next simplest initial state is all ones.  this generates a sequence that is monotonically nondecreasing.  it takes (W-1)^2+1 iterations until the state vector has no repeated elements, after which point the sequence becomes monotonically strictly increasing.

[1,1,1,1,1]
[1,1,1,1,2]
[1,1,1,2,2]
[1,1,2,2,2]
[1,2,2,2,2]
[2,2,2,2,3]
[2,2,2,3,4]
[2,2,3,4,4]
[2,3,4,4,4]
[3,4,4,4,5]
[4,4,4,5,7]
[4,4,5,7,8]
[4,5,7,8,8]
[5,7,8,8,9]
[7,8,8,9,12]
[8,8,9,12,15]
[8,9,12,15,16]

consider running an initial state of all ones backward as far as possible avoiding negative numbers.  if the width of the state vector is even, the earliest such state alternates ones and zeros.

[1,0,1,0,1,0,1,0,1,0]
[0,1,0,1,0,1,0,1,0,1]
[1,0,1,0,1,0,1,0,1,1]
[0,1,0,1,0,1,0,1,1,1]
[1,0,1,0,1,0,1,1,1,1]
[0,1,0,1,0,1,1,1,1,1]
[1,0,1,0,1,1,1,1,1,1]
[0,1,0,1,1,1,1,1,1,1]
[1,0,1,1,1,1,1,1,1,1]
[0,1,1,1,1,1,1,1,1,1]
[1,1,1,1,1,1,1,1,1,1]

if the state vector width is odd, there is a state of alternating ones and zeros part way through, but that state can be rewound further backward to a state with a prefix [1,0,0] followed by alternating ones and zeros.

[1,0,0,1,0,1,0,1,0,1,0]
[0,0,1,0,1,0,1,0,1,0,1]
[0,1,0,1,0,1,0,1,0,1,0]
[1,0,1,0,1,0,1,0,1,0,1]
[0,1,0,1,0,1,0,1,0,1,1]
[1,0,1,0,1,0,1,0,1,1,1]
[0,1,0,1,0,1,0,1,1,1,1]
[1,0,1,0,1,0,1,1,1,1,1]
[0,1,0,1,0,1,1,1,1,1,1]
[1,0,1,0,1,1,1,1,1,1,1]
[0,1,0,1,1,1,1,1,1,1,1]
[1,0,1,1,1,1,1,1,1,1,1]
[0,1,1,1,1,1,1,1,1,1,1]
[1,1,1,1,1,1,1,1,1,1,1]

the following initial state vectors generate sequences that are monotonically strictly increasing.  (the first generates the Fibonacci sequence.)  the first two elements sum to 1 larger than the last element.

[1,2]
[2,3,4]
[3,4,5,6]
[4,5,6,7,8]
[5,6,7,8,9,10]
[6,7,8,9,10,11,12]
[7,8,9,10,11,12,13,14]
[8,9,10,11,12,13,14,15,16]

if we run an even-length such sequence backward, the earliest non-negative state vector (in the example below) has 4s alternated with [0,1,2,3].  the point where the output sequence (last elements) becomes strictly increasing also has a simple form of doubled integers in order [4,4,5,5,6,6,7,7].

[4,0,4,1,4,2,4,3]
[0,4,1,4,2,4,3,4]
[4,1,4,2,4,3,4,4]
[1,4,2,4,3,4,4,5]
[4,2,4,3,4,4,5,5]
[2,4,3,4,4,5,5,6]
[4,3,4,4,5,5,6,6]
[3,4,4,5,5,6,6,7]
[4,4,5,5,6,6,7,7]
[4,5,5,6,6,7,7,8]
[5,5,6,6,7,7,8,9]
[5,6,6,7,7,8,9,10]
[6,6,7,7,8,9,10,11]
[6,7,7,8,9,10,11,12]
[7,7,8,9,10,11,12,13]
[7,8,9,10,11,12,13,14]

for an odd-length initial state vector (width 19 below), the sequence can be rewound further to something with a difficult-to-describe prefix followed by 9s alternated with [0,1,2,3,4,5].

[6,3,3,6,1,8,0,9,0,9,1,9,2,9,3,9,4,9,5]
[3,3,6,1,8,0,9,0,9,1,9,2,9,3,9,4,9,5,9]
[3,6,1,8,0,9,0,9,1,9,2,9,3,9,4,9,5,9,6]
[6,1,8,0,9,0,9,1,9,2,9,3,9,4,9,5,9,6,9]
[1,8,0,9,0,9,1,9,2,9,3,9,4,9,5,9,6,9,7]
[8,0,9,0,9,1,9,2,9,3,9,4,9,5,9,6,9,7,9]
[0,9,0,9,1,9,2,9,3,9,4,9,5,9,6,9,7,9,8]
[9,0,9,1,9,2,9,3,9,4,9,5,9,6,9,7,9,8,9]
[0,9,1,9,2,9,3,9,4,9,5,9,6,9,7,9,8,9,9]
[9,1,9,2,9,3,9,4,9,5,9,6,9,7,9,8,9,9,9]
[1,9,2,9,3,9,4,9,5,9,6,9,7,9,8,9,9,9,10]
[9,2,9,3,9,4,9,5,9,6,9,7,9,8,9,9,9,10,10]
[2,9,3,9,4,9,5,9,6,9,7,9,8,9,9,9,10,10,11]
[9,3,9,4,9,5,9,6,9,7,9,8,9,9,9,10,10,11,11]
[3,9,4,9,5,9,6,9,7,9,8,9,9,9,10,10,11,11,12]
[9,4,9,5,9,6,9,7,9,8,9,9,9,10,10,11,11,12,12]
[4,9,5,9,6,9,7,9,8,9,9,9,10,10,11,11,12,12,13]
[9,5,9,6,9,7,9,8,9,9,9,10,10,11,11,12,12,13,13]
[5,9,6,9,7,9,8,9,9,9,10,10,11,11,12,12,13,13,14]
[9,6,9,7,9,8,9,9,9,10,10,11,11,12,12,13,13,14,14]
[6,9,7,9,8,9,9,9,10,10,11,11,12,12,13,13,14,14,15]
[9,7,9,8,9,9,9,10,10,11,11,12,12,13,13,14,14,15,15]
[7,9,8,9,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16]
[9,8,9,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16]
[8,9,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,17]
[9,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,17,17]
[9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,17,17,18]
[9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,17,17,18,18]
[10,10,11,11,12,12,13,13,14,14,15,15,16,16,17,17,18,18,19]
[10,11,11,12,12,13,13,14,14,15,15,16,16,17,17,18,18,19,20]
[11,11,12,12,13,13,14,14,15,15,16,16,17,17,18,18,19,20,21]
[11,12,12,13,13,14,14,15,15,16,16,17,17,18,18,19,20,21,22]
[12,12,13,13,14,14,15,15,16,16,17,17,18,18,19,20,21,22,23]
[12,13,13,14,14,15,15,16,16,17,17,18,18,19,20,21,22,23,24]
[13,13,14,14,15,15,16,16,17,17,18,18,19,20,21,22,23,24,25]
[13,14,14,15,15,16,16,17,17,18,18,19,20,21,22,23,24,25,26]
[14,14,15,15,16,16,17,17,18,18,19,20,21,22,23,24,25,26,27]
[14,15,15,16,16,17,17,18,18,19,20,21,22,23,24,25,26,27,28]
[15,15,16,16,17,17,18,18,19,20,21,22,23,24,25,26,27,28,29]
[15,16,16,17,17,18,18,19,20,21,22,23,24,25,26,27,28,29,30]
[16,16,17,17,18,18,19,20,21,22,23,24,25,26,27,28,29,30,31]
[16,17,17,18,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32]
[17,17,18,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33]
[17,18,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34]
[18,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35]
[18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36]

here is the earliest nonnegative state vector of width 201.  the prefix consists of triangular numbers in decreasing order alternated with a sequence which causes pairs of elements to sum to a value which increase by 1 each pair.  91 unpaired, 9+78 = 87, 22+66 = 88, 34+55 = 89.  [91,78,66,55] are decreasing triangular numbers.

[91, 9, 78, 22, 66, 34, 55, 45, 45, 55, 36, 64, 28, 72, 21, 79, 15, 85, 10, 90, 6, 94, 3, 97, 1, 99, 0, 100, 0, 100, 1, 100, 2, 100, 3, 100, 4, 100, 5, 100, 6, 100, 7, 100, 8, 100, 9, 100, 10, 100, 11, 100, 12, 100, 13, 100, 14, 100, 15, 100, 16, 100, 17, 100, 18, 100, 19, 100, 20, 100, 21, 100, 22, 100, 23, 100, 24, 100, 25, 100, 26, 100, 27, 100, 28, 100, 29, 100, 30, 100, 31, 100, 32, 100, 33, 100, 34, 100, 35, 100, 36, 100, 37, 100, 38, 100, 39, 100, 40, 100, 41, 100, 42, 100, 43, 100, 44, 100, 45, 100, 46, 100, 47, 100, 48, 100, 49, 100, 50, 100, 51, 100, 52, 100, 53, 100, 54, 100, 55, 100, 56, 100, 57, 100, 58, 100, 59, 100, 60, 100, 61, 100, 62, 100, 63, 100, 64, 100, 65, 100, 66, 100, 67, 100, 68, 100, 69, 100, 70, 100, 71, 100, 72, 100, 73, 100, 74, 100, 75, 100, 76, 100, 77, 100, 78, 100, 79, 100, 80, 100, 81, 100, 82, 100, 83, 100, 84, 100, 85, 100, 86]

here is Haskell source code which investigates these sequences.  although the state vector would have been best implemented with a circular array, we did not pursue this because it seems difficult in a purely functional language (probably need a state monad, e.g., circular).  we instead used Data.Sequence, which probably caused an asymptotic performance penalty of logarithmic versus constant time in the width of the state vector.