Binary Recurrence Sequences

Question

A binary recurrence sequence is a recursively-defined sequence of the following form:

$$F(1) = a_1 \\ \vdots \\ F(y) = a_y \\ F(n) = \alpha F(n-x) + \beta F(n-y), n > y$$

This is a generalization of the Fibonacci (\$x = 1, y = 2, a = [1, 1], \alpha = 1, \beta = 1\$) sequence and the Lucas (\$x = 1, y = 2, a = [2, 1], \alpha = 1, \beta = 1\$) sequence.

The Challenge

Given \$n, x, y, a, \alpha\$, and \$\beta\$, in any reasonable format, output the \$n\$th term of the corresponding binary recurrence sequence.

Rules

• You may choose for the sequence to be either 1-indexed or 0-indexed, but your choice must be consistent across all inputs, and you must make note of your choice in your answer.
• You may assume that no invalid inputs would be given (such as a sequence that terminates prior to \$n\$, or a sequence that references undefined terms, like \$F(-1)\$ or \$F(k)\$ where \$k > n\$). As a result of this, \$x\$ and \$y\$ will always be positive.
• The inputs and outputs will always be integers, within the boundaries of your language's natural integer type. If your language has unbounded integers, the inputs and outputs will be within the range \$[-2^{31}, 2^{31}-1]\$ (i.e. the range for a 32-bit signed two's complement integer).
• \$a\$ will always contain exactly \$y\$ values (as per the definition).

Test Cases

Note: all test cases are 0-indexed.

x = 1, y = 2, a = [1, 1], alpha = 1, beta = 1, n = 6 => 13
x = 1, y = 2, a = [2, 1], alpha = 1, beta = 1, n = 8 => 47
x = 3, y = 5, a = [2, 3, 5, 7, 11], alpha = 2, beta = 3, n = 8 => 53
x = 1, y = 3, a = [-5, 2, 3], alpha = 1, beta = 2, n = 10 => -67
x = 5, y = 7, a = [-5, 2, 3, -7, -8, 1, -9], alpha = -10, beta = -7, n = 10 => 39

• Dennis: Does taking a in reversed order count as reasonable?
• user45941: @Dennis Yes, it does.

Answer 1

Jelly, 11 bytes

4Cịæ.5ṭμ¡6ị

Try it online! 1 | 2 | 3 | 4 | 5

How it works

4Cịæ.5ṭμ¡6ị Main link. Arguments: a; [x, y]; [α, β]; n (1-based)
 μ Combine the links to the left into a chain.
 ¡ Execute that chain n times, updating a after each execution.
4 Yield [x, y].
 C Complement; yield [1 - x, 1 - y].
 ị Retrieve the elements of a at those indices.
 Indexing is 1-based and modular in Jelly, so this retrieves
 [a[-x], a[-y]] (Python syntax).
 5 Yield [α, β].
 æ. Take the dot product of [a[-x], a[-y]] and [α, β].
 6 Yield n.
 ị Retrieve the element of a at index n.

Answer 2

Python 2, 62 bytes

x,y,l,a,b=input();f=lambda n:l[n]if n<y else a*f(n-x)+b*f(n-y)

A direct recursive solution. All inputs are taken from STDIN except for n as a function argument, a split that's is allowed by default (though contentiously).

There doesn't seem to be a way to save bytes with and/or in place of if/else because l[n] could be falsey as 0.

Answer 3

JavaScript (ES6), (削除) 51 (削除ここまで) 44 bytes

(x,y,z,a,b)=>g=n=>n<y?z[n]:a*g(n-x)+b*g(n-y)

Note that the function is partially curried, e.g. f(1,2,[1,1],1,1)(8) returns 34. It would cost 2 bytes to make the intermediate functions independent of each other (currently only the last generated function works correctly).

Edit: Saved 7 bytes thanks to @Mego pointing out that I'd overlooked that the the passed-in array always contains the first y elements of the result.

• Neil: @Mego I know I often overlook details of questions but that one struck me as particularly subtle.

Answer 4

Haskell, (削除) 54 (削除ここまで) 48 bytes

l@(x,y,a,p,q)%n|n<y=a!!n|k<-(n-)=p*l%k x+q*l%k y

Answer 5

Python 2, 59 bytes

x,y,A,a,b,n=input()
exec'A+=a*A[-x]+b*A[-y],;'*n
print A[n]

Test it on Ideone.

Answer 6

J, 43 bytes

{:{](],(2>@{[)+/ .*]{~1-@>@{[)^:(3>@{[)>@{.

Given an initial sequence of terms A, computes the next term n times using the parameters of x, y, α, and β. Afterwards, it selects the n^th term in the extended sequence and outputs it as the result.

Usage

Since J only supports 1 or 2 arguments, I group up all the parameters as a list of boxed lists. The initial seed values A are first, followed by the parameters of x and y as a list, followed by the parameters of α and β as a list, and ending with the value n.

 f =: {:{](],(2>@{[)+/ .*]{~1-@>@{[)^:(3>@{[)>@{.
 2 3 5 7 11;3 5;2 3;8
┌──────────┬───┬───┬─┐
│2 3 5 7 11│3 5│2 3│8│
└──────────┴───┴───┴─┘
 f 2 3 5 7 11;3 5;2 3;8
53
 f _5 2 3 _7 _8 1 _9;5 7;_10 _7;10
39