Click here to Skip to main content
16,021,041 members
Articles / Programming Languages / C++

Prime Number Distribution Sequence

Rate me:
Please Sign up or sign in to vote.
2.67/5 (16 votes)
26 Feb 2019CPOL24 min read 36K   5   33
The following paper is an in-depth analysis of prime numbers, and it also provides the first-ever analytical representation of prime numbers. This paper also presents one of the most decisive tests for determining whether infinitely many twin primes exist.

1. Introduction

The erratic existence of prime number gaps has mesmerized mathematicians and enthusiasts alike for centuries. Going back as early as the late 18th century, eminent mathematicians have made numerous attempts to formulate a prime counting function \(P(N)\), such as Gauss’s early approximation oef.

Currently, we speak of the prime number theorem, which suggests an asymptotic form for the number of primes less than some integer. However, the formulaic representation of the prime number theorem remains one of the largest open problems in the world of mathematics.

Whilst investigating the distribution of primes, one would of course compile the number of primes less than a certain given list of integers, and, amid the \(N\) vs. \(P(N)\)observations, one should arrive at an approximation formula. During Gauss’s later investigations, he noticed that the density of primes in a chiliad decreased approximately as, in turn leading Gauss to revise earlier approximations, e.g.,

$ P(N) \approx Li(N) = \int_{N}^{2} \frac {dx}{ln n}$

For the methods of correlation of \(N\) vs. \(P(N)\), perhaps the most discussed conjecture is the Riemann hypothesis. Proposed by Bernhard Riemann in 1859,the Riemann hypothesis is a conjecture that suggests the non-trivial zeros of the Riemann zeta function all have real part 1/2.However, we shall not refer to or quote the Riemann hypothesis any further in this paper.

Albeit, no single function or formulae that correctly evaluates \(P(N)\) for all \(N < ∞ \) appears to exist. Furthermore, the ever growing approximations and emerging hypotheses pertaining to the prime number theorem seem to be unprovable.

At this point, we will describe the situation as that of a ‘headache’ and consider our options for dealing with it.

In modern day analyses, given the vastly increased computing efficacy on hand, we study larger \(N\), and this usually leads us to modify the Gaussian formulation and/or other similar prime density functions. That is to say, we do our share of the ‘aspirin’ approach. Nonetheless, the headache remains. In this paper, we are, however, free to invent, and we can stop the ‘aspirin’ approach; we abstain from antiquated approaches, such as basic interpolations of Gauss, Legendre, Riemann and others, and can start afresh.

Consequently, noteworthy results follow. We see that a prime number distribution sequence exists and computes the exact count of prime numbers less than and equal to all integers \(N\), for all \(N < ∞,\) making it possibly the first and only ever formulation for the \(P(N)\) calculation. Furthermore, in contrast to the complex variable Riemann zeta function, which is a convergent infinite series, the computations for the prime counting function \(P(N) \)formulated here require fewer than \(N\) steps yet provide accurate results.

In general, the reader will be confronted with questions. Should we have expected an order in the prime numbers or a single analytical function to return true \(P(N)\) values? Also, why is it that a problem description simply defined as the prime number theorem finds its way into complex variable analysis, such as the Riemann zeta function?

The analysis presented here will be new to hardened analysts familiar with the Gaussian or Riemann zeta function formulations that have dominated the history of this problem. With this in consideration, we will be tackling the original approach presented in this paper in its simplest terms.

We will go on to show that the distribution of prime numbers may be best visualized in two-dimensional space. Additionally, it is perhaps here where we can draw the most resemblance between our analysis and the Riemann complex plane analysis.

We will create some controversy. We question whether the number 2 is really a prime number. However, we will make it easier for those who prefer to verify the equations by means of coding, and thus we provide a set of source code at the end of the paper.

We will conclude this paper with a decisive test for determining whether infinitely many twin primes exist.

2. Counting prime numbers less than a positive integer N > 1

Consider computing the count of all prime numbers, less than and including some input integer, \(N\), that is greater than \(1\). We ignore divide and count testing, computational memory sieving solutions or other approximation techniques within our analysis. Suppose, however, that we invent a simplified prime number model whereby we replace the division by divisors model that applies to all integers less than some given \(N\)and that we limit the division to 2 only. Thus, under this proposition, the whole number \(9\), for instance, where \(N ≥ 9\), can be classified as a prime number and counted for \(P\).

Let us examine this further with an example. If we have some input integer \(N\), say, \(10\), then the prime count will be \(5\), i.e., including the integer \(1\), our primes are \(1\), \(3\), \(5\), \(7\) and \(9\). Similarly, if the input \(N\) is \(9\), then there will again be the same \(5\) prime numbers.

Therefore, we can deduce a formula for the prime counting function P, where our simplified model applies and the input integer is greater than\(1\), as follows,

$ P_|2| (N) = [N / 2] + R$
Equation 1

where,

\(P \)is the count of primes; the subscript \(|2|\) denotes the division limit is imposed as \(2\),

\([ ]\) is the floor operation,

and \(R\) is the residue equal either to \(0\) or \(1\)as determined by,

\(R = 0\) if \(((N / 2) - [N / 2]) = 0\) or \(R = 1\) if \(((N / 2) - [N / 2]) > 0\).

Therefore, we prove that we can simply compute the count of primes by means of a prime counting function and we can further our technique. However, before we do so, we shall revisit the definition of prime numbers.

3. Vigorous definition of prime numbers

