Fill in a Sequence

SEQUENCE is a FORTRAN90 program which reads a numeric sequence with missing values, and fills in the missing values.

The input to the program is a string representing a sequence, with missing values denoted by question marks. For instance, we might enter the following sequence:

        ? 3 6 ? 15
The program will try to determine the simplest rule of a certain kind that can be used to fill in the question marks.

The rule deduced for the sequence is found by constructing the polynomial that interpolates the known data. Abscissas for the data are assigned by position in the sequence. Thus for the above sequence, the three known values have abscissas of 2, 3 and 5, which means we might think of the sequence as a table:

Once the interpolating polynomial is found, it is evaluated at the points where data was not given, and the results are reported back to the user. In the example case, we would get the filled in sequence:

        1 3 6 10 15

Note that this procedure will always be able to produce a result, but it may not be the expected result. This is particularly so when the sequence is most easily represented in terms of a geometric calculation, as in

        1 2 4 8 16 32
or as in the Fibonacci sequence:
        1 1 2 3 5 8 13 21 34 55
both of which this program will be unable to recognize.


The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.


SEQUENCE is available in a FORTRAN90 version.

Related Data and Programs:

PUZZLES, FORTRAN90 programs which were used to solve various puzzles.

Source code:

List of Routines:

You can go up one level to the FORTRAN90 source codes.

Last revised on 23 April 2008.