Cellular Automata to More Efficiently Compute the Collatz Map

arXiv1301.3125MaRDI QIDQ6238739FDOQ6238739

Publication date: 14 January 2013

Abstract: 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 problem 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 significant 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.

This page was built for publication: Cellular Automata to More Efficiently Compute the Collatz Map

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6238739)