Paper 2023/648
Collatz Computation Sequence for Sufficient Large Integers is Random
Abstract
The main results in the paper are as follows: (1) We randomly select an extremely large integer and verify whether it can return to 1. The largest one has been verified has length of 6000000 bits, which is overwhelmingly much larger than currently known and verified, e.g., 128 bits, and its Collatz computation sequence consists of 28911397 `I' and `O', only by an ordinary laptop. (2) We propose an dedicated algorithm that can compute 3x+1 for extremely large integers in million bit scale, by replacing multiplication with bit addition, and further only by logical condition judgement. (3) We discovery that the ratio  the count of `O' over the count of `I' in computation sequence goes to 1 asymptotically with the growth of starting integers. (4) We further discover that once the length of starting integer is sufficient large, e.g., 500000 bits, the corresponding computation sequence (in which `I' is replaced with 1 and `O' is replaced with 0), presents sufficient randomness as a bit sequence. We firstly obtain the computation sequence of randomly selected integer with L bit length, where L is 500000, 1000000, 2000000, 3000000, 4000000, 5000000, 6000000, by our proposed algorithm for extremely large integers. We evaluate the randomness of all computation sequences by both NIST SP 80022 and GM/T 00052021. All sequences can pass the tests, and especially, the larger the better. (5) We thus propose an algorithm for random bit sequence generator by only using logical judgement (e.g., logic gates) and less than 100 lines in ANSI C. The throughput of the generator is about 625.693 bits/s over an ordinary laptop with Intel Core i7 CPU (1.8GHz).
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint.
 Keywords
 randomness
 Contact author(s)
 weirencs @ cug edu cn
 History
 20230517: revised
 20230508: received
 See all versions
 Short URL
 https://ia.cr/2023/648
 License

CC BYNCND
BibTeX
@misc{cryptoeprint:2023/648, author = {Wei Ren}, title = {Collatz Computation Sequence for Sufficient Large Integers is Random}, howpublished = {Cryptology ePrint Archive, Paper 2023/648}, year = {2023}, note = {\url{https://eprint.iacr.org/2023/648}}, url = {https://eprint.iacr.org/2023/648} }