はじめに
たまに子供たちに算数・数学の話をする機会があるのだが、数列の話をする時は必ず話すくらい好きな数列である、Look and Say Sequence(見て言って数列)について簡単にまとめていきたいと思う。
この数列の性質の中でジョン・ホートン・コンウェイ(John Horton Conway)氏によって明らかにされた性質があるのだが、コンウェイ氏は昨年、コロナウイルスで亡くなられた。
コンウェイ氏といえば、生態系シミュレーションプログラム「ライフゲーム」を生み出したことで有名な数学者。こうやって偉大な、科学・技術における偉大な方をコロナで失ったこと、大変悲しい。
3月21日をもって、コロナウイルスによる2ヶ月半にわたる緊急事態宣言解除となったわけだが、このあとはどうなっていくのだろうか。
リモート勤務が続き、ちょっとまいってきたところですが、勉強頑張っていかなければ・・・
Look and Say Sequence とは
1, 11, 21, 1211, 111221, 312211, 13112221,・・・
このような数列のことをLook and Say Sequence(見て言って数列)という。
この数列は、前項を見て(look)言って(say)できることによって次の数字が決まるというもの。
\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で始まってたりする)
55555, 55, 25, 1215, 11121115,・・・
初項が22の場合は、ずっと変わらない。以下の通り。
22,22,22・・・
ちなみに小学生・中学生には毎回、以下の形で問題を出す。
1, 11, 21, 1211, 111221, ?
ざっくり、50人に2,3人が正解を出してくるのですが、1人は、数分・数十分でわかり、1人は1週間毎日考え続け、正解を導いていた。子どもって恐ろしい。(勉強頑張らなきゃ・・・)
ちなみにgoogleの入社試験で出たとかなんとか。
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
実行してみる
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以外の数字は出てこない」
「桁数は単調非減少」
「桁数は無限大に発散」
等あるのですが、
一番面白いのは、
\lim_{n \to ∞} \frac{l_{n+1}}{l_n} =λ \\
λ = 1.303577・・・(コンウェイの定数)
なんでこんなことになるのか、とても不思議。
コンウェイの定数とは
\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で図示してみる
コードは以下の通り。
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()
うーん。綺麗。
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 |