Demonstration of the On-Line Encyclopedia of Integer Sequences (Page 2) The main use for the database is to identify a number sequence that you have come across, perhaps in your work, while reading a book, or in a quiz, 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 checking that a file of medical records is in the correct order. (Perhaps you are a computer scientist or someone working in information science.) To handle files of 1, 2, 3, 4, ... records, your algorithm takes 0, 1, 3, 5, 9, 11, 14, 17, 25, ... steps. How can you check if someone has discovered this algorithm before? You decide to ask the On-Line Encyclopedia of Integer Sequences 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: Hints You replace the example by your sequence and click "Submit": Enter a sequence, word, or sequence number: Hints This produces the following response. Greetings from the On-Line Encyclopedia of Integer Sequences! Search: 1,3,5,9,11,14,17,25 Displaying 1-1 of 1 results found. page 1          Format: long | short | internal          Sort: relevance | references | number A003071 Maximal number of comparisons for sorting n elements by list merging. (Formerly M2443) +0 3 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) OFFSET 1,3 REFERENCES 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. LINKS Index entries for sequences related to sorting J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197. FORMULA 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 CROSSREFS Cf. A001855. Sequence in context: A047623 A007950 A034936 this_sequence A109324 A047270 A084060 Adjacent sequences: A003068 A003069 A003070 this_sequence A003072 A003073 A003074 KEYWORD nonn,easy,nice AUTHOR N. J. A. Sloane (njas(AT)research.att.com). EXTENSIONS More terms from David W. Wilson (davidwwilson(AT)comcast.net) page 1 Search completed in 0.083 seconds (0.003 user, 0.029 system, 0 memory pages accessed)

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 Section 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 On-Line Encyclopedia'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 On-Line Encyclopedia of Integer Sequences 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.

• 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: eishelp2.html
• 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 over 150000 today.
  • Numerous correspondents help keep the database up-to-date. New sequences currently arrive at a rate of over 10000 per year.
  • The web pages receive thousands of hits each day, from almost every country on earth.
  • The On-Line Encyclopedia of Integer Sequences is maintained by one person, Neil J. A. Sloane, as part of his research at AT&T Shannon Labs in Florham Park, New Jersey, U.S.A.
  • The web pages are free and carry no ads.
• The On-Line Encyclopedia of Integer Sequences is much more than just this database, however, as will become apparent in subsequent demonstrations.

                                                 

Legal Notice © 2009 AT&T Intellectual Property. All Rights Reserved.