# A Numerical Study on the Regularity ofd-Primes via Informational Entropy and Visibility Algorithms

Authors: B. L. Mayer; L. H. A. Monteiro
Journal: Complexity
 (2020)

---

## Abstract

Let ad-prime be a positive integer number with d divisors. From this definition, the usual prime numbers correspond to the particular case d=2. Here, the seemingly random sequence of gaps between consecutive d-primes is numerically investigated. First, the variability of the gap sequences for d∈2,3,…,11 is evaluated by calculating the informational entropy. Then, these sequences are mapped into graphs by employing two visibility algorithms. Computer simulations reveal that the degree distribution of most of these graphs follows a power law. Conjectures on how some topological features of these graphs depend on d are proposed.


---

## Body

## 1. Introduction

Prime numbers, the building blocks of any positive integer, fascinate math lovers [1, 2]. From a purely theoretical perspective, primes are crucial for understanding the properties of numbers [1, 2]. From an applied science perspective, primes have been used in cryptographic keys [3], can be found in the life cycles of cicadas [4], and characterize the energy spectrum of chaotic quantum systems [5].Since 300 BC, the irregular distribution of primes throughout the sequence of natural numbers has been extensively investigated. Giants as Chebyshev, Dirichlet, Eratosthenes, Erdös, Euclid, Euler, Fermat, Gauss, Legendre, and Riemann analyzed this matter [1, 2]. To get some insight on this distribution, the statistical properties of the gaps between consecutive primes [6, 7], second-order gaps (the gaps between these gaps), and higher-order gaps [8, 9] have been examined. The distribution of primes has also been studied by using graphs. For instance, consider that primes are the nodes of a graph. Since any even number can be written as the sum of two primes, a pair of nodes is linked in this graph if it represents the sum of a given even number [10]. In another graph-based approach, the natural numbers are the nodes, and there is a connection between two nodes if they share a common prime divisor [11]. Graphs are also used in this work.Assume that ad-prime is a positive integer with d divisors. Therefore, the usual prime numbers correspond to the case d=2. In this work, the frequency of the gaps between d-primes is computationally analyzed. First, the difference of successive d-primes is calculated for d∈2,3,…,11, and the gap sequences thereby obtained are considered as discrete time series. To evaluate their variability, the informational entropy [12] of these series is computed. In addition, these series are transformed into undirected graphs by applying two visibility algorithms [13, 14]. The degree distribution and the average degree of these graphs are determined and compared. These are the main contributions of this work, which are described in the next section.The aim of this study based ond-primes is to understand how the gap sequences depend on d. The proposed approach can be used to analyze other sequences of numbers found in nature [15], such as the energy levels of atomic nuclei and the quantum space-time structure [16].


## 2. Methodology and Numerical Results

