12
$\begingroup$

Which methods I can use to predict next number from a series of numbers ?

I know the min & max possible number in advance.

  • 5
    Any method that works.2012-05-14
  • 15
    Plug your sequence (if it is composed of integers) [here](https://oeis.org/) =)2012-05-14
  • 6
    Know the person who asked the question well enough to guess. Mathematically, there isn't really a right answer.2012-05-14
  • 1
    The next number is **always** 42. More seriously, examples like [Moser's problem](http://mathworld.wolfram.com/CircleDivisionbyChords.html) should make you wary of predicting next terms from limited input...2012-05-14
  • 1
    [Here](http://meta.math.stackexchange.com/questions/924) is an apropos meta thread.2012-05-14
  • 3
    The hard copy of the Encyclopedia of Integer Sequences had a long introductory part in which methods were discussed. So far as I can see, that part did not make it into the online encyclopedia.2012-05-14
  • 0
    Amusingly enough, you can justify pretty much **any** number as the next number in a given sequences. I don't have the reference in front of me at the moment, but I read a meta-mathematical discourse on this very thing. The author took 1,2,4,8,16,__, and then justified filling in the blank with 31. The kicker is, unless the questioner doesn't understand that inductive arguments (different from mathematical induction) do not prove that a particular conclusion is correct, then you need only find *some* pattern, then justify it somehow. That's what @copper.hat likely means.2012-05-14
  • 1
    @Cameron, put $n$ points on a circle, draw all the lines connecting pairs of the points (being careful that no three of these chords intersect at an interior point of the circle), and the number of regions formed is $1,2,4,8,16,31,\dots$.2012-05-14
  • 1
    Sourav, did you read any of the comments, and follow up on them, before editing? You have to engage with us to get anywhere, you know.2012-05-14
  • 3
    Tangentially related is the [phenomenon of eventual counterexamples](http://mathoverflow.net/questions/15444/the-phenomena-of-eventual-counterexamples)2012-05-14
  • 0
    @Cam: that indeed is the sequence you get from Moser's problem...2012-05-14
  • 12
    @mixedmath et al, I object to the closure of this as "not a real question." When a sequence comes up in real life, there *are* useful methods for trying to work out the rule behind it and then working out more terms. Just because most of the commenters have gone for the easy "it coould be anything!" reply doesn't mean good replies more in the spirit of the question are impossible.2012-05-15
  • 0
    @Gerry I agree. I cast the 5'th reopen vote.2012-05-16
  • 0
    Sourav, you might want to see [this paper](http://www.jstor.org/stable/2974639). @Gerry, did you have this paper in mind with regards to this question?2012-05-16
  • 0
    @J.M., no, that's not what I had in mind, but thanks for linking to it.2012-05-16
  • 0
    @GerryMyerson, thank you for choosing the 1,2,4,8,16,31 example - I contributed the figure on OEIS (no big deal, I got it from [Mill's book](http://www.amazon.com/Theoretical-Introduction-Programming-Bruce-Mills/dp/1846280214)). More importantly I use that example to show the limitation of Occam razor principle: given 1,2,4,8,16 - 32 is the "simplest" prolongation, but it may have nothing to do with the problem at hand. There are 500+ OEIS sequences that begin with those first 5 values.2012-05-16
  • 0
    @alan, J. M. already gave that example a few comments before I did, with the link to "Moser's problem". If I had followed that link earlier, I would have just referred Cameron to J. M.'s comment.2012-05-16
  • 1
    @GerryMyerson, just trying to put the focus on the larger issue - the limit of Occam's razor principle - by using Moser's problem as example (or rather counterexample). [DARPA math challenge](http://www.darpa.mil/Our_Work/DSO/Programs/23_Mathematical_Challenges.aspx) #7 "Occam's razor in many dimensions"2012-05-16

4 Answers 4

25

Nowadays, the #1 method for predicting the next number from a sequence (assuming the sequence has come up in a "natural" way) is to look it up in the Online Encyclopedia of Integer Sequences. In his 1973 book, A Handbook of Integer Sequences, Sloane gives some suggestions as to what to do if your sequence is not in the Encyclopedia/Handbook. These include,

  1. Add or subtract 1 or 2 from all the terms, and try looking it up again;

  2. Multiply all the terms by 2, or divide by any common factor, and try looking it up again;

  3. Look for a recurrence.

Sloane elaborates on this last suggestion. He mentions the method of differences, where you replace the sequence $a_0,a_1,\dots$ with $a_1-a_0,a_2-a_1,\dots$ and, if necessary, repeat the differencing, until you get something with an obvious pattern. Of course, then you have to know what to do with a recurrence once you have one, but that's another story.

Sloane also says that if a sequence is close to a known sequence, you can try subtracting off the known sequence, and then dealing with the residual by one of the above methods.

If the ratios $a_{n+1}/a_n$ seem to be close to a recognizable sequence $r_n$, then look at the sequence given by $a_{n+1}-r_na_n$.

Factoring the numbers in a sequence, or in a sequence close to the given sequence, will often give a clue as to what is going on.

For examples of all these principles (and others that I haven't mentioned) in operation, I refer you to the Handbook.

12

One possibility is to use Maple's gfun package to guess a generating function. See http://algo.inria.fr/libraries/papers/gfun.html

  • 0
    Indeed, if someone asks "Which methods I can use", pointing to the actual software is highly reasonable. There is also a guessing package in FriCAS, though I've never used it. The documentation seems to be in FriCAS itself, so I can't point to a webpage with the description. No doubt there is something of that kind for Mathematica too.2012-05-16
  • 4
    @Yrogirg: Sure, *Mathematica* has `InterpolatingPolynomial[]`, `FindSequenceFunction[]`, and `FindLinearRecurrence[]`, among other things...2012-05-16
6

As for the software, from Christian Krattenthaler's home page:

If you need to guess sequences of numbers very often, then my Mathematica "guessing machine" RATE (which has now become part of Neil Sloane's Encyclopedia of Integer Sequences) may be useful for you. The Maple implementation by François Béraud and Bruno Gauthier is called GUESS. A Maxima implementation, DEVINE, written by Martin Rubey, is also available. The Axiom guessing package Guess, also written by Martin Rubey, is even more powerful as its range of detected formulas is larger.

For the hyperlinks to packages go to the page itslef. As for the Guess package it is present in FriCAS too and there were changes to it during the past year.

0

Since release 1.0 of the Sympy module, you can also use the sympy.concrete.guess submodule (written by myself for the project); have a glance at the docstring documentation at https://raw.githubusercontent.com/sympy/sympy/master/sympy/concrete/guess.py where you will find various examples.

For instance:

>>> from sympy.concrete.guess import guess_generating_function as ggf >>> ggf([k+1 for k in range(12)], types=['ogf', 'lgf', 'hlgf']) {'hlgf': 1/(-x + 1), 'lgf': 1/(x + 1), 'ogf': 1/(x**2 - 2*x + 1)}  >>> from sympy import sympify >>> l = sympify("[3/2, 11/2, 0, -121/2, -363/2, 121]") >>> ggf(l) {'ogf': (x + 3/2)/(11*x**2 - 3*x + 1)}  >>> from sympy import fibonacci >>> ggf([fibonacci(k) for k in range(5, 15)], types=['ogf']) {'ogf': (3*x + 5)/(-x**2 - x + 1)}  >>> from sympy import simplify, factorial >>> ggf([factorial(k) for k in range(12)], types=['ogf', 'egf', 'lgf']) {'egf': 1/(-x + 1)}  >>> ggf([k+1 for k in range(12)], types=['egf']) {'egf': (x + 1)*exp(x), 'lgdegf': (x + 2)/(x + 1)}  N-th root of a rational function can also be detected (below is an example coming from the sequence A108626 from http://oeis.org). The greatest n-th root to be tested is specified as maxsqrtn (default 2).  >>> ggf([1, 2, 5, 14, 41, 124, 383, 1200, 3799, 12122, 38919])['ogf'] sqrt(1/(x**4 + 2*x**2 - 4*x + 1)) 

Note however that the module is rather oriented toward the detection of generating functions (and not direct formulas).