CODEWITHSUNDEEP
algorithmlanguage-agnosticmath
wkf
wkf

Reputation: 842

What are some algorithms for finding a closed form function given an integer sequence?

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.

Upvotes: 6

Views: 5424

Answers (7)

Thomas Baruchel
Thomas Baruchel

Reputation: 7517

There is no general answers; a simple method can be implemented bu using Pade approximants; in two words, assume your sequence is a sequence of coefficients of the Taylor expansion of an unknown function, then apply an algorithm (similar to the continued-fraction algorithm) in order to "simplify" this Taylor-expansion (more precisely: find a rational function very close to the initial (and truncated) function. The Maxima program can do it: look at "pade" on the page: http://maxima.sourceforge.net/docs/manual/maxima_28.html

Another answer tells about the "guess" package in the FriCAS fork of Axiom (see previous answer by jmbr). If I am not wrong; this package is itself inspired from the Rate program by Christian Krattenthaler; you can find it here: http://www.mat.univie.ac.at/~kratt/rate/rate.html Maybe looking at its source could tell you about other methods.

Upvotes: 1

ephemient
ephemient

Reputation: 204956

There is no one function in general.

For the sequence you specified, The On-Line Encyclopedia of Integer Sequences finds 133 matches in its database of interesting integer sequences. I've copied the first 5 here.

A000217 Triangular numbers: a(n) = C(n+1,2) = n(n+1)/2 = 0+1+2+...+n.
0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, 190, 210, 231, 253, 276, 300, 325, 351, 378, 406, 435, 465, 496, 528, 561, 595, 630, 666, 703, 741, 780, 820, 861, 903, 946, 990, 1035, 1081, 1128, 1176, 1225, 1275, 1326, 1378, 1431

A130484 Sum {0<=k<=n, k mod 6} (Partial sums of A010875).
0, 1, 3, 6, 10, 15, 15, 16, 18, 21, 25, 30, 30, 31, 33, 36, 40, 45, 45, 46, 48, 51, 55, 60, 60, 61, 63, 66, 70, 75, 75, 76, 78, 81, 85, 90, 90, 91, 93, 96, 100, 105, 105, 106, 108, 111, 115, 120, 120, 121, 123, 126, 130, 135, 135, 136, 138, 141, 145, 150, 150, 151, 153

A130485 Sum {0<=k<=n, k mod 7} (Partial sums of A010876).
0, 1, 3, 6, 10, 15, 21, 21, 22, 24, 27, 31, 36, 42, 42, 43, 45, 48, 52, 57, 63, 63, 64, 66, 69, 73, 78, 84, 84, 85, 87, 90, 94, 99, 105, 105, 106, 108, 111, 115, 120, 126, 126, 127, 129, 132, 136, 141, 147, 147, 148, 150, 153, 157, 162, 168, 168, 169, 171, 174, 178, 183

A104619 Write the natural numbers in base 16 in a triangle with k digits in the k-th row, as shown below. Sequence gives the leading diagonal.
1, 3, 6, 10, 15, 2, 1, 1, 14, 3, 2, 2, 5, 12, 4, 4, 4, 13, 6, 7, 11, 6, 9, 9, 10, 7, 12, 13, 1, 0, 1, 10, 5, 1, 12, 8, 1, 1, 14, 1, 9, 7, 1, 4, 3, 1, 2, 2, 1, 3, 4, 2, 7, 9, 2, 14, 1, 2, 8, 12, 2, 5, 10, 3, 5, 11, 3, 8, 15, 3, 14, 6, 3, 7, 0, 4, 3, 13, 4, 2, 13, 4, 4, 0, 5, 9, 6, 5, 1, 15, 5, 12, 11, 6

A037123 a(n) = a(n-1) + Sum of digits of n.
0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 46, 48, 51, 55, 60, 66, 73, 81, 90, 100, 102, 105, 109, 114, 120, 127, 135, 144, 154, 165, 168, 172, 177, 183, 190, 198, 207, 217, 228, 240, 244, 249, 255, 262, 270, 279, 289, 300, 312, 325, 330, 336, 343, 351, 360, 370, 381

If you restrict yourself to polynomial functions, this is easy to code up, and only mildly tedious to solve by hand.

Let f(x)=a_0+a_1x+a_2x^2+\cdots+a_{n-1}x^{n-1}+a_nx^n, for some unknown a_0\ldots a_n

Now solve the equations
y_0=f(0)=a_0
y_1=f(1)=a_0+a_1+a_2+\cdots+a_{n-1}+a_n
y_2=f(2)=a_0+2a_1+4a_2+\cdots+2^{n-1}a_{n-1}+2^na_n
…
y_n=f(n)=a_0+na_1+n^2a_2+\cdots+n^{n-1}a_{n-1}+n^na_n
which simply a system of linear equations.

Upvotes: 10

jason
jason

Reputation: 241741

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 solvable is selling you snake oil (cf. page 118 of the Wilf book (2e).)

Upvotes: 17

jmbr
jmbr

Reputation: 3348

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))

Upvotes: 2

lhf
lhf

Reputation: 72402

If your sequence comes from a polynomial then divided differences will find that polynomial expressed in terms of the Newton basis or binomial basis. See this.

Upvotes: 1

Mark Rushakoff
Mark Rushakoff

Reputation: 258388

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

Upvotes: 3

SplittingField
SplittingField

Reputation: 741

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?

Upvotes: 1

Related Questions