Abstract
We present here a new conjecture for the nature of the Mersenne prime numbers by connecting it with the CollatzKakutani problem. By introducing a natural path length on the basis of the CollatzKakutani tree, we conjecture that this path length of a Mersenne prime from the root of the CollatzKakutani tree is approximately proportional to the index of the Mersenne prime. We also discuss diﬀerence of behaviors between Mersenne numbers and Mersenne primes.
Prime numbers have attracted mathematically oriented minds. They are fountains of the interesting problems which are left unresolved to the present. As well as prime numbers, natural numbers themselves sometimes show unexpected behaviors in spite of their simple appeal. In this note, we would like to present a simple property arising from the combination of two unsolved problems in number theory; the Mersenne prime numbers and the CollatzKakutani conjecture. Namely, we show that there exists an approximate linear relation between an index of the Mersenne prime and its CollatzKakutani path length, both of which are deﬁned in the next section.
Let us start with a brief descriptions of the Mersenne primes and the CollatzKakutani conjecture[1]. A Mersenne number is a positive integer given by
$${M}_{n}={2}^{n}1,$$where $n$ is a positive integer, called “index”. A Mersenne prime is a Mersenne number that is prime. It has been shown that if ${M}_{n}$ is a Mersenne prime, $n$ must be prime. However, the converse is not true. In fact, only fortyseven Mersenne primes have been found up to date with the largest one given when $n=43,112,609$. This is also the largest known prime number. There are many fundamental questions left unresolved such as whether there are inﬁnitely many Mersenne primes. The behaviors of Mersenne primes are irregular and unpredictable as seen in other types of prime numbers. Therefore, the recent discoveries of the Mersenne primes were achieved with the help of massively distributed computers, and the eﬀort for ﬁnding new Mersenne primes has been made continuously [2]. The Mersenne primes are known for their relationships with the perfect numbers, and they are also applied to create pseudorandom number generators [3].
The CollatzKakutani conjecture is also one of the unsolved problems in number theory. This conjecture is a halting problem that the following operations will stop for an arbitrary positive number. Consider a positive integer $X$.
If $X$ is odd, $3X+1$ is the next integer.
If $X$ is even, $X\u22152$ is the next integer.
If we repeat this process, it will eventually reach the halting state $X=1$ for all positive integers. For example, if we start from $X=7$, we have a sequence as
$$7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1.$$
This process can be visualized as the CollatzKakutani tree as shown in Fig. 1A. The conjecture states that this tree covers all the positive integers. Even though this conjecture is unsolved, it is generally believed as true from arguments through probability theories and through computational veriﬁcations.
Let us introduce the “CollatzKakutani path length” $D\left(X\right)$ for a number of steps for $X$ to reach $X=1$ through the above operations, i.e., a number of operational steps needed to reach $1$ (“the root”) on the CollatzKakutani tree. For example, $D\left(7\right)=16$. The relationship between $X$ and $D\left(X\right)$ is highly irregular and no simple law for the path length is found^{1}. As a result, the plot of $D\left(X\right)$ versus $X$ produces a irregular graph as shown in Fig. 1B. While the general relationship between $X$ and $D\left(X\right)$ is unknown, there are some trivial relations such as $D\left({2}^{n}\right)=n$. Note that, the number ${2}^{n}$ is just one larger than the Mersenne number ${M}_{n}={2}^{n}1$.
Our main ﬁnding to report is the fact that a path length of a Mersenne prime is approximately proportional to its index for large n, namely,
$$D\left({M}_{n}\right)\approx 13.45n.$$  (1) 
This is shown in Fig. 2, which we were able to compute up to the 38th Mersenne prime, ${M}_{p}\left(38\right)={M}_{6972593}$. The behavior of the path length $D$ is non monotonic for small indices, e.g., $D\left({M}_{89}\right)>D\left({M}_{107}\right)$. We expect, however, beyond $n=107$, the path length increases monotonically with $n$ for the Mersenne primes. Also, there seems no regular path to reach the root of the tree, $X=1$. For example, we have examined the path for two nearby Mersenne primes, ${M}_{p}\left(16\right)={M}_{2203}$ and ${M}_{p}\left(17\right)={M}_{2281}$. While they have the path length $D$ of approximately $30,000$, they share the last 16 steps, namely,
$22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,$ and $1$.
The relations between indices of the Mersenne primes and their path lengths are summarized in Table 1.
Number  Indices  $D\left(X\right)$  $D\left(X\right)\u2215n$

