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/
The core step wise computation (I avoided the base case of n = 1 here because it is handled higher up, perhaps wrongly):
Reducing on an infinite sequence, interrupted via
reduced
. Maintaining the result is offloaded to the reduction machinery: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':