Collatz Conjecture Redefinition on Prime Numbers

Abstract

The definition of Collatz Operator, the mathematical avatar of the Collatz Algorithm, permits the transformation of the Collatz conjecture, which is delineated over the whole natural number set, into an equivalent inference restricted to the odd prime number set only. Based on this redefinition, one can describe an empirical-heuristic proof of the Collatz conjecture.

Share and Cite:

Carbó-Dorca, R. (2023) Collatz Conjecture Redefinition on Prime Numbers. Journal of Applied Mathematics and Physics, 11, 147-157. doi: 10.4236/jamp.2023.111011.

1. Introduction

The present paper follows the published effort of the author to understand some aspects of the Collatz conjecture [1] [2] [3] and several characteristics of prime numbers [4] [5]. Collatz conjecture has been studied from many points of view and still is an active scientific subject; see, for example, references [6] - [28].

The aim of this study is to show that one can circumscribe the original Collatz or ( 3 n + 1 ) conjecture to the set of prime numbers instead of the whole natural number set. In fact, in previous studies [1] [2], one has shown that the odd natural numbers only can be the subject of the Collatz conjecture, as one can demonstrate that even numbers fulfill it by construction. Out, it will be demonstrated that the odd prime numbers are the backbone of the Collatz conjecture. Within these results, one can find sufficient arguments to define an Extended Syracuse algorithm and obtain empirical-heuristic arguments to prove the Collatz conjecture.

For this purpose, the structure of this study will contain the first needed definitions, involving the set of prime powers and the definition of natural pseudospaces to understand the factorization of composite numbers, followed by a third section, where the Collatz algorithm and operators will be described, and application examples are given. To these preliminaries, will follow a section analyzing the meaning of a number being Collatz compliant, followed by the characteristics of the Collatz operator applied to the prime numbers in the Mersenne interval [ 0 , 31 ] . This will lead to the final section on the Extended Syracuse algorithm and conclusions.

2. Definitions

A previous set of the employed concepts and definitions is necessary before developing the main idea of the present study. The readers can peruse our previous papers on the Collatz conjecture [1] [2] [3] and our studies about some characteristic features of prime numbers [4] [5]. These can provide the previous main definitions and some mathematical background.

The basic principle in the present paper consists of the leading role of odd prime numbers in the redefinition of the Collatz conjecture.

2.1. Natural Numbers Power Set

Let’s choose any natural number: n .

Define the natural powers of n as the set: n = { n 0 , n 1 , n 2 , , n p , } . Also, let’s write the set of all the powers of natural numbers sets n as1:

= { 0 ; 1 ; 2 ; ; n ; } . (1)

2.2. Prime Numbers Power Set

Let’s symbolize the set of natural prime numbers as: F .

Let’s define the set of all the natural powers of the natural prime numbers set as: F = { 2 ; 3 ; ; p ; } .

2.3. Representation of Natural Numbers

As a result of defining the elements of the prime natural powers set, one represents all natural numbers using products of some elements of the set F . One can symbolize this property as: F = , meaning:

n A = { a I | I = 1 , M } F P = { p I | I = 1 , M } C = { ( a I ) p I | I = 1 , M } n = I = 1 M [ ( a I ) p I ] . (2)

When one chooses a natural prime set of bases A and some natural power set P is selected, their elements construct another natural set C, such that the product of their elements yields a natural number. This is a trivial problem, where information on factorization of a large set of natural numbers can be found in reference [29].

A simple yet interesting example is: 5005 = 5 × 7 × 11 × 13 , where M = 4 , the bases are a | = { 5 , 7 , 11 , 13 } , and the exponents are p | = { 1 , 1 , 1 , 1 } . When changing the exponents to the vector p | = { 4 , 3 , 2 , 1 } , the resultant number is 337211875.

2.4. The Vector Pseudospace Structure of the Natural Number Generation

The example described above might suggest an alternative description. One can construct such a numerical picture on the fact that natural numbers can be generated with M-dimensional vector elements (for previous studies on similar problems, see references [30] [31] [32] ). These vectors could be constructed with tuples of prime numbers to the powers of natural numbers as defined in Equation (1), but choosing just the prime set of powers F described in Section 2.2, and finally ordering the vector elements according to the bases’ order.

