The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)

Demonstration of the

On-Line Encyclopedia of Integer Sequences® (or OEIS®)

(Page 2)

  • The main use for the database is to identify a number sequence that you have come across, perhaps on the Internet, in your work, on a test, etc.
  • This page and the next two or three will show some examples.

Identifying a Sequence - Description of Database

You discover what you think may be a new algorithm for putting a file of patient's medical records into alphabetical order. (Perhaps you are a computer scientist or someone working in information science.)

To handle a pile of 1, 2, 3, 4, ... records, your algorithm takes

0, 1, 3, 5, 9, 11, 14, 17, 25, ...


How can you check if someone has discovered this algorithm before? You decide to ask the OEIS if this sequence has appeared before in the scientific literature.

You go to the main web page, which gives you the following. (These responses have been slightly edited to save space.)

The On-Line Encyclopedia of Integer Sequences

Enter a sequence, word, or sequence number:

You replace the example by your sequence and click "Submit":
Enter a sequence, word, or sequence number:


This produces the following response.

Greetings from the On-Line Encyclopedia of Integer Sequences!

Search: seq:1,3,5,9,11,14,17,25
Displaying 1-1 of 1 result found. page 1
     Sort: relevance | references | number | modified | created         Format: long | short | data
A003071 Sorting numbers: maximal number of comparisons for sorting n elements by list merging.
(Formerly M2443)
0, 1, 3, 5, 9, 11, 14, 17, 25, 27, 30, 33, 38, 41, 45, 49, 65, 67, 70, 73, 78, 81, 85, 89, 98, 101, 105, 109, 115, 119, 124, 129, 161, 163, 166, 169, 174, 177, 181, 185, 194, 197, 201, 205, 211, 215, 220, 225, 242, 245, 249, 253, 259, 263, 268, 273, 283, 287, 292, 297, 304 (list; graph; refs; listen; history; edit; internal format)



Comment from Jeremy Gardiner, Dec 28 2008: The following sequences all appear to have the same parity: A003071, A029886, A061297, A092524, A093431, A102393, A104258, A122248, A128975.


J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.

D. E. Knuth, Art of Computer Programming, Vol. 3, Sections 5.2.4 and 5.3.1.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.

Index entries for sequences related to sorting


Let n = 2^e_1 + 2^e_2 + ... + 2^e_t, e_1 > e_2 > ... > e_t >= 0, t >= 1. Then a(n) = 1 - 2^e_t + Sum_{1<=k<=t} (e_k+k-1)*2^e_k [Knuth, Problem 14, Section 5.2.4].

a(n) = a(n-1) + A061338(n) = a(n-1) + A006519(n) + A000120(n)-1 = n + A000337(A000523(n)) + a(n-2^A000523(n)). a(2^k) = k*2^k + 1 = A002064(k). - Henry Bottomley (se16(AT)btinternet.com), Apr 27 2001

G.f.: x/(1-x)^3 + 1/(1-x)^2*Sum(k>=1, (-1+(1-x)*2^(k-1))*x^2^k/(1-x^2^k)). - Ralf Stephan (ralf(AT)ark.in-berlin.de), Apr 17 2003


Cf. A001855.




N. J. A. Sloane (njas(AT)research.att.com).


More terms from David W. Wilson (davidwwilson(AT)comcast.net)

page 1

Search completed in 0.884 seconds

And so you discover that your sequence is the number of steps needed for sorting by list merging, a well-known algorithm.

The entry directs you to 5.3.1 of Volume 3 of D. E. Knuth, The Art of Computer Programming, where you find your algorithm described. The entry even gives an explicit formula for the nth term.

You decide not to apply for a patent!

The OEIS's files are full of stories like that (although that one is imaginary). A frequent comment is

... your database saved me six months of work.

The OEIS has helped people from almost every country in the world, and from almost every field. From school children to high-school students to undergraduates to ... to professionals to retirees. Anyone who likes numbers will find something interesting here.

The database has been called the mathematical analogue of a fingerprint file [B. Cipra, Mathematicians get an on-line fingerprint file, Science, 265 (22 July, 1994), page 473], since it serves to identify number sequences.

Other comments, stories and anecdotes will be mentioned in subsequent demonstrations.

It is hoped that eventually the database will include every (interesting) number sequence that has ever been published.

Description of the Database

  • The database is first of all a very large collection of number sequences.
  • The example in the 5th demonstration will be taken from chemistry. Other examples have come from physics, computer science, etc., and all branches of mathematics, especially discrete mathematics, combinatorics, number theory, algebra, game theory, recreational mathematics, ...
  • The typical entry for a sequence gives among other things:

    • the beginning of the sequence
    • its name or description
    • any references to the scientific literature or links to relevant web sites
    • any formulae, recurrences, generating functions, etc. that are known
    • cross-references to other sequences
    • a list of keywords
    • the name of the person who submitted it
  • A more complete description of the entries is available from the web page:
  • Some details

    • The sequences in the database have been collected over several decades. The database has grown from 2400 sequences in 1973 to 5500 in 1995 to nearly 200000 today.
    • New sequences currently arrive at a rate of over 15000 per year.
    • The web pages receive thousands of hits each day, from almost every country on earth.
    • The web pages are free and carry no ads.
    • The OEIS was started by N. J. A. Sloane in 1964, and maintained by him until 2010.
    • In 2010 a tax-exempt charitable foundation, The OEIS Foundation Inc., was set up to own, maintain, and raise funds to support the OEIS.
    • Since Nov 11 2010 the OEIS has been running as a moderated wiki on its own web site, http://oeis.org. The conversion to a wiki — a monumental task — was carried out by Russ Cox. David Applegate is the OEIS webmaster.
    • Please see the OEIS Foundation web site for more information about the history of the OEIS and its conversion to a wiki — and to make donations!
  • The OEIS is much more than just this database, however, as will become apparent in subsequent demonstrations.

Click the single right arrow to go to the next page, or the single left arrow to return to the previous page.

Main page           Start Previous                               NEXT! Last           Main page

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 2 03:22 EST 2021. Contains 341741 sequences. (Running on oeis4.)