SEQUENCE
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:

1 2 3 4 5

? 3 6 ? 15

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.

Licensing:

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

Languages:

SEQUENCE is available in a FORTRAN90 version.

Related Data and Programs:

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

Source code:

sequence.f90, the source code;
sequence_input.txt, sample input;
sequence.txt, the output file;

List of Routines:

SEQUENCE reads in a sequence and calls SEQUENCE_FILLER to fill it in.
CH_CAP capitalizes a single character.
CH_EQI is a case insensitive comparison of two characters for equality.
CH_TO_DIGIT returns the integer value of a base 10 digit.
DATA_TO_DIF sets up a divided difference table from raw data.
DIF_TO_POLY converts a divided difference polynomial to standard form.
DIF_VAL evaluates a divided difference polynomial at a point.
POLY_PRINT prints out a polynomial.
R4VEC_DISTINCT is true if the entries in an R4VEC are distinct.
S_EQI is a case insensitive comparison of two strings for equality.
S_IS_R is TRUE if a string represents a real number.
S_TO_R reads a real number from a string.
SEQUENCE_FILLER "fills in" a sequence with missing values.
WORD_NEXT_READ "reads" words from a string, one at a time.

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