426 PurelyFunctional.tv Newsletter

00 Collatz sequence.md

Collatz sequence

A Collatz sequence for a positive integer n is defined by repeatedly applying the following rules:

• If n is even, divide by 2.
• If n is odd, multiply by 3 and add 1.

The sequence ends when n = 1.

Write a function that generates a lazy Collatz sequence given a number.

Examples

(collatz 1) ;=> (1)
(collatz 2) ;=> (2 1)
(collatz 3) ;=> (3 10 5 16 8 4 2 1)

Thanks to this site for the problem idea, where it is rated Hard in Ruby. The problem has been modified.

Please submit your solutions as comments on this gist.

To subscribe: https://purelyfunctional.tv/newsletter/

(defn collatz-conjecture [n]
  (->> n
       (iterate (fn [n] (if (even? n) (/ n 2) (inc (* n 3)))))
       (take-while (partial not= 1))
       (conj '(1))
       flatten)

(defn n+1 [n]                                                                                                                                         
  (if (even? n)                                                                                                                                       
    (/ n 2)                                                                                                                                           
    (inc (* 3 n))))

(defn collatz [n]
  (concat
   (take-while (partial not= 1) (iterate n+1 n))
   [1]))

(defn collatz [n]
  (lazy-seq
   (cons n (cond
             (= 1 n) ()
             (even? n) (collatz (/ n 2))
             :else (collatz (inc (* 3 n)))))))

;; (collatz 1) ;; => (1)
;; (collatz 2) ;; => (2 1)
;; (collatz 3) ;; => (3 10 5 16 8 4 2 1)
;; (realized? (collatz 3)) ;; => false

(defn collatz [n]
  (if (= n 1)
    (list n)
    (lazy-seq
     (let [m (if (even? n)
               (quot n 2)
               (+ 1 (* n 3)))]
         (cons n (collatz m))))))

(defn collatz
  [n]
  (lazy-seq
   (concat (list n)
           (cond
             (= n 1) nil
             (even? n) (collatz (/ n 2))
             :else (collatz (inc (* 3 n)))))))

(defn collatz [x]
  (lazy-seq
   (cond (= 1 x) '(1)
         (even? x) (cons x (collatz (/ x 2)))
         :else (cons x (collatz (+' (*' x 3) 1))))))

(defn collatz [num]
    (loop [num num
              out (list)]
        (cond (<= 1 num) (reverse (cons 1 out))
                  (even? num) (recur (/ num 2) (cons num out))
                  :else (recur (+ (* num 3) 1) (cons num out)))))

(defn collatz [x] false
  (if (= x 1)
    [1]
    (cons x (lazy-seq (collatz (if (even? x)
                                 (/ x 2)
                                 (+ (* x 3) 1)) )))))

(defn collatz [x]
  (if (vector? x)
    (let [n (last x)]
      (cond
        (= 1 n) (seq x)
        (even? n) (collatz (conj x (/ n 2)))
        (odd? n) (collatz (conj x (+ 1 (* 3 n))))))
    (collatz (vector x))))