This site is supported by donations to The OEIS Foundation.

User:Olivier Gérard/Welcome fr

From OeisWiki
Jump to: navigation, search

Bienvenue sur le site de l'OEIS™

Encyclopédie Electronique des Suites de Nombres Entiers

(On-Line Encyclopedia of Integer Sequences™)


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.

classic list graph listen

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

Crossrefs

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

Citations

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

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




Links to Other Sites

Awards, Press Clippings

  • 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

  • Dec 05, 2007

  • 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

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

Retrieved from "https://oeis.org/w/index.php?title=User:Olivier_Gérard/Welcome_fr&oldid=1574186"