Look-and-say sequence(見て言って数列)
更新
この記事では,以下のような数列について考えます。
1, 11, 21, 1211, 111221, 312211,
おもしろい性質と規則性を持った数列です。
Look-and-say sequence
Look-and-say sequence
さきほどの数列は,以下のような規則性があります。
初項は1
1 は 1 個の 1
なので,第2項は 11
11 は 2 個の 1
なので,第3項は 21
21 は 1 個の 2 と 1 個の 1
なので,第4項は 1211
1211 は 1 個の 1 と 1 個の 2 と 2 個の 1
なので,第5項は 111221
このように,前の項の個数と数字を順番に読んで次の項を作った数列のことを Look-and-say sequence と言います。強引に日本語訳すると「見て言って数列」でしょうか。
Look-and-say sequence の性質
Look-and-say sequence の性質
以下では,初項が である Look-and-say sequence の性質を見ていきます。
各項の各桁は のいずれかである。
第2項以降は,左から奇数桁目が「数字の個数」を表し,偶数桁目は「前の数字に現れる数字」を表す。
0 が現れないことの証明:
奇数桁目は「数字の個数」を表すので 0 は現れない。また,偶数桁目は「前の数字に現れる数字」を表すので,0 が現れたとすると,1つ前の項にも 0 が現れる。これを繰り返すと,さかのぼって にも 0 が現れる必要があるが,そうではないので 0 は現れない。
4 から 9 が現れないことの証明:
の奇数桁目に4以上の数字が現れたと仮定する。すると, には同じ数字が4つ以上連続することになる。しかし, 偶数桁目に同じ数字が連続することは無い(注)ので,4つ以上連続になることは無い。よって の奇数桁に 4 は現れない。
さらに「0が現れないことの証明」と同じ理由により,偶数桁目に4以上の数字が現れないことも分かる。
注: のように偶数桁目に同じ数字 が連続することはありません。 個の と 個の は,まとめて 個の と言うべきだからです。
桁数は単調非減少。つまり, の桁数を とすると,
はすぐ確認できる。
2項目以降は, は偶数である。そして,さきほどの性質:
偶数桁目に同じ数字が連続することは無い
より, には 個以上の「 個の というブロック」が存在する。よって,1個のブロックに次の項の2桁が対応するので,
は 以上である。
つまり,
桁数は無限大に発散する。つまり,
性質1や性質2の証明よりは少しだけ難しいですが,頑張ればできます。考えてみてください!
ちなみに,初項が 1 ではなく 22 である Look-and-say sequence はいつまでも 22 を繰り返します。
ただし, は定数で,およそ
つまり,十分大きな を持ってくると というわけです。
性質4は,性質3よりも強いです。
英語では「two 1s」ですが,日本語では「2個の1」と言うよりも「1が2個」と言いたくなる気もします。