article

The Achievement of The Online Encyclopedia of Integer Sequences

by: Staff, March 6, 2012
OEIS-article-top3
 
 

1, 4, 9, 16, 25, 36, 49, 64, 81, . . .

0, 1, 1, 2, 3, 5, 8, 13, . . .  

0, 1, 8, 78, 944, 13800, 237432, . . .
 

Why does one integer follow another? What is the pattern? What rule or formula dictates the position of each integer?

Most people think deeply about sequences only when confronted by one on a test, but for mathematicians, computer scientists, and others, sequences are part and parcel of their work. Today sequences are especially important in number theory, combinatorics, and discrete mathematics, but sequences have been known and wondered about even before the time of Pythagoras, who discovered an infinite sequence of integers such that a2 + b2 = c2. In medieval times, bell ringers relied on sequences to cycle through all possible combinations of bells.

But no one in the intervening millennia had thought to compile sequences into a collection that could be referenced by others.

 

3x+1 sequence  (A033478)

Also known as the Collatz or hailstone sequence.

Start with any positive integer. If that number is odd, multiply it by three and add one. If it is even, divide by two. Then repeat.

Starting with 3 produces this sequence: 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, ... , ending in a 4-2-1 loop. It is conjectured that each hailstone sequence, no matter the starting term, ends up in the 4-2-1 loop. While shown to be true for all starting values up to 5,700,000,000,000,000,000, the conjecture has not been proved to hold for all numbers.

 

It was the mid-60s when Neil J. Sloane began collecting sequences. Then a student at Cornell, Sloane was looking at tree-like neural networks, which were little understood at the time. He needed to know how far on average would any random node be from the root of a tree containing n total nodes. He figured it out for the first few n’s to get the sequence 0, 1, 8, 78, 944, 13800, 237432, . . .

Not seeing the pattern that dictated the eighth term he figured he could simply look it up in a combinatorics or other math book, saving the trouble of calculating it himself. He didn’t find it, but he realized that the same situation could happen again. He would need to know a sequence and not be able to find it. He started a list, noting down on file cards the ones he encountered in his own work, and then expanded the search, actively collecting sequences from all the obvious places—math books and colleagues—and the not-so-obvious places (magic and gambling books).
 

What is a sequence?

An integer sequence is an ordered list of integers that has been produced in some non-random way. Sequences, usually infinite, mostly fall into three main general types:

  • Property-based sequences in which integers all share a set of properties that are true for it and not true for other sequences. This set includes the sequence of primes (A000040), the sequence of squares (A000290), and the sequences of odds and evens (A005408 and A005843).
  • Recursive sequences in which an inherent pattern dictates the position of each integer in the sequence. This includes the famous Fibonacci sequence (see A000045 and the sidebar).
  • Enumerating sequences, such as Catalan numbers (A000108), for determining or counting the number of discrete objects in a set: the number of binary trees or paths, the set of all solutions to a given problem, and the number of pieces or moves in a chess game.
201203_OEIS_sequence-diagram

 

Sequences can come from anywhere. Mathematical fields not surprisingly generate a lot of sequences, number theory and combinatorics in particular, but also game theory (winning positions), chemistry (sizes of clusters of atoms, numbers of alkanes - A000602, esters with n carbon atoms - A000632), communications (m-sequences - A011655 and many more, weight distributions - A001380), physics (paths on a lattice - A006191, Feynman diagrams with n vertices - A005411) and biology (secondary structures of RNA with n nucleoitides).

Computer science, to a large extent based on discrete math, also makes use of sequences (number of steps to sort n things).

While it makes sense that sequences appear in mathematics, they are all around. The Fibonacci sequence in particular appears in nature: the growth of branches, pinecone rows, sandollar, and the number petals in many flowers all relate to the Fibonacci sequence). The sequence appears in art and literature (in the Da Vinci Code, the dying Jacques Saunier scrawls a scrambled form of the sequence on the floor as a code).

 

201203_OEIS-fibonacci_Branches

 

 

