3

In his paper John Conway has put forward some theorems describing the behaviour of the look-and-say sequence. The very first theorem, the One-Day Theorem, states that no one-day-old string contains substrings of the following types:

$•$ $yxzx$

$•$ $x^k$ $with$ $k ≥ 4$

$•$ $x^3y^3$

How to prove this theorem for the last two cases? The proof for the first case is that the sequence may be represented as $x^yx^z$, which simplifies into $x^{(y+z)}$, and as the superscript must always be the largest possible it is not allowed to divide it into more powers, i.e. $y$ and $z$. The other two are said to be special cases of the first one, but, frankly, I don't see how they are.

One-day old strings are the first iterations of the seeds in the look-and-say sequences, so if the seed is 2 then the one-day old string is 12. Look up this PDF for further clarifications (page 1-2).

Daphne
  • 383
  • 2
    What is a one-day-old string? – lulu Dec 10 '16 at 22:12
  • @lulu As edited. – Daphne Dec 10 '16 at 22:17
  • So if I start with a string of $111$ $1's$, why isn't the one day sequence $1111$? – lulu Dec 10 '16 at 22:20
  • If you start with with $111$ $1's$, this simplifies into $1^{111}$, and the one day old string of that is $1111$. I just got a little confused because you seem to have found a counter example to the second case. – Daphne Dec 10 '16 at 22:33
  • Also, if my seed is $15533$ isn't the one day string $112523$ which contains the substring $1252$ contrary to your first claim? – lulu Dec 10 '16 at 22:36
  • Assume the seed to be a string of $1111$ $1's$, then this can be represented as $1^{1111}$, and the one day old string of that is $11111$, which is $1^{5}$, and $5 =>4$. Does that violate the first case? – Daphne Dec 10 '16 at 22:37
  • @Daphne Also, I claim I have a direct counterexample to your first case, namely the seed $15533$ which yields $112523$ containing $1252$ as a substring. – lulu Dec 10 '16 at 22:38
  • Yes, thank you, I'm aware, let me delve into it for a moment. – Daphne Dec 10 '16 at 22:39
  • There has to be a parity issue for the first case....maybe for the later ones? – lulu Dec 10 '16 at 22:39
  • @Daphne: Isn’t the $yxzx$ restriction limited to $yxzx$ starting at an odd position? See p. $2$ of the PDF. – Brian M. Scott Dec 10 '16 at 22:39
  • Yes, it is, forgot to include it. – Daphne Dec 10 '16 at 22:40
  • @BrianM.Scott That makes sense! The others also? Ok, I'll go look at the article. – lulu Dec 10 '16 at 22:40
  • @lulu: The others are as stated in the question. The author says: About the first of these three types of substrings, note that if $yxzx$ begins in an odd position, then it describes the string $x^yx^z$, which should instead be written as $x^{y+z}$. The two other types of substrings, whether they begin in an odd or an even position, are special cases of the first type. – Brian M. Scott Dec 10 '16 at 22:40
  • @BrianM.Scott Ok, and why isn't my long string of $1's$ a counterexample? – lulu Dec 10 '16 at 22:41
  • @lulu: From the PDF: ‘Technically, we must assume a base as large as needed for our numeral system.’ In other words, it’s $(1111)1$, a two-element string. – Brian M. Scott Dec 10 '16 at 22:45
  • @BrianM.Scott Ah, you've lost me. So there are a priori limits on the nature of what a "seed" can be? Well, obviously a topic I don't know and shouldn't comment on. Looks like it might be fun, maybe I'll read about it. Thanks for trying to explain. – lulu Dec 10 '16 at 22:47
  • 2
    @lulu: There’s no limit on what a seed can be: you just have to understand that the count part of a pair is always to be thought of as a single digit, so we always assume that we’re writing in a base large enough to make that true. If $d$ is a name for the digit representing the (decimal) number $1111$, your look-say sequence on day $1$ is $d1$. This produces $1d11$ on day $2$, then $111d21$, and so on. – Brian M. Scott Dec 10 '16 at 22:49
  • @BrianM.Scott Ah, that's simple. Is it clear that the "base" so defined never needs to be expanded? Alternatively, as my sequence grows, is it possible that my "base" grows to infinity? – lulu Dec 10 '16 at 22:57
  • 2
    @lulu: I honestly don’t know. I’ve not actually had time to think about this at all, beyond finding the PDF and taking a quick look. I’m hoping to do so tonight. – Brian M. Scott Dec 10 '16 at 22:58
  • 3
    @BrianM.Scott And that's what I'll do as well. That's for taking the time to explain. – lulu Dec 10 '16 at 22:59

2 Answers2

1

There are always exactly two ways to produce any sequence in look and say numbers. Either our sequence starts from a power or it starts from a value.

For example the sequence $x$ can only happen if day before we see: $a^x$ or $x^a$, where $a$ is any arbitrary value. In the first example $x$ starts from the power, and in the second one it starts from the value. $$x^k, k \ge 4$$ First it should be noted that for any value $k \ge 4$ the sequence will always be a super sequence of $x^4$. Thus if we can show that $x^k$ can not exist when $k=4$ then that must be true for all values of $k>4$ as well.

Next lets look at if this value came from a power starting sequence, then the day before we would see $x^xx^x$. We can rewrite this sequence as $x^{2x}$ and that generates an $ax$, where $a=2x$ on the next day. Thus the sequence could not be generated starting from a power.

Lastly lets look at if this value came from a value starting sequence, then the day before we would see $x^ax^xb^x$, where $a$ and $b$ are arbitrary values. This can be rewritten as $x^{a+x}b^x$. This sequence would generate $cxxb$, where $c=a+x$. Thus it is impossible to generate $x^4$ from a value starting sequence, and by extension it is impossible to generate $x^k$, where $k\ge4$ in any circumstance.

What if $c=x$ and $b=x$ in our sequence $cxxb$?

Well that would be impossible because $c=x+a$ implies $a=0$ and we can not have $x^0$ as that would be read as nothing. We alternatively can show that if $b=x$, then on the day before we would have had $x^ax^xx^x$, which is rewritten as $x^ax^{2x}$, and that generates $axdx$, where $d=2x$.

$$x^3y^3$$

Our value starting sequence we get $x^ax^xy^yb^y$, where $a$ and $b$ are arbitrary values. This can be rewritten as $x^{a+x}y^yb^y$. This then generates the sequence $cxyyyb$, where $c=a+x$. Thus it can not be from a value starting sequence.

The day before, if this is from a power starting sequence we get $x^xy^xy^y$, which is rewritten as $x^xy^{x+y}$. This sequence would produce $xxcx$, where $c=x+y$. This shows that $x^3y^3$ is completely impossible.

Benji Altman
  • 1,237
1

As pointed out in the comments, the first should be no copies of $yxzx$ starting at an odd position. Crucially, $x,y,z$ do not have to be different here.

The other two are special cases. If we contain $a^4$ then either it starts at an odd position or an even position. If an odd position, we have $aaaa$ starting at an odd position so $x=y=z=a$. If an even position, then $a^4$ isn't at the start of the string, so we have $ba^4$ for some $b$. This contains $baaa$ starting at an odd position, here $x=z=a,y=b$.

If we contain $a^3b^3$ then either it starts at an odd position, giving $abbb$ starting odd (here $x=z=b,y=a$), or an even position, and looking at the previous position gives $caaa$ starting at odd for some $c$.

Especially Lime
  • 40,828