The conventional definition of a prime number, or simply a prime, is given as "a positive integer greater than 1 that has no positive divisors other than 1 and itself". This definition, therefore, explicitly excludes \(1\) as being the lower boundary of the prime number test. The equation for \(P{|2|}\) provided by equation [1] should therefore take this omission into account, giving,

$ P_{|2|} (N) = [N / 2] + R - 1$
Equation 2

Consequently, \(P_{|2|}(N)\) will be equal to \(4\), as will\(P_{|2|}9\), now yielding the primes \(3\), \(5\), \(7\) and \(9\).

We know that the natural number \(2\) is universally accepted to be a prime number. Let us, however, reestablish whether two is a prime number. On this occasion, we can safely use equation [2] when evaluating \(P(2)\).

Following from the conventional definition of primes, \(2\) is greater than \(1\), making it eligible for prime testing. However, \(2\) cannot be divide-tested by \(2\), as it is equal to itself, i.e., it is the upper boundary of the prime number test. Therefore, when the divisors \(1\) and \(2\) are taken away from the prime testing of the value \(2,\) we are not left with any other whole number to subject \(2\) to for any specific prime testing. Therefore, one point of argument can be that \(2\) is not a prime number because, by definition, it has removed itself from the analysis altogether.

Let us look at an alternative argument by considering the modified \(P_{|2|}(N)\) in equation [2]; when we input the integer \(2\), we obtain the following result,

$ P_{|2|} (2) = [2 / 2] + 0 - 1 = 0$
Equation 3

Therefore, the output of equation [3] suggests that there are no primes between \(1\) and \(2\) inclusive. Therefore, it may be claimed that \(2\) is not a prime number and that there are no primes less than and including \(2\).

Whilst the basis for rejecting the whole number \(2\) as a prime number is compelling enough, in this paper, however, overall \(P\) values will count the integer \(2\) as a prime number for the sake of historical conformity. Furthermore, except where stated otherwise, in the computation of the \(P\) value for a given natural number \(N\), \(N\) will also be subjected to prime testing and factored to \(P\) value provided that \(N\) itself is a prime number.

4. Extension of the basic P|2| formula

We shall now show that the \(P_{|2|}\) formulation given by equation [2] can be extended to larger integers, consequently leading to the derivation of an orderly series that allows us to compute precise \(P(N)\) values for all input \(N\)→∞.

We advance our analysis with the extension of division to the divisor 3 in the simplified prime number analysis introduced earlier. Now, let us examine the impact the divisors \(2\) and \(3\) have on the count of \(P\). We can call the new \(P\) value \(P_{|2, 3|}\) and seek to evaluate by formulating as before.

When we prime tested integers less than some given \(N\) in accordance with our simplified \(P|2|\) model, it was obvious that, starting with \(3\), every alternating number was a prime number,

2 3 4 5 6 7 8 9 10 11 12…
2   2   2   2   2   2…

As we evolve our prime number analysis to \(P|2, 3|\), we now have,

2 3 4 5 6 7 8 9 10 11 12…
2 3 2   2   2 3 2   2…

We note that one of the important consequences of this new arrangement is that every alternating \(3\) will now be masked by the smaller integer division, in this case \(2\).

Accordingly, every 4th and 2nd gap between \(2\)'s (in the bottom rows of the above sets)is now a prime number. Let us rename these gaps between \(2\)'s as voids and call this arrangement a 4–2 system.

An equation for the above 4–2 system can be conveniently formulated, and a particular solution is given here as,

$ P_{|2,3|}(N) = \frac {\left (N + A\left (\frac {3}{2} - \frac {-1^{B(N + C)}}{2} \right ) \right )}{3} +1$
Equation 4

Where \(A\), \(B\) and \(C\) are constants that take the values \(A = -1, 0, 1\); \(B = 0, 1\) and \(C = 0, 1\)to provide for the integer solution to \(P_{|2, 3|}\), and where \(2 < N < \infty\). Note that the \(P_{|2, 3|}\) equation may be reformulated in different ways or by using trigonometric functions without any loss of generality. The addition of \(+1\) accounts for the prime number \(2\).

The \(P_{|2, 3|}\) equation may be computed by means of software coding. We provide the source code for equation [4] in section 10.1 for testing purposes.

In the below table, we tabulate the \(P(N)\)values for 2 <\(N < 25\) using equation [4].

\(N\) \(P(N)\)
3 2
4 2
5 3
6 3
7 4
8 4
9 4
10 4
\(N\) \(P(N)\)
11 5
12 5
13 6
14 6
15 6
16 6
17 7
18 7
\(N\) \(P(N)\)
19 8
20 8
21 8
22 8
23 9
24 9

We incidentally showed that \(P_{|2, 3|}\) given by equation [4] calculates the exact count of prime numbers for any given positive integer \(2 < N < 25\). As expected, the \(P(N)\) values in the above table also reflect the order of the \(4–2\) system. The \(P_{|2, 3|}\) succeeds because all values of \(N\) less than \(25\) have divisors of \(2\) or \(3\); otherwise, they happen to be prime numbers. This, however, first changes when \(N = 25\), where the smallest divisor is no longer \(2\) or \(3\).

Inevitably, the discussed methodology may be extended to the formulation of \(P(N)\) for larger integers. However, as \(N\), the onset of new integers that can remove the potential primes from their residing voids and the possible masking by smaller divisors makes the formulation of \(P(N)\) increasingly cumbersome. It is worth pointing out now that this convoluted yet systematic removal/masking process is what shapes or distorts the count of primes, providing its erratic appearance.

