## Brainteaser 1547: Doing the rounds

**From The Sunday Times, 3rd May 1992** [link]

This week, I share a find-the-next-row puzzle that is doing the rounds of dons’ whiteboards:

1

1 1

2 1

1 2 1 1

?To avoid invasion of ivory towers, I will give you the answer:

1 1 1 2 2 1

with the explanation that, starting with the initial 1, each subsequent row is obtained by

readingthe previous row. Thus, row five is formed (with reference to row four) from one “one”, followed by one “two”, and terminating with two “one”s.However, I do have four questions about the first billion rows of this sequence.

1. What is the largest digit that can be found anywhere?

2. What is the largest number of ones that can occur consecutively in any single row?

3. Repeat (2), looking for twos instead.

4. Repeat (2), looking for threes instead.Multiply each answer by its question number and send in the total.

This puzzle was selected for the book *Brainteasers* (2002, edited by Victor Bryant), in which it appeared in the following form:

Read me!Consider the sequence:

1

11

21

1211

111221

312211

…You might like to try and work out the next few terms before reading on and trying the rest of this Teaser.

In fact, having started with 1, each subsequent term simply

readsthe previous line. So, for example, after 111221 we note that this consists of:three ones, two twos, one one

i.e. the next term is simply:

312211

Here are some questions about the first billion terms of this sequence:

(a) What is the largest number of consecutive ones in any term?

(b) What is the largest number of consecutive twos in any term?

(c) What is the largest number of consecutive threes in any term?

(d) What is the largest digit which can be found in any term?

[teaser1547]

## Jim Randell 8:33 am

on18 April 2019 Permalink |This Python program generates the first few terms of the sequence. To do the first 12 terms takes 80ms.

Run:[ @repl.it ]Together with some analysis we can now answer the questions:

First we note that we can’t split runs of the same digit, so if we have (for example) five

d‘s,…ddddd…., they will appear in the next sequence as…(5d)…, and not as…(2d)(3d)…etc.So in any transformed sequence we cannot have two pairs appearing consecutively for the same digit, i.e.

…(xd)(yd)…would not appear, because it would be…({x+y}d)…So, we certainly cannot have a sequence of four consecutive digits

…(dd)(dd)…appearing in a transformed sequence.But neither can we have

…(xd)(dd)(dy)…appearing, as that also has two pairs appearing consecutively for the same digit.So we cannot have a run of more than three consecutive digits in any transformed sequence.

Which means in any transformed sequence we will not see a digit greater than 3.

Running the program we see that in the first 12 sequences we have three 1’s appearing in sequence 5:

and three 2’s appearing in sequence 7:

but we only manage two 3’s in sequence 11:

And in fact we can see that it is not possible to achieve three 3’s.

If we think about the first sequence in which

…333…appears, then the digits must be paired as…(33)(3x)…(as…(x3)(33)…is not possible), but then the(33)indicates that the sequence before this one must have had a run of three 3’s (followed by three of another digit). But this is a contradiction. So we cannot find a first sequence with three 3’s.So that answer to puzzle from the book is:

Solution:(a) 3; (b) 3; (c) 2; (d) 3.And solution for the original puzzle is: 1×3 + 2×3 + 3×3 + 4×2 = 26.

To consider the first 40 sequences take my program 5.5s, and the 40th sequence has 63,138 digits, so it is not suitable for attempting to examine the first billion terms.

The sequence is known as the “look and say” sequence [ link ].

LikeLike