# Polynomial generating a given sequence

**URL:** <https://boards.straightdope.com/t/polynomial-generating-a-given-sequence/415752>\
**Category:** Factual Questions\
**Created:** [August 15, 2007, 11:31pm UTC](https://boards.straightdope.com/t/polynomial-generating-a-given-sequence/415752 "2007-08-15T23:31:04Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![psychonaut](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/psychonaut/32/4655_2.png) [@psychonaut](https://boards.straightdope.com/u/psychonaut)\
**Post date:** [August 15, 2007, 11:31pm UTC](https://boards.straightdope.com/t/polynomial-generating-a-given-sequence/415752/1 "2007-08-15T23:31:04Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [August 15, 2007, 11:55pm UTC](https://boards.straightdope.com/t/polynomial-generating-a-given-sequence/415752/2 "2007-08-15T23:55:41Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![yabob](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/yabob/32/2821_2.png) [@yabob](https://boards.straightdope.com/u/yabob)\
**Post date:** [August 15, 2007, 11:57pm UTC](https://boards.straightdope.com/t/polynomial-generating-a-given-sequence/415752/3 "2007-08-15T23:57:48Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\
**Post date:** [August 16, 2007, 12:04am UTC](https://boards.straightdope.com/t/polynomial-generating-a-given-sequence/415752/4 "2007-08-16T00:04:11Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Happy\_Fun\_Ball](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/happy_fun_ball/32/17664_2.png) [@Happy\_Fun\_Ball](https://boards.straightdope.com/u/Happy_Fun_Ball)\
**Post date:** [August 16, 2007, 3:30am UTC](https://boards.straightdope.com/t/polynomial-generating-a-given-sequence/415752/5 "2007-08-16T03:30:49Z")

</div>

I think the easiest way is to use a divided difference table. This [site](http://www.maths.lancs.ac.uk/~gilbert/m243a/node6.html) 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…

---

<div class="post-metadata">

**Author:** ![sinjin](https://avatars.discourse-cdn.com/v4/letter/s/ebca7d/32.png) [@sinjin](https://boards.straightdope.com/u/sinjin)\
**Post date:** [August 16, 2007, 3:43am UTC](https://boards.straightdope.com/t/polynomial-generating-a-given-sequence/415752/6 "2007-08-16T03:43:00Z")

</div>

Also of note is the [On-Line Encyclopedia of Integer Sequences](http://www.research.att.com/~njas/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.

---

<div class="post-metadata">

**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\
**Post date:** [August 16, 2007, 2:57pm UTC](https://boards.straightdope.com/t/polynomial-generating-a-given-sequence/415752/7 "2007-08-16T14:57:42Z")

</div>

There are a _lot_ of methods for [polynomial interpolation](http://en.wikipedia.org/wiki/Polynomial_interpolation). My “when I’m just plain lazy” favorite is [Lagrange interpolation](http://www.math-linux.com/spip.php?article71). But if I wanted to get serious I would use something like [Chebyshev polynomials](http://en.wikipedia.org/wiki/Chebyshev_polynomials).
