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-step [n]
  (if (zero? (bit-and n 1)) (bit-shift-right n 1) (+ n n n 1)))

(defn collatz [n]
  (->>
   n
   (iterate collatz-step)
   (take-while #(> % 1))
   (#(if (>= n 1) (lazy-cat % [1]) %))))

The core step wise computation (I avoided the base case of n = 1 here because it is handled higher up, perhaps wrongly):

(defn step [n]
  (if (even? n)
    (/ n 2)
    (-> n (* 3) inc)))

Reducing on an infinite sequence, interrupted via reduced. Maintaining the result is offloaded to the reduction machinery:

(defn collatz [n]
  (or (and (= 1 n) '(1))
      (->> (range) 
           (reductions (fn [x _] 
                         (let [x' (step x)]
                           (or (and (= 1 x') (reduced 1)) 
                               x')))
                       n))))

The above is quite noisy, with (or (and...)) logic to save a couple lines (also, the reducing fn logic could be made faster/terser with a case-let expression/macro). Here is another approach picking off each step from an infinite collatz 'index table':

(def sieve 
  (let [f (fn f [i]
            (lazy-seq 
             (cons (step i) 
                   (f (inc i)))))]
    (cons nil (cons 0 (f 2)))))

(defn collatz [n]
  (case n
    0 nil
    (cons n (collatz (nth sieve n)))))

(defn collatz [n]
  (take-while some? (iterate #(when (not= % 1)
                                (if (odd? %)
                                  (inc' (*' 3 %))
                                  (quot % 2)))
                             n)))

An example long Collatz sequence:

(count (collatz 931386509544713451))
=> 2284

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

(defn collatz [n]
  (concat (take-while #(not= 1 %) (iterate #(if (even? %) (/ % 2) (inc (* % 3))) n)) [1]))

Implementation with iterate.

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

(defn collatz [n]
  (take-while (complement zero?) (iterate next-collatz n)))

Implementation with recursion and lazy-seq.

(defn collatz2 [n]
  (if (= 1 n)
    (cons 1 nil)
    (lazy-seq (cons n (collatz2 (if (even? n) (/ n 2) (inc (* 3 n))))))))

(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))))