This site is supported by donations to The OEIS Foundation.

User:N. J. A. Sloane/Welcome

From OeisWiki
Jump to: navigation, search
This is a draft for a revised version of the Welcome Page for the OEIS. See here for the current version


Welcome to the On-Line Encyclopedia of Integer Sequences

| |- bgcolor="#76767F" | |- bgcolor="#EEEEFF" | valign="top" |

A060843

Busy Beaver problem: maximal number of steps that an n-state Turing machine can make on an initially blank tape before eventually halting. +30
5

|- |

1, 6, 21, 107 (list; graph; listen)

|- | valign="top" |

OFFSET

1,2

COMMENT

"In 1965 [Tibor] Rado, together with Shen Lin, proved that BB(3) is 21. ... Next, in 1983, Allan Brady proved that BB(4) is 107. ... Then, in 1989, Heiner Marxen and Juergen Buntrock discovered that BB(5) is at least 47,176,870. ... As for BB(6), Marxen and Buntrock set another record in 1997 by proving that it is at least 8,690,333,381,690,951." Aaronson. 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 S(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, pp. 259-277, Oxford Univ Press 1988. Brady, A. H. The determination of Rado's noncomputable function Sigma(k) for four-state Turing machines, Math. Comp. 40 #62 (1983) 647-665. 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. 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 E. W. Weisstein, Link to a section of The World of Mathematics. E. W. Weisstein, 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 (JudMcCranie@ugaalum.uga.edu) and njas, 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)

|- |

|}{| width="100%" bgcolor="#FFFFCC"

|- bgcolor="#7F7F66" | |- | align="right" | page 1 |- bgcolor="#7F7F66" | |}

    • Most people use this web site 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 [[<dont>|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 database to see the variety of topics that are covered. In a way this database 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.
    • You can run the [[<dont>|demonstration]] pages to see more examples of how to use the On-Line Encyclopedia of Integer Sequences.
    • 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 [[<dont>|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 number sequences arranged in lexicographic order. The entry for each sequence gives:
    • the beginning of the sequence
    • its name or description
    • any references or links
    • any formulae
    • cross-references to other sequences
    • the name of the person who submitted it, etc. For further information about the format of replies received from the database, [[<dont>|click here]]. A second file describes the [[<dont>|internal format]] in which the sequences are stored in the database. See also the hints file for further useful information.
  • Sources: Since the mid-1960's Neil Sloane has been collecting integer sequences from every possible source. His goal is to have all interesting number sequences in the table. At the present time the table contains over 150000 sequences. 5487 of the best of these sequences were published in 1995 in The Encyclopedia of Integer Sequences, by Neil Sloane and Simon Plouffe. The book is still useful, since it contains many of the most important sequences. The database (which would now fill 750 volumes the size of the 1995 book) is too huge to use except as a reference.
  • Editorial Board: Beginning in 2002, a group of associate editors has been helping to process new sequences and updates to the database. At present the associate editors are:
    • Franklin T. Adams-Watters (franktaw(AT)netscape.net)
    • Max Alekseyev (maxale(AT)gmail.com)
    • Jean-Paul Allouche (Jean-Paul.Allouche(AT)lri.fr)
    • David Applegate (david(AT)research.att.com)
    • Joerg Arndt (arndt(AT)jjj.de)
    • Christian G. Bower (bowerc(AT)usa.net)
    • David Broadhurst (D.Broadhurst(AT)open.ac.uk)
    • Klaus Brockhaus (klaus-brockhaus(AT)t-online.de)
    • Ray Chandler (RayChandler(AT)alumni.tcu.edu)
    • Russ Cox (rsc(AT)swtch.com)
    • Emeric Deutsch (deutsch(AT)duke.poly.edu)
    • Farideh Firoozbakht (mymontain(AT)yahoo.com)
    • Georg Fischer (Georg.Fischer(AT)t-online.de)
    • Martin Fuller (martin_n_fuller(AT)btinternet.com)
    • Charles R. Greathouse IV
    • Richard K. Guy (rkg(AT)cpsc.ucalgary.ca)
    • Paul D. Hanna (pauldhanna(AT)juno.com)
    • Maximilian Hasler (maximilian.hasler(AT)gmail.com)
    • Alois Heinz (heinz(AT)hs-heilbronn.de)
    • Vladeta Jovovic (vladeta(AT)eunet.yu)
    • Antti Karttunen
    • Michael Kleber (michael.kleber(AT)gmail.com)
    • John W. Layman (layman(AT)math.vt.edu)
    • Marc LeBrun (mlb(AT)well.com)
    • R. J. Mathar (mathar(AT)mpia.de)
    • Jud McCranie (JudMcCranie@ugaalum.uga.edu)
    • Wouter Meeussen (wouter.meeussen(AT)pandora.be)
    • Joseph S. Myers (jsm(AT)polyomino.org.uk)
    • Tony Noe (noe(AT)sspectra.com)
    • Simon Plouffe (simon.plouffe(AT)gmail.com)
    • Paul Raff (praff(AT)math.rutgers.edu)
    • Don Reble (djr(AT)nk.ca)
    • Giovanni Resta (g.resta(AT)iit.cnr.it)
    • Zak Seidov (zakseidov(AT)yahoo.com)
    • Neil J. A. Sloane (njasloane@gmail.com), editor-in-chief
    • Harry J. Smith (hjsmithh(AT)sbcglobal.net)
    • Michael Somos (somos(AT)grail.cba.csuohio.edu)
    • Stefan Steinerberger (stefan.steinerberger(AT)gmail.com)
    • Ralf Stephan (ralf(AT)ark.in-berlin.de)
    • David Wasserman (dwasserm(AT)earthlink.net)
    • David W. Wilson (davidwwilson(AT)comcast.net)
    • Joshua Zucker (joshua.zucker(AT)gmail.com)Many other volunteers help by sending corrections, comments, links or even completely editing an entry.
  • Arrangement of Sequences in Database. Most of the sequences are arranged in the database 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 [[<dont>|Sending in a new sequence]].) Sequences received in the last few days and not yet placed in the lexicographic ordering will be found at the end of the table.
  • [[<dont>|Format used in replies from the database]]. [[<dont>|Internal format used in the database]].
  • Short 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.
  • The Recent Additions file. (Note that you can also browse these using the WebCam.)
  • 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)
  • [[<dont>|Contributing a new sequence]] (or a comment on an existing sequence, or more terms for an existing sequence). Want to help? Set the WebCam to browse the sequences that need extending,
    or use the main look-up page to search for keyword:more.
    See also the future projects web page.
    Other related pages: [[<dont>|Demos]], Transformations of sequences, Maple or Mathematica (see EISFormat.m) scripts to format sequences.
  • OEIS Search Bar. To add OEIS search to the search bar in Firefox (1.5 or later), Internet Explorer (7 or later), or Mozilla Seamonkey (and perhaps Camino) [[<dont>|click here]].
    To add OEIS search to the search bar in Opera (9 or later), go to the main lookup page, right click in the text box, and select "Create search...". You can also add the OEIS to the search bar using Tools -> Preferences -> Search.
    It may be possible to add OEIS search to Safary by using the Saft plugin.
    There are also OpenSearch and Sherlock OEIS search plugins available at mycroft.mozdev.org
    (Thanks to several sequence fans who set up these plugins.)
  • Sequences in Classic Books. Comtet's Advanced Combinatorics, Flajolet and Sedgewick's Analytic Combinatorics, Graham, Knuth and Patashnik's Concrete Mathematics, Harary and Palmer's Graphical Enumeration, Stanley's Enumerative Combinatorics.
  • 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:
    N. J. A. Sloane, (2008), The On-Line Encyclopedia of Integer Sequences,
    www.research.att.com/~njas/sequences/.
    Or, since that often causes spacing problems with LaTeX (the line is too long and is hard to break):
    N. J. A. Sloane, (2008), The On-Line Encyclopedia of Integer Sequences,
    published electronically at www.research.att.com/~njas/sequences/. Another possibility is to say something like:
    N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences.
    World-Wide Web URL www.research.att.com/~njas/sequences/.
  • URLs
    The URL for the main lookup page is
    http://www.research.att.com/~njas/sequences/
    (or http://www.research.att.com/%7enjas/sequences/
    if your keyboard lacks the tilde character). The URL for this page is
    http://www.research.att.com/~njas/sequences/Seis.html
    (or http://www.research.att.com/%7enjas/sequences/Seis.html
    if your keyboard lacks the tilde character).
  • 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 database. The URL for sequence A000108 (for example) is
    http://www.research.att.com/~njas/sequences/A000108
    A text reference might say: N. J. A. Sloane, Ed. (2008), The On-Line Encyclopedia of Integer Sequences,
    published electronically at www.research.att.com/~njas/sequences/, Sequence A000108or, if it is clear who "discovered" the sequence, something likeJ. H. Conway, Sequence A007970 in N. J. A. Sloane (Ed.), The On-Line Encyclopedia of Integer Sequences (2008), published electronically at http://www.research.att.com/~njas/sequences/A007970.In an HTML file one might say something like this:... where the C(n) are the Catalan numbers
    (<a href="http://www.research.att.com/~njas/sequences/A000108">Sequence A000108</a> in [OEIS]).One can also create active links in PDF or POSTSCRIPT files. From LATEX for example one can use the HYPERREF package. In that case one would say:... where the C(n) are the Catalan numbers (sequence \htmladdnormallink{A000108} {http://www.research.att.com/A000108} in \cite{OEIS}).For an example of a LATEX file which produces active links in this way, see "My Favorite Integer Sequences" in three versions: LATEX, PDF and POSTSCRIPT. [That LATEX file uses the old style of links to the OEIS, and needs to be changed.]
  • URL for Searching the Database
    To bypass the web page and search for a sequence directly using the cgi program, for instance the sequence 2,5,14,50,233,
    use (with no line break and no internal spaces): 
    http://www.research.att.com/~njas/sequences/index.html?q=2,5,14,50,233

To put a window on your own page to do lookups, use the following html commands: 

    To look up a number sequence in the
    <a href="http://www.research.att.com/~njas/sequences/">
    On-Line Encyclopedia of Integer Sequences</a>,
    enter it here and click "Submit":
    <form
    action="http://www.research.att.com/~njas/sequences/"
    method=get>
    <input type=text name=q SIZE=60 VALUE=
    "1,2,3,6,11,23,47,106,235">
    <input type=submit VALUE="Submit">
    </form>

To bypass the web page and search for a word or phrase directly using the cgi program, for instance the phrase "number of factors",
use (with no line break and no internal spaces): 

    http://www.research.att.com/~njas/sequences/index.html?q="number of factors"
  • 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.
  • Policy on Email Addresses in the OEIS
    If possible I prefer to give the author's name and email address with each sequence, so that people can get in touch with each other. This is an important feature of the database. Email addresses are disguised by replacing @ by (AT).Let me know if you don't want your email address to appear in any form. However, if you ask to have your email address removed, try to give me a link to your home page - send me a line that looks like this:%H A077001 John Smith, <a href="http://members.aol.org/~JSmth/">Home Page</a> (listed in lieu of email address)that I can add to each sequence.Again, when sending in a sequence or comment using the [[<dont>|Contribute new seq. or comment]] web page, if you don't want your email address to be used, say so in one of the windows, and if possible put the URL of your home page into one of the "links" windows.
  • Copyright Notice. This database and its associated files are copyright 1996-2009 by N. J. A. Sloane.
  • Acknowledgments. A very large number of people have contributed to the table, and it is impossible to thank them individually. Their names can be seen in the "Author" and "Extension" lines of the entries. The following are some of the people who have made major contributions in recent years. Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Asher Natan Auel (auela(AT)reed.edu), Lekraj Beedassy (beedassylekraj(AT)hotmail.com), Mira Bernstein (mira(AT)math.Stanford.edu). Henry Bottomley, Christian Bower (bowerc(AT)usa.net), Benoit Cloitre (abcloitre(AT)wanadoo.fr), John Conway (conway(AT)math.princeton.edu), Patrick De Geest, Patrick Demichel, Frank Ellermann, Steven Finch, Erich Friedman, Olivier Gérard, Richard K. Guy (rkg(AT)cpsc.ucalgary.ca), Vladeta Jovovic (vladeta(AT)Eunet.yu), Clark Kimberling, Elemer Labos (labos(AT)ana1.sote.hu), Wolfdieter Lang, Amarnath Murthy (amarnath_murthy(AT)yahoo.com), T. D. Noe (noe(AT)sspectra.com), who has provided extended version ("b-files") for nearly 3000 sequences, Simon Plouffe, Larry Reeves (larryr(AT)acm.org), Francisco de Salinas, James Sellers, Jeffrey Shallit, Michael Somos, Ralf Stephan (ralf(AT)ark.in-berlin.de), Eric Weisstein, Barry E. Williams, David W. Wilson (davidwwilson(AT)attbi.com), Robert G. Wilson V (rgwv(AT)rgwv.com) and Reinhard Zumkeller (reinhard.zumkeller(AT)lhsystems.com). 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":
    • A007318 (Pascal's triangle),
    • A008277 (triangle of Stirling numbers of second kind),
    • A011971 (Aitken's array),
    • A026300 (Motzkin's triangle),
    • A034851 (Losanitsch's triangle). 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. The first versions of the new programs were written by Alex Healy and the final versions by Russ Cox. My colleague David Applegate then helped install them on our new server. The new searches are much faster than the old ones and can handle much more complicated queries. See the hints file for details.
  • Links.
  • Awards, etc. NJAS's 2003 article about the OEIS received the Math. Assoc. America David R. Robbins Prize, Jan 07, 2008. The OEIS was mentioned on the TV program Numb3rs, May 05 2006. Featured in Science News Online, May 17, 2003. Written up in the Frankfurter Allgemeine Zeitung on May 9, 2001, and by Slashdot on Feb 22, 2000. One of Science magazine's Hot Picks for 15 May 1998. 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. Also:
    {|

| align="center" | Sprott's Spots Award
(Dec 05, 2007) | align="center" | Cool Math Award
(May 10, 2001) |

Key Resource
(Mar 09, 2000)

|- |

Scout Report for Science and Engineering Selection
(Jun 12, 2000)

| The Rail
(May 15, 1998) |

Knot a Braid of Links Logo
(Apr 29, 1997)

|

Member of the Permutation
(1997)
|}
{|

|

Dr Matrix Award Logo
(May 22, 1997)

|

Geek Site of the Day badge
(Oct. 9, 1996)

|

Top 5% badge
(1995)
|}
Retrieved from "https://oeis.org/w/index.php?title=User:N._J._A._Sloane/Welcome&oldid=1574187"