Let ad-prime be defined as a positive integer pd greater than 1 that is divisible by 1, the number itself, and d−2 (smaller) positive integers. Thus, a d-prime has exactly d distinct divisors. For instance, number 12 is a 6-prime because its (six) divisors are 1, 2, 3, 4, 6, and 12. A d-prime with d>2 is usually called a composite number [1, 2]. Note that the 2-primes are just the usual primes. Thus, d-prime is a naive generalization of the concept of prime number.Letpdn be the nthd-prime, with n∈ℕ∗. For instance, p34 is the fourth 3-prime, which is equal to 49. Table 1 presents a list of the first d-primes for d∈2,3,…,11. Let xdn=pdn+1−pdn be the gap between consecutive d-primes. For instance, x51=65 because p52=81 and p51=16. Note that the sequence xdn can be taken as a time series, in which n corresponds to the time variable. Table 2 shows the first numbers of the series xdn for d∈2,3,…,11.Table 1
Sequences ofd-primes, denoted by pdn with n∈ℕ∗, for d∈2,3,…,11.
dpdn22,3,5,7,11,13,17,19,23,29,31,37,41,…34,9,25,49,121,169,289,361,529,841,…46,8,10,14,15,21,22,26,27,33,34,35,…516,81,625,2401,14641,28561,83521,…612,18,20,28,32,44,45,50,52,63,68,75…764,729,15625,117649,1771561,4826809,…824,30,40,42,54,56,66,70,78,88,102,…936,100,196,225,256,441,484,676,1089,…1048,80,112,162,176,208,272,304,368,…111024,59049,9765625,282475249,…Table 2
Sequences of first-order differences of consecutived-primes, given by xpn=pdn+1−pdn with n∈ℕ∗, for d∈2,3,…,11.
dxpn21,2,2,4,2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,…35,16,24,72,48,120,72,168,312,120,408,…42,2,4,1,6,1,4,1,6,1,1,3,1,7,5,4,2,1,4,…565,544,1776,12240,13920,54960,46800,…66,2,8,4,12,1,5,2,11,5,7,1,16,6,1,17,1,…7665,14896,102024,1653912,3055248,…86,10,2,12,2,10,4,8,10,14,2,1,5,4,14,2,…964,96,29,31,185,43,192,413,67,69,219,…1032,32,50,14,32,64,32,64,37,59,32,16,…1158025,9706576,272709624,25654949352,…In order to evaluate the variability of the seriesxd for d∈2,3,…,11, the informational entropy H [12] was computed. This entropy has been calculated, for instance, in investigations on the dynamics of biological [17] and social systems [18]. Its normalized value, denoted by Δ, is given by(1)Δ=HHmax.The entropyH=−∑i=1qpilnpi and its maximum value Hmax=lnq (obtained in the case of pi=1/q for i=1,…,q [12]) are calculated by taking pi as the relative frequency of occurrence of distinct xd. In these expressions, q is the number of distinct values of xd.As the next step, the time seriesxdn were converted into undirected graphs by using two visibility algorithms [13, 14]. These algorithms have been employed, for instance, in the analysis of stock indices [19] and electroencephalography recordings [20]. Here, in the visibility graphs, each node represents a distinct value of xd.Consider thatna<ni<nb. In the natural visibility (NV) graph [13], the nodes corresponding to xdna and xdnb are connected if any intermediate point ni,xdni in the time series satisfies the inequality(2)xdni<xdna+xdnb−xdnani−nanb−na.Thus, these nodes are connected if there is a straight line joiningna,xdna and nb,xdnb in the plot xdn×n, provided that any intermediate point ni,xdni is below such a line. For instance, the four first points of the sequence x3n shown in Table 2 are x31=5, x32=16, x33=24, and x34=72. There is a connection between the nodes corresponding to x3=16 and x3=72 because the intermediate datum x3=24 is below the straight line linking these points in the plot x3n×n, that is, because x33=24<x32+x34−x323−2/4−2=16+72−16/2=44. Also, note that there is not a connection between the nodes x3=5 and x3=24 because x32=16>x31+x33−x312−1/3−1=5+24−5/2=14.5. In this case, the datum (2, 16) is high enough to prevent the data (1, 5) and (3, 24) from seeing each other.In the horizontal visibility (HV) graph [14], the nodes associated with xdna and xdnb are connected if(3)xdna,xdnb>xdni,with na<ni<nb. Thus, these nodes are connected if any intermediate point ni,xdni in the plot xdn×n is below the horizontal line joining na,xdna and nb,xdnb. In the HV graph built from the beginning of the sequence x3n, the nodes corresponding to x3=16 and x3=72 are not connected because x32=16<x33=24; that is, 2,16 and 4,72 cannot see each other because 3,24 is high enough to block their horizontal visibility. Thus, x3=16 and x3=72 are connected in the NV graph, but they are not connected in the HV graph.Numerical experiments were performed by takingn=1,2,…,10000, that is, the first 10,000 d-primes for each value of d. From these 10,000 d-primes, 9999 values of xdn were computed. The values corresponding to n=1,2,9998,9999 were discarded in order to neglect the initial transient n=1,2 and the effects of truncation n=9998,9999.The normalized entropyΔ was computed by using equation (1). As shown in Table 3, Δ=1 for d=5,7, and 11 because there is no repeated value of xd in the corresponding sequences. For d=3 and d=9, Δ≃1; for d even, Δ≈0.7. Hence, for d∈2,3,…,11, d odd favors equiprobable values of pi more than d even.Table 3
Normalized informational entropyΔ for xpn for d∈2,3,…,11.
d234567891011Δ0.7130.9970.6531.0000.7971.0000.6960.9990.7001.000From the gap sequencesxdn for d∈2,3,…,11, undirected visibility graphs were built by using equations (2) and (3). Then, the corresponding degree distributions Pk and the average degree k were determined. Recall that the degree of a node is the number of edges connected to this node [21]. Recall also that the degree distribution expresses how the percentage Pk of nodes with degree k varies with k [21]. Usually, Pk is interpreted as the probability of randomly picking a node with degree k.Figures1 and 2 exhibit the log-log plot of Pk for NV and HV graphs, respectively, for d∈2,3,…,11. Observe that most Pk decay as a power law in these plots. Power laws have been found in the distribution of prime gaps [22] and in a myriad of contexts, such as a psychiatric ward [23] and financial crashes [24]. Here, Pk is proportional to k taken to the power −γ, that is, Pk=Ak−γ, in which A is the proportionality constant. In a log-log plot, logPk=logA−γlogk; thus, the power-law dependence is transformed into a linear relation between logPk and logk. At least as a first approximation, this relation can be taken as linear in most plots shown in both figures; that is, a power-law form for Pk can be considered a plausible model for these plots. Possible exceptions are the NV plots for d=7,11.Figure 1
The degree distribution found in the NV graphs (dots) and the corresponding fitted functionAk−γ (solid line) for d∈2,3,…,11.Figure 2
The degree distribution found in the HV graphs (dots) and the corresponding fitted functionAk−γ (solid line) for d∈2,3,…,11. The dotted line representing Prandk=1/32/3k−2 was included just for comparison.Tables4 and 5 present A, γ, and k for the 20 graphs. The average degree k for the HV graphs is smaller than that for the NV graphs because HV graphs are subgraphs of the corresponding NV graphs. For the NV graphs, k≈6, with the exception of d=5,7,11, which present higher values. For the HV graphs, k>3.90 for d odd and k<3.90 for d even. Note also that the values of A and γ, determined from least square fitting [25], present smaller variability for the HV graphs than for the NV graphs. In addition, for the NV graphs, γ≃1.1; for the HV graphs, γ≃1.7.Table 4
Values ofA and γ of the fitted degree distribution Pk=Ak−γ and the average degree k in function of d for the natural visibility algorithm employed for mapping xdn into graphs.
VisibilitydAγkNatural20.4±0.11.1±0.26.17Natural30.4±0.11.1±0.26.52Natural41.2±0.21.6±0.16.40Natural51.03±0.071.53±0.0514.3Natural60.5±0.11.1±0.26.33Natural70.29±0.031.02±0.0627.7Natural80.4±0.11.1±0.26.28Natural90.12±0.050.6±0.26.66Natural100.4±0.11.1±0.26.23Natural110.19±0.020.91±0.0445.2Table 5
Values ofA and γ of the fitted degree distribution Pk=Ak−γ and the average degree k in function of d for the horizontal visibility algorithm employed for mapping xdn into graphs.
VisibilitydAγkHorizontal21.2±0.31.7±0.33.67Horizontal31.1±0.21.6±0.23.98Horizontal41.7±0.21.9±0.23.47Horizontal51.1±0.21.6±0.23.97Horizontal61.1±0.21.6±0.23.89Horizontal71.1±0.21.6±0.23.96Horizontal81.5±0.21.8±0.23.59Horizontal91.0±0.21.6±0.23.99Horizontal101.1±0.21.6±0.23.84Horizontal111.1±0.21.6±0.23.95By reducing the quantity ofd-primes used in this computational study from n=10,000 to n=5000, the values of Δ, A, γ, and k vary about 1% on average as compared to the numbers presented in Tables 3 and 5. For the results shown in Table 4, larger variations are found for A and γ, the parameters of the fitted straight lines; the variations related to k are also about 1% on average, with the exception of d=11.From the numerical experiments reported in this work, the following relations were found:p3n=p2n2, p5n=p2n4, p7n=p2n6, and p11n=p2n10; thus, 3-primes, 5-primes, 7-primes, and 11-primes are just powers of prime numbers with powers 2, 4, 6, and 10, respectively. However, no relation between p2n and pjn with j=4,6,8,9,10 was found; that is, no relation was found between prime numbers and d-primes when d is not prime.


