백만 이하로 시작하는 우박수 중 가장 긴 과정을 거치는 것은?

백만 이하로 시작하는 우박수 중 가장 긴 과정을 거치는 것은? (tistory.com)

백만 이하로 시작하는 우박수 중 가장 긴 과정을 거치는 것은?

 

Common Lisp:

(let ((hh (make-hash-table)))
  (defun hailstone (n)
    (if (= n 1) (return-from hailstone 1))
    (let ((h (gethash n hh)))
      (if h h
        (setf (gethash n hh) (1+ (hailstone (if (evenp n) (/ n 2) (1+ (* 3 n))))))))))

(let ((max-n 1) (max 0))
  (loop for n from 1 to 1000000 do
    (let ((h (hailstone n))) (if (> h max) (setf max h max-n n))))
  (format t "n=~a count=~a~%" max-n max))

 

n=837799 count=525

 

 

Clojure:

(let [hh (atom {})]
  (defn hailstone [n]
    (if (= n 1) 1
      (let [h ((deref hh) n)]
	(cond h h,
	      :else
	      (let [v (inc (hailstone (if (even? n) (/ n 2) (inc (* 3 n)))))]
		(swap! hh assoc n v)
		v))))))

(loop [n 1, max-n 1, max 0]
      (cond (<= n 1000000)
	(let [h (hailstone n)]
	  (cond (> h max) (recur (inc n) n h),
		:else (recur (inc n) max-n max)))
	:else
	(println "n:" max-n "count: " max)))

 

Clojure memoized:

(def hailstone (memoize (fn [n]
  (cond (= n 1) 1,
     (even? n) (inc (hailstone (/ n 2)))
	 :else (inc (hailstone (inc (* 3 n))))))))

(loop [n 1, max-n 1, max 0]
      (cond (<= n 1000000)
	(let [h (hailstone n)]
	  (cond (> h max) (recur (inc n) n h),
		:else (recur (inc n) max-n max)))
	:else
	(println "n:" max-n "count: " max)))

 

JavaScript:

JSFiddle - Code Playground

 

Racket:

#lang racket
(define h (make-hash))
(hash-set! h 1 1)
(define (collatz n)
  (hash-ref! h n
             (lambda () (add1 (collatz (if (even? n) (/ n 2) (add1 (* 3 n))))))))

(define max-i 0)
(define max 0)
(for ([i (in-range 1 1000000)])
  (define c (collatz i))
  (when (> c max)
    (set! max-i i)
    (set! max c)))
(displayln (format "~a ~a" max-i max))

 

 

Julia:

h = Dict{Int,Int}()

function collatz(n)
    if n <= 1; return 1 end
    c = get(h, n, false)
    if c != false
        c
    else
        h[n] = 1 + collatz(if n % 2 == 0; div(n, 2) else 3n + 1 end)
    end
end

function main()
    maxc = -Inf
    maxn = 0
    for n in 1:1000000
        c = collatz(n)
        if c > maxc
            maxc = c
            maxn = n
        end
    end
    println(maxn, ": ", maxc)
end

main()

 

Python(Julia 버전을 변환):

h = {}

def collatz(n):
    if n <= 1:
        return 1
    c = h.get(n, False)
    if c != False:
        return c
    else:
        r = h[n] = 1 + collatz(n // 2 if n % 2 == 0 else 3 * n + 1)
        return r

def main():
    maxc = float('-inf')
    maxn = 0
    for n in range(1, 1000001):
        c = collatz(n)
        if c > maxc:
            maxc = c
            maxn = n
    print(f"{maxn}: {maxc}")

main()