The sequence collection comes of age

Sloane went to work in 1969 at AT&T Bell Labs, where he was given wide latitude in exploring theoretical work and built a reputation as a leading theorist in coding  theory and combinatorics, publishing several books and countless articles and technical papers. Two of his books are standouts in their respective fields: The Theory of Error-Correcting Codes (co-authored with Florence J. MacWilliams) in algebraic coding theory, and Sphere Packing, Lattices and Groups (co-authored with John Conway of Princeton University), considered to be the essential monograph on the topic.

Sloane also had a foot in the practical side of mathematics (his PhD is in electrical engineering), and his work on underwater fiber optic systems and his theoretical and practical study of attaining high-density sphere distributions helped improve the company’s communications and networks.

But throughout his career, Sloane continued working on his sequence collection, by now stored on computer punched cards, making the collection essentially a private one. This changed in 1973 with the publication of A Handbook of Integer Sequences containing 2400 sequences. For the first time, the outside world had access to the sequences, and as word spread, Sloane started receiving sequences from all over the world, from professionals and amateurs in a wide variety of disciplines. The collection grew, and twenty years later in 1995, he published The Encyclopedia of Integer Sequences (co-authored with Simon Plouffe) containing 5487 sequences, a number that could have been larger had the book format not forced Sloane to exclude some sequences. With other people contributing, the collection had the potential to expand much further. In fact within a year of the second book, the collection doubled to 10,000 sequences.

By this time—the beginning of the Internet age—the rapidly evolving web offered the possibility of free publishing, unlimited web space, and instant, two-way communication with almost anyone, anywhere. In 1996, Sloane moved the database online where it became The Online Encyclopedia of Integer Sequences (OEIS), or simply Sloane’s to many. It was as an online research tool that the OEIS came fully into its own.

Freed from space limitations, Sloane opened the floodgates, giving in to his more natural tendency to be open and generous when accepting new sequences and new types of sequences, including fractions (split into two sequences: numerator and denominator), triangles of numbers, and the digits of transcendental numbers and complex numbers.

 

Pascal's triangle (A007318)

The first row has a single term, and each row beneath has one additional term, offset so that each term is between two terms of the row above. A term is calculated by adding the two numbers above it to the left and the right. (If no number appears, assume zero). Thus the 2 in the third row is produced by adding the two ones above it. The ones in the second row are both produced by adding 0 + 1.

                    1
                1     1
             1    2     1
          1    3     3     1
        1    4    6     4    1
     1     5  10   10    5   1
   1   6   15   20   15   6   1

Pascal’s triangle can determine the coefficient of a binomial expansion, with every row correspdoning to coefficients in the expansion of a binomial (row 0 at top corresponds to exponent of 0; the second row corresponds to the exponent of 1, etc.)

Here are a couple of expansions

Row 4: (a+b)4 = 1a4 + 4a3b1 + 6a2b2 + 4a1b3 +1b

Row 6: (a+b)6 = 1a6 + 6a5b1 + 15a4b2 + 20a3b3 + 15a2b2 +  6a1b5 + 1b6    

 

 

With the launching of the OEIS, Sloane no longer had to seek out sequences; they were coming to him via a “crowd,” 6,000 frequent and trusted contributors.

Tapping into the collective wisdom of the crowd seems like an obvious thing today, but the OEIS was doing it in 1996, five years before Wikipedia, making the OEIS one of the first large-scale efforts to incorporate crowd-sourcing to expand mathematical and scientific information.

While Sloane himself describes the evolution of the OEIS as organic and something that just occurred naturally, it’s hard to see how the whole thing would have come about without his specific mix of pure, abstract interest in numbers and an equally pragmatic appreciation for workable tools—something that is probably not that common in the world of theoretical mathematics. It may be the reason why no one before him had followed through in creating a collection of sequences. It required having the initial idea, the practical (and early) grasp of computers and evolving technology to implement an online resource at large scale and make it accessible, and a willingness to collaborate and share the experience with others. 

