コラッツ・角谷の問題 in Common Lisp DouKaku?

任意の数nを与えたときに
・nが偶数ならば2で割る　(n=n/2)
・nが奇数ならば3倍して1を足す （n = 3*n+1)
を繰り返すと、いづれは1になる。というものがあります。

数値計算の上ではかなりの数まで成り立つことが知られています。
（すべての数について成り立つかは不明）
参考リンク先参照

ある任意の数nがコラッツ・角谷の問題で1になるまでのステップ数をf(n)とします。
1～2^20までの数でf(n)を求めて、f(n)が最大になるときのnとf(n)を表示してください。

たとえばn=9だと次のような数列をたどって、19ステップで1になります。
9->28->14->7->22->11->34->17->52->26->13->40->20->10->5->16->8->4->2->1
つまりf(9)=19です。

また、最大を求めた際の実行時間と環境を書いてください。

see: コラッツの問題の成り立つ範囲

とりあえず書いたって感じですが。CLISP で約9秒。

(defun collatz (n)
  (let ((memo (make-hash-table)))
    (setf (gethash 1 memo) 1)
    (labels ((collatz-loop (i)
               (cond ((gethash i memo))
                     ((evenp i)
                      (setf (gethash i memo) (1+ (collatz-loop (/ i 2)))))
                     (t
                      (setf (gethash i memo) (1+ (collatz-loop (1+ (* 3 i)))))))))
      (loop with max = 0 and j for i from 1 to n as x = (collatz-loop i)
        if (< max x) do (setf max x j i)
        finally (format t "max ~D for n=~D~%" max j)))))

SBCL 1.0.13 x86_64 / Linux / Core2 E6600 2.4GHzで、2〜3秒でした。
(time  (collatz-max (expt 2 20)))
;=> f(837799) = 524
;
;Evaluation took:
;  1.355 seconds of real time
;  2.672167 seconds of user run time
;  0.0 seconds of system run time
;  0 calls to %EVAL
;  0 page faults and
;  1,728 bytes consed.

(defun collatz (n)
  (do ((cnt 0 (1+ cnt))
       (res n (if (evenp res) (ash res -1) (1+ (* res 3)))))
      ((= 1 res) cnt)
    (declare (fixnum cnt res n))))

(defun collatz-max (num)
  (do ((i 1 (1+ i)) (n 0) (highest 0))
      ((> i num) (format t "f(~D) = ~D~%" n highest))
    (let ((cur (collatz i))) 
      (when (< highest cur) 
        (setq n i highest cur)))))

DouKaku?

コラッツ・角谷の問題

Posted feedbacks - Common Lisp

Index

Feed

Other

Link

Pathtraq