I'm looking form a programatic way to take an integer sequence and spit out a closed form function. Something like:
Given: 1,3,6,10,15
Return: n(n+1)/2
Samples could be useful; the language is unimportant.
views:
577answers:
6
+1
A:
I think your problem is ill-posed. Given any finite number of integers in a sequence with no generating function, the next element can be anything.
You need to assume something about the sequence. Is it geometric? Arithmetic?
SplittingField
2009-06-25 02:01:51
All kinds of sequences. Maybe a 'sequence' is given where there isn't a generating function. I'd like to be able to handle that case as well. I'm at square one right now, so if you think there is some way I should re-factor the question, I'd appreciate your input.
wkf
2009-06-25 02:18:54
+2
A:
If your data is guaranteed to be expressible as a polynomial, I think you would be able to use R (or any suite that offers regression fitting of data). If your correlation is exactly 1, then the line is a perfect fit to describe the series.
There's a lot of statistics that goes into regression analysis, and I am not familiar enough with even the basics of calculation to give you much detail.
But, this link to regression analysis in R might be of assistance
Mark Rushakoff
2009-06-25 02:01:54
You could form the polynomial by taking all of the roots given, say a, b and c, and write it in the form f(x) = (x-a)*(x-b)*(x-c). But that doesn't mean that they are not other polynomials that would satisfy it.
sharth
2009-06-25 02:07:21
+14
A:
This touches an extremely deep, sophisticated and active area of mathematics. The solution is damn near trivial in some cases (linear recurrences) and damn near impossible in others (think 2, 3, 5, 7, 11, 13, ....) You could start by looking at generating functions for example and looking at Herb Wilf's incredible book (cf. page 1 (2e)) on the subject but that will only get you so far.
But I think your best bet is to give up, query Sloane's comprehensive Encyclopedia of Integer Sequences when you need to know the answer, and instead spend your time reading the opinions of one of the most eccentric personalities in this deep subject.
Anyone who tells you this problem is solveable is selling you snake oil (cf. page 118 of the Wilf book (2e).)
Jason
2009-06-25 02:10:19
Some fantastic links; exactly what I was looking for. I had a feeling the answer would be complicated. I think perhaps I need more knowledge of the subject matter before I can ask the right questions. Thanks!
wkf
2009-06-25 02:25:35
Waugh, I took too long texifying my solution. You beat me by a mile :)
ephemient
2009-06-25 02:43:46
You might also want to look at the book "Concrete Mathematics." You may find it more accessible than Wilf's book.
John D. Cook
2009-06-25 02:54:32
The problem I have with this answer is that it implicitly assumes that there is *one* correct function, when in fact there are an infinite number of closed form functions that go through any specified finite set of points -- as just 1 example, a degree-n polynomial will go through any n+1 given points. But the bigger problem is: there is no way to choose which function of these functions is "best". Why? One reason is because the next number in the sequence **could be anything**. I'm -1ing until you mention this up front.
j_random_hacker
2009-06-26 11:24:15
You gave an example algorithm, while the "correct" answer asserted that no such algorithm exists. Interesting.Your answer assumes that the sequence is finite, which I think is a correct assumption.
Martin Hock
2009-06-25 04:02:33
@Martin: ephemient clearly stated that the solution state was restricted to polynomials of degree n, which can always be fit to a finite set of n points.
Autoplectic
2009-06-25 07:08:01
Small correction: a polynomial of degree n can always be fit to a finite set of n+1 points.
ephemient
2009-06-25 20:57:03
+1. This should be the correct answer IHMO. The most important point to make is that the problem is sorely underconstrained, and I think the list of 5 different plausible functions for 1, 3, 6, 10, 15 you gave demonstrates that quite nicely.
j_random_hacker
2009-06-26 11:29:20
A:
The Axiom computer algebra system includes a package for this purpose. You can read its documentation here.
Here's the output for your example sequence in FriCAS (a fork of Axiom):
(3) -> guess([1, 3, 6, 10, 15])
2
n + 3n + 2
(3) [[function= -----------,order= 0]]
2
Type: List(Record(function: Expression(Integer),order: NonNegativeInteger))
jmbr
2009-06-25 22:37:44