13
\$\begingroup\$

Background

A linear recurrence relation is a description of a sequence, defined as one or more initial terms and a linear formula on last \$k\$ terms to calculate the next term. (For the sake of simplicity, we only consider homogeneous relations, i.e. the ones without a constant term in the formula.)

A formal definition of a linear recurrence relation looks like this, where \$y_n\$ is the desired sequence (1-based, so it is defined over \$n\ge 1\$) and \$x_i\$'s and \$a_i\$'s are constants:

$$ y_n = \begin{cases} x_n, & 1\le n\le k \\ a_1y_{n-1}+a_2y_{n-2}+\cdots+a_ky_{n-k}, & k<n \end{cases} $$

In this challenge, we will accelerate this sequence by converting it to a matrix form, so that the \$n\$-th term can be found by repeated squaring of the matrix in \$O(\log n)\$ steps, followed by inner product with the vector of initial terms.

For example, consider the famous Fibonacci sequence: its recurrence relation is \$y_n=y_{n-1} + y_{n-2}\$ with \$k=2\$, and let's use the initial values \$x_1=x_2=1\$. The recurrence relation can be converted to a matrix form:

$$ \begin{bmatrix} y_{n-1} \\ y_{n} \end{bmatrix} = \begin{bmatrix} y_{n-1} \\ y_{n-1}+y_{n-2} \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}\begin{bmatrix} y_{n-2} \\ y_{n-1} \end{bmatrix} $$

So multiplying the matrix once advances the sequence by one term. Since this holds for any \$n\$, it can be extended all the way until we reach the initial terms:

$$ \begin{bmatrix} y_{n-1} \\ y_{n} \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}\begin{bmatrix} y_{n-2} \\ y_{n-1} \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^2\begin{bmatrix} y_{n-3} \\ y_{n-2} \end{bmatrix} \\ = \cdots = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^{n-2}\begin{bmatrix} y_{1} \\ y_{2} \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^{n-2}\begin{bmatrix} 1 \\ 1 \end{bmatrix} $$

In general, one way to construct such a matrix is the following:

$$ \begin{bmatrix} y_{n-k+1} \\ y_{n-k+2} \\ \vdots \\ y_{n-1} \\ y_{n} \end{bmatrix} = \begin{bmatrix} 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ & \vdots & & & \vdots \\ 0 & 0 & 0 & \cdots & 1 \\ a_k & a_{k-1} & a_{k-2} & \cdots & a_1 \end{bmatrix}\begin{bmatrix} y_{n-k} \\ y_{n-k+1} \\ \vdots \\ y_{n-2} \\ y_{n-1} \end{bmatrix} $$

Note that, if you reverse the vectors and the matrix in every dimension, the equation still holds, retaining the property of "advancing a term by matmul-ing once". (Actually any permutation will work, given that the rows and columns of the matrix are permuted in the same way.)

Challenge

Given the list of coefficients \$a_1,\cdots,a_k\$, construct a matrix that represents the recurrence relation (so that its powers can be used to accelerate the computation of \$n\$-th term of the sequence).

You can take the coefficients in reverse order, and you can optionally take the value \$k\$ as a separate input. \$k\$ (the number of terms) is at least 1.

Standard rules apply. The shortest code in bytes wins.

Test cases

In all cases, any other matrix that can be formed by permuting rows and columns in the same way is also valid.

Input
[1,1]
Output
[[0, 1],
 [1, 1]]

Input
[5]
Output
[[5]]

Input
[3, -1, 19]
Output
[[0,  1,  0],
 [0,  0,  1],
 [19, -1, 3]]
or reversed in both dimensions:
[[3, -1, 19],
 [1, 0,  0],
 [0, 1,  0]]
or cycled once in both dimensions:
[[3, 19, -1],
 [0, 0,  1],
 [1, 0,  0]]
etc.
\$\endgroup\$

13 Answers 13

8
\$\begingroup\$

