Geek Answers Handbook

What are some algorithms for finding a closed shape function given by an entire sequence?

I am looking for a programmatic way to take a whole sequence and spit out a closed form. Something like:

Given: 1,3,6,10,15

Return: n (n + 1) / 2

Samples may be helpful; language is unimportant.

+6
language-agnostic math algorithm
source share
7 answers

This applies to the extremely deep, complex and active field of mathematics. In some cases, this solution is almost trivial (linear recurrence) and almost impossible in others (I think 2, 3, 5, 7, 11, 13, ...). You can start by looking at the generate functions , and by looking at Herb Wilf an incredible book (see page 1 (2e)) for that matter, but for now it will take you.

But I believe that it is best to refuse the request, request the Sloane comprehensive Encyclopedia of whole sequences when you need to know the answer and instead spend your time reading the opinions of one of the most eccentric characters in this deep subject.

Anyone who tells you that this problem is solvable will sell you snake oil (see page 118 of Wilf’s book (2e).)

+17
source share

In general, there is no function.

In this sequence, the Online Encyclopedia of Integer Sequences finds in its database of interesting integer sequences 133 matches. I 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 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 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 kth line, as shown below. The 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 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 limit yourself to polynomial functions, this is easy to code and only slightly tedious to solve manually.

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 we 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
& Hellip;
y_n = f (n) = a_0 + na_1 + n ^ 2a_2 + \ cdots + n ^ {n-1} a_ {n-1} + n ^ na_n
which is simply a system of linear equations.

+10
source share

If your data is guaranteed to be expressed as a polynomial, I think you can use R (or any set that offers regression fitting of data). If your correlation is exactly 1, then the line is ideal for describing the series.

There are a lot of statistics that are included in the regression analysis, and I am not familiar with even the basics of calculation to give you a lot of details.

But this link to regression analysis in R may help

+3
source share

Axiom Computer Algebra System includes a package for this purpose. You can read your documentation here .

Here's the output for the sequence of your example in FriCAS (Axiom plug):

(3) -> guess([1, 3, 6, 10, 15]) 2 n + 3n + 2 (3) [[function= -----------,order= 0]] 2 Type: List(Record(function: Expression(Integer),order: NonNegativeInteger))
+2
source share

I think your problem is inappropriate. For any finite number of integers in a sequence with no generating function, the next element can be any.

You need to take something about consistency. Is it geometric? Arithmetic?

+1
source share

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

+1
source share

There are no general answers; a simple method can be implemented using the Padé approximation ; in a nutshell, suppose your sequence is a sequence of Taylor expansion coefficients of an unknown function, then apply an algorithm (similar to the continuous fraction algorithm) to "simplify" this Taylor expansion (more precisely: find a rational function is very close to the original (and truncated) function The Maxima program can do this: look at the "pade" on the page: http://maxima.sourceforge.net/docs/manual/maxima_28.html

Another answer talks about the guessing package in the FriCAS Axiom plug (see jmbr's previous answer). If I'm not mistaken; this package itself is inspired by Rate by Christian Krattenthaler; you can find it here: http://www.mat.univie.ac.at/~kratt/rate/rate.html Perhaps viewing the source may tell you about other methods.

0
source share

More articles:


All Articles