How to Fast Verify Collatz Conjecture by Automata

To verify Collatz conjecture for a given integer, we need to justify whether or not the given starting number goes to 1 finally. Current method computes 3*x+1 and x/2 one by one. In this paper, we propose an automata-based algorithm to compute the process in a batch with m steps - (3*x+1)2 or x/2. We also propose reduced Collatz conjecture and we prove it is equivalent to Collazt conjecture. We also point out that original dynamics is the combination of reduced dynamics. (Original dynamics is a serial of occurred 3*x+1 and x/2 computation in the process from a starting number to 1; Reduced dynamics is a serial of occurred 3*x+1 and x/2 computation in the process from a starting number to the first transformed number that is less than the starting number.) We study the properties of reduced dynamics and discover that reduced dynamics for some starting numbers can be determined directly without conducting concrete 3*x+1 or x/2 computations. We build a binary tree called Collatz tree and use it as a visual tool for automata design. We find that each partition of starting number residue class decides the further computation is whether 3*x+1 or x/2. The proposed automata can output code segment with m+2 computations in terms of (3*x+1)/2 or x/2 by taking as input x=4t+3, where t is in residue class i module 2^m and m is a natural number. We finally propose a conjecture whose proof implies the proof of Collatz conjecture by using proposed Collatz tree.