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, ...
steps.
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.)
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.
Search: seq:1,3,5,9,11,14,17,25
|
|
|
|
|
A003071
|
|
Sorting numbers: maximal number of comparisons for sorting n elements by list merging.
(Formerly M2443)
|
|
+20
13
| |
|
|
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)
|
|
|
|
OFFSET
| 1,3
|
|
|
COMMENTS
| 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.
|
|
|
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.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
| 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
|
|
|
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.
|
|
|
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)
|
|
|
|
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:
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 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.
