Coreli

Coreli stand for "Collatz Research Library". Archangelo Corelli.

The Collatz process is a very simple to describre: take any number x, if even do x/2 if odd do (3x+1)/2. Repeat.

Starting from 5: [5, 8, 4, 2, 1, 2, 1, 2, 1, ...].

Starting from 43: [43, 65, 98, 49, 74, 37, 56, 28, 14, 7, 11, 17, 26, 13, 20, 10, 5, 8, 4, 2, 1, 2, 1, 2, 1, ...].

The Collatz Conjecture, unresolved since the 60s, states that, any stritcly positive natural numbers reaches 1.

The appararent simplicity of this problem hides a very difficult mathematical problem. Actually, we believe that this problem has a lot to do with Computer Science. That's why we created Coreli, a library for experimenting and testing hypothesises regarding the Collatz process.

The features of Coreli are based on research which is listed below. Please browse the examples folder to get an idea of what you can do with it.

Examples

Regular expressions of ancestors

The notebook examples/Binary expression of ancestors in the Collatz graph.ipynb shows how to use coreli to generate the regular expression generating Collatz ancestors at odd distance k in the Collatz graph. Refer to the paper: Binary expression of ancestors in the Collatz graph for more details.

Running the Collatz process on 2-adic integers

The notebook examples/Collatz 2-adic and rational cycles.ipynb shows how to use coreli to run the Collatz process in its generalisation to numbers with infinite binary expansion (2-adic integers). See [Lagarias 1985] or Olivier Rozier's Parity sequences of the 3x+1 map on the 2-adic integers and Euclidean embedding for more details.

Important note

If you want to play with the notebooks presented in examples (as you are very encouraged to do), please copy them in the folder examples_safe before doing anything and run those copied notebooks instead.

Indeed, the folder examples_safe is not under version control hence, you won't encounter annoying problems related to what you may have done in the notebooks when you pull future versions of coreli.

Doc

Coreli's doc is hosted here.

References

• David Applegate and Jeffrey Lagarias. Density bounds for the 3x + 1 problem. ii. krasikov inequalities. Mathematics of Computation - Math. Comput., 64:427–438, 01 1995. doi: 10.2307/2153346.

• Jean Berstel, Jr. and Christophe Reutenauer. Rational Series and Their Languages. Springer- Verlag, Berlin, Heidelberg, 1988.

• Jose Capco. Odd Collatz Sequence and Binary Representations. Preprint, March 2019. URL: https://hal.archives-ouvertes.fr/hal-02062503.

• Livio Colussi. The convergence classes of Collatz function. Theor. Comput. Sci., 2011. URL: https://doi.org/10.1016/j.tcs.2011.05.056, doi:10.1016/j.tcs.2011.05.056.

• J.H Conway. Unpredictable iterations. Number Theory Conference, 1972. Zachary Franco and Carl Pomerance. On a Conjecture of Crandall Concerning the qx + 1 Problem. Mathematics of Computation, 64(211):1333–1336, 1995. URL: http://www.jstor. org/stable/2153499.

• Patrick Chisan Hew. Working in binary protects the repetends of 1/3h : Comment on Colussi’s ’The convergence classes of Collatz function’. Theor. Comput. Sci., 618:135–141, 2016. URL: https://doi.org/10.1016/j.tcs.2015.12.033, doi:10.1016/j.tcs.2015.12.033.

• Pascal Koiran and Cristopher Moore. Closed-form analytic maps in one and two dimen- sions can simulate universal Turing machines. Theoretical Computer Science, 210(1):217– 223, January 1999. URL: https://doi.org/10.1016/s0304-3975(98)00117-0, doi:10.1016/ s0304-3975(98)00117-0.

• Stuart A. Kurtz and Janos Simon. The Undecidability of the Generalized Collatz Problem. In TAMC 2007, pages 542–553, 2007. URL: https://doi.org/10.1007/978-3-540-72504-6_49, doi:10.1007/978-3-540-72504-6_49.

• Jeffrey C. Lagarias. The 3x + 1 problem and its generalizations. The American Mathematical Monthly, 92(1):3–23, 1985. URL: http://www.jstor.org/stable/2322189.

• Jeffrey C. Lagarias. The 3x+1 problem: An annotated bibliography (1963–1999) (sorted by author), 2003. arXiv:arXiv:math/0309224.

• Jeffrey C. Lagarias. The 3x+1 problem: An annotated bibliography, ii (2000-2009), 2006. arXiv:arXiv:math/0608208.

• Kenneth Monks. The sufficiency of arithmetic progressions for the 3x + 1 conjecture. Proceed- ings of the American Mathematical Society, 134, 10 2006. doi:10.2307/4098142.

• Terence Tao. Almost all orbits of the collatz map attain almost bounded values, 2019. arXiv:arXiv:1909.03562.

• Riho Terras. A stopping time problem on the positive integers. Acta Arithmetica, 30(3):241–252, 1976. URL: http://eudml.org/doc/205476.

• Günther Wirsching. On the combinatorial structure of 3n + 1 predecessor sets. Discrete Math- ematics, 148(1-3):265–286, January 1996. URL: https://doi.org/10.1016/0012-365x(94)00243-c, doi:10.1016/0012-365x(94)00243-c.

• Günther J. Wirsching. The dynamical system generated by the 3n + 1 function. Springer, Berlin New York, 1998.