It is reasonable to assume that there should not be any basis for a single analytic function, complex variable or not, to represent exact values of \(P(N)\) because the underlying principle of \(P(N)\) can be regarded as a step change process.

Let us explain this with an example. We know that (P(106) = 78,498), (P(107) = 664,579), (P(108) = 5,761,455), etc. In addition, the largest prime, (L), for (N = 1000 is 997). Let us assume that there are no other primes in existence that are larger than (L). Then, the (P(N)) values would change to (P(106) = 120,784), (P(107) = 1,203,466 )and (P(108) = 12,029,477). The new (P(N)) values clearly show that a more behaved relationship now exists.

The order of the prime numbers is therefore in the destruction rather than in the creation, and because the underlying operation belongs to an elimination process, we now attempt to formulate the order of the elimination process and show that the residual, i.e., what now becomes the prime numbers, provides an accurate calculation of \(P(N)\). We do this next.

5. Overall prime number order and prime number distribution sequence

For reasons that will become apparent later in the paper, we will continue to extend our analysis on the aforesaid \( 4–2\) system. However, the reader should note that the results that follow can be obtained in the absence of the \(4–2\) system, for example, by means of similar inference.

We noted that the divisors \(2\) and \(3\) result in the four integer solutions of equation [4] during our \(P(N)\) calculations. As discussed earlier, the constants of equation [4] take the following values: \(A = 0\); \(A = -1\) and \(B = 0\); or \(A= 1\),\(B = 1\) and \(C = 0\) or \(1\).

We will again look for four integer solutions, which we will represent by \(S_n\) and where \(n = 1\), \(2\), \(3\) and \(4\), such that every \(S \) is a product of two base prime numbers \(S_n = S_x \times S_y \), and show that a set of four second order sequences,\( P_n\), exists and that each \(P_n\) has a starting point of \(S_n \) with higher terms derived by simple \(S_n \)relationships. Furthermore, the terms of the \(P_n\) sequence will solely occupy the voids of the \(4 - 2\) system for all \(N \lt \infty \).

Previously, we noted that \(S_1\) is equal to \(25\), which, as we know, is a product of two prime numbers, so that\( S_n = S_x \times S_y = 5 × 5\). We therefore know that our first series\(P_1\) will be based on multiples of the smallest divisor of\( S_1\).

Accordingly, by way of interpolation and using an extension for equation [4], we can formulate the following series,

$ P_n = (P'n \times 3) - \frac {3}{2} + \frac {-1^{P'_n}}{2}$
Equation 5

where,

$ P'_n = \left (\frac {\left ((S_x \times S_r) + \frac {3}{2} - \frac {-1^{(s_x \times s_y + D)}}{2} \right )}{3} \right ) + (i\times (2\times S_x)) + (j\times ((2\times S_r) + (i\times ((2 \times (S_x + E))))))$
Equation 6

\(S_x \)and\( S_y\) are base primes,

i, j = 0, 1, 2…,

\(D \)is a constant equal to either \(0\) or \(1\) providing for integer solutions to \(n\),

\(E\) is a constant equal to \(+/-1\) (positive for P1 and P2 and negative for P3 and P4).

By way of a similar correlation, we obtain the remaining three prime base sets as (5 × 7), (7 × 7) and (7 × 11). (Note that, in the source code provided in section 10.3, the base prime values are quoted as (2 + 3, 2 + 3), (2 + 3, (2 × 2) + 3), ((2 × 2) + 3, (2 × 2) + 3) and ((2 × 2) + 3, (3 × 3) + 2) to reflectthe \(P|2, 3|\)| dependency, which the reader can easily verify).

