Ask Your Question

ternary recurrence sequence

asked 2024-03-18 17:52:47 +0200

brennan gravatar image

updated 2024-03-18 23:28:16 +0200

Max Alekseyev gravatar image

Is there a built in general recurrence sequence function like the binary recurrence sequence?

def a(n):
    return BinaryRecurrenceSequence(a,b,c,d)

returns the sequence $U_0=c$, $U_1=d$, and $U_n=aU_{n-1}+bU_{n-2}$.

I would like something that returns $U_n=aU_{n-1}+bU_{n-2}+cU_{n-3}$

Any help is much appreciated!

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2024-03-19 11:18:11 +0200

Max Alekseyev gravatar image

updated 2024-03-19 11:19:22 +0200

If you need to compute $U_n$ efficiently - here is a way:

u0=u1=u2=1     # initial values
x = polygen(QQ)
C = companion_matrix(x^3-a*x^2-b*x-c)

def U(n):
    return (vector([u0,u1,u2]) * C^n)[0]

Alternatively you can use LFSR as described at

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2024-03-18 17:52:47 +0200

Seen: 97 times

Last updated: Mar 19