Publication Details

Convergence verification of the Collatz problem

BAŘINA David. Convergence verification of the Collatz problem. The Journal of Supercomputing, vol. 77, no. 3, 2021, pp. 2681-2688. ISSN 1573-0484.
Czech title
Ověření konvergence Collatzova problému
Type
journal article
Language
english
Authors
Keywords

Collatz conjecture, software optimization, parallel computing, number theory

Abstract

This article presents a new algorithmic approach for computational convergence verification of the Collatz problem. The main contribution of the paper is the replacement of huge precomputed tables containing O(2^N) entries with small lookup tables comprising just O(N) elements. Our single-threaded CPU implementation can verify 4.2×10^9 128-bit numbers per second on Intel Xeon Gold 5218 CPU computer, and our parallel OpenCL implementation reaches the speed of 2.2×10^11 128-bit numbers per second on NVIDIA GeForce RTX 2080. Besides the convergence verification, our program also checks for path records during the convergence test.

Published
2021
Pages
2681-2688
Journal
The Journal of Supercomputing, vol. 77, no. 3, ISSN 1573-0484
Publisher
Springer Verlag
DOI
UT WoS
000544846600001
EID Scopus
BibTeX
@ARTICLE{FITPUB12315,
   author = "David Ba\v{r}ina",
   title = "Convergence verification of the Collatz problem",
   pages = "2681--2688",
   journal = "The Journal of Supercomputing",
   volume = 77,
   number = 3,
   year = 2021,
   ISSN = "1573-0484",
   doi = "10.1007/s11227-020-03368-x",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/12315"
}
Files
Back to top