The first few values of \(P'_n\) for each of the base primes is tabulated below, where columns correspond to \(i\) terms and rows \(j\) terms,

9 19 29 39 49 59 69 79 89
  41 63 85 107 129 151 173 195
    97 131 165 199 233 267 301
      177 223 269 315 361 407
        281 339 397 455 513
          409 479 549 619
            561 643 725
              737 831
                937
12 22 32 42 52 62 72 82 92
  48 70 92 114 136 158 180 202
    108 142 176 210 244 278 312
      192 238 284 330 376 422
        300 358 416 376 422
          432 502 572 642
            588 670 752
              768 862
                972
17 31 45 59 73 87 101 115 129
  57 83 109 135 161 187 213 239
    121 159 197 235 273 311 349
      209 259 309 359 409 459
        321 383 445 507 569
          457 531 605 679
            617 703 789
              801 899
                1009
26 40 54 68 82 96 110 124 184
  74 100 126 152 178 204 230 256
    146 184 222 260 298 336 374
      242 292 342 392 442 492
        362 424 486 548 610
          506 580 654 728
            674 760 846
              866 964
                1082

Substituting the above \(P'_n\) values into equation [5], we evaluate the boundary values of all prime numbers as \(N \to \infty \) at least once.

To compute \(P(N)\), we count the terms of the sequence \(P_n\) provided that its value is less than \(N\), followed by subtracting the total sum, \(T\), from the \(P_{|2, 3|}\) value calculated using equation [4], as follows,

$ P(N) = P_{|2,3|}(N) - T$
Equation 7

We can combine the set of \(P_n\) series and arrive at the prime number distribution sequence previously self-published on the Nuclear Strategy, Inc. webpage,

$ P_n = (i + j) \left (3 \left (\frac {3}{2} + i \right ) + \frac{-1^i}{2} \right ) + (-1)^{i + j} - i - 2 + k(3(2j + 2i - 1) + (-1)^{i + j - 2}))$
Equation 8

where,

\(i = 0, 1\),

\(j = 2, 3, 4…\) and,

$ k = \frac {1}{4} (-1^{j-2} - (2+3) + 2j)$

Equation [8] is a simplified version of equation [6] for programming convenience. The source code that implements equation [8] is provided in section 10.2 (applicable for \(N < 175\)). Once again, we apply equation [5] and [7] to compute \(P(N)\) for all \(N \to \infty\).

Note that, in the source code of section 10.3, the reader can see that the total element count \(T \)of elements of \(n\) for which the element value is less than \(P_{|2, 3|}\) is calculated first and then subtracted from \(P_{|2, 3|}\). This effectively eliminates the implementation of equation [5] in our code because equation [5] is in fact the inverse of \(P_{|2, 3|}\). In both cases, as expected, the value of the total sum \(T\) will be the same.

Equation [8] may also be written in various ways. However, equation [6] remains the crux of the prime number origin and, accordingly, the prime number distribution sequence is the function that forms the relationship between values that measure the disorder in prime numbers.

Finally, we tabulate the \(P(N)\)values for 24 <\(N < 175\) using equation [7] and discuss its limitations in the next section,

\(N\) \(P(N)\)
25 9
26 9
27 9
28 9
29 10
30 10
31 11
32 11
33 11
\(N\) \(P(N)\)
34 11
35 11
36 11
37 12
... ...
162 37
163 38
164 38
165 38
\(N\) \(P(N)\)
166 38
167 39
168 39
169 39
170 39
171 39
172 39
173 40
174 40

The reader can verify the results provided in the above table by experimenting with the source code of equations [7] and [8],which is provided in sections 10.2 and 10.3.

6. Limitations of the prime number distribution sequence

When we substitute \(i = 0, j = 2\) and \(k = 5\) into equation [8], we obtain \(59\). Similarly, when we substitute \(i = 1, j = 2\) and \(k = 3\) into equation [8], we again obtain \(59\). This implies that the terms of the sequence will produce repeated roots. This is because of the way terms of the \(P'_n\) series intertwine. Accordingly, equation [5] of the prime number distribution sequence can only provide accurate results if multiple counting of equal terms is averted. The first such instance of repeated roots occurs when \(N = 175\).

Fortunately, there are a number of methods for managing the prime number distribution sequence effectively. As the repeated roots exist in orderly fashion, one apparent approach to prevent double counting is by forcing parameter increment thresholds. Alternatively, we can simply allow multiple counting and correct the resultant \(P(N)\) by subtracting the repeat sequence values. A restricted parameter increment technique is used in the source code provided in section 10.3.

We obtain the results below using the prime number distribution sequence using the source code provided in section 10.3,

\(N\) \(P(N)\)
101 4
102 25
103 168
104 1229
105 9592
106 78498
107 664579
108 5761455
109 50847534

7. Effective use of the prime number distribution sequence

By variation of the parameters of the prime number distribution sequence, we observe that, as we increment through \(j\) at constant \(i\), the terms of the \(P_n\) series approach \(N\) more rapidly than incrementing through \(i\) at constant \(j\). For example, given \(P'_1\), when \(i = 8\) and \(j = 0\), the result is \(P'_1 = 89\); however, when \(i = 0\) and \(j = 8\), \(P'_1 = 937\); see section 5. Furthermore, for small \(j\), the problem of repeated terms of the prime number distribution sequence is less prevalent. Therefore, we can implement a technique called block counting, defined as follows: block counting enables us to omit the counting of the terms of the prime number distribution sequence, replacing it with the formulaic evaluation of the entire size of a row at a particular \(j\). This works effectively for small \(j\) and eliminates \(i\) computations altogether. However, as \(j\) increases, efficient methods for the first integer solution of the Diophantine equation and combinatory mathematics begin to dominate our analysis.

However, as expected, the most significant advantage of block counting that cannot be overlooked is that the computation time will be constant irrespective of how large \(N\) is.

Although we do not wish to explore this particular trait of the prime number distribution sequence in any further detail, we can provide a basic implementation of block counting in the source code in section 10.3. Enthusiastic programmers may set the Boolean variable \(RowJ1\) to TRUE to calculate the entire size of row \(j = 0\), implemented for the sub-sequences \(P_1\) and \(P_3\) outside the \(i\) and \(j\) counters. The reader can easily observe the resultant gains made in terms of computational performance.

The block counting method has been experimented with to a greater extend by the author, resulting in the computation of \(P(1010)\) in less than \(10\) seconds, executed on an average \(4\)-processor 2.49GHz machine. The executable that implements the unique approaches for the effective first integer solutions of the Diophantine equation and combinatory mathematics is provided on the Nuclear Strategy, Inc. website.

However, the purpose of this paper is to prove that the existence of prime numbers is based on an orderly phenomenon; therefore, we now move on to discuss other open questions and the relevance of the prime number distribution sequence.

8. Twin primes and the Riemann Hypothesis

In section 5, we laid emphasis on building our model on the so-called \(4\) - \(2\) system. Now, we discuss the reasons for adopting the \(4\) - \(2 \)system. However, we first revisit the definition of twin primes.

A twin prime is where two primes differ in value by two. The first few twin primes are (3, 5), (5, 7), (11, 13), and so on. Recall from our earlier \(P_{|2, 3|}\) formulation that a cyclic positioning of the divisor 3 approximately 2 has emerged, i.e., right and left of \(2\) and masked by \(2\), for all \(2 × n\), where \(n = 1, 2…\) and was the basis for the \(4\)\(2 \)pattern, giving us the four integer solutions to equation [4].

Now, notice that the \(4\)\(2\) system is actually what lays the groundwork for the twin primes. Moreover, provided that the \(4\)\(2\) system is undisturbed, we would have infinitely many twin primes.

However, we note that the first non-twin prime is (23, 25). It is no coincidence that the smallest term of the prime number distribution sequence given by equation [5] is equal to \(25\).

Consider the sequence \(P_1\), i.e., equation [6] for \(n=1\).When \(j = 2\) and \(i = 0, 1, 2...\), we know that 1/5th of all twin primes will vanish for all \(N<∞\). As we increment \(j\), more twin primes will be wiped out, to a lesser degree, however. There are three reasons for this. Firstly, the gaps between the \(i \)steps rapidly increase as \(j\) increases. Secondly, masking works in favor of the twin primes, or, generally speaking, for any primes. And lastly, as the \(4–2\) system clearly demonstrates, all \(j\) will become cyclic and passive at some point. In the grand scheme of things, the cyclic behavior of the prime number distribution sequence explains why we unexpectedly come across isolated twin primes for very large \(N\).

Therefore, it is the task of the prime number distribution sequence to ensure twin primes cease to exist. If we can prove that, beyond some point, the terms of all Pn will at most differ by 2, then we can conclude absolutely that there will not be infinitely many twin primes. Of course, we know that this analysis can be carried out by considering the relationship between the \(i\) and \(j \)parameters of the sequence \(Pn\).

9. Conclusions

This paper attempts to demonstrate that the \(P(N) \)problem is an inverse (or residual) stepwise phenomenon. This study also provides vigorous proofs, as well as the prime number distribution sequence, for the accurate and analytical calculation of \(P(N)\). These analyses seem to contradict the Riemann hypothesis, where it is stated that the non-trivial zeros of the Riemann zeta function all have real part ½. It is evident that the Riemann hypothesis has been provided in the absence of prime number distribution analysis and is based on an arbitrary analytical function. We conclude this paper by stating that there is the very real possibility of deriving infinitely many functions, for certain upper and lower boundaries of \(N\), to arrive at some reasonable approximation for \(P(N)\); however, no real or complex variable function, or any constant values, will ever accurately predict \(P(N)\) for all \(N→∞\), as demonstrated in this paper.

10. Source Code

10.1. P|2, 3| formula

The below source code is written in Microsoft Excel VBA and can be implemented in the Sheet Cell function as \(=pTwoThree(N)\). The function is applicable for when the input \(N\) is less than \(25\).

VB
Function pTwoThree(N As Integer) As Integer

Dim P As Double

    If N Mod 3 = 0 Then
        P = N / 3
    ElseIf (((N + 3 / 2 - ((-1) ^ N) / 2) / 3) - Int((N + 3 / 2 - ((-1) ^ N) / 2) / 3) = 0) Then
        P = (N + 3 / 2 - ((-1) ^ N) / 2) / 3
    ElseIf (((N + 3 / 2 - ((-1) ^ (N + 1)) / 2) / 3) - Int((N + 3 / 2 - ((-1) ^ (N + 1)) / 2) / 3) = 0) Then
        If (((N - 1) / 3) - Int((N - 1) / 3) = 0) Then
            P = ((N - 1) / 3)
        Else
            P = (N + 3 / 2 - ((-1) ^ (N + 1)) / 2) / 3
        End If
    End If
    
    pTwoThree = P + 1

End Function

10.2. Prime number distribution sequence in VBA

The below source code is written in Microsoft Excel VBA and can be implemented in the Sheet Cell function as \(= pNDS (N)\). The function is applicable for when the input \(N\) is less than \(175\).

VB
Function pNDS(N As Integer) As Integer

Dim P As Double

    If N Mod 3 = 0 Then
        P = N / 3
    ElseIf (((N + 3 / 2 - ((-1) ^ N) / 2) / 3) - Int((N + 3 / 2 - ((-1) ^ N) / 2) / 3) = 0) Then
        P = (N + 3 / 2 - ((-1) ^ N) / 2) / 3
    ElseIf (((N + 3 / 2 - ((-1) ^ (N + 1)) / 2) / 3) - Int((N + 3 / 2 - ((-1) ^ (N + 1)) / 2) / 3) = 0) Then
        If (((N - 1) / 3) - Int((N - 1) / 3) = 0) Then
            P = ((N - 1) / 3)
        Else
            P = (N + 3 / 2 - ((-1) ^ (N + 1)) / 2) / 3
        End If
    End If
    
    pNDS = P + 1

    j = 2
    Do
        For j = j To j + 1
            For k = (1 / 4) * (-1) ^ (j - 2) - 5 / 4 + (1 / 2) * j To 0 Step -1
                For i = 1 To 0 Step -1
                    Pp = (i + j) * (3 * (3 / 2 + i) + (1 / 2) * (-1) ^ i) + (-1) ^ (i + j) - i - 2 + k * (3 * (2 * j + 2 * i - 1) + (-1) ^ (i + j - 2))
                    If Pp <= P Then
                        pNDS = pNDS - 1
                    End If
                Next i
            Next k
        Next j
    Loop While Pp < P

End Function

10.3. Prime number distribution sequence in C++

The below source code is written in C++. The function is applicable for any input \(N\) less than infinity.

C++
// PNT.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <stdio.h> 
#include <math.h>      
#include <vector>


using namespace std;

double N, P23, Pi, Pj, i, uj, r, s, ui, PSx[4], PSy[4], PJS;
vector<double> T;
bool RowJ1 = false;

int _tmain(int argc, _TCHAR* argv[])
{
	cout << "Copyright (c) 2014 by Yoldas Askan. ALL RIGHTS RESERVED." << '\n';
	cout << "Please visit www.NuclearStrategy.co.uk for further details." << '\n' << '\n'; 
	cout << "Enter interger N to compute count of primes in N: ";
	cin >> N;
  	cout << '\n';

	//	Processor number
	//	There is no limit to the number of processors can be used for P(N) computations by pnds
	int numProcessor = 4;
	T.resize(numProcessor);

	if(((int)N % 3) == 0.)
		P23 = (int)(N / 3.);
	else if( ((N + 3./2. - pow(-1., N) / 2.) / 3.) - floor((N + 3./2. - pow(-1., N) / 2.) / 3.) == 0.){
		P23 = (int)(N + 3./2. - pow(-1., N) / 2.) / 3.;
	}
	else if( ((N + 3./2. - pow(-1., (N + 1.)) / 2.) / 3.) - floor((N + 3./2. - pow(-1., (N + 1.)) / 2.) / 3.) == 0.){
		if( ((N - 1.) / 3.) - floor((N - 1.) / 3.) == 0.){
			P23 = ((int)(N - 1) / 3.);
		}
		else
			P23 = (int)(N + 3./2. - pow(-1., (N + 1.)) / 2.) / 3.;
	}

	//	base primes
	PSx[0] = (2. + 3.); PSy[0] = (2. + 3.); PSx[1] = (2. + 3.); PSy[1] = (2. * 2.) + 3.;
	PSx[2] = (2. * 2.) + 3.; PSy[2] = (2. * 2.) + 3.; PSx[3] = (2. * 2.) + 3.; PSy[3] = (3. * 3.) + 2.;

	//	Formulaic computation of row j = 0 for the sequences P1 and P3
	//	Set boolean variable RowJ1 to 'TRUE' to activate 
	RowJ1 = false;
	PJS = 0.;
	if(RowJ1)
		PJS = 1.;

	P1(0., PSx[0], PSy[0], 0., 1.);
	P2(1., PSx[1], PSy[1], 1., 1.);
	P3(2., PSx[2], PSy[2], 0., -1.);
	P4(3., PSx[3], PSy[3], 1., -1.);

	//	Formulaic computation of row j = 0 for sequence P1 and p3
	if(RowJ1){
		//	equation [6]
		Pi = (((PSx[0] * PSy[0])+ 3./2. - pow(-1., (PSx[0] * PSy[0] + 0.)) / 2.) / 3.) + 0. * (2 * PSx[0]);
		Pj = (2 * PSy[0]) + (0. * (2 * (PSx[0] + 1.)));
		T[0] += floor((P23 - Pi) / Pj) + 1.;
		T[0] -= floor(((floor((P23 - Pi) / Pj) + 1.) - PSx[0]) / PSx[2]) + 1.;

		//	equation [6]
		Pi = (((PSx[2] * PSy[2])+ 3./2. - pow(-1., (PSx[2] * PSy[2] + 0.)) / 2.) / 3.) + 0. * (2 * PSx[2]);
		Pj = (2 * PSy[2]) + (0. * (2 * (PSx[2] + 1.)));
		T[2] += floor((P23 - Pi) / Pj) + 1;
	}
	
	for(int i = 0; i < numProcessor; i++){
		//	equation [7]
		P23 -= T[i];			
	}

	P23++;	//	Is 2 a prime number?
	cout  << endl << "There are " << P23 << " primes in " << (int)N << '\n' << endl  << endl;	

	system("pause");
	return 0;
}

void P1(double I, double Sx, double Sy, double D, double E)
{
	T[I] = 0.;
	i = 0.;
	do{
		Pi = (((Sx * Sy)+ 3./2. - pow(-1., (Sx * Sy + D)) / 2.) / 3.) + i * (2 * Sx);	//	equation [6]
		Pj = (2 * Sy) + (i * (2 * (Sx + E)));
		(floor((P23 - Pi) / Pj) < i) ? uj = floor((P23 - Pi) / Pj) : uj = i;

		if(i > (2. * 2.)){								//	Limit increments of j
			if(RowJ1){
				s = (3. + 2.);
				r = (2. * 2.) + 3.;
				if (i == s || floor((i - s) / r) - ((i - s) / r) == 0){
					uj = -1.;
				}
			}
			if(uj > -1.){
				for(double w = 0; w < uj; w++){
					s = (3. + 2.) + w * ((2. * 2.) + 3.);
					r = (3. + 2.) + w * (3. * 2.);
					if(s > i)
						break;
					
					if (i == s || floor((i - s) / r) - ((i - s) / r) == 0){
						if(w < uj) 
							uj = w;
						break;
					}
				}
			}
		}

		for(double j = PJS; j <= uj; j++){
			if(j > (2. * 2.)){							//	Limit increments of i
				for(double w = 1; w * (3. + 2.) <= j; w++){
					s = (3. + 2.) + (w - 1.) * ((2. * 2.) + 3.);
					r = (3. + 2.) + (w - 1.) * (3. * 2.);
					if(s > j)
						break;

					if (j == s || floor((j - s) / r) - ((j - s) / r) == 0){
						T[I]--;
						break;
					}
				}
			}
			T[I]++;
		}
		i++;
	}while(Pi + (PJS * Pj) <= P23);
}

void P2(double I, double Sx, double Sy, double D, double E)
{
	T[I] = 0.;
	i = 0.;
	do{
		Pi = (((Sx * Sy)+ 3./2. - pow(-1., (Sx * Sy + D)) / 2.) / 3.) + i * (2 * Sx);	//	equation [6]
		Pj = (2 * Sy) + (i * (2 * (Sx + E)));
		(floor((P23 - Pi) / Pj) < i) ? uj = floor((P23 - Pi) / Pj) : uj = i;

		if(i > 2.){										//	Limit increments of j
			for(double w = 0; w < uj; w++){
				s = 3. + w * (3. + 2.);
				r = (3. + 2.) + w * (3. * 2.);
				if(s > i)
					break;

				if (i == s || floor((i - s) / r) - ((i - s) / r) == 0){
					if(w < uj) 
						uj = w;
					break;
				}
			}
		}

		if(uj > ((2. * 2.) + 3.)){
			for(double w = 0; w < i; w++){
				s = 2 * ((2. * 2.) + 3.) + (w * ((2. * 2.) + 3.));
				r = (2. * 2.) + (3. * 3.) + (w * (3. * 2.));
				if(s > i)
					break;

				if (i == s || ceil((i - s) / r) - ((i - s) / r) == 0){
					if(uj > ((2. * 2.) + 3.))
						uj = ((2. * 2.) + 3.);
					break;
				}
			}
		}

		for(double j = 0; j <= uj; j++){
			if(j > (2. * 2.)){							//	Limit increments of i
				for(double w = 1; w <= j; w++){
					s = (3. + 2.) + (w - 1.) * ((2. * 2.) + 3.);	
					r = (3. + 2.) + (w - 1.) * (3. * 2.);
					if(s > j)
						break;

					if (j == s || floor((j - s) / r) - ((j - s) / r) == 0){
						T[I]--;
						break;
					}
				}
			}
			T[I]++;
		}
		i++;
	}while(Pi <= P23);
}

void P3(double I, double Sx, double Sy, double D, double E)
{
	T[I] = 0.;
	i = 0.;
	do{
		Pi = (((Sx * Sy)+ 3./2. - pow(-1., (Sx * Sy + D)) / 2.) / 3.) + i * (2 * Sx);	//	equation [6]
		Pj = (2 * Sy) + (i * (2 * (Sx + E)));
		(floor((P23 - Pi) / Pj) < i) ? uj = floor((P23 - Pi) / Pj) : uj = i;

		if(i > 2.){										//	Limit increments of j
			for(double w = 0; w < (i + ((3. * 2.) + 2.)) / ((3. * 3.) + 2.); w++){
				s = 3. + w * (3. + 2.);
				r = (3. + 2.) + w * (3. * 2.);
				if(s > i)
					break;

				if (i == s || floor((i - s) / r) - ((i - s) / r) == 0){
					uj = -1.;
					break;
				}
			}
		}
		if(uj != -1.){
			if(i > (3. * 2.)){
				for(double w = 0; w < uj; w++){
					s = ((2. * 2.) + 3.) + w * ((2. * 2.) + 3.);		
					r = ((2. * 2.) + 3.) + w * (3. * 2.);
					if(s > i)
						break;

					if (i == s || floor((i - s) / r) - ((i - s) / r) == 0){
						if(w < uj) 
							uj = w;
						break;
					}
				}
			}
		}

		for(double j = PJS; j <= uj; j++){
			ui = false;
			if(j > 2.){									//	Limit increments of i
				double w = 1;
				for(w = 1; w <= j; w++){
					s = 3. + (w - 1.) * (3. + 2.);
					r = (3. + 2.) + (w - 1.) * (3. * 2.);
					if(s > j)
						break;

					if (j == s || floor((j - s) / r) - ((j - s) / r) == 0){
						T[I]--;
						ui = true;
						break;
					}
				}
			}
			if(j > (3. * 2.) && !ui){
				double w = 1;
				for(w = 1; w <= j; w++){
					s = ((2. * 2.) + 3.) + (w - 1.) * ((2. * 2.) + 3.);
					r = ((2. * 2.) + 3.) + (w - 1.) * (3. * 2.);
					if(s > j)
						break;

					if (j == s || floor((j - s) / r) - ((j - s) / r) == 0){
						T[I]--;
						ui = true;
						break;
					}
				}
			}
			T[I]++;
		}
		i++;
	}while(Pi + (PJS * Pj) <= P23);
}

void P4(double I, double Sx, double Sy, double D, double E)
{	
	T[I] = 0.;
	i = 0.;
	do{
		Pi = (((Sx * Sy)+ 3./2. - pow(-1., (Sx * Sy + D)) / 2.) / 3.) + i * (2 * Sx);	//	equation [6]
		Pj = (2 * Sy) + (i * (2 * (Sx + E)));
		(floor((P23 - Pi) / Pj) < i) ? uj = floor((P23 - Pi) / Pj) : uj = i;

		for(double w = 0.; w < ((3. * 2.) + 2.); w++){	//	Limit increments of j
			s = (2. * 2.) + (w * ((2. * 2.) + 3.));       
			r = (3. + 2.) + (w * (3. * 2.));         
			if(s > i)
				break;

			if (i == s || ceil((i - s) / r) - ((i - s) / r) == 0){
				uj = -1.;
				break;
			}
		}
		if(uj != -1.){
			for(double w = 0; w < (i + ((3. * 2.) + 2.)) / ((3. * 3.) + 2.); w ++){
				s = (2. * 2.) + w * (3. + 2.);		
				r = ((2. * 2.) + 3.) + w * (3. * 2.);
				if (i == s || floor((i - s) / r) - ((i - s) / r) == 0){
					if(w < uj)
						uj = w;
					break;
				}
			}
		}

		for(double j = 0; j <= uj; j++){
			ui = false;
			if(j > 2.){									//	Limit increments of i
				double w = 1;
				for(w = 1; w <= j; w++){
					s = 3. + (w - 1.) * (3. + 2.);
					r = (3. + 2.) + (w - 1.) * (3. * 2.);
					if(s > j)
						break;

					if (j == s || floor((j - s) / r) - ((j - s) / r) == 0){
						T[I]--;
						ui = true;
						break;
					}
				}
			}
			if(j > (3. * 2.) && !ui){
				double w = 1;
				for(w = 1; w <= j; w++){
					s = ((2. * 2.) + 3.) + (w - 1.) * ((2. * 2.) + 3.);
					r = ((2. * 2.) + 3.) + (w - 1.) * (3. * 2.);
					if(s > j)
						break;

					if (j == s || floor((j - s) / r) - ((j - s) / r) == 0){
						T[I]--;
						ui = true;
						break;
					}
				}
			}
			T[I]++;
		}
		i++;
	}while(Pi <= P23);
}

This article was originally published by Nuclear Strategy, Inc. on http://nuclearstrategy.co.uk/prime-number-distribution-series

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



Comments and Discussions

 
GeneralPerformance Pin
Stefan_Lang14-Mar-19 7:04
Stefan_Lang14-Mar-19 7:04 
BugAnother error Pin
Stefan_Lang14-Mar-19 4:51
Stefan_Lang14-Mar-19 4:51 
BugIncorrect prime classification Pin
Stefan_Lang13-Mar-19 22:55
Stefan_Lang13-Mar-19 22:55 
Question1-->3 Pin
Stefan_Lang12-Mar-19 5:46
Stefan_Lang12-Mar-19 5:46 
Question3 Pin
#realJSOP26-Feb-19 19:07
professional#realJSOP26-Feb-19 19:07 
AnswerRe: 3 Pin
DRHuff27-Feb-19 3:50
DRHuff27-Feb-19 3:50 
GeneralRe: 3 Pin
#realJSOP27-Feb-19 5:30
professional#realJSOP27-Feb-19 5:30 
AnswerRe: 3 Pin
TheGreatAndPowerfulOz27-Feb-19 6:13
TheGreatAndPowerfulOz27-Feb-19 6:13 
AnswerRe: 3 Pin
Stefan_Lang13-Mar-19 22:44
Stefan_Lang13-Mar-19 22:44 
QuestionIncorrect Claim Pin
Rick York26-Feb-19 15:05
mveRick York26-Feb-19 15:05 
GeneralMy vote of 1 Pin
Chris Hills22-Feb-16 1:44
Chris Hills22-Feb-16 1:44 
GeneralRe: My vote of 1 Pin
Yoldas Askan23-Feb-16 9:59
Yoldas Askan23-Feb-16 9:59 
GeneralRe: My vote of 1 Pin
Chris Hills23-Feb-16 10:49
Chris Hills23-Feb-16 10:49 
GeneralRe: My vote of 1 Pin
Yoldas Askan27-Feb-16 3:35
Yoldas Askan27-Feb-16 3:35 
GeneralRe: My vote of 1 Pin
Chris Hills3-Mar-16 1:39
Chris Hills3-Mar-16 1:39 
It’s really interesting that http://mathworld.wolfram.com/PrimeNumber.html [^] says “while 2 is considered a prime today, at one time it was not”. I knew that 1 was once considered to be prime, but I didn’t know that 2 was once considered to be not prime. To me, the big reason that we consider 2 to be prime and 1 to be not prime is that it results in integers having unique factorisations into prime factors. If we considered 2 to be not prime or 1 to be prime then we would not have unique factorisations. So the most useful definition of prime has to make 2 prime and 1 not prime.

I would be very interested to see your program that can evalute pi(1E100) in 3 seconds. If it works then I shall certainly change my vote (if codeproject lets me).
GeneralRe: My vote of 1 Pin
Yoldas Askan6-Mar-16 11:13
Yoldas Askan6-Mar-16 11:13 
GeneralRe: My vote of 1 Pin
Chris Hills10-Mar-16 11:33
Chris Hills10-Mar-16 11:33 
GeneralRe: My vote of 1 Pin
Yoldas Askan12-Mar-16 10:40
Yoldas Askan12-Mar-16 10:40 
GeneralRe: My vote of 1 Pin
Chris Hills13-Mar-16 8:34
Chris Hills13-Mar-16 8:34 
GeneralRe: My vote of 1 Pin
Yoldas Askan13-Mar-16 13:03
Yoldas Askan13-Mar-16 13:03 
GeneralRe: My vote of 1 Pin
Chris Hills15-Mar-16 12:57
Chris Hills15-Mar-16 12:57 
GeneralRe: My vote of 1 Pin
Yoldas Askan16-Mar-16 11:18
Yoldas Askan16-Mar-16 11:18 
GeneralRe: My vote of 1 Pin
Chris Hills17-Mar-16 6:29
Chris Hills17-Mar-16 6:29 
GeneralRe: My vote of 1 Pin
Yoldas Askan20-Mar-16 7:21
Yoldas Askan20-Mar-16 7:21 
GeneralGreat paper! You may also consider a Calculate Primes Book. Pin
Alex Knutson17-Feb-15 7:23
Alex Knutson17-Feb-15 7:23 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.