Find the next entry in a sequence

In Facebook, Xing, Google+, Vk.com, Linkedin and other of these social media networks we are often encountered with a trivial question like this:
1->2 2->8 3->18 4->32 5->50 6->72 7->?
There are some easy patterns. Either it is some polynomial formula or some trick with the digits.
But the point is, that any such sequence can easily be fullfilled by a polynomial formula. That means we can put any value for 7 and make it work. Or any answer is correct. So what would probably be the real question is the most simple function to full-fill the given constraints. Simplicity can be measured in some way… If the solution is unique is unclear, but let us just look at the polynomial solution.

A function is needed that takes as parameter a list of key-value-pairs (or a hash map) and that yields a function such that the function of any of the key is the associated value.

Assuming a polynomial function in one variable we can make use of the chinese remainder theorem, which can be applied to univariate polynomials over a field $F$ as well as to integral numbers. For a polynomial p(X) we have

$p(x) \equiv p(X) \mod X-x$

where $X$ is the polynomial variable and $x\in F$ is a concrete value.

We are looking for a polynomial $p(X)$ such that for given values $x_0,\ldots x_{n-1}, y_0,\ldots,y_{n-1} \in F$ we have

$\bigwedge_{i=0}^{n-1} p(x_i) = y_i$

or in another way

$\bigwedge_{i=0}^{n-1} p(X) \equiv y_i \mod X-x_i$

which is exactly the Chinese remainder theorem.
Let

$I=\{0,\ldots,n-1\}$

and

$\bigwedge_{j=0}^{n-1} I_j = I \setminus \{j\}$

We can see that for all $i \in I$ the polynomials

$e_i = \prod_{j \in I_j} \frac{X-x_j}{x_i-x_j}$

have the properties

$e_i(x_i)=1$

$\bigwedge_{j \in I_i} e_i(x_j)=0$

$\bigwedge_{i \in I}\bigwedge_{j \in J} e_i(x_j)=\delta_{i,j}$

where $\delta_{i,j}$ is the Kronecker symbol, which is 0 if the two indices differ and 1 if they are equal.
Or as congruence:

$\bigwedge_{i \in I}\bigwedge_{j \in J} e_i(X)\equiv \delta_{i,j} \mod X-x_j$

Then we can just combine this and use

$p(X) =\sum_{i \in I} y_i e_i(X)$

This can easily be written as a Ruby function
def fun_calc(pairs) n = pairs.size result = lambda do |x| y = 0 n.times do |i| p_i = pairs[i] x_i = p_i[0].to_r y_i = p_i[1].to_r z = y_i n.times do |j| if (j != i) p_j = pairs[j] x_j = p_j[0] z *= (x - x_j) / (x_i - x_j) end end y += z end y end result end
This takes a list of pairs as a parameter and returns the polynomial function als lambda.
It can be used like this:
lop = [[0, 0], [1, 1], [2, 4], [3, 9], [4, 16], [5, 25], [6, 36], [7, 64]]


f = fun_calc(lop)

20.times do |x| y = f.call(x) puts sprintf("%6d -> %6d", x, y) end
Put this together into a ruby program and add some parsing for the list of pairs or change the program each time you use it and all these „difficult“ questions „that 99.9% fail to solve“ are not just easy, but actually soluble automatically.

This is interesting for more useful applications. I assume that there will always be situations where a function is needed that meets certain exact values a certain inputs and is an interpolation or extrapolation of this.

Please observe that there are other interesting and useful ways to approach this:

Use a „best“ approximation from a set of functions, for example polynomials with a given maximum degree
use cubic splines, which are cubic polynomials within each section between two neighboring input values such that at the input values the two adjacent functions have the same value ( $y_i$ , of course), the same first derivative and the same second derivative.

For highway and railroad construction other curves are used, because the splines are making an assumption on what is the $x$ -axis and what is the $y$ -axis, which does not make sense for transport facilities. They are using a curve called Clothoid.

Use Java, C, Perl, Scala, F# or the programming language of your choice to do this. You only need Closures, which are available in Java 8, F#, Scala, Perl, Ruby and any decent Lisp dialect. In Java 7 they can be done with an additional interface as anonymous inner classes. And for C it has been described in this blog how to do closures.

Schreibe einen Kommentar

Antworten abbrechen