In mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, the look-and-say sequence is the sequence of integers

Integer sequence

In mathematics, an integer sequence is a sequence of integers.An integer sequence may be specified explicitly by giving a formula for its nth term, or implicitly by giving a relationship between its terms...

 beginning as follows:

1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, ... .

To generate a member of the sequence from the previous member, read off the digits of the previous member, counting the number of digits in groups of the same digit. For example:

• 1 is read off as "one 1" or 11.
• 11 is read off as "two 1s" or 21.
• 21 is read off as "one 2, then one 1" or 1211.
• 1211 is read off as "one 1, then one 2, then two 1s" or 111221.
• 111221 is read off as "three 1s, then two 2s, then one 1" or 312211.

The idea is similar to that of run-length encoding

Run-length encoding

Run-length encoding is a very simple form of data compression in which runs of data are stored as a single data value and count, rather than as the original run...

.

If we start with any digit d from 0 to 9, d will remain indefinitely as the last digit of the sequence. For d different from 1, the sequence starts as follows:

d, 1d, 111d, 311d, 13211d, 111312211d, 31131122211d, …

Ilan Vardi has called this sequence, starting with d = 3, the Conway sequence .

Basic properties

• The sequence grows indefinitely. In fact, any variant defined by starting with a different integer seed number will (eventually) also grow indefinitely, except for the degenerate
  Degeneracy (mathematics)
  In mathematics, a degenerate case is a limiting case in which a class of object changes its nature so as to belong to another, usually simpler, class....
  
   sequence: 22, 22, 22, 22, ….
• No digits other than 1, 2, and 3 appear in the sequence, unless the seed number contains such a digit or a run of more than three of the same digit.

• Conway's
  John Horton Conway
  John Horton Conway is a prolific mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory...
  
   cosmological theorem: Every sequence eventually splits into a sequence of "atomic elements", which are finite subsequences that never again interact with their neighbors. There are 92 elements containing the digits 1, 2, and 3 only, which John Conway named after the natural chemical element
  Chemical element
  A chemical element is a pure chemical substance consisting of one type of atom distinguished by its atomic number, which is the number of protons in its nucleus. Familiar examples of elements include carbon, oxygen, aluminum, iron, copper, gold, mercury, and lead.As of November 2011, 118 elements...
  
  s. There are also two "transuranic" elements for each digit other than 1,2, and 3.

• The terms eventually grow in length by about 30% per generation. If denotes the number of digits of the -th member of the sequence, then the limit
  Limit (mathematics)
  In mathematics, the concept of a "limit" is used to describe the value that a function or sequence "approaches" as the input or index approaches some value. The concept of limit allows mathematicians to define a new point from a Cauchy sequence of previously defined points within a complete metric...
  
  

where is an algebraic number

Algebraic number

In mathematics, an algebraic number is a number that is a root of a non-zero polynomial in one variable with rational coefficients. Numbers such as π that are not algebraic are said to be transcendental; almost all real numbers are transcendental...

 of degree 71 known as Conway's constant

Mathematical constant

A mathematical constant is a special number, usually a real number, that is "significantly interesting in some way". Constants arise in many different areas of mathematics, with constants such as and occurring in such diverse contexts as geometry, number theory and calculus.What it means for a...

. This fact was proven by Conway. This also holds for variants of the sequence starting with any integer other than 22.

Conway's constant is the unique positive real root of the following polynomial

Polynomial

In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...

:

Origin

It was introduced and analyzed by John Conway in his paper "The Weird and Wonderful Chemistry of Audioactive Decay" published in Eureka 46, 5–18 in 1986.

Popularization

It is also popularly known as the Morris Number Sequence, after cryptographer Robert Morris

Robert Morris (cryptographer)

Robert Morris , was an American cryptographer and computer scientist. -Family and Education:Morris was born in Boston, Massachusetts. His parents were Walter W. Morris, a salesman, and Helen Kelly Morris...

, and the puzzle is sometimes referred to as the Cuckoo's Egg from a description of Morris in Clifford Stoll

Clifford Stoll

*High-Tech Heretic: Reflections of a Computer Contrarian, Clifford Stoll, 2000, ISBN 0-385-48976-5.-External links:* at Berkeley's Open Computing Facility**, December 3, 1989* copy at Electronic Frontier Foundation, May 1988...

's book The Cuckoo's Egg.

Computer program

The following Python

Python (programming language)

Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...

 code generates a look-and-say sequence using lazy evaluation

Lazy evaluation

In programming language theory, lazy evaluation or call-by-need is an evaluation strategy which delays the evaluation of an expression until the value of this is actually required and which also avoids repeated evaluations...

:


def look_and_say(member):
while True:
yield member
breakpoints = [0]+[i for i in range(1,len(member)) if member[i-1] != member[i]]+[len(member)]
groups = [member[breakpoints[i-1]:breakpoints[i]] for i in range(1,len(breakpoints))]
member = .join(str(len(group)) + group[0] for group in groups)

1. Print the 10-element sequence beginning with "1"

sequence = look_and_say("1")
for i in range(10):
print sequence.next

Pea pattern

Pea pattern

A pea pattern is a mathematical pattern that, when following certain steps, will yield a string of patterned numbers.The first Pea pattern made goes as such:...

This is described as being the series which counts the number of occurrences of a digit and appears for the first few steps to have similarities with the Look-andSay(1) series. Pea(1) proceeds 1, 11, 21, 1112 (reading as 1 occurence of 1 and 1 of 2), 3112, 211213, but after 15 steps Pea(1) loops at 21322314. This looping characteristic also occurs with Pea(2) and Pea(0) at 1021223314.

External links

• Look and Say sequence generator
• Look and Say sequence - from 0 up to 70 (very large)
• A Derivation of Conway’s Degree-71 “Look-and-Say” Polynomial

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.