For example, define the M-dimensional pseudospace:

f | = ( f I p I | I = 1 , M ) A M ( F ) . (3)

There is no need to describe any operation on pseudospaces; one only needs to consider the existence of the infinite set of elements as M-dimensional vectors made of tuples containing powers of prime numbers.

Defined the M-dimensional pseudospace A M ( F ) , then one can construct an operation over its elements, transforming them into natural numbers:

Π : A M ( F ) , (4)

that is:

f | A M ( F ) : Π ( f | ) = n n = I = 1 M f I p I .

Such a transformation can be considered a non-linear operator or a geometric vector norm. Therefore, one can consider the pseudospaces in Equation (3), defined over F , or more generally over , as some Banach semispaces or lattices, see references [30] [31] [32].

As defined in Equation (3), a set of pseudospace vectors with varying dimension M, and the associated operation (4), might be used to generate the whole set of natural numbers. Practical generation on a large set of natural numbers can be found in reference [29].

3. Collatz Algorithm, Collatz Operator, Collatz Compliant Natural Numbers, and the Redefinition of the Collatz Conjecture

A pseudocode implementing a Collatz algorithm, the computational avatar of the Collatz conjecture, was described in references [1] [2]. It is provided below with slight modifications, which one can easily associate with a Collatz operator, the mathematical avatar of the Collatz conjecture, performing the same indicated algorithmic operations on any natural number, as represented in Equation (2).

3.1. Collatz Algorithm

Input : n ! n isanynaturalnumber m n ; I 0 Define C I [ m ] while m > 1 I I + 1; c m / 2 if2 c m : m 3 m + 1 else: m c Output : I , n

For more details about the Collatz Algorithm and the associated Collatz operator, see reference [2].

3.2. Definitions

Then, one can use the Collatz algorithm as an operator such that choosing a given natural number n, after S ( n ) steps following an n-path (consisting of the set of natural numbers resulting from every iteration when applying the Collatz algorithm), yields 1. That is, one can write the Collatz Conjecture as:

n C S ( n ) [ n ] = 1 , (5)

hence, one can call the natural number n Collatz compliant whenever Equation (5) holds.

3.3. Collatz Operator over a Product of Collatz Compliant Natural Numbers

Admitting the Collatz operator can act on a natural number product of two Collatz compliant numbers, as shown in the following sequence:

m , n C S ( m ) [ m ] = C S ( n ) [ n ] = 1 p = m n C [ p ] = C [ m ] C [ n ] = 1 1 = 1 .

Then, with this property in mind, it will be the same if one writes:

C [ m n ] = C [ m ] n = 1 C [ n ] = 1 1 = 1 .

This way of acting of the Collatz operator is the same as saying that its application on a product of natural numbers is equivalent to the product of the applications of the Collatz operator on the factors, or one can alternatively consider the result of the successive Collatz operator application to every factor.

3.4. Collatz Operator over a Natural Power of a Natural Number

Thus, one can write the application of the Collatz operator to a natural power p of a Collatz compliant natural number n:

p , n C [ n ] = 1 C [ n p ] = ( C [ n ] ) p = 1 p = 1 ,

then one can deduce that any natural power of a Collatz compliant number is also Collatz compliant.

Suppose a Collatz compliant set of natural prime numbers is defined as in Equation (2). Thus, one can write the application of the Collatz operator to such a composite number like:

C [ n ] = I = 1 M [ C [ ( a I ) p I ] ] = I = 1 M [ C [ a I ] p I ] = I = 1 M [ 1 p I ] = 1 .

3.5. The Collatz Conjecture from the Point of View of Prime Numbers

Hence, the Collatz conjecture, usually presented as all natural numbers are Collatz compliant, can be reformulated by the equivalent sentence that the set of natural prime numbers is Collatz compliant.

4. Collatz Compliance of the Even Numbers and the Extended Syracuse Algorithm