## 3. Discussion and Conclusion

The absence of a discernible pattern in the sequence of prime numbers has historically hampered the derivation of a formula for correctly generating such a sequence [1, 2]. The analytical generation of d-primes, with d>2, can be an even more challenging task mainly if d is not prime. Here, the distribution of the gaps between d-primes was examined by using a variability measure and two visibility graphs, which were deterministically built.As shown in Table3, Δ≃1 for d=3,5,7,9,11 because repetitions in the sequences of xd are absent or rare; that is, these sequences are aperiodic. In addition, Δ≈0.7 for d=2,4,6,8,10; thus, the variability of the gap lengths for d even is lower than for d odd. Therefore, a possible conjecture is: the normalized entropy Δ distinguishes d even Δ≈0.7 from d odd Δ≃1. In other words, the parity of d determines the value of Δ.As shown in Figures1 and 2 and Tables 4 and 5, most degree distributions Pk of the visibility graphs built from the differences between successive d-primes for d∈2,3,…,11 approximately follow a power law written as Pk=Ak−γ. Fluctuations observed around the fitted straight lines shown in both figures can be effects of the finite size of the gap sequences xdn used in the numerical experiments [26]. Recall that power-law distributions in the connectivity are associated with complex networks known as scale-free [26–28]. Scale invariance in the degree distribution implies self-similarity; that is, Pk of renormalized networks, obtained by a coarse-graining procedure [29], also follows a power law. Note that the value of γ in the NV and HV plots is not a good parameter to show the influence of the value of d on the networks derived from the gap sequences; however, k can highlight this influence: in NV plots, for d that is prime, k increases with d; for d that is not prime, k≈6; in HV plots, k>3.90 for d odd and k<3.90 for d even. Therefore, another possible conjecture is: k in NV plots distinguishes d that is prime from d that is not prime; k in HV plots distinguishes d odd from d even.It is well known that, for HV graphs obtained for periodic sequences of periodT (without repeated number within a period), the average degree is given by k=41−1/2T [30]. As a consequence, for aperiodic series, k=4 (because T⟶∞). According to Table 5, this is the approximate value of k found for d-primes with d odd, which is in agreement with the value of Δ presented in Table 3. It is also well known that, for an uncorrelated random sequence, the HV graph has Prandk=1/32/3k−2 [30]. Therefore, deviations from this degree distribution reveal that the studied sequence was not generated by an uncorrelated random process. The straight line corresponding to Prandk is shown as a dotted line in Figure 2. Note that Pk for d-primes has a smaller slope than the slope of Prandk. This smaller slope and k=4 can be features of chaotic sequences [30].A final comment about the generation ofd-primes by deterministic equations: when d is prime, then pdn=p2nd−1; however, the way of obtaining pdn when d is not prime is not yet evident. Also, a formula to generate p2n (the exact sequence of primes) remains to be found.



---

*Source: 1480890-2020-09-10.xml*