Polynomial generating a given sequence

I just watched the eighteenth episode of Lost, which revolves around the number sequence (4, 8, 15, 16, 23, 42). I looked around on the net and found that someone had discovered that the polynomial P(x) = (1/40)(-9x^5 + 125x^4 - 585x^3 + 1075x^2 - 446x + 160) generates this sequence for x = (0, 1, 2, 3, 4, 5).

How did this person discover this polynomial? Is there some algorithm which takes a finite integer sequence (s_0, s_1, …, s_n) and returns a polynomial P(x) producing that sequence for x = 0 through n?

Note: I haven’t watched the rest of Lost yet. Please don’t spoil it for me by telling me what the numbers mean.

Yes, it’s easy enough to do it. Here’s the idea:

Suppose you want a polynomial P(x) to give a particular value s_0 on input 0. Then you know P(x) is of the form Q(x) * x + s_0.

Now, furthermore, you want it to give the value s_1 on input 1. Therefore, Q(1) * 1 + s_0 = s_1. We see that Q(1) = (s_1 - s_0)/1. Letting P_1(x) = Q(x+1), we just need to find P_1(x) such that P_1 gives the value s_1 - s_0 on input 0. Thus, P_1(x) must be of the form Q_1(x) * x + s_1 - s_0.

Continuing on in this way, you eventually get all the values you need.

It’s quite easy.

To fit an nth degree polynomial to n+1 points, simply plug in the values for each pair with unknowns for the coefficients. That gives you n+1 linear equations in n+1 unknowns to solve.

So, for your case, let ax^5 + bx^4 + cx^3 + dx^2 + ex + f be our polynomial

f = 4, plugging in (0,4)
a + b + c + d + e + f = 8, plugging in (1,8)
32a + 16b + 8c + 4d + 2e + f = 15, plugging in (2,15)

etc. Then solve the 6 linear equations.

Meh, I wanted to reword that post but I guess it’s too late. Well, here’s my rewording anyway:

Suppose you want a polynomial P(x) to give a particular value s_0 on input 0. Then you know P(x) is of the form Q(x) * x + s_0 for some polynomial Q(x); that is to say, the lowest degree term of P is s_0, and all the other degree terms, when “downshifted”, give Q(x). Now, we’ll reanalyze it a little for our convenience, by defining R(x) as Q(x+1). Then, we have that P(x) = R(x-1) * x + s_0 for some polynomial R(x).

What’s so great about that? Well, now, you want the polynomial P(x) to give a particular value s_1 on input 1. That means R(1-1) * 1 + s_0 = s_1. Thus, we have a specific value for R(x) to give on input 0; we can recursively begin setting R(x) up to do this, the same way as with P(x).

Continuing on in this way, you eventually get all the values you need, and your recursion can bottom out to a zero polynomial (or whatever else you like).
On edit: Aw, hell, yabob put it better/simpler anyway.

I think the easiest way is to use a divided difference table. This site has a decent description of how to do it. I can whip out a polynomial of any degree you choose in <5 minutes using Excel with this (or in ~15 minutes with pencil and paper), including polynomials where the derivatives are specified. If you want more details, just ask…

Also of note is the On-Line Encyclopedia of Integer Sequences. You can type in a sequence of numbers and see if it’s “interesting”. Good for a few hours of summer browsing. You can look up the “Lost Numbers” there, too.

There are a lot of methods for polynomial interpolation. My “when I’m just plain lazy” favorite is Lagrange interpolation. But if I wanted to get serious I would use something like Chebyshev polynomials.