1  2  7  3.5 
2  3  16  5.33333 
3  5  106  21.2 
4  7  46  6.57143 
5  13  158  12.1538 
6  17  224  13.1765 
7  19  177  9.31579 
8  31  450  14.5161 
9  61  860  14.0984 
10  89  1454  16.3371 
11  107  1441  13.4673 
12  127  1660  13.0709 
13  521  6769  12.9923 
14  607  8494  13.9934 
15  1279  17094  13.3651 
16  2203  29821  13.5365 
17  2281  30734  13.4739 
18  3217  43478  13.5151 
19  4253  55906  13.1451 
20  4423  60716  13.7273 
21  9689  129608  13.3768 
22  9941  134345  13.5142 
23  11213  153505  13.6899 
24  19937  265860  13.335 
25  21701  293161  13.5091 
26  23209  312164  13.4501 
27  44497  598067  13.4406 
28  86243  1158876  13.4373 
29  110503  1482529  13.4162 
30  132049  1771117  13.4126 
31  216091  2906179  13.4489 
32  756839  10197081  13.4732 
33  859433  11568589  13.4607 
34  1257787  16927967  13.4585 
35  1398269  18807193  13.4503 
36  2976221  40055567  13.4585 
37  3021377  40663017  13.4584 
38  6972593  93778449  13.4496 
This linear behavior can be understood by the following heuristic arguments. Suppose $N$ is a large random number. The standard heuristic arguments for the path length for $N$ gives
$$D\left(N\right)\approx \left(3\u2215\left(ln4\u22153\right)\right)lnN.$$  (2) 
A Mersenne number ${2}^{n}1$ becomes $3\times {2}^{n1}1$ after two steps in CollatzKatutani tree. Therefore, A Mersenne Number ${2}^{n}1$ becomes ${3}^{n}1$ after $2n$ steps. If we consider the number $N={3}^{n}1\sim {3}^{n}$ to be a large random number for large $n$, then the path length of the number is given by
$$D\left({3}^{n}1\right)\approx \left(3\u2215\left(ln4\u22153\right)\right)nln3.$$  (3) 
Finally, we obtain the heuristic estimation of the path length of the Mersenne number to be
$$D\left({2}^{n}1\right)\approx 2n+\left(3\u2215\left(ln4\u22153\right)\right)nln3\approx 13.45652n,$$  (4) 
which is consistent with our numerical results [4, 5, 6]. This arguments implies that our ﬁnding is true not only for the Mersenne primes, but also for the Mersenne numbers. Our main conjecture, however, is that this linear relationship for the Mersenne primes are better than that for the general Mersenne numbers, or other general sequence of integers.
In order to show the diﬀerence between the Mersenne numbers in general and the Mersenne primes, the ratio of the path length to the index, $D\left({M}_{n}\right)\u2215n$, is plotted against $n$ in Fig. 2B. If the distance increases linearly to the index, then $D\left({M}_{n}\right)\u2215n$ becomes a constant. Figure 2B shows that the Mersenne primes show better linearity than the general Mersenne numbers.
To be more quantitative, we have performed the following statistical analyses. We have chosen thirteen Mersenne primes from the $2{6}^{\text{th}}$ (${M}_{p}\left(26\right)={M}_{23,209}$) to the $3{8}^{\text{th}}$ (${M}_{p}\left(38\right)={M}_{6,972,593}$), and computed the mean and the variance of $D\left({M}_{n}\right)\u2215n$. Let us call the prime indices of the Mersenne primes as the Mersenne prime indices. We compare the result with that from the following set of thirteen points approximately in the same interval.
A) Thirteen prime indices which is the next smallest to thirteen Mersenne prime indices. We note the Mersenne numbers associated with this set is not prime numbers themselves.
B) Thirteen indices which are near the midpoint of two successive Mersenne prime indices.
C) Thirteen indices which are twice the Mersenne prime indices. These are all even numbers. We have selected some which are close to the Mersenne prime indices.
D) Thirteen indices which is on the least squre bestﬁt line based on the heuristics that, given the $k$th Mersenne prime ${M}_{p}\left(k\right)$, the plot of ${log}_{2}\left({log}_{2}\left({M}_{p}\left(k\right)\right)\right)$ versus $k$ lies approximately on the straight line (Figure 3). We have selected some which are close to the Mersenne prime indices [7].
The results of these comparison are shown in Table 2.
Set  Indices  $D\left(X\right)$  E$\left[D\left(X\right)\u2215n\right]$  Var[$D\left(X\right)\u2215n$]