Let’s split the set of natural numbers as the trivial union of the even number set E and the odd number set O, such that: = E O .

4.1. Collatz Compliance of the Even Natural Number Set

It is easy to see now that even natural numbers are Collatz compliant. One can write any even number according to the equation:

2 p 2 n O : x = 2 p n x E . (6)

Considering that the odd numbers up to n have been found Collatz compliant, accordingly using the definition of the even number x in Equation (6) above, one can also write:

n O n < x C S ( n ) [ n ] = 1 ,

furthermore, the following expression holds:

C p [ x ] = C p [ 2 p ] n = 1 n = n C S ( x ) [ x ] = C p [ 2 p ] C S ( n ) [ n ] = 1 1 = 1 .

Such a result permits one to be confident that the Collatz algorithm can transform into an Extended Syracuse Algorithm, where the powers of two appearing in all the even composite numbers are obviated in the expression of the Collatz path, taking implicitly the fact that p : C [ 2 p ] = 1 holds; so, for example:

C [ 40 ] = C [ 8 5 ] = C [ 2 3 ] C [ 5 ] = 1 C 1 [ 5 ] = C [ 16 ] = C 4 [ 2 4 ] = 1 .

Therefore, only odd natural numbers must be submitted to the Collatz Extended Syracuse Algorithm.

4.2. Collatz Algorithm on the Odd Number Set

However, this is not all that can be added to the Extended Syracuse Algorithm. In this way, define the odd prime numbers set P such as: F = 2 P . Then, the odd natural numbers can be considered as products of the elements of the set of sets of powers of odd primes:

P N = { 3 ; 5 ; ; q ; } .

One can symbolize this property as: P = O .

Supposing that the odd prime numbers have been proved Collatz invariant up to some value, q say. Then, any product where each factor is the power of an arbitrary odd prime number, less or equal to q, becomes an odd composite number, which is Collatz compliant.

Therefore, to prove the Collatz conjecture, the odd prime numbers only are relevant. In the Collatz paths of the odd prime numbers, one can easily observe that these prime numbers might appear larger than the Collatz algorithm origin prime. If such an occurrence is present, it also demonstrates that some larger than an initial prime number is Collatz compliant within each path.

4.3. Some Examples in the Mersenne Interval [ 0 , 3 1 ]

One can see the definition and usefulness of Mersenne intervals in references [2] [4]. One can see the mentioned properties of the Collatz operator or algorithm using the following examples. Numbers in red are primes greater than the initial and in blue lesser than the initial in the associated paths. Colons indicate a step in the corresponding Collatz path.

First, one can observe the path for the prime numbers 3 and 7:

C S ( 3 ) [ 3 ] 3 : 10 : 5 : 16 = 2 4 : 1 C S ( 7 ) [ 7 ] 7 : 22 : 11 : 34 : 17 : 52 : 2 2 13 : 13 : 2 3 5 : 5 : 2 4 : 1 .

In this way, it is evident that within the 3-path, the prime {5} is Collatz compliant, and within the 7-path, the prime set { 11 , 13 , 17 } does appear; thus, these three primes are Collatz compliant. Hence, one can skip the observation of their paths because they are already contained in the 7-path, and one can enter to test the 19-path directly:

C S ( 19 ) [ 19 ] 19 : 58 : 29 : 88 = 2 3 11 : 11 : 1 ,

where the new prime 29 appears, while the 19-path arrives at the already Collatz compliant prime 11, and the algorithm sequence can stop. This shows that the 19 and 29 prime numbers are also Collatz compliant. The prime 23 has been left aside in all the studied paths, so one obtains for the 23-path:

C S ( 23 ) [ 23 ] = 23 : 70 : 35 = 7 5 : 1 ,

where a composite product of two Collatz compliant primes appears. So, the algorithm can stop at this stage, and the prime number 23 can be considered Collatz compliant. The following not yet considered prime is the Mersenne number M ( 5 ) = 2 5 1 = 31 :

C S ( 31 ) [ 31 ] 31 : 94 : 47 : 142 : 71 : 214 : 107 : 322 : 161 = 7 23 : 1 ,

