The Universal Sequence Expander



Get the n-th term of a sequence
Enter the sequence, which term, then Get it!

Sequence: separated by spaces and commas
n: leave blank for next term
Term:

Questions of type “what is the next number in the sequence…”, where the dotted field is filled with a few numbers, and occasionally other symbols frequently crop up on Quora, and are quite common in aptitude tests, as exemplified here, here, here, here, and here.

What is sought after, allegedly, is a display of mathematical ability in uncovering a rule underlying the given sequence, and then producing the next number. Actually, not a rule, but the rule that was in the mind of the one that proposed the question. And that is a problem, as some telepathy is usually required, but not explicitly. Many aptitude tests proceed as there was an unique answer to the question – you can bet that whoever posed that has a very poor and limited knowledge of Math.

What kind of rules are accepted? This is never explained, but some characteristics seem to be:

  1. They should be algorithmic.

  2. The complexity should be very low; a normal person should be able to compute the next number by hand in a short time.

  3. They should involve a very small set of mathematical operators, usually at elementary school level.

  4. They should allow one to compute any element of the (supposedly infinite) sequence, not just the next one.

  5. They should be “logical” (whatever that means).

  6. The rule, overall, should be “a formula”, understandable by the proposer.

They may also involve external, non-mathematical data, assumed to be “common knowledge”, like names of weekdays or months and their lengths, but those are smart-assness tests, rather than “mathematical” tests.

There is a standard solution to problems of arithmetical sequences: just assume that the given one is generated by a polynomial. A finite difference table will implicitly fit the lowest possible degree polynomial to data, and can be used to compute the next one. It only involves computing some sums and differences, so, if the given numbers are not too large, conditions 1-4 above are satisfied. However, there is a problem with condition 5: the difference table is hardly a formula, and a conventional polynomial formula is more computationally demanding to produce. By that I mean representing the polynomial in the standard basis, as an expression involving the Pochhammer symbol would not be understandable by the proposer.

Actually, the solution above can be turned into its head, and any number can follow the given one. The same methods above will fit a polynomial to the new sequence – for extra glibness, choose a complex transcendental number as the next one. But this method suffers from the same problem with respect to condition 5.



Actually, coming back after a few years, I decided to amend the paragraph above with an observation of what seems to be a pattern in the mind of most answerers: a linear-recursive sequence. That is, what is sought after is a constant-recursive sequence fitting the given data. Again, both those that ask and those that answer those questions are unaware of the old and completely developed theory on such objects, neither of the mathematical language used. Answers usually describe the pattern using words instead of a compact notation.

In any case, those solutions are still too complicated. To help those many questioners, in particular those of Quora, I have developed the Universal Sequence Expander (USE) that can, given any finite sequence, compute all terms of its infinite expansion.

To show that conditions 1 and 4 are satisfied, I have produced a Python implementation. To show that 2,3 and 5 are satisfied, I am releasing the code as free software. I would stress “The freedom to study how the program works” among the four freedoms as the one most relevant to the case at hand.

Python code for the USE

Just download it and save as USE.py.

If you are familiar with python, you know how to import USE and call

nth_term([any python list]).

That will give you the next term, and the sequence does not even have to be numerical. You can call with a second argument, n, and be served the nth term.

Bear in mind that the USE was developed to answer unadorned questions of the form what is the next number in the sequence… . Questions that somehow restrict the acceptable answers further than conditions 1-5 are beyond its grasp, but are unlikely to occur. But, whenever it answers you, remember: the answer was given by a computer, so it can't be wrong!

I hope this is useful to the many Quorans ever asking that type of questions, and to those who have found the answer too.



A final remark: there are some cases in which one has a finite sequence at hand and wonder if there are interesting ways of expanding it, unrestricted by 1-5. For one definition of interesting (“has appeared in the mathematical literature”), one can do no better than consult the amazing The On-Line Encyclopedia of Integer Sequences. Have fun there!



Arnaldo Mandel <amandel@gmail.com>