Collatz (角谷) の予想と有酸素運動マン

Scheme

コラッツの問題という、数論上の未解決の問題があります。

任意の自然数について、偶数ならば 2 で割り、奇数なら 3 倍して 1 を加える、という操作を繰り返すと 1 に収束する (無限大に発散しない)、という主張です。

ストリームで表すと、このようになります:

(require (lib "40.ss" "srfi"))

(define (collatz n)
  (stream-cons n
               (cond ((= n 1) stream-null)
                     ((even? n) (collatz (/ n 2)))
                     (else (collatz (+ (* n 3) 1))))))

例えば 3 で試すと

(define (display-stream s)
  (stream-for-each display-line s))

(define (display-line x)
  (printf "~a~%" x)
  (flush-output (current-output-port)))

(display-stream (collatz 3))

3
10
5
16
8
4
2
1

のように表示されるわけです。

さらに、もっと大きな数で自動試行するために、自然数のストリームに対して collatz を適用してみましょう:

;; SICP 3.5.2
(define (integers-starting-from n)
  (stream-cons n (integers-starting-from (+ n 1))))

(stream-for-each (lambda (n)
                   (display-line "**************")
                   (display-stream (collatz n))
                   (sleep 1))
                 (integers-starting-from (* (expt 2 53)
                                            3)))

2^53 * 3 では

27021597764222976
...
3
10
5
16
8
4
2
1

となり、最初の例の 3 が表れて 1 に収束しました。

その後も延々と数字が出力されますが、いずれも似たようなパターンで 1 に収まります。

問題は、collatz の計算プロセスが止まらなくなる (無限大に発散、または 1 を含まない数列で無限ループする) ような n が存在するのか、ということなんですが、そのような数を発見した人は未だ居ないみたいです。


ところで、このような収束パターンを見て、パナキを連想するのは私だけでしょうか？　関西在住のお笑い好き、もしくはアメトークをよく見ている方ならご存知でしょうが、サバンナ八木の考案によるもので、任意に与えられた単語をしりとりで繋いでいき、最後は「パナキ」で終わらせる、というゲームです。

これが普通の人にはなかなか難しくて途中で詰まったりするんですが、彼だけは驚くべき高速で「パナキ」に収束させることが出来ます。

と言うのも、彼は「にく -> くじら -> らっぱ -> パナキ」とか、「りんご -> ごりら -> らっぱ -> パナキ」のようなお得意のパターンを幾つか持っており、ひとたびこれらのパターンに繋がる単語に辿り着くと一瞬で「パナキ」に持っていくことが出来るからです。

また、それらお得意のパターンに持ち込むまでのスピードも超高速なのが凄いところです。

このことと、2 の乗数が出現すると一気に 1 に収束する collatz の数列が何となく似ているなぁ、と思いました。

それが言いたかっただけです。良いお年を。