MATL, 8 7 bytes

-1 byte thanks to @LuisMendo

Xy4LY)i

Takes the coefficients in reverse order

Try it online!

Explanation

Xy4LY)i
Xy        : Create an identity matrix of size equal to input
  4LY)    : Remove the first row
      i   : Insert input onto the stack
| improve this answer | |
\$\endgroup\$
6
\$\begingroup\$

J, 10 8 bytes

Returns the matrix reversed in both dimensions.

,}:@=@/:

Try it online!

How it works

 ,}:@=@/:   input:             3 _1 19
       /:   indices that sort: 1 0 2
            (just to get k different numbers)
     =@     self-classify:     1 0 0
                               0 1 0
                               0 0 1
  }:@       drop last row:     1 0 0
                               0 1 0
 ,          prepend input:     3 _1 19
                               1  0  0
                               0  1  0
| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

JavaScript (ES6), 36 bytes

a=>a.map((_,i)=>i?a.map(_=>+!--i):a)

Try it online!

Returns:

$$ \begin{bmatrix} a_1 & a_2 & a_3 & \cdots & a_{k-1} & a_k \\ 1 & 0 & 0 & \cdots & 0 & 0 \\ 0 & 1 & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 1 & 0 \end{bmatrix} $$

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Io, 56 bytes

method(a,a map(i,v,if(i<1,a,a map(I,v,if(I==i-1,1,0)))))

Try it online!

Explanation

method(a,                                              )   // Input an array.
         a map(i,v,                                   )    // Map. i = index, v = value
                   if(i<1,                           )     //     If the indice is 0,
                          a,                               //         Return the inputted list
                            a map(I,v,              )      //     Otherwise, map: (I is the current index)
                                      if(I==i-1,   )       //     If I == i-1,
                                                1,         //         Return 1,
                                                  0        //     Otherwise 0
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

APL (Dyalog Unicode), 10 bytes

⊢⍪¯1↓⍋∘.=⍋

Try it online!

Tacit function taking the list of coefficients on the right.

Explanation

⊢⍪¯1↓⍋∘.=⍋
     ⍋   ⍋  ⍝ Grade up to obtain a list of k distinct values
      ∘.=   ⍝ Outer product with operation `equals` (identity matrix)
  ¯1↓       ⍝ Drop the last row
⊢⍪          ⍝ Prepend the list of coefficients
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Python 2, 46 bytes

lambda l,k:[l]+zip(*[iter(([1]+[0]*k)*~-k)]*k)

Try it online!

Takes input as a tuple l and number of terms k, and outputs with both rows and columns reversed.

The idea is to use the zip/iter trick to create an identity-like matrix by splitting a repeating list into chunks. The is similar to my solution to construct the identity matrix but changed to have one fewer row by changing the inner multiplier k to k-1 (written ~-k).

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Cool, a nice trick of which I was unaware! \$\endgroup\$ – Jonathan Allan Jul 31 at 11:51
1
\$\begingroup\$

Charcoal, 12 bytes

IEθ⎇κEθ⁼⊖κμθ

Try it online! Link is to verbose version of code. Produces the "reversed in both directions" output. Works by replacing the first row of a shifted identity matrix with the input. Explanation:

 Eθ             Map over input list
   ⎇κ           If this is not the first row then
     Eθ         Map over input list
       ⁼⊖κμ     Generate a shifted identity matrix
           θ    Otherwise replace the first row with the input
I               Cast to string for implicit print
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ @xash Actually I was thinking of a different permutation, but either way I've probably misunderstood the question. I'll rewrite it to use the reversed in both directions option. \$\endgroup\$ – Neil Jul 30 at 12:48
1
\$\begingroup\$

R, 34 bytes

function(r,k)rbind(diag(k)[-1,],r)

Try it online!

Takes the length as well; the TIO link has a k=length(r) argument so you can just input the recurrence relation.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Python 3, 60 58 bytes

