Brute force but works. The real trick, for me at least, was to convert the number into a sequence of 1's. The rest was like an exercise in programming Turing machines (and a nice flashback into the freshman year of college).