Sloane is no longer maintaining the OEIS alone. Since 2002 a board of associate editors and volunteers, mostly professional mathematicians and computer scientists, has been helping with the daily workload of 200 or so proposals for new sequences or additional commentary and links. Fifty new sequences make it in each day.

Towards ensuring the long-term future of the OEIS as a free, independent resource, Sloane set up The OEIS Foundation in October 2009, transferring the hosting of the OEIS from AT&T Research to servers owned and operated by the foundation.

 

Using the OEIS

The OEIS is simple to use. It has two main parts: the lookup page (oeis.org) that operates as an integer sequence search engine, and a wiki (oeis.org/wiki) for discussion pages, indexes, instructions and everything else.

OEIS-web-page

From the main OEIS main webpage, enter a sequence, an ID, a keyword, an author, or an integer.

Typing a sequence into the lookup page returns a webpage listing the sequence’s ID (a six-digit number preceded with the letter A), the first 20 or so terms, along with comments, references to the literature, links to other websites, cross-references to related sequences, and formulas and computer code (usually Maple and Mathematica) for producing the sequence, and even the option to generate a graph or to play a musical representation of the sequence on any one of 128 instruments.

The OEIS is nothing if not complete.

Besides the simple lookup option, sequences can be browsed in lexicographic order (helpful when comparing and contrasting neighboring sequences), browsed randomly using the webcam feature, or searched by topic from the index page, which returns all sequences related to hundreds of topics: chess, Möbius functions, postage stamp problems, fractals, Boolean functions.

Of course, the best way of knowing what’s in the OEIS is to enter and begin exploring.

 

Sequences in the real world

Sloane originally started the sequence collection as an aid to research so that anyone coming upon a sequence in their calculations could immediately get additional terms and maybe a formula. This use of the OEIS is more important than ever today, since many computer-related tasks can be stated in terms of a sequence: minimizing the number of steps needed to count a set of items, ranking a list of unsorted numbers from lowest to highest, even characterizing the behavior of a program or algorithm.

As more applications today depend on ideas and concepts taken from pure mathematics—cryptography, the use of graphs to study social networks, the ranking of search engine listings—sequences increasingly play a more direct role in solving real-world problems.

 
OEIS-labeled-balls

Any problem that involves selecting or counting a subset from two groups can be stated as a sequence.
 
While the OEIS can solve immediate problems and provide a ready formula, its more fundamental contribution is facilitating the discovery of connections between seemingly unrelated fields.

Someone for instance may come upon an unknown type of polynomial. By figuring out five or six coefficients and entering the sequence into the OEIS, the formula may be found, but the more important discovery may be that the sequence is a second-order Chebyshev polynomial, and thus related to orthogonal polynomials. Because the OEIS provides commentary and links to related topics, it can take less than a few minutes to gain access to an entirely new broad body of knowledge or class of problem. Or find a different interpretation of a known sequence.

Integer sequences, because they often have many mathematical interpretations and can be solved in different ways, act in some sense as an intersection of those interpretations. Two people may approach the same sequence from different perspectives, providing the each other a fresh way of looking at a sequence. Several collaborative papers on sequences are the result of researchers finding one another through when proposing new information on the same sequence.

 

Sequences as sequences

Sequences may be key to solving problems in diverse mathematical fields, but there is also this: sequences by themselves—divorced from practical applications—have an inherent interest all their own.

Sloane talks of sequences as being interesting or nice, by which he means something unique or hard to explain is occurring within the sequence. Some sequences grow smoothly, others explode so fast only the first few terms can be listed (A028444), while still other sequences end up in a loop and go nowhere (A033478). Why? If two sequences have properties in common, is it a coincidence or is something deeper going on?

The OEIS, by pulling together the existing knowledge about sequences, makes it easier to study these questions. The OEIS itself is a rich data set to be mined for more sequences, more knowledge. Existing sequences can be transformed into new ones, providing more material for mathematicians to start to consider new conjectures concerning power series expansions, number theory, combinatorics, nonlinear recurrences, binary representations, and other mathematical areas.