Mersenne Prime  23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593  312164, 598067, 1158876, 1482529, 1771117, 906179, 10197081, 11568589, 16927967, 18807193, 40055567, 40663017, 93778449  13.4473  0.0002977 
A  23227, 44501, 86249, 110527, 132059, 216103, 756853, 859447, 1257827, 1398281, 2976229, 3021407, 6972607  312182, 598071, 1158882, 1482553, 1771127, 2906191, 10197095, 11568603, 16928007, 18807205, 40055575, 40663047, 93778463  13.4460  0.0003194 
B  22455, 33853, 65370, 98373, 121276, 174070, 486465, 808136, 1058610, 1328028, 2187245, 2998799, 4996985  299801, 457438, 875438, 1327329, 1633743, 2344640, 6524449, 10868120, 14246657, 17876449, 29428265, 40364153, 67195624  13.4485  0.0017853 
C  22426, 43402, 46418, 88994, 172486, 221006, 264098, 432182, 1513678, 1718866, 2515574, 2796538, 5952442  299772, 584422, 627877, 1201650, 2320161, 2974984, 3556035, 5828307, 20384499, 23124964, 33827530, 37632788, 80085173  13.4618  0.00132591 
D  20160, 43644, 64216, 94484, 139021, 204550, 442830, 651562, 958682, 1410567, 2075452, 3053739, 4493150  270868, 587280, 866299, 1265873, 1871202, 2748585, 5947053, 8769774, 12911249, 18991590, 27939124, 41095221, 60441877  13.4515  0.000502943 
The data summarized in Table. 2 show that the path lengths of the Mersenne primes have the smaller variance than other sets. However, this diﬀerence is not enough to single out a Mersenne prime index.
In spite of the above, we look more detail into this property. We have examined the plot of $D\left(X={2}^{n}1\right)$ versus $n$ more closely and noted that they are composed of a collection of “ﬂat” regions with jumps like a staircase. Correspondingly, the plot of $D\left(X\right)\u2215n$ versus $n$ becomes collection of stripes, which interestingly appears near parallel. They are plotted in Figure 4. These plots are made for the sampled prime indices near three Mersenne prime indices, $23209,110503,216091$ which give $2{6}^{\text{th}}$, $2{9}^{\text{th}}$, and $3{1}^{\text{th}}$ Mersenne primes respectively. It is also interesting that there are occasional “overlaps” of “stair steps”.
The nature and mechanism of these properties appeared in Figure 4 need to be studied further. We, nevertheless, conjecture that these qualitative behavior will continue to larger Mersenne numbers, and the Mersenne prime appears with its $D\left(X\right)\u2215n\approx 13.45$. Unfortunately, again, this is clearly not suﬃcient to select out the Mersenne primes. If this conjecture is true, however, we can heuristically rule out points that are further away from the horizontal line of $D\left(X\right)\u2215n\approx 13.45$ from candidates of the Mersenne primes.
We have used the CollatzKakutani tree as a provider of “length” for natural numbers, and obtained a conjecture for the Mersenne primes. This may be yet another example where prime numbers can give rise to an emergence of unexpected order, such as Ulam Spiral [8, 9].
Though the reason behind such simple behavior is left unclear, this approach of using the CollatzKakutani tree can be extended to other types of set of numbers known for irregularities, possibly leading to interesting insights.
Acknowledgments Authors would like to thank Dr. Masaru Suzuki, Dr. Atsushi Kamimura, and Shigenori Matsumoto for useful discussions. T.O. is also aﬃliated with Sony Computer Science Laboratories in Tokyo, and would like to thank Emeritus Prof. Yuji Ito of Keio University, for his account on his advisor, late Prof. Shizuo Kakutani of Yale University.
[1] The Math Forum Internet Mathematics Library, available at http://mathforum.org/library/.
[2] Great Internet Mersenne Prime Search:GIMPS, available at http://www.mersenne.org/default.php/.
[3] M. Matsumoto, T. Nishimura, Mersenne twister: A 623dimensionally equidistributed uniform pseudorandom number generator, ACM Trans. on Modeling and Computer Simulations 8 (1998) 3.
[4] This heuristic arguments of this paragraph is provided by one of the anonymous reviewers.
[5] J. C. Lagarias, The $3x+1$ Problem and Its Generalizations, Amer. Math. Monthly 92 (1985) 3
[6] A. V. Kontorovich, J. C. Lagarias, Stochastic Models for the $3x+1$ and $5x+1$ Problems, arXive:09101944 [math.NT] (2009)
[7] M. R. Schroeder, Where Is the Next Mersenne Prime Hiding? Mathematical Intelligencer 5 (1983) 31
[8] M. L. Stein, S. M. Ulam, M. B. Wells, A Visual Display of Some Properties of the Distribution of Primes, Amer. Math. Monthly 71 (1964) 516
[9] M. L. Stein, S. M. Ulam, An Observation on the Distribution of Primes, Amer. Math. Monthly 74 (1967) 43.
Shirokanedai Institute, Tokyo, Japan.
ohriatoru@gmail.com
The Institute of Solid State Physics, The University of Tokyo, Kashiwa, Japan.