キミならどう書く 2.0 - ROUND 2 - Collatz予想
http://ll.jus.or.jp/2006/blog/doukaku2

ROUND 1は素数を求める問題だったので意識的にスルーしてた。今回の問題も、この問題がCollatz予想と呼ばれているなんて知らない頃にpythonで素直に解いていたので、最初はスルーするつもりだった。Schemeで同じように解いてもつまらないし、あれから何か凄い計算の効率化のアイデアを思い付いたわけでもないので。ちなみに、効率化についてはWikipediaにも工夫のしどころが掲載されているみたい（Collatz conjecture）。

むしろ、なんでこんな問題が数学の難問になってるのかが興味深いとこだ。そこでちょっと逆向きに考えて、1に収束するまでのステップ数ごとに数字の分布を見てみようと思った。

(define (one-step-far ls)
  (cond ((null? ls)
         '())
        ((and (even? (car ls))
              (> (car ls) 4)
              (zero? (remainder (- (car ls) 1) 3)))
         (cons (/ (- (car ls) 1) 3)
               (cons (* 2 (car ls))
                     (one-step-far (cdr ls)))))
        (else
         (cons (* 2 (car ls))
               (one-step-far (cdr ls))))))

(define (gs step)
  (let R ((step step) (collatz '(1)))
    (cond ((zero? step) collatz)
          (else
           (R (- step 1) (one-step-far collatz))))))

収束先である1からの距離が10までの数字たちを並べると、こんな感じ。

gosh> (gs 1)
(2)
gosh> (gs 2)
(4)
gosh> (gs 3)
(8)
gosh> (gs 4)
(16)
gosh> (gs 5)
(5 32)
gosh> (gs 6)
(10 64)
gosh> (gs 7)
(3 20 21 128)
gosh> (gs 8)
(6 40 42 256)
gosh> (gs 9)
(12 13 80 84 85 512)
gosh> (gs 10)
(24 26 160 168 170 1024)

まあ、なんてことない結果なんだけど、やたらに密度が低いことがわかる。つまり、パラパラとしか数字が出現しない。この先、1に収束するまでのステップ数がnである数字の個数は、ほぼ10^n/10のスピードで急激に増えていくんだけど、どんなにnを大きくしても、いつまでたっても出現しない比較的小さな数字が残ってしまう（実際、97はn=118で始めて出現する）。

gosh> (length (gs 10))
6
gosh> (length (gs 20))
72
gosh> (length (gs 30))
732
gosh> (length (gs 40))
7628
gosh> (length (gs 50))
79255

こういうパラパラとした自然数の集まりって、素数と同じように、現在の数学（つーか代数）ではうまく扱えない構造なんだろうな。

ところで上で定義したone-step-farを使って「キミならどう書く 2.0」の関数hを書くこともできる。

(use srfi-1)

(define (h n)
  (let R ((rest (iota n 1))
   (collatz '(1)))
    (cond ((null? (lset-difference = rest collatz))
           rest)
          (else
           (R (lset-difference = rest collatz)
              (one-step-far collatz))))))

ただしcollatzの長さが爆発するので、これだとh(30)ですら止まらない。h(20)は18と19らしいんだけど……