here the Collatz algorithm 31-path provides a trio of new Collatz compliant primes: { 47 , 71 , 107 } and ends with the composite natural number 161. As the two involved primes are already Collatz compliant and lesser than the starting number, one can conclude that 31 is a prime Mersenne number which is also Collatz compliant.

4.4. Collatz Compliance of the Prime Mersenne Number M ( 7 ) = 2 7 1 = 1 2 7

A slightly involved example supposes having tested all the sequence of prime numbers previously found Collatz compliant, except for the prime Mersenne number 127. Then, one can write the development of the 127-path as:

C S ( 127 ) [ 127 ] 127 : 382 : 191 : 574 : 287 = 7 41 : 1 ,

where a new prime 191 appears to be Collatz compliant. The 127-path can be stopped after the step yielding 287, as it is a composite product of two primes lesser than 127. Then, resulting in 127 being a Collatz compliant prime number.

5. Extended Syracuse Algorithm

Therefore, one can enrich the Extended Syracuse Algorithm with the addition that the algorithm can stop whenever a given p-path produces a lesser prime than the initial or a composite number, where the present prime powers involve prime bases lesser than the initial prime number.

These final considerations, as well as the prior ones in Section 4.1, constitute the structure of the Extended Syracuse Algorithm, which can be presented in pseudocode as follows.

5.1. Extended Syracuse Algorithm

Input : n P ! n isanoddprimenumber Define S J [ n ] m n ; J 0; while a i P m Π i a i p i P and .not . ( a i < n ) : J J + 1 ; m 3 m + 1 if w O and m 2 n w : then m w Output : J , n , m

5.2. Application Examples on Mersenne Numbers

As an assorted application example, one could be interested in the behavior of higher prime Mersenne numbers when submitted to the Collatz algorithm in the Extended Syracuse version. The prime Mersenne number set (see, for example, the web-provided list [33] ):

{ M ( 13 ) , M ( 17 ) , M ( 19 ) , M ( 31 ) , M ( 61 ) , M ( 89 ) , M ( 107 ) , M ( 127 ) }

has been studied. The computing website facility constructed by Alpern [34] has also been used to handle large primes and prime factors. The resultant paths on these primes show that in a few path steps, one arrives at composite numbers involving two or not too many prime products, lesser than the starting Mersenne number.

Extended Syracuse Algorithm doesn’t count the steps where the powers of two are simplified. Then, excepting M ( 19 ) which in two Extended Syracuse Algorithm steps arrives to a composite number: 1179647 = 7 × 17 × 23 × 431 , and thus can be supposed Collatz compliant, the rest of Mersenne primes in the set above arrive in one or two steps to composite numbers with two factors. The most conspicuous case is the Mersenne M ( 61 ) number tested:

M ( 61 ) = 2305843009213693951 ,

which after the first Extended Syracuse Algorithm step, yields the composite number:

C [ M ( 61 ) ] = 1019 × 3394273320726733 ,

in this last decomposition, the second number is a large prime, but around four orders of magnitude smaller than the initial prime M ( 61 ) . Therefore, one can accept M ( 61 ) as Collatz compliant.

The example of the prime Mersenne number M ( 89 ) is also significative, as one gets via the Extended Syracuse Algorithm a final composite number of three odd prime factors, less than the original prime number:

C [ M ( 89 ) ] = 1856910058928070412348686334 = 5749 × 57347 × 2816163471621326689 .

Follows the last one, the next Mersenne prime, possessing only two odd primes after the first path step, obviating factor 2:

C [ M ( 107 ) ] = 486777830487640090174734030864382 = 13194244031 × 18446597976509719527361 ,

and finally, one finds three odd prime factors in the next Mersenne prime number again:

C [ M ( 127 ) ] = 510423550381407695195061911147652317182 = 190837 × 1062601 × 1258542562146007274238268043 .

In this way, it can be seen how the first Collatz path step on prime numbers, followed by a decomposition of the composite number obtained, yields the product of a considerably smaller prime, so both last Mersenne numbers can be considered Collatz compliant.