Sequences by themselves are subjects of serious scholarship. Entire papers, some of them 30 or more pages long, are devoted to the mathematics behind sequences, often a single sequence. To provide a place for these papers, Sloane founded in 1998 the Journal of Integer Sequences, where recent papers cover the Bernoulli & Euler polynomials, truncated kernel function, the r-Bell numbers, all are in the OEIS.

But among the serious sequences are other ones, too: New York City subway stops, bus line numbers in Philadelphia, the number of stable towers of 2 x 2 Lego blocks. How is it that such sequences appear among the subfactorial or rencontres numbers, the doubly automorphic primes, and Hexanacci numbers?

If a sequence is interesting, Sloane would argue, what does it matter where it came from? The Fibonacci sequence, simple as a child’s game—add two consecutive numbers to get the next, then do it again, forever—exhibits such impressive properties that an entire publication, The Fibonacci Quarterly, is devoted to it.

Sloane’s own favorite sequence—0, 1, 3, 6, 2, 7, 13, 20, 12, 21, . . ., (A005132) has no source in number theory or discrete math, nor did it come out of his theoretical work. It’s the invention of Bernardo Recamán Santos, a serious, amateur mathematician, who following Arnold Ross´s advice to think deeply of simple things, stumbled upon the sequence while working on a problem. The exact problem has long since been forgotten, but Recamán recalls very well working out the sequence by hand to prove it contained all numbers. Failing to get beyond 100 terms, he scribbled the sequence on a postcard while traveling somewhere by European train and sent it off to Sloane for inclusion in the OEIS.

 

Recamán’s sequence - A005132  

This sequence was named by Sloane for its inventor, Bernardo Recamán Santos.

It unfolds as follows: Subtract a number from the next larger lexicographic one (0,1, 2, 3, 4, are in lexicographic order) to produce the next term, unless it results in a number that is negative or has already appeared, in which case, add.

That is, a(0) = 0; for n > 0, a(n) = a(n-1)-n if that number
is positive and not already in the sequence, otherwise a(n) = a(n-1)+n.

Start with 0 (0, . . . ).

