Collatz sequences in dc
,Inspired by this recent post and code snippet by John Gruber, I decided to have a go at outputting Collatz conjecture sequences in dc
. Running
dc -e '?[r3*1+]so[d2~1=opd1<x]dsxx'
from the command line will take a single value as input, and run the sequence.
?
takes input, puts it on the stack. [r3*1+]so
is our macro for n3+1, what we do when we encounter an odd value. [d2~1=opd1<x]dsxx
is our main macro, as well as our macro for handling even numbers (n/2). First it duplicates the value on the stack (last iteration) and divides by 2 to return the quotient and the remainder. 1=o
uses the remainder to test for oddness and run o
if true. Here I do something rather lazy for the sake of concise code: that initial duplication was solely for the sake of oddness. o
swaps the top of the stack to get that value back, then multiplies by three and adds one, leaving this value on the stack. Evenness will never run this, and since the test for evenness leaves the outcome for evenness on the stack (what luck!), and the initial duplication is below it. Either way, the bottom of the stack is going to fill up with a lot of garbage, which should be inconsequential unless our sequences become absurdly long. At this point, the top of our stack is the result of the current step, so we p
rint it, d
uplicate it, and run x
if it’s greater than 0. Finally, we d
uplicate our main macro, s
ave it as x
, and then ex
ecute the copy we left on the stack.
dc -e ‘?[r3*1+]so[d2~1=opd1<x]dsxx’ 21 64 32 16 8 4 2 1