Mersenne Numbers, Recursive Generation of Natural Numbers, and Counting the Number of Prime Numbers

Ramon Carbó-Dorca

Institut de Química Computacional i Catàlisi, Universitat de Girona, Campus de Montilivi, Girona (Catalonia), Spain.

DOI: 10.4236/am.2022.136034                

Abstract

A simple recursive algorithm to generate the set of natural numbers, based on Mersenne numbers: M_N = 2^N – 1, is used to count the number of prime numbers within the precise Mersenne natural number intervals: [0; M_N]. This permits the formulation of an extended twin prime conjecture. Moreover, it is found that the prime numbers subsets contained in Mersenne intervals have cardinalities strongly correlated with the corresponding Mersenne numbers.

Keywords

Mersenne Numbers, Recursive Generation of Natural Numbers, Mersenne Natural Number Intervals, Counting the Number of Prime Numbers in Mersenne Natural Intervals, Correlation between Prime Number Set Cardinalities and Mersenne Numbers, Extended Twin Prime Number Conjecture

1. Mersenne Intervals and Natural Subsets

Previous work described an uncomplicated algorithm to recursively generate natural numbers [1], which was based on intervals guided by Mersenne numbers [2] themselves.

Here it will be shown that the number of primes contained in the Mersenne intervals is strongly correlated with the associated Mersenne numbers.

Mersenne intervals are defined as natural number subsets $S_N\subset N$ starting with zero, considered here as a natural number, and ending in the N-th Mersenne number: $\forall N\in N:{\text{M}}_N=2^N-1$.

That is, one can define the Mersenne sets: $S_N=\left\{0;{\text{M}}_N\right\}$, as sets of natural numbers contained within the Mersenne intervals: $\left[0;{\text{M}}_N\right]$. Considering this description, one can easily write recursive equality like:

$S_{N+1}=S_N\cup \left(2^N\oplus S_N\right)$, (1)

where the symbol: $2^N\oplus$ means the N-th power of two, $2^N$, is summed up to every element of the Mersenne set $S_N$.

The cardinality of Mersenne sets might be defined as: $Card\left(S_N\right)=2^N$ and therefore: $Card\left(S_{N+1}\right)=2^{N+1}=2Card\left(S_N\right)$ ; that is, the number of elements in every Mersenne set doubles when augmenting the Mersenne order: $N\to N+1$. Also, the first $2^N$ numbers of the Mersenne set $S_N$ are those of the Mersenne set $S_{N-1}$.

2. Number of Prime Numbers within a Mersenne Set

Within any Mersenne set $S_N$, there is present a subset of prime numbers: $P_N\subset S_N$. Taking into consideration the set of prime numbers as a subset of natural numbers: $P\subset N$, then one can also write: $P_N\subset P$. Also, it seems plausible to say that the cardinality of such prime number subsets augments with the Mersenne order.

To obtain empirical proof of this prime cardinality behavior, a sequence of the number of primes in increasing Mersenne intervals has been calculated (including the prime number 2) yielding the following arrangement:

Sequence 1. Mersenne orders (N) and cardinalities of prime number subsets $Card\left(p_N\right)$ contained within Mersenne $S_N$ sets

(1) 0; (2) 2; (3) 4; (4) 6; (5) 11; (6) 18; (7) 31; (8) 54; (9) 97; (10) 172;

(11) 309; (12) 564; (13) 1028; (14) 1900; (15) 3512; (16) 6542; (17) 12,251;

(18) 23,000; (19) 43,390; (20) 82,025; (21) 155,611; (22) 295,947;

(23) 564,163; (24) 1,077,871; (25) 2,063,689; (26) 3,957,809; (27) 7,603,553;

(28) 14,630,843; (29) 28,192,750; (30) 54,400,028; (31) 105,097,565;

(32) 203,280,221;

Where the numbers between parentheses in Sequence 1 are the Mersenne orders (N), and the numbers next are the cardinality of prime number subsets: $Card\left(P_N\right)$, also each numeric pair: $\left(N\right)Card\left(P_N\right)$ is separated by a semicolon.

As it is expected, the number of primes grows as one considers larger natural Mersenne intervals. Here, such prime set cardinality increase can be seen roughly under the doubling (~1.9) of the previous value in Sequence 1.

Also, as the Mersenne number order increases, the number of primes becomes roughly an order of magnitude lower than the corresponding Mersenne number. For example:

$Card\left(P_{23}\right)=564163\iff {\text{M}}_{23}=2^{23}-1=\text{8388607}$.