An attempt to go beyond the already commented large Mersenne numbers has brought to study the set of the successive Mersenne primes on the list [33] : { M ( 521 ) , M ( 607 ) , M ( 1279 ) } . However, they contain many digits; therefore, publishing the first steps of the corresponding Collatz paths is quite difficult to print.

The behavior of these three Mersenne prime numbers is similar to the already commented ones. Besides some reasonably small prime factors, the computational web procedure yields large composite numbers, which are pretty slow in computer time to be further analyzed. These difficulties altogether have decided the present author to skip them and use the results as a wording example; the potential readers can use the aforementioned web facility [34] to test this kind of mammoth prime number by themselves patiently.

6. Conclusions

After the theoretical setup and the studied practical results, one can conclude that the original Collatz conjecture involving any natural number is contained in the statement: The odd prime number set is Collatz compliant.

One can presume that the set of prime numbers lesser than the one tested are Collatz compliant. Then, the present empirical inductive proof stops the Collatz algorithm path, considering the tested number Collatz compliant whenever it appears: a prime number lesser than the initial or a composite number with all the prime number bases less than the initial prime.

Thus, one can empirically prove the Collatz conjecture in light of the studied prime number cases. The larger prime number thoroughly studied and shown Collatz compliant is the Mersenne number M ( 127 ) . Although partial, sufficient information has also been obtained up to M ( 1279 ) , corresponding to a prime number with 386 digits.

Acknowledgements

The present author wants to acknowledge the critical issues put forward by Prof. Dr. Jacek Karwowski.

The first version of this paper was finished on December 6th, 2022. Because of this time link, it is dedicated to Blanca Cercas.

NOTES

