Look and Say Sequenceについて - コロナなんて大嫌いだ -

# はじめに

たまに子供たちに算数・数学の話をする機会があるのだが、数列の話をする時は必ず話すくらい好きな数列である、Look and Say Sequence(見て言って数列)について簡単にまとめていきたいと思う。

この数列の性質の中でジョン・ホートン・コンウェイ(John Horton Conway)氏によって明らかにされた性質があるのだが、コンウェイ氏は昨年、コロナウイルスで亡くなられた。
コンウェイ氏といえば、生態系シミュレーションプログラム「ライフゲーム」を生み出したことで有名な数学者。こうやって偉大な、科学・技術における偉大な方をコロナで失ったこと、大変悲しい。

3月21日をもって、コロナウイルスによる2ヶ月半にわたる緊急事態宣言解除となったわけだが、このあとはどうなっていくのだろうか。
リモート勤務が続き、ちょっとまいってきたところですが、勉強頑張っていかなければ・・・


# Look and Say Sequence とは


```math
1, 11, 21, 1211, 111221, 312211, 13112221,・・・
```
このような数列のことをLook and Say Sequence(見て言って数列)という。

この数列は、前項を見て(look)言って(say)できることによって次の数字が決まるというもの。

```math

\begin{align}
1&・・・初項 \\
11&・・・前項が 1つの1 \\
21&・・・前項が 2つの1 \\
1211&・・・前項が 1つの2と1つの1 \\ 
111221&・・・前項が 1つの1と1つの2と2つの1 \\   
\end{align}

```

初項が5の場合は以下の通り。(コンウェイ氏の論文の導入では、55555で始まってたりする)

```math
55555, 55, 25, 1215, 11121115,・・・
```

初項が22の場合は、ずっと変わらない。以下の通り。

```math
22,22,22・・・
```


ちなみに小学生・中学生には毎回、以下の形で問題を出す。

```math
1, 11, 21, 1211, 111221, ?
```

ざっくり、50人に2,3人が正解を出してくるのですが、1人は、数分・数十分でわかり、1人は1週間毎日考え続け、正解を導いていた。子どもって恐ろしい。(勉強頑張らなきゃ・・・)

ちなみにgoogleの入社試験で出たとかなんとか。



# pythonで書いてみる

```python

def cal(x):
    r = []
    l = [1, x[0]] 
    for n in (x + "x")[1:]:
        if n is l[1]:
            l[0] += 1
        else:
            r.extend(l)
            l = [1, n]
    return "".join(map(str,r))

def look_and_say(a1, n):
    s = str(a1)
    r = [str(a1)]
    for i in range(n-1):
        s = cal(s)
        r.append(s)
    return r
```

実行してみる

```python
n = 10
print(look_and_say(1, n))
```

```
// 実行結果
['1', '11', '21', '1211', '111221', '312211', '13112221', '1113213211', '31131211131221', '13211311123113112211']
```

# Look and Say Sequenceの性質

「数列に、1,2,3以外の数字は出てこない」
「桁数は単調非減少」
「桁数は無限大に発散」
等あるのですが、

一番面白いのは、

```math
\lim_{n \to ∞} \frac{l_{n+1}}{l_n} =λ \\

λ = 1.303577・・・(コンウェイの定数)
```

なんでこんなことになるのか、とても不思議。


## コンウェイの定数とは

```math

\begin{align}
x ^ {71} &&&&-x ^ {69} &&-2x ^ {68} &&-x ^ {67} && + 2x ^ {66} && + 2x ^ {65} && + x ^ {64} &&-x ^ {63}\\
-x ^ {62} &&-x ^ {61} &&-x ^ {60} &&-x ^ {59} && + 2x ^ {58} && + 5x ^ {57} && + 3x ^ {56} &&-2x ^ {55} &&-10x ^ {54} \\
-3x ^ {53} &&-2x ^ {52} && + 6x ^ {51} && + 6x ^ {50} && + x ^ {49} && + 9x ^ {48} &&-3x ^ {47} &&-7x ^ {46} &&-8x ^ {45} \\
-8x ^ {44} && + 10x ^ {43} && + 6x ^ {42} && + 8x ^ {41} &&-5x ^ {40} &&-12x ^ {39} && + 7x ^ {38} &&-7x ^ {37} && + 7x ^ {36} \\
+ x ^ {35} &&-3x ^ {34} && + 10x ^ {33} && + x ^ {32} &&-6x ^ {31} &&-2x ^ {30} &&-10x ^ {29} &&- 3x ^ {28} && + 2x ^ {27} \\
+ 9x ^ {26} &&-3x ^ {25} && + 14x ^ {24} &&-8x ^ {23} &&&&-7x ^ {21} && + 9x ^ {20} && + 3x ^ {19} &&-4x ^ {18} \\
-10x ^ {17} &&-7x ^ {16} && + 12x ^ {15} && + 7x ^ {14} && + 2x ^ {13} &&-12x ^ {12} &&-4x ^ {11} &&-2x ^ {10} && + 5x ^ {9} \\ 
&& + x ^ {7} &&-7x ^ {6 } && + 7x ^ {5} &&-4x ^ {4} && + 12x ^ {3} &&-6x ^ {2} && + 3x &&-6 
\end{align}

```

の実根のうち最大のもの。



## matplotlibで図示してみる

コードは以下の通り。

```python
import matplotlib.pyplot as plt

#
# <省略>
#

n = 20
x = list(range(1, n + 1))
list = [1 ,13, 23, 312, 55555]
for a1 in list:
    s = look_and_say(a1, n)
    plt.plot(x, [len(d) for d in s], label=f'a1={a1}')

plt.yscale('log')
plt.legend()
plt.show()

```

![スクリーンショット 2021-03-22 3.10.12.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/87188/3ef47ae3-2f54-928f-2a6a-2ee0e346d71c.png)

うーん。綺麗。

50項目までやってみると、割と1.303に近づいてくる。驚き。

||$\frac{l_{20}}{l_{19}}$|$\frac{l_{30}}{l_{29}}$|$\frac{l_{40}}{l_{39}}$|$\frac{l_{50}}{l_{49}}$|
|----| ---- | ---- | ---- | ---- |
|a1=1 | 1.337| 1.309| 1.304| 1.303|
|a1=13| 1.313| 1.314| 1.305| 1.303|
|a1=23| 1.226| 1.299| 1.305| 1.304|
|a1=312| 1.244| 1.313| 1.309| 1.304|
|a1=55555| 1.334| 1.316| 1.305| 1.303|