Cellular Automata to More Efficiently Compute the Collatz Map.

The Collatz, or 3x + 1, Conjecture claims that for every positive integer n, there exists some k such that T^k(n) = 1, where T is the Collatz map. We present three cellular automata (CA) that transform the global prob-lem of mimicking the Collatz map in bases 2,3, and 4 into a local one of transforming the digits of iterates. The CAs streamline computation first by bypassing calculation of certain parts of trajectories: the binary CA bypasses division by two altogether. In addition, they allow for multiple trajectories to be calculated simultaneously, representing both a signif-icant improvement upon existing sequential methods of computing the Collatz map and a demonstration of the efficacy of using a massively parallel approach with cellular automata to tackle iterative problems like the Collatz Conjecture. [ABSTRACT FROM AUTHOR]