Munafo's Classical Sequences

This is a listing of integer sequences generated by what I call 'classical' definitions. These include virtually all number sequences known by ancient cultures (the notable exception is the prime numbers). There are also many others that have equally simple definitions. Examples include:

Types of Sequence Definitions

The following broad categories of sequence definitions are used:

Direct: Each term AN is computed directly from a formula involving N but not depending on other terms in the sequence.(This category includes the even numbers, if defined as EN=2N.)

First-Order Recurrence: After an initial term A0, subsequent terms AN+1 are defined in terms of a formula involving AN (and possibly also involving N). (This category includes the factorials, if defined as F0=1, FN=N FN-1, and the even numbers, if defined as E0=0, EN=2+EN-1. Notice that the same sequence can have both a direct definition and a recurrence definition.)

Second-Order Recurrence: After two initial terms A0 and A1, subsequent terms AN+1 are defined in terms of a formula involving AN-1, and possibly also AN and/or N. (This category includes the Fibonacci numbers, F0=0, F1=1, FN+1=FN+FN-1.).

Third-Order Recurrence: After three initial terms A0, A1 and A2, subsequent terms AN+1 are defined in terms of a formula involving AN-2, and possibly also AN, AN-1, and/or N.

All formulas are a sum of terms involving a constant coefficient multiplied by some combination of a power of N and zero or more previous terms. This table shows the combinations that are used:


initial
terms 		coefficients
   1      N       N2      N3
A0 AN   NAN   N2AN
A1 AN-1 NAN-1          ANAN-1
A2 AN-2


Direct formulas use only the first row; first-order recurrence formulas use the first two rows, and so on.

Sequence ID Number

Each sequence definition is given an identification number that uniquely specifies the initial term(s) (if any) and formula. All ID numbers begin with the letters MCS (for Munafo Classical Sequence) followed by one or more decimal digits. The decimal digits are chosen by the following steps:

1. The sequence type, initial value(s) if needed and coefficients are encoded into fields, either by using the coefficient directly as a field value, or using a translation table that ensures the "default" coefficient has a field value of 0.
2. The fields are Huffman-encided into binary strings.
3. The binary strings are concatenated into a single bitstring.
4. The bitstring is modified into a truncated bitstring.
5. The truncated bitstring is treated as a single positive integer; this is the sequence number, and the decimal representation of this integer is placed after MCS to make the sequence ID number.

Step 1: Fields

The first field gives the sequence type as defined above: 4 for direct, 3 for 1st-order recurrence, 2 for 2nd-order recurrence and 1 for 3rd-order recurrence. After this there are several more fields for the coefficients, in the order shown here:

For direct definitions: K, CN, CN2

For 1st-order recurrence: K, CAN, CN, CN AN, CN2, A0

For 2nd-order recurrence: K, CAN, CN, CAN-1, CN AN, CN2, A0, A1-A0-1

For 3rd-order recurrence: K, CAN, CN, CAN-1, CN AN, CN2, CAN-2, CN AN-1, CN2AN, CN3, A0, A1-A0-1, A2-A1-1

Step 2: Huffman Encoding

All fields are then converted to one or more binary digits according to the following table:

 0 → 0
 1 → 100
 2 → 1010
-2 → 10110
 4 → 101110
-4 → 1011110
-5 → 1011111
-1 → 110
 3 → 1110
 5 → 111100
 6 → 1111010
-6 → 1111011
-3 → 111110
 7 → 111111000
 8 → 111111001
 x → 11111101x (for future expansion)
-7 → 111111100
-8 → 111111101
 x → 11111111x (for future expansion)

and the bits are concatenated in the order given above to form the bitstring. The table was generated by a normal Huffman statistical division based on the frequency of coefficient values in all sequence definitions with a complexity score (see below) of 9 or less; then the lengths were diminished as much as possible with the goal of reducing the average overall bitstring length; it was then reordered so that all but the rarest values end in 0, and so that larger coefficients map onto larger bitstrings.

