This site is supported by donations to The OEIS Foundation.
User:Olivier Gérard/Welcome fr
Bienvenue sur le site de l'OEIS™
Encyclopédie Electronique des Suites de Nombres Entiers
(On-Line Encyclopedia of Integer Sequences™)
Contents
- 1 Une suite célèbre
- 2 General Information About OEIS
- 3 Informations générales sur l'OEIS
- 4 Description of the Database (or, What is the Next Term?)
- 5 OEIS: Petit historique
- 6 OEIS: The movie
- 7 Arrangement of Sequences in Database
- 8 Format used in replies from the database
- 9 Index
- 10 Recent Additions
- 11 Compressed versions
- 12 Contributing a new sequence, comment or more terms
- 13 OEIS Search Bar
- 14 Email Addresses, Getting in Touch With Authors
- 15 Sequences in Classic Books
- 16 Citations
- 17 Referencing the OEIS
- 18 URLs
- 19 Referencing a Particular Sequence
- 20 Policy on Searching the Database
- 21 Acknowledgments
- 22 Related OEIS Pages
- 23 Links to Other Sites
- 24 Awards, Press Clippings
- 25 Copyright Notice
Une suite célèbre
Commençons par un exemple, celui d'une suite importante et d'une grande difficulté, A060843, le problème dit "Busy Beaver" (le castor surmené). Voici la page de l'encyclopédie pour A060843:
A060843
Busy Beaver Problem: a(n) = maximal number of steps that an n-state Turing machine can make on an initially blank tape before eventually halting.
Sequence
1, 6, 21, 107
Offset
1,2
Comment
- "In 1965 Tibor Rado, together with Shen Lin, proved that a(3) is 21. ... Next, in 1983, Allan Brady proved that a(4) is 107. ... Then in 1989 Heiner Marxen and Juergen Buntrock discovered that a(5) is at least 47176870. ... As for a(6), Marxen and Buntrock set another record in 1997 by proving that it is at least 8690333381690951." [Based on Aaronson's web page.]
- The function Sigma(n) (A028444) denotes the maximal number of tape marks which a Turing Machine with n internal states and a two-way infinite tape can write on an initially empty tape and then halt. The function a(n) (the present sequence) denotes the maximal number of steps (shifts) which such a machine can make (it needs not produce many tape marks).
- Given that 5-state machines can compute Collatz-like congruential functions (see references), it may be very hard to find the next term.
- The sequence grows faster than any computable function of n and so is non-computable.
References
- Brady, A. H., The busy beaver game and the meaning of life, in Herken, R. (Ed) The Universal Turing Machine: A Half-Century Survey, pp. 259-277, Oxford Univ Press 1988. Reprinted by Springer-Verlag, 1995 (see pages 237-254). [Reference updated by Daniele Giorgio Degiorgi, Nov 22 2008]
- Brady, A. H. The determination of Rado's noncomputable function Sigma(k) for four-state Turing machines, Math. Comp. 40 #62 (1983) 647-665.
- Shen Lin and T. Rado, Computer Studies of Turing Machine Problems, J. ACM 12 (1965), 196-212.
- Machlin, R. (nee Kopp) and Stout, Q, The Complex Behavior of Simple Machines, Physica D 42 (1990) 85-98
- Michel, Pascal, Busy beaver competition and Collatz-like problems, Arch. Math. Logic (1993) 32:351-367.
- Rado, T., On Non-Computable Functions, Bell System Technical J. 41 (1962), 877-884.
- R. M. Robinson, Minsky's small universal Turing machine, Int'l Jnl. Math, 2 #5 (1991) 551-562.
- Yu. V. Rogozhin, Seven universal Turing machines (Russian), abstract, Fifth All-Union Conference on Math. Logic, Akad. Nauk. SSSR Sibirsk. Otdel., Inst. Mat., Novosibirsk, 1979, p. 127.
- Yu. V. Rogozhin, Seven universal Turing machines (Russian), Systems and Theoretical Programming, Mat. Issled. no. 69, Akademiya Nauk Moldavskoi SSSR, Kishinev, 1982, pp. 76-90.
- Claude E. Shannon, A universal Turing machine with two internal states, Automata Studies, Ann. of Math. Stud. 34 (1956) 157-165.
Links
- Scott Aaronson, Who Can Name the Bigger Number?
- Bill Dubuque, Re: Halting is weak
- A. Gravell and U. Ultes-Nitsche, BB(n) Grows Faster Than Any Computable Function
- H. Marxen, Busy Beaver Problem
- M. Somos, Busy Beaver Turing Machine
- M. Somos, Busy Beaver
- Q. F. Stout, The Complex Behavior of Simple Machines
- Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
- Eric Weisstein's World of Mathematics, Busy Beaver
- Index entries for sequences related to Busy Beaver problem
Crossrefs
- Cf. A028444.
- Sequence in context: A012662 A012418 A083558 this_sequence A026650 A009253 A012840
- Adjacent sequences: A060840 A060841 A060842 this_sequence A060844 A060845 A060846
Keyword
hard,nice,nonn,bref
Author
Jud McCranie (j.mccranie(AT)comcast.net) and N. J. A. Sloane (njas(AT)research.att.com), May 02 2001
Extensions
- The next two terms are at least 47176870 and 3*10^1730.
- Additional references from Bill Dubuque (wgd(AT)martigny.ai.mit.edu)
(That is the end of the example. Of course the keyword "hard" is an understatement - it will be a major triumph for mathematics if the next term is ever discovered!) (Fin de l'exemple. Bien entendu le mot-clef "hard" (difficile) est une litote - ce serait un immense succès pour les mathématiques si le prochain terme était un jour obtenu !)
General Information About OEIS
Informations générales sur l'OEIS
- Most people use the OEIS to get information about a particular number sequence. If you are a new visitor, then you might ask the database if it can recognize your favorite sequence, if you have one. To do this, go to the main look-up page. (Of course the number sequence should be well-defined, of general interest and ideally it should be infinite. Short sequences such as phone numbers are not appropriate.)
- If your sequence isn't in the database, and if it is interesting, please submit it using the web page for contributing a new sequence or comment.
- If you have stumped the database, you can try Superseeker, which tries really hard to identify a sequence.
- You can browse the database, using the WebCam. This can be set to look at the most interesting sequences, recent additions, or sequences needing more terms. It can be quite addictive.
- It is interesting to scan the Index to the OEIS to see the variety of topics that are covered. In a way this OEIS can be regarded as an index to all of science. It is like a dictionary or fingerprint file for number sequences.
- Also worth visiting are the pages dealing with Puzzle sequences, Classic sequences and Hot sequences. (These pages need to be updated.)
- You can run the demonstration pages to see more examples of how to use the OEIS.
- The Search pages have little buttons called "list", "graph", "listen" and sometimes "table".
- "List" produces a numbered list of the terms, plus a bracketed list suitable for importing into other programs.
- "Graph" produces two plots of the sequence. The first is a pin plot of the first 200 terms (less if fewer terms are available), the second is a linear or log scatterplot of all available terms, using terms from the b-file if there is one. Some noteworthy plots are the Fibonacci numbers A000045, the partition numbers A000041, the Euler phi-function A000010, etc. The plotting program was written by Deborah Swayne using the R language.
- "Listen" produces a midi file so that you can listen to the sequence. The first time you use it you will probably have to tell your browser to allow popups from the OEIS web site. (This works best with Firefox.) Try listening to Recaman's sequence A005132, turn the volume up to 127 and set the instrument to #103 !
- "Table": If the sequence is formed by reading a triangle across rows (or by reading a table by antidiagonals), this button produces three different two-dimensional views of the sequence. For an example, see Pascal's triangle A007318.
- Finally, you might like to see a list of papers that have acknowledged help from the database and some comments from readers.
Description of the Database (or, What is the Next Term?)
What comes next after 1, 2, 4, 9, 20, 48, 115, 286, 719, ... ? (for example). This is the place to find out!
- The main table is a collection of about 200000 number sequences. The entry for each sequence gives some or all of:
- the beginning of the sequence
- its name or description
- additional comments
- any references or links
- any formulas
- computer programs to generate the sequence
- cross-references to other sequences
- the name of the person who submitted it, etc.
- In the OEIS Wiki, each sequence has its own page. These pages were initially created in 2010 from the "Classic" version of the OEIS.
- For further information about the format of replies received from the database, click here. A second file describes the internal format in which the sequences are stored in the classic version of the database. See also the hints file for further useful information.
OEIS: Petit historique
La base de données des suites entières est née en 1965, imaginée par Neil J. A. Sloane (NJAS dans la suite) lorsqu'il était un étudiant-chercheur à l'université Cornell (Ithaca, état de New-York). Il avait rencontré une suite de nombre pendant son travail de thèse, plus précisément 1, 8, 78, 944, ... (maintenant A000435 dans l'Encyclopédie), et cherchait une formule générale pour le n-ième terme pour pouvoir estimer sa croissance.
Il remarqua que plusieurs ouvrages de la librairie de mathématiques de l'université Cornell comportaient des suites entières assez similaires, celle-ci n'était pas mentionnée. Pour garder la trace des suites de contenues dans ces livres, NJAS commença à les noter sur des fiches cartonnées, qu'il triait par ordre lexicographique.
Les suites furent ensuite transférées à des cartes perforées, et transformé en livre en 1973 ("A Handbook of Integer Sequences" =(Répertoire des Suites Entières), par NJAS, Academic Press, New-York). Ce livre contenait 2372 suites entières.
NJAS avait intégré les Laboratoires Bell (compagnie américaine AT&T) en 1969. La publication du livre lui valut une large correspondance avec des suggestions pour de nouvelles suites et des modifications des entrées existantes. De nombreux lecteurs remarquèrent à quel point le livre leur avait été utile et qu'il était surprenant que personne n'ai songé à publier une compilation de ce genre auparavant.
Au début des années 1990 il y avait déjà un mètre cube de lettres et de documents accumulé. Un mathématicien canadien, Simon Plouffe, proposa son aide pour la préparation d'une édition revue et corrigée et en 1995 "The Encyclopedia of Integer Sequences", par NJAS et Simon Plouffe fut publiée chez Academic Press, à San Diego.
OEIS: The movie
To celebrate the launching of The OEIS Foundation Inc, Tony Noe has made an 8.5-minute movie showing the first 1000 terms of 1000 sequences, with soundtrack from Recaman's sequence A005132.
There are four ways to view the movie:
- On YouTube (you can find it by searching for "OEIS" and "Movie").
- By downloading a 5 MB QuickTime movie that is viewable with QuickTime Player 7 and some browsers.
- By downloading a 27 MB movie that uses the H264 codec and AAC sound. This movie is viewable on recent versions of Windows Media Player and most up-to-date browsers.
- By going to Tony's website for a frame-by-frame display, with links to the definitions of the sequences.
(Incidentally, you can convert the movie to just about any other format at http://www.media-convert.com, without downloading any software).
Arrangement of Sequences in Database
In the classic OEIS, most of the sequences are arranged in lexicographic order of absolute values, indexed by the position of the first term that is greater than 1 in absolute value. Sequences that contain only 0's, 1's and -1's are in strict lexicographic order by absolute value at the beginning of the table. Thus there is an essentially unique place to look in order to see if a sequence is already in the table. (If it isn't, submit it and it will added if it is sufficiently interesting - see contributing a new sequence or comment.) Sequences received in the last few days and not yet placed in the lexicographic ordering will be found at the end of the table.
Format used in replies from the database
For information about the format of replies received from the database, click here. A second file describes the internal format in which the sequences are stored in the classic version of the database. See also the hints file for further useful information.
Index
- There is an Index to the most important sequences.
- The main look-up page will also allow you to search for a word (or do much more complicated searches) in the database.
Recent Additions
- Recent additions to the OEIS can be seen in the Recent Additions file.
- You can also browse the recent additions using the WebCam.
Compressed versions
- A gzipped file containing just the sequences and their A-numbers (about 9 megs)
- A gzipped file containing just the names of the sequences and their A-numbers (about 3 megs)
Contributing a new sequence, comment or more terms
- For contributing a new sequence, comment or more terms for an existing sequence, see this page.
- Want to help? See the web page Sequences that need more terms, use the WebCam to browse the sequences that need more terms, or use the main look-up page to search for the keyword more (I admit I'm not sure how to do the latter, but it has to be possible).
- See also the page future projects (this page needs updating)
OEIS Search Bar
To add OEIS search to the search bar in your browser, see the instructions in the Welcome Page for the Classic OEIS.
Email Addresses, Getting in Touch With Authors
The Classic OEIS provides email addresses (in disguised form) for all contributors. This is essential in a scientific database, in order that questions involving definitions, possible errors, etc., can be discussed. In the OEIS Wiki, however, email addresses will not be made public. A different mechanism will be used for getting in touch with authors.
First, find the author in the list of Registered Users and go to the author's User Page. Click the Discussion Tab to go to the User Talk page. Then click on the Edit/+ Tab to enter a message. Sign the message by typing ~~~~ (four tildes) when you are done. Then be sure to click both Preview and Save Page. This should trigger an email message to the author.
There are several web pages that provide advice on editing Talk Pages. See for example Wikipedia's Help:Using Talk Pages.
Sequences in Classic Books
These files contain concordances to the sequences mentioned in certain classic books.
- L. Comtet's Advanced Combinatorics
- P. Flajolet and R. Sedgewick's Analytic Combinatorics
- R. L. Graham, D. E. Knuth and O. Patashnik's Concrete Mathematics
- F. Harary and E. M. Palmer's Graphical Enumeration
- R. P. Stanley's Enumerative Combinatorics.
Citations
- Papers Citing the Encyclopedia of Integer Sequences. Shows some of the ways that people have used the database.
Referencing the OEIS
If the database helped your work and you wish to reference it, the usual citation is something like this:
The On-Line Encyclopedia of Integer Sequences, published electronically at http://oeis.org, 2010.
URLs
- The URL for the main lookup page is http://oeis.org/wiki
- The URL for the present page is http://oeis.org/wiki/Welcome
Referencing a Particular Sequence
- If you are writing a paper and wish to refer the Catalan numbers, say (sequence A000108), but don't want to digress to describe them, simply add a reference or link that points directly to that sequence in the OEIS.
- The URL for sequence A000108 (for example) is http://oeis.org/A000108.
- A text reference might say:
The On-Line Encyclopedia of Integer Sequences, published electronically at http://oeis.org, 2010, Sequence A000108
or, if it is clear who "discovered" the sequence, something like
J. H. Conway, Sequence A007970 in The On-Line Encyclopedia of Integer Sequences (2010), published electronically at http://oeis.org.
- In an HTML file one might say something like this: ... where the C(n) are the Catalan numbers (<a href="http://oeis.org/A000108">Sequence A000108</a> in [OEIS]).
Policy on Searching the Database
- Just as it is OK for a browser (such as Firefox) to access the OEIS, so it is also OK for a computer algebra program such as SAGE or Haskell to have an interface with the OEIS, provided of course that this does not put too much of a burden on the server here.On the other hand, it would definitely not be OK to distribute a copy of the OEIS with such a program.
- See The OEIS End-User License Agreement for further information.
Acknowledgments
- A very large number of people have contributed to the database, and it would be impossible to thank them individually. Their names can be seen throughout the nearly 200000 entries.
- Special thanks to Antti Karttunen, who wrote the program that displays sequences based on arrays (those with keyword "tabl") in three different two-dimensional formats. To see this, look at some of the following sequences, and click on the keyword "tabl":
- At the end of 2005, Alex Healy and Russ Cox (rsc(AT)swtch.com) made a huge contribution to OEIS by greatly speeding up the search process in the Classic OEIS. The first versions of the new programs were written by Alex Healy and the final versions by Russ Cox. David Applegate helped install them. The new searches were much faster than the old ones and can handle much more complicated queries. See the hints file for details.
- During 2009-2010, David Applegate has been working on the enormous tasks of (1) moving the OEIS from Neil Sloane's home page at AT&T to its new home at oeis.org, and (2) converting it to a wiki format at oeis.org/wiki. The second step has turned out to be unexpectedly difficult, because we discovered that the Wikimedia software is unsuitable for performing the kind of searches needed for the OEIS. Russ Cox has also been helping solve this problem. It is hoped that this work will be completed in the summer of 2010.
Related OEIS Pages
Some of these are links to the Classic OEIS. They will be gradually be replaced by links to the OEIS Wiki. Also several of these pages still need to be converted from html to wikimedia.
- Main look-up page
- Lookup hints
- Welcome page (this page)
- Index to OEIS
- Classic OEIS
- OEIS in other languages (use the Classic OEIS)
- The OEIS Foundation Inc.
- Register (an account is necessary to contribute to the Wiki).
- Registered Users
- Contributing a new sequence, comment or more terms for an existing sequence
- Editorial Board
- Format (1), Format (2)
- Transformations of sequences
- Maple or Mathematica (see EISFormat.m) scripts to format sequences
- OEIS FAQ, Wiki FAQ
- OEIS 100K E-Party
- OEIS MOVIE
- Demonstration pages
- OEIS WebCam
- Sequences that need more terms
- Future projects (this page needs updating)
- Index to Fractions
- Find Friends
- Music (this page needs updating)
- Plot one sequence against another
- Puzzle sequences, Classic sequences, Hot sequences (these pages need to be updated)
- More Pages (Wiki version), More Pages (Classic version)
Links to Other Sites
- b-file Maple programs written by R. J. Mathar
- Caldwell's Prime Pages
- Combinatorial Object Server
- Davalan's Jeux et Mathématiques
- De Geest's World of Numbers
- Encyclopedia of Combinatorial Structures
- Finch's Mathematical Constants
- Geometry Junkyard
- Journal of Integer Sequences
- MathSciNet
- The Nth Prime Page
- Plouffe's Inverter (see also the Inverse Symbolic Calculator)
- SeqFan Mailing List
- Primo
- Neil Sloane's home page
- Eric Weisstein's MathWorld
Awards, Press Clippings
- Jochen Reinecke, Gehen sie ins netz?, Frankfurter Allgemeine Sonntagszeitung, March 14, 2010, No. 10, page 61.
- Ivars Peterson, Deciphering Integer Sequences, The Mathematical Tourist, March 10 2010.
- Barry Cipra, What Comes Next?, Science Magazine, 327 (Feb 19, 2010), p. 943. [One of mathematicians' most beloved Web sites is getting ready for a makeover, it was reported at the Joint Mathematics Meetings. The Online Encyclopedia of Integer Sequences, established by Neil Sloane at AT&T Labs Research in 1996 and run largely as a one-man shop, is poised to go "wiki," with 50 associate editors taking over much of the workload....]
- Irena Cieslinska, Co rozpala umysly, których nikt nie rozumie?, [What enkindles the greatest intellects in the world?] (Polish), Gazeta Wyborcza, September 28, 2009. (Article contains several errors.)
- NJAS's 2003 article about the OEIS received the Math. Assoc. America David R. Robbins Prize, Jan 07, 2008.
- Sprott's Spots Award (Dec 05, 2007)
- The OEIS was mentioned on the TV program Numb3rs, May 05 2006.
- Vincenzo Origlio, L'Enciclopedia delle sequenze intere, Biblioteche Oggi, January-February 2006, pp. 41-45.
- Alonso Del Arte, Mathematician reaches 100k milestone of online integer archive, The South End (Wayne State University Newspaper), Nov 11, 2004 (Cached copy (black and white))
- Antii Karttunen, Tuhansien lukujonojen aarreaitta (Finnish) [A treasure-trove of thousands of integer sequences], Helsingin Sanomat, Science & Nature section, page D1, Tuesday, November 9 2004.
- Heather Catchpole, Exploring the number jungle online, Australian Broadsacting Commission (ABC) News in Science story about NJAS, Oct 05, 2004 (Cached copy)
- The OEIS was featured in Ivars Peterson's MathTrek in Science News Online for May 17, 2003.
- The Italian monthly magazine for software developers, Dev. has a piece about the OEIS in the Feb 2003 issue, No. 104, on page 72.
- Ivars Peterson, The EKG Sequence, MathTrek, Apr 08 2002.
- Cool Math Award (May 10, 2001)
- Heinrich Hemme, Die Leidenschaft eines Zahlenreihen-Sammlers (The Passion of a Collector of Number Sequences), Frankfurter Allgemeine Zeitung, May 9, 2001.
- Scout Report for Science and Engineering Selection (Jun 12, 2000)
- Science and Technology Key Resource (Mar 09, 2000)
- Featured by Slashdot on Feb 22, 2000.
- The Rail (May 20, 1998)
- One of Science magazine's Hot Picks for 15 May 1998.
- Dr Matrix Award(May 22, 1997)
- Knot a Braid of Links (Apr 29, 1997)
- Member of the Permutation (1997)
- Geek Site of the Day, (Oct. 9, 1996)
- Review by J. M. Borwein and R. M. Corless in SIAM Review (Vol. 38, 1996, pp. 333-337) of The Encyclopedia of Integer Sequences.
- American Scientist, Vol. 84, January-February 1996, A question of numbers, by Brian Hayes, pp. 10-14, talks about The Encyclopedia of Integer Sequences and the email sequence servers.
- Top 5% badge (1996)
- Sunday Star Ledger, June 18, 1995, "Count him in: Bell expert tracks trends in numbers", pp. 1, 18, by Kitta MacPherson.
- The email servers were written up in Newsweek's "Cyberscope" column on Jan. 9, 1995; in Science on July 22, 1994; and in several other places.
- Science, July 22, 1994, Mathematicians get an on-line fingerprint file, p. 473, by Barry Cipra.
- Montreal Gazette, Feb. 21, 1987 p. J7, Among sequence buffs, this man's No 1: (Neil Sloane).
- New York Times, Tuesday, January 27, 1987, front page of Science Tuesday section, "In a `random world', he collects patterns", by James Gleick. (The picture shows an extract from the first page, with the error in the third example corrected in red.) Added Dec 16 2009: The full text of the article (but not the illustrations) can now be seen on the New York Times web site.
- Scientific American, April, 1974, Review of ``A Handbook of Integer Sequences, pp. 125-126, by Philip Morrison.
Thumbnails
- Award coolmath.gif
May 10, 2001
- Se-scoutsel.gif
Jun 12, 2000
- Key.gif
May 09, 2000
- Railicon.gif
May 15, 1998
- Dm160120.gif
May 22, 1997
- Linkcandy.gif
Apr 29, 1997
- Permu.gif
1997
- Gsotd4.gif
Oct 09, 1996
Copyright Notice
This database and its associated files are copyright 2010 by The OEIS Foundation Inc.. Copyright 2010 - Cette base de données et les fichiers qui lui sont associés sont la propriété de The OEIS Foundation Inc..