1Note that there one can admit that the indefinite expression 00 is equivalent to 0.

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1] Carbó-Dorca, R. (2020) Boolean Hypercubes, Mersenne Numbers and the Collatz Conjecture. Journal of Mathematical Sciences and Modelling, 3, 120-129.
https://doi.org/10.33187/jmsm.776898
[2] Carbó-Dorca, R. (2022) Boolean Hypercubes, Classification of Natural Numbers, and the Collatz Conjecture. Journal of Mathematical Sciences and Modelling, 5, 80-91.
https://doi.org/10.33187/jmsm.972781
[3] Castro Perelman, C. and Carbó-Dorca, R. (2022) The Collatz Conjecture and the Quantum Mechanical Harmonic Oscillator. Journal of Mathematical Chemistry, 60, 145-160.
https://doi.org/10.1007/s10910-021-01296-6
[4] Carbó-Dorca, R. (2022) Mersenne Numbers, Recursive Generation of Natural Numbers, and Counting the Number of Prime Numbers. Applied Mathematics, 13, 538-543.
https://doi.org/10.4236/am.2022.136034
[5] Balasubramaniam, K. and Carbó-Dorca, R. (2022) Three Conjectures on Extended Twin Primes and the Existence of Isoboolean and Singular Primes Inspired by Relativistic Quantum Computing. Journal of Mathematical Chemistry, 60, 1751-1583.
https://doi.org/10.1007/s10910-022-01364-5
[6] The Collatz Conjecture. Wikipedia.
https://en.wikipedia.org/wiki/Collatz_conjecture
[7] What Is the Importance of the Collatz Conjecture?
https://math.stackexchange.com/questions/2694/what-is-the-importanceof-the-collatz-conjecture
[8] Nowak, H. Collatz Conjecture and Emergent Properties.
https://www.youtube.com/watch?v=QrzcHhBQ2b0
[9] Lagarias, J.C. (1985) The 3x + 1 Problem and Its Generalizations. The American Mathematical Monthly, 92, 3-23.
https://doi.org/10.2307/2322189
[10] Lagarias, J.C. and Weiss, A. (1992) The 3x + 1 Problem: Two Stochastic Models. Annals of Applied Probability, 2, 329-361.
https://doi.org/10.1214/aoap/1177005779
[11] Korec, I. (1994) A Density Estimate for the 3x + 1 Problem. Mathematica Slovaca, 44, 85-89.
[12] Wirsching, G.J. (1998) The Dynamical System Generated by the 3n + 1 Function. Vol. 1681, Springer-Verlag, New York.
https://doi.org/10.1007/BFb0095985
[13] Lagarias, J.C. and Soundararajan, K. (2006) Benford’s Law for the 3x + 1 Function. Journal of the London Mathematical Society, 74, 289-303.
https://doi.org/10.1112/S0024610706023131
[14] Lagarias, J.C. (2010) The Ultimate Challenge: The 3x + 1 Problem. American Mathematical Society, Providence.
[15] Oan, F. and Draayer, J.P. (2019) A Polynomial Approach to the Collatz Conjecture.
[16] Izadi, F. (2019) A New Approach on Proving Collatz Conjecture. Journal of Mathematics, 2019, Article ID: 6129836.
https://doi.org/10.1155/2019/6129836
[17] Barina, D. (2020) Convergence Verification of the Collatz Problem. The Journal of Supercomputing, 77, 2681-2688.
https://doi.org/10.1007/s11227-020-03368-x
[18] Tao, T. (2020) Almost All Orbits of the Collatz Map Attain Almost Bounded Values.
[19] Machado, J.A.T., Galhano, A. and Cao Labora, D. (2021) A Clustering Perspective of the Collatz Conjecture. Mathematics, 9, 314-328.
https://doi.org/10.3390/math9040314
[20] Izadi, F. (2021) Complete Proof of Collatz’s Conjectures.
[21] Gurbaxani, B.M. (2021) An Engineering and Statistical Look at the Collatz (3n + 1) Conjecture.
[22] Stefanov, B.B. (2021) Two-Parameter Generalization of the Collatz Function Characterization of Terminal Cycles and Empirical Results. Online Mathematics OMJ, 3, 19-25.
[23] Pochon, L.-O. and Favre, A. (2021) La Suite de Syracuse, un Monde de Conjectures.
[24] Fabiano, N., Mirkov, N. and Radenovic, S. (2021) Collatz Hypothesis and Planck’s Black Body Radiation. Journal of Siberian Federal University, Mathematics & Physics, 2, 1-5.
[25] Rahn, A., Sultanov, E., Henkel, M., Ghosh, S. and Aberkane, I.J. (2021) An Algorithm for Linearizing the Collatz Convergence. Mathematics, 9, 1898-1930.
https://doi.org/10.3390/math9161898
[26] Kleinnijenhuis, J. and Kleinnijenhuis, A.M. (2020) Pruning the Binary Tree, Proving the Collatz Conjecture.
[27] Schwob, M.R., Shiue, P. and Venkat, R. (2021) Novel Theorems and Algorithms Relating to the Collatz Conjecture. International Journal of Mathematics and Mathematical Sciences, 2021, Article ID: 5754439.
https://doi.org/10.1155/2021/5754439
[28] Zucchini, R. (2022) The Logical Solution Syracuse Conjecture. Mnamon.
[29] Abramovitz, M. and Stegun, I.A. (1965) Handbook of Mathematical Functions. Dover Publishing, New York, 844-869.
[30] Carbó-Dorca, R. (2017) Natural Vector Spaces (Inward Power and Minkowski Norm of a Natural Vector, Natural Boolean Hypercubes) and Fermat’s Last Theorem. Journal of Mathematical Chemistry, 55, 914-940.
https://doi.org/10.1007/s10910-016-0708-6
[31] Carbó-Dorca, R. (2018) Boolean Hypercubes and the Structure of Vector Spaces. Journal of Mathematical Sciences and Modelling, 1, 1-14.
https://doi.org/10.33187/jmsm.413116
[32] Carbó-Dorca, R. (2019) Role of the Structure of Boolean Hypercubes When Used as Vectors in Natural (Boolean) Vector Semispaces. Journal of Mathematical Chemistry, 57, 697-700.
https://doi.org/10.1007/s10910-018-00997-9
[33] List of Known Mersenne Prime Numbers.
https://www.mersenne.org/primes
[34] Alpern, D. (2022) Integer Factorization Calculator.
https://www.alpertron.com.ar/ECM.HTM

Copyright © 2023 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.