The number of prime numbers less or equal to a given natural number n: $\pi \left(n\right)$, see for example reference [3], can be used here to connect such step function with the present description; in this manner, one can write: $Card\left(P_N\right)=\pi \left({\text{M}}_N\right)$.

2.1. Structure of Prime Numbers in Terms of Powers of 2

Furthermore, one must be aware of the fact present in Equation (1) consisting in that every element of the subset $T_N=2^N\oplus S_N$ is constructed as:

$\forall t_{N;I}\in T_N:\exists s_{N;I}\in S_N\Rightarrow t_{N;I}=2^N+s_{N;I}$ (2)

then it is also true that the primes contained in the set $T_N$, if any, are expressed in the same manner, that is:

$\forall p_{N;I}^T\in P_N\wedge p_{N;I}^T\in T_N:\exists s_{N;I}\in S_N\Rightarrow p_{N;I}^T=2^N+s_{N;I}$. (3)

This is an expression showing that some prime numbers might have the form:

$\exists p\in P\wedge \exists s,N\in N:p=2^N+s$, (4)

but possibly also occurs that in Equation (3) the natural number, providing the new prime could be prime itself. Therefore, in various cases, two primes belonging to a given Mersenne interval they might be separated by $2^N$ units:

$\exists \left\{p,q\right\}\in P\to p=2^N+q$. (5)

Equation (4) becomes in the present natural number construction a general feature common to all natural numbers, for example: $31=16+15=2^4+15$ ; but also of some prime numbers, because the parent equation represents a restricted relation, which might be sometimes present, like in: $13=8+5=2^3+5$. The well-known twin primes, for example, the pair: $\left\{17,19\right\}$, are a particular case of this general possibility, as shown in Equation (5), where $N=1$.

But one can easily observe the existence of such primes separated by a $2^N$ gap, just picking up a prime q and calculating the sequence: $\left(N=1,2,\cdots \right):p_N=2^N+q$ ; further observing that for specific values of the power: $N\in \left\{N_I|I=1,2,\cdots \right\}$, several primes can be collected in the set: $\left\{p_{N_I}|I=1,2,\cdots \right\}\subset P$.

As a final example, one can consider that some Mersenne numbers are prime, see for instance the web page devoted to them [4]. Then one must be aware that in general, prime or not, Mersenne numbers possess the property already discussed because they can be also expressed in general by recursive equality:

${\text{M}}_N=2^N-1=2^{N-1}+\left(2^{N-1}-1\right)=2^{N-1}+{\text{M}}_{N-1}$. (6)

2.2. Extended Twin Prime Number Conjecture

Several contributions about conjectures related to the prime numbers’ gap structure have been posted [5] [6]. The use of the proposed recursive generation of natural numbers as previously described here resumed in Equation (5) suggests that there might be possible, in addition to the infinite number of twin primes whose gap is 2, to propose a general conjecture aiming at the existence of an indefinite number of extended twin primes whose gaps could be associated to 2^N. Such a possible occurrence will be further studied elsewhere. A recently posted work deepens the information in this area [7].

2.3. Shannon Entropy

Within Sequence 2, which can be found below, it is also present the Shannon entropy ${\text{S}}_N$ of the prime numbers contained in a Mersenne interval ${\text{M}}_N$ when the cardinality of the Mersenne interval is also considered.

That is, the relative frequency $f_{P;N}$ of finding a prime in a Mersenne interval ${\text{M}}_N$ can be written as: $f_{P;N}=Card\left(P_N\right)2^{-N}$ and the relative frequency of finding a composite number can be written as: $f_{\neg P;N}=1-f_{P;N}$. Therefore, the total Shannon entropy can be computed as:

${\text{S}}_N=-\ln \left(f_{P;N}\right)-\ln \left(f_{\neg P;N}\right)$. (7)

3. Number of Primes and Mersenne Numbers Relationship

One can consider an empirical way to obtain a relationship between the number of primes contained in Mersenne intervals and the Mersenne numbers. In the following lines, there is shown a plausible way to obtain such a connection.

Surprisingly enough, in preliminary tests, the prime cardinalities of Sequence 1, presented some polynomial-exponential structure when drawn in front of the Mersenne orders. The natural logarithms of the cardinalities of Mersenne prime subsets presented a good correlation with the Mersenne orders too.

However, after some in-depth study, the best correlation has been found when the following equation:

