login

Demonstration of the

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

(Page 2)

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.)

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: 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)
+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)

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

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