Look-and-say sequence

『カッコウはコンピュータに卵を産む』を僕が初めて読んだのは、おそらく大学の3年か4年のときだったと思う。当時はヘコタれていた話にも、今の自分は結構食いついていけるので、この本に出てくる話でも、たとえば GNU Emacs のセキュリティホールと出てくると、あー movemail の話だよね、だからここでメール云々と出てくるのは rmail のことを言ってるのか、位は何とかなるわけだけど、下巻の pp.170 で、クリフォード・ストールが、Bell Labsとあの悪名高いNSAで活躍した暗号学者であるRobert "Bob" H. Morris(1988年にインターネットを壊滅状態にしたことで有名なMorris wormの作者Robert Tappan Morrisの父親である)にクイズとして出題された級数、というのが、哀しいかな、完全自力では解けなかった。

そんなふうにして、ひとしきりなぞなぞや回文で遊んだ。これはどうだ、とボブは一連の数字を書き並べた。

1, 11, 21, 1211, 111221。

「この級数をつづけてごらん、クリフ」

私は五分間黒板をにらんで降参した。きっと簡単なことだろうとは思うけれど、今にいたるまで私はこれが解けぬままである。

これは想像なのだけど、おそらくクリフはこの問題の答を知っていると思う。彼の身近にいる物理学者だったら、一人位はこの級数を知っているだろう、と思うからだ……この級数は、標記の通り、"Look-and-say sequence" と呼ばれる。日本語で言うならば、さしづめ、「『見て言って』級数」とでもすればいいのだろうか。この級数を自力で解きたい方は、この次の行からはお読みになられないように。

さて、この級数だけど、その名の通り、項を「見て言って」次の項が決まる、というものである。この場合、a1 = 1とまず定義する。そして、次の項a2を決めるためにa1を見返す。a1は「1個1がある」→a2 = 11と定まる。次の項a3を決めるためにa2を見返すと、a2は「2個1がある」→a3 = 21と定まる。次の項a4を決めるためにa3を見返すと、a3は「1個2があり、1個1がある」→a4 = 1211……という風に、以下、111221、312211、13112221、1113213211……と決まっていくのである。以下、Fortran で(すみませんね古い奴で)a10まで計算した結果を参考までに載せておこう。

  1. 1
  2. 11
  3. 21
  4. 1211
  5. 111221
  6. 312211
  7. 13112221
  8. 1113213211
  9. 31131211131221
  10. 13211311123113112211

この級数には、いくつか面白い性質があることが知られている。たとえば、これらの項を見て何となく予想できると思うけれど、この級数の各項は 1, 2, 3 だけで構成されている(つまり、同じ数字が4つ以上連なることがない)ようだ。また、上で最初に定義したa1を色々変えることを考えると、a1 = 22an = 22 for all nNとなるのはお分かりだろうと思う。他にはどんな性質があるのだろうか。

実は、この級数には、あのライフゲームを考案したイギリスの数学者ジョン・ホートン・コンウェイ John Horton Conway によって、更に不思議な性質があることが明らかになっている。上に示したように、この「『見て言って』級数」は、項数nが増えるとすぐに巨大な桁数になるのだけど、よーく見ると、項が長くなるに連れ、その項がいくつかの要素……各々の要素を別々に「見て言って」操作をしてからくっつけても、くっついた状態で「見て言って」操作をしても、結果が変わらないような要素……に分割できることが分かる。コンウェイは、その要素が合計92個であることを示した。この92という数は、水素からウランまでの原子番号に等しいので、分割できない要素を原子になぞらえて(ギリシャ語の ἄτομος は「分割できない」という意味である)、上述の「見て言って」操作を分類している。たとえば22 は最も安定な水素、3 はウラン……という具合である。

ちなみに、この話に関しては、日本語で書かれた明解な document がまだない状態、のようだ。暇なときにでも、英語の文献をちょこちょこ読んでおこうと思う。

2010/04/17(Sat) 23:02:49 | コンピュータ&インターネット
Tittle: Name:

Profile

T.T.Ueda
Tamotsu Thomas UEDA

茨城県水戸市生まれ。

横山大観がかつて学んだ小学校から、旧水戸城址にある中学、高校と進学。この頃から音楽を趣味とするようになる。大学は、学部→修士→博士の各課程に在籍し、某省傘下の研究所に就職、その2ヵ月後に学位を授与される(こういう経緯ですが最終学歴は博士課程「修了」です)。職場の隣の小学校で起こった惨劇は未だに心に深く傷を残している。

その後某自動車関連会社の研究法人で国の研究プロジェクトに参画、プロジェクト終了後は数年の彷徨を経て、某所で教育関連業務に従事。

New Entries

Comment

Categories

Archives(896)

Link

Search

Free

e-mail address:
e-mail address