brhfl.com

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 print it, duplicate it, and run x if it’s greater than 0. Finally, we duplicate our main macro, save it as x, and then execute 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