${\left[\ln \left(Card\left(P_N\right)\right)\right]}^Q=A{\left[\ln \left(2^N-1\right)\right]}^P+B$ (8)

has been iteratively optimized for the parameters: $\left\{A,B,P,Q\right\}$ with a non-linear least-squares procedure recently described [8]. The results of such a non-linear fitting are as follows. After a maximum of 10 iterations to search for the optimal parameters, an assorted number of the computed Mersenne intervals are shown in the following sequence:

Sequence 2. Results obtained in several assorted Mersenne intervals for the optimal parameters of Equation (8): {A, B, P, Q}, plus the regression coefficient R, the quadratic error ε⁽²⁾, and the Shannon entropy S.

N = 12 A = 0.53985 B = 0.72053 P = 1.31098 Q = 1.15804

R = 0.99979 ε⁽²⁾ = 0.00248 S = 0.58868

N = 14 A = 0.52737 B = 0.72780 P = 1.28485 Q = 1.12001

R = 0.99988 ε⁽²⁾ = 0.00179 S = 0.54164

N = 20 A = 0.53929 B = 0.72081 P = 1.32529 Q = 1.17103

R = 0.99997 ε⁽²⁾ = 0.00158 S = 0.43374

N = 24 A = 0.54876 B = 0.70343 P = 1.31822 Q = 1.17103

R = 0.99998 ε⁽²⁾ = 0.00151 S = 0.38351

N = 30 A = 0.56646 B = 0.66466 P = 1.30737 Q = 1.17235

R = 0.99999 ε⁽²⁾ = 0.00200 S = 0.32799

N = 32 A = 0.57275 B = 0.65067 P = 1.32472 Q = 1.19384

R = 0.99999 ε⁽²⁾ = 0.00242 S = 0.31318

Both, the regression coefficient parameter and the quadratic error can be further refined by transforming the involved logarithmic vector elements into the unit interval, according to a previous study [9]. This possibility will be analyzed elsewhere.

4. Concluding Remarks

Thus, it seems out of the question that there appears a computational high relationship between the cardinality of the prime number Mersenne subsets, found within the Mersenne sets themselves, and the Mersenne numbers acting as upper bounds of the Mersenne intervals.

Such strong empirical functionality is well-grounded, due to the obtained high correlation coefficient in the company of the present small quadratic error.

Interestingly enough, the Shannon entropy of Mersenne intervals diminishes as the cardinality of the interval increases. The meaning of this entropic information behavior could be associated with the fact consisting on the presence of primes within Mersenne intervals appears more ordered (or less random), as the cardinality 2^N of the Mersenne intervals grows.

As a collateral finding, a potential conjecture about the existence of extended twin primes has been noted.

Willingness to Share the Results

The author will share the results and programs of this paper upon reasonable demand.

Acknowledgements

The author wants to warmly acknowledge Professor’s Krishnan Balasubramaniam sharp remarks that permitted a refined accurate new version of this manuscript. This work is dedicated to Blanca C. on the occasion of her anniversary.

Conflicts of Interest

The author states that there is no conflict of interest related to this work.

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]	Weisstein, E.W. (n.d.) Mersenne Number. MathWorld—A Wolfram Web Resource. https://mathworld.wolfram.com/MersenneNumber.html
[3]	Derbyshire, J. (2004) Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics. A Plume Book, Penguin Group.
[4]	https://www.mersenne.org/primes/
[5]	Goldston, D.A., Pintz, J. and Yildirin, C.Y. (2005) Primes in Tuples I. arXiv:math\0508185v1 [math.NT] 10 Aug.
[6]	Maynard, J. (2019) Gaps between Primes. Proceedings of the International Congress of Mathematicians, 345-361. https://doi.org/10.1142/9789813272880_0057
[7]	Balasubramaniam, K. and Carbó-Dorca, R. (2022) A Conjecture on Extended Twin Primes. Research Gate. https://doi.org/10.13140/RG.2.2.22432.25600
[8]	Carbó-Dorca, R. (2022) Shadows’ Hypercube, Vector Spaces, and Non-Linear Optimization of QSPR Procedures. Journal of Mathematical Chemistry, 60, 283-310. https://doi.org/10.1007/s10910-021-01301-y
[9]	Carbó-Dorca, R. (2019) Universal Transformation and Non-Linear Connection between Experimental and Calculated Property Vectors in QSPR. Journal of Mathematical Chemistry, 57, 1075-1087. https://doi.org/10.1007/s10910-019-01009-0