Collatz computation sequence for sufficiently large integers is a pseudo-random bit sequence

Collatz conjecture states that each positive integer will return to 1 after two computations — either [Formula: see text] when x is odd or [Formula: see text] when x is even. We denote [Formula: see text] as ‘I’ and [Formula: see text] as ‘O’. Given a starting integer x, the computational sequence from x to 1 can be looked as a string consisting of ‘I’ and ‘O’. We call this sequence (string) as the dynamics of x. The key results are as follows: (1) To verify the Collatz conjecture, we randomly select an extremely large integer and verify whether it can return to 1. The largest one has been verified by us has 6,000,000 bits, which is overwhelmingly much larger than currently verified by others, e.g., 128 bits, and we only use a laptop. (2) To verify whether extremely large integers can return 1, we propose an dedicated algorithm that can compute [Formula: see text] for extremely large x whose length can be million bits, e.g., 5 million bits. The subtlety of our algorithm is replacing integer multiplication by bit addition, and further only by logical condition judgment (e.g., logic operation). (3) By observing dynamics of extremely large integers, we discover that the ratio — the count of ‘O’ over the count of ‘I’ in the dynamics goes to 1 asymptotically with the growth of starting integers. (4) We discover that once the length of starting integer is sufficiently large, e.g., 1 million bits, the corresponding dynamics presents sufficient randomness as a bit sequence (‘I’ is replaced with 1 and ‘O’ is replaced with 0). Thus, the computation of the dynamics of a sufficiently large integer can be looked as a pseudo-random bit sequence generator. We change the algorithm from outputting dynamics into outputting bit sequence, and then we compute randomly selected integers with L bit length, where L is 1, 2, 3, 4, 5, 6 million bits. We evaluate the randomness of the generated bit sequences by standards such as NIST SP 800-22 and GM/T 0005-2021. All sequences can pass the tests, and the larger the starting integer, the better. (5) We thus propose an algorithm for random bit sequence generator by only using logical judgment and less than 100 lines in ANSI C.