Steps 3-4: Truncated Bitstring, and Sequence Number

To make the truncated bitstring, first an initial 1 is added (because otherwise, initial 0's would be lost when the bitstring is converted to a decimal integer). Then any trailing 0's are removed (there is no loss of information because, as specified below, extra 0 terms at the end are always assumed and allow future expansion). Then a single trailing 1 is removed (again there is no loss of information because at this point we know there is at least one trailing 1). The bitstring is then converted to decimal as if it were a binary integer. "MCS" followed by this decimal number is the sequence ID number. No zeros are added; the sequence numbers have a variable number of digits. In general, sequences with simpler definitions will have smaller sequence numbers.

Future Expansion

For future expansion of the sequence generator, sequence types other than 1 through 4 are unused (which means that there are currently no bitstrings starting with 10, corresponding to sequence numbers between 2N and 3×2N-1 for all N; plus other smaller ranges defined similarly). This provides space to define new sequence types and formulas, without having to resort to long sequence ID numbers. These new sequence types can use any encoding whatsoever, even abandoning the requirements given in the next few paragraphs, so long as the bitstring of all 0's remains undefined (because it results in a 0 or null sequence number).

Additional fields can be added at the end of the existing coefficient lists. For example, an N4 term could be added, with all existing sequences having a CN4 coefficient of 0. Any new fields and the corresponding formula terms will be defined with this compatibility in mind. (Here is an example: suppose it is decided to allow the coefficient of AN to be a fraction. This necessitates a new "denominator of CAN" term. Its useful values are positive integers; the value of 1 is the one that has no effect. So, a 1 in this coefficient would be encoded as a field value of 0; the higher values 2, 3, 4, 5, ... could be encoded as 1, -1, 2, 3, etc. respectively, in order to take maximum advantage of the huffman field lengths.) Since the Huffman table maps 0→0, and trailing 0's are discarded before converting to a decimal sequence ID, it is easy to see that any number of extra 0 fields can be added, with no effect on the resulting sequence ID number. Even after the hypothetical N4 and "denominator of CAN" terms are added, all previously-defined sequences will still have the same ID numbers.

Furthermore, for any new fields, a different Huffman table could be used, or the expansion could even use a non-Huffman type of encoding, so long as all sequence numbers as currently defined result in the sequences currently defined.

There are by definition no sequence numbers with a leading 0, such as MCS027. These are intended to be used as manually-assigned sequence numbers, as in the Sloane database (except that there is still no fixed number of digits). Thus, to find out the definition of MCS027 or MCS0143 you would have to look in the database. (No such database exists at present, however it is anticipated that these will be used to attach notes and cross-references, for example to document the multiple different equivalent definitions of a sequence; an example follows.)

Notes

The sequence number is not affected by the scoring system, although the scoring system affects which sequences are listed in the main table. There is, however, a rough correlation between the coefficient value weights in the scoring system and their Huffman symbol lengths.

Examples

The Fibonacci numbers have a second-order recurrence definition: A0=0; A1=1; AN+1=AN+AN-1. The coefficients that need to be encoded are: sequence type=2; K=0; CAN=1; CN=0; CAN-1=1; CN AN=0; CN2=0; A0=0; A1-A0-1=0. So the fields, before encoding are: 2, 0, 1, 0, 1, 0, 0, 0, 0. By the Huffman table, this becomes the bitstring 1.110.0.100.0.100.0.0.0.0 (after adding the initial 1). Then trailing zeros are dropped, and then a single trailing 1 is dropped, making 111001000; this is converted to decimal giving the value 456. So, this definition of the Fibonacci numbers is given sequence number MCS456.

Note that some sequences have multiple definitions. For example, the natural numbers may be defined as a direct sequence: AN = N. Using this definition the bitstring is 1.10110.0.100.0, and the sequence number is MCS108. However, the natural numbers can also be defined by a 1st-order recurrence A0=0; AN+1 = AN + 1. By this definition, the bitstring is 1.1110.100.100.0.0.0.0, and the sequence number is MCS244. As you might expect, the first definition has a lower complexity score, and that is the one shown in the main table.

Complexity Score

Each sequence definition is given a complexity score based on the number of terms and the size of its coefficients.

The main table includes those sequences with complexity scores up to 5.


Main Table

2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

MCS30786 (alias 30818, 61602, 61666, 123234, 246754, 248408): A0 = 2; AN+1 = N AN (score: 3)

2, 0, 0, 2, 0, 0, 2, 0, 0, 2, 0, 0, 2, 0, 0, 2, 0, 0, 2, 0, 0, 2, 0, 0

MCS393481 (alias 1748161): A0 = 0; A1 = 0; A2 = 2; AN+1 = AN-2 (score: 4)

2, 0, 0, 3, 4, 2, 2, 5, 6, 4, 4, 7, 8, 6, 6, 9, 10, 8, 8, 11, 12, 10, 10, 13

MCS214208: A0 = 1; A1 = 2; AN+1 = - AN-1 + N (score: 3)

2, 0, 0, 4, 0, 0, 8, 0, 0, 16, 0, 0, 32, 0, 0, 64, 0, 0, 128, 0, 0, 256, 0, 0

MCS196769 (alias 393541, 787081, 12593366): A0 = 0; A1 = 0; A2 = 1; AN+1 = 2 AN-2 (score: 4)

2, 0, 1, 1, 4, 4, 5, 3, 4, 4, 7, 7, 8, 6, 7, 7, 10, 10, 11, 9, 10, 10, 13, 13

MCS6701446: A0 = 1; A1 = 1; A2 = 2; AN+1 = - AN-2 + N - 1 (score: 5)

2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1

MCS768: A0 = 0; A1 = 1; A2 = 2; AN+1 = AN-2 (score: 3)

2, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22

MCS123298: A0 = 2; AN+1 = - N AN + N2 (score: 5)

2, 0, 1, 3, 1, 2, 4, 2, 3, 5, 3, 4, 6, 4, 5, 7, 5, 6, 8, 6, 7, 9, 7, 8

MCS1730945: A0 = -1; A1 = 0; AN+1 = - AN - AN-1 + N (score: 5)

2, 0, 1, 4, 15, 64, 325, 1956, 13699, 109600, 986409, 9864100, 108505111, 1302061344, 16926797485, 236975164804

MCS123458: A0 = 2; AN+1 = N AN + N (score: 4)

2, 0, 1, 5, 6, 4, 5, 9, 10, 8, 9, 13, 14, 12, 13, 17, 18, 16, 17, 21, 22, 20, 21, 25

MCS1755840: A0 = 1; A1 = 2; AN+1 = - AN-1 + 2 N - 1 (score: 5)

2, 0, 1, 6, 27, 124, 645, 3906, 27391, 219192, 1972809, 19728190, 217010211, 2604122676, 33853594957, 473950329594

MCS123170: A0 = 2; AN+1 = N AN + N2 (score: 5)

2, 0, 1, 6, 39, 316, 3165, 37986, 531811, 8508984, 153161721, 3063234430, 67391157471

MCS246946: A0 = 2; AN+1 = 2 N AN + N (score: 5)

2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0

MCS981 (alias 251266): A0 = 0; AN+1 = - AN + 2 (score: 3)

2, 0, 2, 0, 6, 0, 30, 0, 210, 0, 1890, 0, 20790, 0, 270270, 0, 4054050, 0, 68918850, 0, 1309458150, 0, 27498621150, 0

MCS213768 (alias 106884): A0 = 1; A1 = 2; AN+1 = N AN-1 - AN-1 (score: 4)

2, 0, 2, 1, 1, 2, 1, 2, 2, 2, 3, 3, 4, 5, 6, 8, 10, 13, 17, 22, 29, 38, 50, 66

MCS13072: A0 = 0; A1 = 1; A2 = 2; AN+1 = AN-1 + AN-2 - 1 (score: 5)

2, 0, 2, 1, 4, 4, 8, 9, 14, 16, 22, 25, 32, 36, 44, 49, 58, 64, 74, 81, 92, 100, 112, 121

MCS3499136: A0 = 1; A1 = 2; AN+1 = AN-1 + N - 2 (score: 5)

2, 0, 2, 2, 2, 4, 4, 6, 8, 10, 14, 18, 24, 32, 42, 56, 74, 98, 130, 172, 228, 302, 400, 530

MCS1581321: A0 = 0; A1 = 0; A2 = 2; AN+1 = AN-1 + AN-2 (score: 5)

2, 0, 2, 4, 0, 4, 8, 0, 8, 16, 0, 16, 32, 0, 32, 64, 0, 64, 128, 0, 128, 256, 0, 256

MCS3074 (alias 3148310): A0 = 0; A1 = 1; A2 = 2; AN+1 = 2 AN-2 (score: 4)

2, 0, 2, 8, 30, 128, 650, 3912, 27398, 219200, 1972818, 19728200, 217010222, 2604122688, 33853594970, 473950329608

MCS247106: A0 = 2; AN+1 = N AN + 2 N (score: 5)

2, 0, 2, 9, 14, 16, 22, 33, 42, 48, 58, 73, 86, 96, 110, 129, 146, 160, 178, 201, 222, 240, 262, 289

MCS213792: A0 = 1; A1 = 2; AN+1 = - AN-1 + N2 (score: 4)

2, 0, 3, 0, 4, 0, 5, 0, 6, 0, 7, 0, 8, 0, 9, 0, 10, 0, 11, 0, 12, 0, 13, 0

MCS3454145: A0 = 0; A1 = 0; AN+1 = - 2 AN - AN-1 + N (score: 5)

2, 0, 3, 1, 4, 2, 5, 3, 6, 4, 7, 5, 8, 6, 9, 7, 10, 8, 11, 9, 12, 10, 13, 11

MCS250689 (alias 1005186): A0 = -1; AN+1 = - AN + N + 1 (score: 4)

2, 0, 3, 2, 6, 6, 11, 12, 18, 20, 27, 30, 38, 42, 51, 56, 66, 72, 83, 90, 102, 110, 123, 132

MCS438848: A0 = 0; A1 = 2; AN+1 = AN-1 + N - 1 (score: 5)

2, 0, 3, 6, 0, 9, 18, 0, 27, 54, 0, 81, 162, 0, 243, 486, 0, 729, 1458, 0, 2187, 4374, 0, 6561

MCS3075: A0 = 0; A1 = 1; A2 = 2; AN+1 = 3 AN-2 (score: 5)

2, 0, 4, 0, 16, 0, 96, 0, 768, 0, 7680, 0, 92160, 0, 1290240, 0, 20643840, 0, 371589120, 0, 7431782400, 0, 163499212800, 0

MCS26628: A0 = 0; A1 = 2; AN+1 = N AN-1 (score: 4)

2, 0, 5, 5, 12, 14, 23, 27, 38, 44, 57, 65, 80, 90, 107, 119, 138, 152, 173, 189, 212, 230, 255, 275

MCS250641: A0 = -1; AN+1 = - AN + N2 + 1 (score: 5)

2, 0, 6, 0, 30, 0, 210, 0, 1890, 0, 20790, 0, 270270, 0, 4054050, 0, 68918850, 0, 1309458150, 0, 27498621150, 0, 632468286450, 0

MCS106756: A0 = 0; A1 = 2; AN+1 = N AN-1 + AN-1 (score: 5)

2, 0, 6, 27, 58, 98, 158, 245, 354, 484, 646, 847, 1082, 1350, 1662, 2025, 2434, 2888, 3398, 3971, 4602, 5290, 6046, 6877

MCS213776: A0 = 1; A1 = 2; AN+1 = - AN-1 + N3 (score: 5)

2, 0, 8, 0, 48, 0, 384, 0, 3840, 0, 46080, 0, 645120, 0, 10321920, 0, 185794560, 0, 3715891200, 0, 81749606400, 0

MCS3328 (alias 3416214): A0 = 0; A1 = 1; AN+1 = N AN-1 (score: 3)

2, 0, 8, 0, 64, 0, 768, 0, 12288, 0, 245760, 0, 5898240, 0, 165150720, 0, 5284823040, 0, 190253629440, 0

MCS53258: A0 = 0; A1 = 2; AN+1 = 2 N AN-1 (score: 5)

2, 0, 12, 0, 120, 0, 1680, 0, 30240, 0, 665280, 0, 17297280, 0, 518918400, 0, 17643225600, 0, 670442572800, 0

MCS1704278: A0 = 1; A1 = 0; AN+1 = 2 N AN-1 (score: 5)

2, 1, 0, 1, 2, 1, 0, 1, 2, 1, 0, 1, 2, 1, 0, 1, 2, 1, 0, 1, 2, 1, 0, 1

MCS12568: A0 = 0; A1 = 1; A2 = 2; AN+1 = AN - AN-1 + AN-2 (score: 5)

2, 1, 0, 1, 4, 7, 8, 7, 6, 7, 10, 13, 14, 13, 12, 13, 16, 19, 20, 19, 18, 19, 22, 25

MCS3515584: A0 = 1; A1 = 2; AN+1 = AN - AN-1 + N - 1 (score: 5)

2, 1, 0, 2, 1, 0, 2, 1, 0, 2, 1, 0, 2, 1, 0, 2, 1, 0, 2, 1, 0, 2, 1, 0

MCS786966 (alias 6295702): A0 = 0; A1 = 2; A2 = 1; AN+1 = AN-2 (score: 5)

2, 1, 0, 2, 4, 3, 2, 4, 6, 5, 4, 6, 8, 7, 6, 8, 10, 9, 8, 10, 12, 11, 10, 12

MCS107104: A0 = 0; A1 = 2; AN+1 = - AN-1 + N (score: 4)

2, 1, 0, 3, 2, 1, 4, 3, 2, 5, 4, 3, 6, 5, 4, 7, 6, 5, 8, 7, 6, 9, 8, 7

MCS3461893: A0 = 0; A1 = -1; AN+1 = - AN - AN-1 + N (score: 5)

2, 1, 1, 0, 1, 1, 2, 1, 1, 0, 1, 1, 2, 1, 1, 0, 1, 1, 2, 1, 1, 0, 1, 1

MCS413745 (alias 3309958): A0 = 0; A1 = 1; A2 = 1; AN+1 = - AN-2 + 2 (score: 5)

2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

MCS500322 (alias 500546): A0 = 2; AN+1 = - N AN + N + 1 (score: 5)

2, 1, 1, 1, 3, 4, 5, 4, 4, 4, 6, 7, 8, 7, 7, 7, 9, 10, 11, 10, 10, 10, 12, 13

MCS26177 (alias 6358572): A0 = 0; A1 = 1; A2 = 2; AN+1 = - AN-2 + N - 1 (score: 5)

2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1

MCS393478 (alias 1573932, 25183066): A0 = 1; A1 = 1; A2 = 2; AN+1 = AN-2 (score: 3)

2, 1, 1, 2, 2, 2, 3, 4, 5, 7, 10, 14, 20, 29, 42, 61, 89, 130, 190, 278, 407, 596, 873, 1279

MCS13120: A0 = 0; A1 = 1; A2 = 2; AN+1 = AN + AN-2 - 1 (score: 5)

2, 1, 1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, 67, 79, 92, 106, 121, 137, 154, 172, 191, 211, 232

MCS504962: A0 = 2; AN+1 = AN + N - 1 (score: 4)

2, 1, 1, 2, 7, 34, 203, 1420, 11359, 102230, 1022299, 11245288, 134943455, 1754264914, 24559708795, 368395631924

MCS504898: A0 = 2; AN+1 = N AN + AN - 1 (score: 5)

2, 1, 1, 3, 1, 1, 5, 1, 1, 9, 1, 1, 17, 1, 1, 33, 1, 1, 65, 1, 1, 129, 1, 1

MCS3342982: A0 = 1; A1 = 1; A2 = 2; AN+1 = 2 AN-2 - 1 (score: 5)

2, 1, 1, 3, 2, 2, 4, 3, 3, 5, 4, 4, 6, 5, 5, 7, 6, 6, 8, 7, 7, 9, 8, 8

MCS1638665 (alias 3486913, 6554677, 13847574, 26218710): A0 = 0; A1 = 0; A2 = 2; AN+1 = AN-2 + 1 (score: 5)

2, 1, 1, 3, 4, 3, 3, 5, 6, 5, 5, 7, 8, 7, 7, 9, 10, 9, 9, 11, 12, 11, 11, 13

MCS869568 (alias 1713673, 7022093): A0 = 1; A1 = 2; AN+1 = - AN-1 + N + 1 (score: 4)

2, 1, 1, 4, 12, 27, 51, 86, 134, 197, 277, 376, 496, 639, 807, 1002, 1226, 1481, 1769, 2092, 2452, 2851, 3291, 3774

MCS504866: A0 = 2; AN+1 = AN + N2 - 1 (score: 5)

2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1

MCS63328 (alias 253314): A0 = 1; AN+1 = - AN + 3 (score: 4)

2, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1, 2

MCS6295642: A0 = 2; A1 = 1; A2 = 2; AN+1 = AN-2 (score: 5)

2, 1, 2, 2, 2, 3, 3, 4, 5, 6, 8, 10, 13, 17, 22, 29, 38, 50, 66, 87, 115, 152, 201, 266

MCS6693126: A0 = 1; A1 = 1; A2 = 2; AN+1 = AN-1 + AN-2 - 1 (score: 5)

2, 1, 2, 2, 3, 4, 6, 9, 14, 22, 35, 56, 90, 145, 234, 378, 611, 988, 1598, 2585, 4182, 6766, 10947, 17712

MCS439360: A0 = 0; A1 = 2; AN+1 = AN + AN-1 - 1 (score: 5)

2, 1, 2, 2, 4, 4, 5, 4, 5, 5, 7, 7, 8, 7, 8, 8, 10, 10, 11, 10, 11, 11, 13, 13

MCS1589638: A0 = 1; A1 = 1; A2 = 2; AN+1 = - AN-2 + N (score: 4)

2, 1, 2, 2, 6, 8, 30, 48, 210, 384, 1890, 3840, 20790, 46080, 270270, 645120, 4054050, 10321920, 68918850, 185794560, 1309458150, 3715891200, 27498621150, 81749606400

MCS3408474: A0 = 2; A1 = 1; AN+1 = N AN-1 (score: 5)

2, 1, 2, 3, 2, 3, 4, 3, 4, 5, 4, 5, 6, 5, 6, 7, 6, 7, 8, 7, 8, 9, 8, 9

MCS3200 (alias 6761, 819329, 819333, 1638661, 6554646, 6554668): A0 = 0; A1 = 1; A2 = 2; AN+1 = AN-2 + 1 (score: 4)

2, 1, 2, 3, 3, 5, 6, 8, 11, 14, 19, 25, 33, 44, 58, 77, 102, 135, 179, 237, 314, 416, 551, 730

MCS25301174: A0 = 1; A1 = 1; A2 = 0; AN+1 = AN-1 + AN-2 (score: 5)

2, 1, 2, 4, 2, 4, 8, 4, 8, 16, 8, 16, 32, 16, 32, 64, 32, 64, 128, 64, 128, 256, 128, 256

MCS3148332: A0 = 1; A1 = 2; A2 = 1; AN+1 = 2 AN-2 (score: 5)


Forward to page 2


Robert Munafo's home pages at Pair Networks

Men Core Values


© 1996-2008 Robert P. Munafo. Email the author