[hzwtbcrh] slow-growing integer exponentials

the sequence a[n] = 2^n, the powers of 2, has growth rate 2.

a[n] = a[n-1] + a[n-2], Fibonacci sequence (also Lucas sequence), powers of the matrix [1 1 ; 1 0], growth rate = golden ratio = 1.618 = Roots[1+x-x^2==0,x] = (1+sqrt(5))/2.

growth rate is the largest eigenvalue of the matrix.  golden ratio seems to be the slowest constant growth possible with 2x2 integer matrix.  (but doubling every two iterations, average growth sqrt(2) = 1.4 is also possible.)

longer lag a[n] = a[n-1] + a[n-3], OEIS A000930 (also A179070), powers of matrix [1 0 1; 1 0 0 ; 0 1 0], growth rate = supergolden ratio = 1.46557123187676802665673122522 = Roots[1+x^2-x^3==0,x] = (1 + (29/2 - (3*sqrt(93))/2)^(1/3) + ((29 + 3*sqrt(93))/2)^(1/3))/3

longer lag a[n] = a[n-1] + a[n-4], powers of matrix [1 0 0 1; 1 0 0 0 ; 0 1 0 0 ; 0 0 1 0], growth rate 1.38027756909761411567330169182 = Roots[1+x^3-x^4==0,x] = 1/4 + sqrt(1 - 16*(2/(3*(-9 + sqrt(849))))^(1/3) + 2*(2/3)^(2/3)*(-9 + sqrt(849))^(1/3))/4 + sqrt(1/2 + 4*(2/(3*(-9 + sqrt(849))))^(1/3) - ((-9 + sqrt(849))/2)^(1/3)/3^(2/3) + 1/(2*sqrt(1 - 16*(2/(3*(-9 + sqrt(849))))^(1/3) + 2*(2/3)^(2/3)* (-9 + sqrt(849))^(1/3))))/2

the quintic case surprisingly has a closed-form growth rate: a[n] = a[n-1] + a[n-5], powers of matrix [1 0 0 0 1; 1 0 0 0 0; 0 1 0 0 0; 0 0 1 0 0 ; 0 0 0 1 0], growth rate 1.3247179572447460260 = Roots[1+x^4-x^5==0,x] = (27/2 - (3*sqrt(69))/2)^(1/3)/3 + ((9 + sqrt(69))/2)^(1/3)/3^(2/3).  the polynomial factors 1 + x^4 - x^5 = (1 - x + x^2) * (1 + x - x^3) .  the real root (that of the cubic factor), the growth rate, is the plastic number: see Padovan sequence below.

sextic: a[n] = a[n-1] + a[n-6], growth rate 1.28519903324534936790726046413 = N[Roots[1+x^5-x^6==0,x],30]

the next polynomial that factors is 1 + x^10 - x^11 = (1 - x + x^2) * (1 + x - x^3 - x^4 + x^6 + x^7 - x^9) .  the quadratic factor is the same as in the quintic case.

what is the growth rate as function of lag?

because these sequences are powers of a matrix, one can compute high terms very quickly using exponentiation by squaring.  the matrices contain repeated values.  how can this be exploited to compute quicker?

if we take the two oldest numbers, growth rate is slower:

Padovan sequence OEIS A000931 (also Perrin sequence A001608): a[n] = a[n-2] + a[n-3], powers of matrix [0 1 1; 1 0 0 ; 0 1 0], growth rate = plastic number = 1.32471795724474602596090885448 = Roots[0==1+x-x^3,x] = (27/2 - (3*sqrt(69))/2)^(1/3)/3 + ((9 + sqrt(69))/2)^(1/3)/3^(2/3)

a[n] = a[n-3] + a[n-4], OEIS A017817, growth rate = 1.22074408460575947536168534911 = Roots[0==1+x-x^4,x] = sqrt(-4*(2/(3*(9 + sqrt(849))))^(1/3) + ((9 + sqrt(849))/2)^(1/3)/3^(2/3))/2 + sqrt(4*(2/(3*(9 + sqrt(849))))^(1/3) - ((9 + sqrt(849))/2)^(1/3)/3^(2/3) + 2/sqrt(-4*(2/(3*(9 + sqrt(849))))^(1/3) + ((9 + sqrt(849))/2)^(1/3)/3^(2/3)))/2

quintic case a[n] = a[n-4] + a[n-5], growth rate = 1.16730397826141868425604589985 = Roots[0==1+x-x^5,x].

growth rate seems to be 1+ln(2)/lag for large lag (via Mathematica and Inverse Symbolic Calculator).  more series terms?

previously, evaluating recursive sequences modulo N.

motivation was to test something on integer inputs varying in scale exponentially, but the inputs should not have easy factorizations.  a first attempt, the sequence interleaving 2^n and 3*2^n grows more slowly than 2^n but has all easy factorizations.  Fibonacci is better (though it does have algebraic factorizations) but has no degrees of freedom to control growth rate.  a^n+1 and a^n-1 for integer a and n have algebraic factorizations: Cunningham project.  rounded decimal powers of two.