-2 bytes thanks to @JonathanAllan

lambda a,k:[map(i.__eq__,range(k))for i in range(1,k)]+[a]

Try it online!

Takes the coefficients in reverse order

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ -1 byte: lambda a,k,r=range(k):[[i==j for j in r]for i in r[1:]]+[a] \$\endgroup\$ – ManfP Jul 30 at 19:05
  • \$\begingroup\$ @ManfP - that's invalid, k is not defined at the point it's being used by range (TIO). \$\endgroup\$ – Jonathan Allan Jul 31 at 1:12
  • \$\begingroup\$ lambda a,k:[map(i.__eq__,range(k))for i in range(1,k)]+[a] is 58. Returns a list of iterables, and False==0 and True==1. \$\endgroup\$ – Jonathan Allan Jul 31 at 1:25
  • \$\begingroup\$ @JonathanAllan oh sorry you are totally right, the perils of testing locally with shadowing variable names... \$\endgroup\$ – ManfP Jul 31 at 10:08
1
\$\begingroup\$

05AB1E, 7 bytes

āDδQ`\)

Outputs reversed in both dimensions.

Try it online or verify all test cases.

Explanation:

ā        # Push a list in the range [1,length] (without popping the implicit input-list)
 D       # Duplicate it
  δ      # Apply double-vectorized:
   Q     # Check if it's equal
         # (this results in an L by L matrix filled with 0s, with a top-left to
         #  bottom-right diagonal of 1s; where `L` is the length of the input-list)
    `    # Pop and push all rows of this matrix separated to the stack
     \   # Discard the last row
      )  # And wrap all list on the stack into a list
         # (after which the matrix is output implicitly as result)
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Jelly, 8 bytes

W;J⁼þṖ$$

A monadic Link accepting a list which yields a list of lists in the reversed rows & columns permutation.

Try it online!

How?

W;J⁼þṖ$$ - Link: list A                    e.g. [5,2,5,4]
W        - wrap (A) in a list                   [[5,2,5,4]]
       $ - last two links as a monad - f(A):
  J      -   range of length (A)                [1,2,3,4]
      $  -   last two links as a monad - f(J):
     Ṗ   -     pop                              [1,2,3]
    þ    -     (J) outer product (that) with:
   ⁼     -       equals?                        [[1,0,0,0],[0,1,0,0],[0,0,1,0]]
 ;       - (W) concatenate (that)               [[5,2,5,4],[1,0,0,0],[0,1,0,0],[0,0,1,0]]
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

C (gcc), 90 89 80 bytes

Saved 9 bytes thanks to ceilingcat!!!

i;j;f(a,k)int*a;{for(i=k;i--;puts(""))for(j=k;j--;)printf("%d ",i?i-1==j:a[j]);}

Try it online!

Inputs an array of coefficients (in forward order) along with its length.
Prints a matrix that represents the recurrence relation.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Google Sheets, 52

Closing Parens discounted.

  • Input cells is Row 1, starting in column B.
  • A2 - =COUNTA(1:1). Rules say that we can take this as input too, so I have discounted this as well. (Our "k")
  • A3 - =ArrayFormula(IFERROR(0^MOD(SEQUENCE(A2-1,A2)-1,A2+1)))

The output matrix starts in B1.

How it works

  1. Since this is a spreadsheet, the input cells give us free output too. As long is it's the first row and we end up with a square set of cells, we're good. If this didn't count, we'd have to do this with Column 1 instead to use TRANSPOSE() to copy the input. (Because it's smaller than ArrayFormula())
  2. Cache the number of columns in A2
  3. Generate a k-1 x k matrix using SEQUENCE. Values are MOD number of columns + 1. (Diagonals are 0, otherwise something else).
  4. Since 0^0 is 1 in Sheets, that means this effectively is a Boolean NOT() converted to an integer.
  5. IFERROR handles input size of 1. (Output a Blank)
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.