Calculating polynomal function [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question does not appear to be about programming within the scope defined in the help center.

Closed 8 years ago.

Improve this question

Considering a sequence of integers, how can I find the polynomial function that models it? (i.e generates the first item for x=1, second items for x=2, etc)

For example, let us consider this sequence: 1, 683, 44287, 838861. How do I find that the matching generating function is y = 118008*x^3 - 686587*x^2 + (10^6)*x - 665807.

note: Code must work up to tenth degree.

Answer 1

This isn't really a java question... it's a basic math question. If you consider [1, 4, 9, 16, 25], take the differences between them, you get [3, 5, 7, 9]. Do that again and you get [2, 2, 2].

Now look at [1, 8, 27, 64, 125]... the differences there are [7, 19, 37, 61]. The differences of those work out to [12, 18, 24] and the differences yet again are [6, 6].

If you did it for x^4, then the fourth set of differences you'd have would be [24, 24, 24...] etc.

In other words, if the highest term in the equation is a*x^n, then the ultimate difference you get, after taking the difference n times, is a*n!.

So, starting with [1, 683, 44287, 838861] the first difference is [682, 43604, 794574], the second difference is [42922, 750970] and the third difference is [708048]. So divide that by 3! or 6 and you get the first term of 118008*x^3.

Now you get to go back, subtract 118008*x^3 from your original sequence, and figure out the x^2 term from your new sequence of [-118007, -943381, -3141929, -6713651]. There's probably a shortcut you can put in here so you don't have to go all the way back to the beginning, but that's up to you to figure out.