Subtract 0 from 1 to get 1. (0, 1, . . . ). The next number to add or subtract is 2. Since subtracting 1 from 2 gives 1, which already appears, you must add 1 and 2 to get 3 (0, 1, 3, . . .). Go on to 3. 3 - 3 produces 0, so you must add to get 6 (0, 1, 3, 6, . . . ). Go on to 4 following the same rule (in this case, subtracting 4 from 6 results in 2, which has not yet been seen, so the next term is 2. Now add or subtract 5.

0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, . . . ,

 

The simple rule created by Recamán produces a complex sequence that is hard to understand and hard to analyze. The sequence displays no recurrences or particular regularity. Nor does it increase, decrease, or oscillate in any predictable way. (The Fibonacci sequence, which starts out similarly to the Recamán sequence, grows at a smooth, predictable rate.)

Sloane with others’ help has computed the sequence to 1015 terms (the OEIS displays the first 100,000), finding that some low-value integers don’t appear for a very long time. The integer 19 doesn’t appear until well past 100,000; 61 and 179 also take their time to appear, and 2406 goes missing well after 100 billion terms. (The holdouts form their own sequence, A064228.) Sloane found 852655 to be the smallest number missing when the sequence is computed to 1015 terms; even after 4.28 x 1073 terms, there is no sign of 852655.

Not all sequences can be as interesting as Recamán’s; in truth, some are barely interesting or even mathematical. Sloane himself is aware of this and there are keywords in the OEIS to identify sequences as being core, base, nice, or dumb. He includes them all because his aim for the OEIS is completeness. A sequence that is apt to be seen or noticed by many people will almost certainly be found in the OEIS: subway stops memorized by subway riders; sequences found in literature (the book Gödel, Escher, Bach by Douglas Hofstadter is filled with sequences, all of them, to be sure, listed in the OEIS); sequences that result from gambling or games (A027887, the possible hands of Skat, and A083276, the number of chess positions after n plies.)

Who knows what is yet to be discovered among unexamined sequences?

If the OEIS didn’t exist, someone might see a sequence and wonder about it for a brief moment or do a calculation perhaps to be seen by no one else. With the OEIS, there’s a place for that momentary contemplation to become a stepping stone to the larger examination of the mathematics behind the sequence and to lead one perhaps to an entirely new field of study or to a collaborative working relationship with others captivated by the same sequence. And it’s this ability to bring together people over a shared appreciation of sequences and mathematics that Sloane sees as the OEIS’s highest achievement.

 

 








 

201203_OEIS-at-a-glance

 

How to look up a sequence

1.  Go to the OEIS (oeis.org).

2.  Enter the sequence.
Separate terms by a space or comma.

Enter about six terms starting with the second term (unless it’s a 0).

If every other term is a zero (e.g., 1, 0, 2, 0, 4, 0, 8, 0, 16, 32, 0, 64, 0, . . . ., ), skip the zeros (1, 2, 3, 4, 8, 16, 32,  . . . ). If the sequence has an obvious factor (2, 6, 12, 20, 30, 42,  . . . ,), divide it out (1, 3, 6, 10, 15, 21,  . . . ,).

You can also search by sequence name (“fermat’s little theorem”), author (author:njas), keyword (keyword:base), OEIS ID (id:A64413), or even a single integer.

If the sequence is not in the OEIS, you’re given an option to add it (registration is required).
 

Some keywords

Base: Dependent on base used
Core: Most important sequences.
Easy. A formula exists.
Full: All terms are shown.
Hard: Term following those given is not known.
Nice: Nice!
Nonn: No negative numbers.
Sign: Contains negative numbers.
Unkn: Little is known; an unsolved problem.
Word: Depends on words for the sequence (language-dependent).

 

Fun facts about Fibonacci - A000045

The sums and differences of consecutive Fibonacci numbers are Fibonacci numbers.

The greatest common divisor of two Fibonacci numbers is another Fibonacci number.

Every 4th Fibonacci number is divisible by 3; every 5th by 5; and every 6th by 8.

The ratio of successive Fibonacci numbers converge to the golden ratio.

201203_OEIS-Golden-rectangle

Any four consecutive Fibonacci numbers can be combined to form a Pythagorean triple.

For any m and n, if m is divisible by n, then Am is divisible by An.

 

How to submit a sequence  

1.  Check that the sequence is not already in the OEIS.

Omit zeros if every other term is a zero, and divide by any factor shared by all terms.

Infinite sequences are preferred over finite ones.

It’s highly recommended to first run any new sequence through the superseeker program. Do this as follows: create an email containing a single line in this format:
lookup 1 2 4 6 10 14 20 26 36 46 60 74 94 114. Send to  

201203_superseeker-email-image

which will apply a series of transformations to determine if it’s similar to an existing sequence.

 2.  To propose a new sequence, go to the OEIS lookup page and select the option Contribute new seq or comment at the bottom of the page.

3.  Enter the sequence, separating the terms with commas. Enter any other information.

The sequence will then be evaluated by a board of editors, which can take 1 or 2 days.
 

Common reasons sequences are rejected 

1. The sequence is already there.

2.  The sequence is arbitrary or not well-defined.

Sequences should not depend on an arbitrary parameter (such as primes that begin 999).
An example of an ill-defined sequence: the number of pages in n volume of Harry Potter (an actual proposed sequence). It’s not well defined because the page count changes from one printing to another and from one language to another.

3.  The sequence is a close variation of an existing sequence.


 

Contribute to the OEIS

The OEIS, for many years hosted by AT&T Research, is now its own foundation supported by volunteers and tax-deductible donations. The OEIS does not show ads or pay contributors.

For more information, visit The OEIS Foundation site.