Top

The Journal of Supercomputing

Published in:

01-07-2020

Convergence verification of the Collatz problem

Author: David Barina

Published in: The Journal of Supercomputing | Issue 3/2021

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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 \times 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 \times 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.

previous article ILP formulation and heuristic method for energy-aware application mapping on 3D-NoCs

next article Scalable parallel implementation of migrating birds optimization for the multi-objective task allocation problem

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

http://www.ericr.nl/wondrous/.

https://boinc.thesonntags.com/collatz/.

http://sweet.ua.pt/tos/3x+1.html.

Enhancement proposed by Eric Roosendaal.

https://github.com/xbarin02/collatz/.

Hercher C (2018) Über die Länge nicht-trivialer Collatz-Zyklen. Die Wurzel 6 and 7

Lagarias JC (2003) The \(3x+1\) problem: an annotated bibliography (1963–1999) (sorted by author). arXiv:math/0309224

Lagarias JC (2006) The \(3x+1\) problem: an annotated bibliography, II (2000–2009). arXiv:math/0608208

Conway JH (1972) Unpredictable iterations. In: Proceedings of the 1972 Number Theory Conference, pp 49–52

Mol LD (2008) Tag systems and Collatz-like functions. Theor Comput Sci 390(1):92–101. https://doi.org/10.1016/j.tcs.2007.10.020MathSciNetCrossRefMATH

Lagarias JC (1985) The 3x + 1 problem and its generalizations. Am Math Mon 92(1):3–23. https://doi.org/10.2307/2322189MathSciNetCrossRefMATH

Honda T, Ito Y, Nakano K (2017) GPU-accelerated exhaustive verification of the Collatz conjecture. Int J Netw Comput 7(1):69–85

Oliveira e Silva T (2010) Empirical verification of the 3x+1 and related conjectures. In: Lagarias JC (ed) The ultimate challenge: The 3x+1 problem. American Mathematical Society, Providence, pp 189–207MATH

Leavens GT, Vermeulen M (1992) 3x+1 search programs. Comput Math Appl 24(11):79–99. https://doi.org/10.1016/0898-1221(92)90034-FMathSciNetCrossRefMATH

10.

Dunn R (1973) On Ulam’s problem. Tech. rep., University of Colorado at Boulder

11.

Oliveira e Silva T (1999) Maximum excursion and stopping time record-holders for the \(3x+1\) problem: computational results. Math Comput 68(225):371–384. https://doi.org/10.1090/S0025-5718-99-01031-5MathSciNetCrossRefMATH

12.

Lagarias JC, Weiss A (1992) The \(3x + 1\) problem: two stochastic models. Ann Appl Probab 2(1):229–261. https://doi.org/10.1214/aoap/1177005779MathSciNetCrossRefMATH

Title: Convergence verification of the Collatz problem
Author: David Barina
Publication date: 01-07-2020
Publisher: Springer US
Published in: The Journal of Supercomputing / Issue 3/2021
Print ISSN: 0920-8542
Electronic ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-020-03368-x

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 3/2021

Energy efficiency in cloud computing based on mixture power spectral density prediction

Scalable parallel implementation of migrating birds optimization for the multi-objective task allocation problem

ILP formulation and heuristic method for energy-aware application mapping on 3D-NoCs

Performance benchmarking of deep learning framework on Intel Xeon Phi

Relation collection using Pollard special-q sieving to solve integer factorization and discrete logarithm problem

Applying Taiwanese indigenous health literacy for designing an elders’ prevention fall course: a statistical analysis and deep learning approach

Premium Partner