Small challenge

[robve]

(04-23-2023 01:01 PM)robve Wrote:  We can use the Chains of Recurrences algebra to optimize sequence evaluations such as x^10. We only need 10 additions to produce the next value in the sequence.

To expand \( x^{10} \) to CR form, let \( x \) be the integer sequence CR \( x =\{1,+,1\} \) expand to the CR \( \{1,+,1\}\times\{1,+,1\}\times\{1,+,1\}\times\{1,+,1\}\times\{1,+,1\}\times\{1,+​,1\}\times\{1,+,1\}\times\{1,+,1\}\times\{1,+,1\}\times\{1,+,1\} \). Simplify using the CR rule \( \{\phi_0,+,f_1\} \times \{\psi_0,+,g_1\} \Rightarrow
\{\phi_0\times\psi_0,+,\{\phi_0,+,f_1\}\times g_1+\{\psi_0,+,g_1\}\times f_1+f_1\times g_1\} \) giving the polynomial CR \( \{1,+,1023,+, 57002,+, 874500,+, 5921520,+, 21538440,+, 46070640,+, 59875200,+, 46569600,+, 19958400,+, 3628800 \} \). Note that each value is produced with just 10 additions.

Now you may ask, what's the difference here with difference tables? These CR coefficients look familiar. And you are correct! Polynomial CR forms are identical to difference table upper diagonals of polynomials evaluated over equidistant grids. CRs are not restricted to polynomials, it's just that CRs of polynomials are easy to construct with difference tables or with the CR algebra.

A difference table for the sequence shown in the picture reveals that the sequence is an x^10 polynomial since the 11th difference column is zero:
   

Not surprising, starting from x=1 you get the diagonal that matches the CR coefficients:
   

- Rob