콜라츠 시퀀스의 구현

JavaScript

#!/usr/bin/env node

function collatzSequence(n) {
    var seq = [n];
    while (n !== 1) {
        if (n % 2 === 0) {
            n = n / 2;
        } else {
            n = 3 * n + 1;
        }
        seq.push(n);
    }
    return seq;
}

console.log(
    collatzSequence(
        parseInt(process.argv[2], 10)));

위의 구현을 파일에 저장하고 실행하면 다음과 같은 콜라츠 시퀀스를 얻을 수 있다.

$ ./collatz.js 123
[
  123, 370, 185, 556, 278, 139, 418, 209, 628, 314,
  157, 472, 236, 118,  59, 178,  89, 268, 134,  67,
  202, 101, 304, 152,  76,  38,  19,  58,  29,  88,
   44,  22,  11,  34,  17,  52,  26,  13,  40,  20,
   10,   5,  16,   8,   4,   2,   1
]

$ ./collatz.js 7
[
   7, 22, 11, 34, 17, 52, 26,
  13, 40, 20, 10,  5, 16,  8,
   4,  2,  1
]

Clojure

Clojure로 구현하면 take-while의 특성을 사용해 두 개의 함수(next-collatz와 #(> % 1))로 심플하게 구현할 수 있다.

(defn next-collatz [n]
  (if (even? n)
    (/ n 2)
    (-> n (* 3) (+ 1))))

(defn collatz-sequence [n]
  (-> (into [] (take-while #(not= % 1)
                           (iterate next-collatz n)))
      (conj 1)))

실행하면 다음과 같은 결과를 볼 수 있다.

(collatz-sequence 123)
=> [123 370 185 556 278 139 418 209 628 314 157 472 236 118 59 178 89 268 134 67 202 101 304 152 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1]

(collatz-sequence 7)
=> [7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1]

참고문헌