[qshviooe] initial transients of generalized Fibonacci

we explore a family of generalized Fibonacci sequences parameterized by width:

X[i+width] = X[i] + X[i+1]

"width" is the width of the state vector needed to generate the sequence.  it can also be called the "lag".  (the state vector is best implemented with a circular array.)

we initialize the state vector with X[1]=1, X[2 ... width]=0, because that is the slowest to get going.

these sequences grow exponentially, but the growth rate can be quite small.  the growth rate decreases with increasing width (future post hzwtbcrh).

the initial part of the sequence has oscillatory behavior, which we call transients.  we are interested when the transients die away, or more likely, when the exponential growth drowns out the oscillatory behavior.  in the table below, we count the number of iterations until the state vector is monotonically increasing, and, when it has become so, report the size in bits of the latest value.  note that a monotonic state vector is not equivalent to transients having died down; it is only a proxy for something close to that.

for a width of 100, it takes over half a million iterations, and numbers with sizes of thousands of bits, before the transients die away.

does this result have any bearing on lagged Fibonacci pseudo random number generators?  perhaps not: those PRNGs concern themselves with the least significant bits, where (abstractly) the transients never die.

if one were to initialize the state vector with all ones, then there is no oscillatory behavior (future post qxjnommp).

Pari/GP code below.  note that the state vector is backward: each newest element is inserted at the front of the list a.  in the calc function, we return the number of iterations by appending it to the end of the state vector, a bit of a hack.

ismonotonic(l)=for(i=1, length(l)-1, if(l[i]<=l[i+1], return(0))); 1

calc(len)=my(a=List([])); for(i=2, len, listput(a, 0)); listput(a, 1); for(i=0, +oo, if(ismonotonic(a), listput(a, i); return(a)); my(x=a[len]+a[len-1]); listpop(a); listinsert(a, x, 1))

? for(i=2, 100, a=calc(i); print(i, " ", a[length(a)], " ", log(a[1])/log(2)))

in the table below, columns are the width of the state vector, number of iterations until monotonic, size in bits (log2) of the largest number in the state vector at that point.  what are the asymptotic growth rates of the second and third columns?

2 1 0.0
3 9 2.0
4 19 3.5
5 47 8.0
6 90 13.8
7 145 19.5
8 242 29.3
9 351 38.1
10 487 48.0
11 664 59.8
12 877 72.7
13 1128 86.6
14 1434 102.4
15 1772 118.3
16 2158 135.2
17 2627 155.2
18 3119 174.1
19 3704 196.0
20 4333 217.9
21 5027 240.8
22 5788 264.8
23 6642 290.7
24 7595 318.6
25 8629 347.6
26 9695 375.5
27 10897 406.5
28 12188 438.4
29 13543 470.4
30 15051 505.3
31 16659 541.3
32 18339 577.2
33 20156 615.2
34 22083 654.1
35 24122 694.1
36 26277 735.0
37 28550 777.0
38 30982 821.0
39 33502 864.9
40 36229 911.9
41 39009 957.9
42 42006 1006.8
43 45058 1054.8
44 48380 1106.8
45 51762 1157.7
46 55382 1211.7
47 59017 1263.7
48 62994 1320.6
49 67036 1376.6
50 71289 1434.6
51 75709 1493.5
52 80298 1553.5
53 85007 1613.5
54 89997 1676.5
55 95167 1740.4
56 100465 1804.4
57 106004 1870.4
58 111733 1937.4
59 117654 2005.3
60 123830 2075.3
61 130207 2146.3
62 136787 2218.3
63 143511 2290.2
64 150570 2365.2
65 157714 2439.2
66 165268 2517.2
67 172912 2594.1
68 180777 2672.1
69 189004 2753.1
70 197462 2835.1
71 205943 2915.1
72 214942 3000.0
73 224038 3084.0
74 233449 3170.0
75 243181 3258.0
76 253165 3347.0
77 263250 3434.9
78 273744 3525.9
79 284498 3617.9
80 295436 3709.9
81 306800 3804.9
82 318435 3900.9
83 330262 3996.8
84 342448 4094.8
85 354915 4193.8
86 367494 4291.8
87 380615 4393.8
88 394028 4496.7
89 407558 4598.7
90 421650 4704.7
91 436045 4811.7
92 450562 4917.7
93 465476 5025.7
94 480793 5135.7
95 496425 5246.6
96 512374 5358.6
97 528644 5471.6
98 545042 5583.6
99 562058 5699.6
100 579406 5816.6