# Construction of an exact function for counting primes in intervals.

I have constructed an exact function for counting primes in intervals and am curious to know if it 1) has any importance? 2) Has been derived already? I have no formal education in number theory, and no university affiliation, so my only option is to post on here to get any advice or feedback. $$\mathbb{P}$$ represents the set of prime numbers. Defining $$a\#$$ as the product of all primes less than or equal to $$a$$, it is possible to move forward.

Chebyshev's Theorem states there will exist a prime number between $$a$$ and $$2a$$ for all $$a \in \mathbb{N}$$. Since two is the only even prime number, it follows that for every $$a > 1$$, there will exist some natural number $$b < a$$ where $$a + b$$ is an odd, prime number.

The next question to consider is when the sum of two natural numbers is a prime. Given $$a, b \in \mathbb{N}$$ where $$a \geq b$$, the sum $$a + b \in \mathbb{P}$$ only when $$GCD(a + b, a\#) = 1$$}.

For the forward conditional where $$a, b \in \mathbb{N}$$ and $$a \geq b$$ is given by

$$a + b \in \mathbb{P} \Rightarrow GCD(a + b, a\#) = 1$$ Let $$a + b$$ be a prime number less than or equal to $$2a$$. Since $$a + b$$ is a prime, it will have no divisors other than one and itself, showing $$GCD(a + b, a\#) = 1$$ must hold. For the reverse condition given by $$GCD(a + b, a\#) = 1 \Rightarrow a + b\in \mathbb{P}$$ Since all composite numbers between $$a$$ and $$2a$$ must be the product of prime numbers less than or equal to $$a$$, it follows that when $$a + b$$ is coprime to $$a\#$$, that number is not divisible by any lesser prime numbers. This forces $$a + b \in \mathbb{P}$$, thus proving the proposition.

As a remark, it is important to note, that in general, $$b$$, can take any value up to the value $$a^2 + a$$. This holds because the first number that is coprime to $$a\#$$, and composite, is the square of the first prime greater than $$a$$. Since the smallest value this prime can have, in principle, is $$a + 1$$, it is clear that $$a^2 + 2a < (a + 1)^2$$. This means that the maximum value for $$b$$ is $$a^2 + a$$.

In order to predict the number of prime numbers between some value $$a$$ and $$a + b$$, the number of coprime elements to $$a\#$$ up to $$a + b$$ will be needed. The Möbius Function, will be needed and its properties are as follows.

$$\begin{equation*} \mu(x)=\begin{cases} 1, & \text{if x = 1} \\ 0, & \text{if x is not square-free}.\\ (-1)^r, & \text{where r is the number of distinct primes of x}. \end{cases} \end{equation*}$$

Recall that $$a$$ and $$b$$ sum to a prime only when $$GCD(a + b, a\#) = 1$$. This is equivalent to stating that the number of prime numbers between $$a$$ and $$a + b$$ are those elements up to $$a + b$$ and greater than $$a$$ which are coprime to $$a\#$$.

The number of primes between $$a$$ and $$a + b$$ where $$b \leq a(a + 1)$$, which will be denoted by the prime interval counting function $$\pi(a, a + b)$$ where $$a \in \mathbb{N}$$, is given by the relationship $$\pi(a, a + b) = \sum_{m | a\#} \mu(m) \big{[}\frac{a + b}{m}\big{]} - 1$$. This can be proven below.

The number of primes between $$a$$ and $$a + b$$ where $$a \in \mathbb{N}$$ and $$b \leq a(a+1)$$, is given by the number of coprime elements to $$a\#$$ up to $$a + b$$. Knowing that the totient function is related to the Möbius Function, where $$\phi(a\#) = a\# \sum_{m | a\#}\frac{\mu(m)}{m} \; \text{and} \; m \in \mathbb{N}$$, gives the total number of coprime elements of $$a\#$$. Truncation of the excess elements is what is needed. To accomplish this, the number of coprime elements of $$a\#$$ up to $$a + b$$ is given by taking the partial sum $$\sum_{n \leq a + b} \sum_{m | a\#} \frac{\mu(m)}{m} = \sum_{m | a\#} \mu(m) \big{[} \frac{a + b}{m}\big{]}$$. Since this function gives all of the coprime values to $$a\#$$ up to $$a + b$$, it is necessary to subtract off the coprime values less than or equal to $$a$$. Since $$a\#$$ is simply the product of all prime numbers up to the value $$a$$, the only $$c < a$$ where $$GCD(c, a\#) = 1$$ is when $$c = 1$$, since any composite or prime less than $$a$$ will share a factor with $$a\#$$. With this, the exact number of primes in range of $$a$$ and $$a + b$$, written as $$\pi(a, a + b)$$, is given by $$\pi(a, a + b) = \sum_{m | a\#} \mu(m) \big{[} {\frac{a + b}{m}}\big{]} - 1$$.

My reason for creating this function was to find the conditions where $$\pi(a, a + b) = 1$$ in a general sense. Knowing that would essentially allow one to parametrize the primes as $$p = a + f(a)$$, where $$p \in \mathbb{P}$$. As I said, I have no formal training, so if it is something that isn't important, so be it.

• Can you write matlab function that do this? – Mendi Barel Aug 17 '19 at 0:45
• I have written python code to verify it to certain values. Using it iteratively, it gives the exact number of primes beyond 10,000,000. I also wrote a code to choose random values of $a$ and $b$ based on the constraints to calculate the number of primes in those intervals, and it works perfectly. The proof I think is sound, but it is always nice to verify. – jmath Aug 17 '19 at 0:49
• Can you post the pyton code in your question? – Mendi Barel Aug 17 '19 at 1:50
• I may decide to post the code on a different exchange dealing with computation. For the purposes of this question the code is not needed, as the proof should suffice. – jmath Aug 17 '19 at 2:09
• @Mendi In the formula $\pi(a,a+b)=\sum_{m|a\#}\mu(m)\big{[}{\frac{a+b}{m}}\big{]}-1$, $\pi(a,a+b)$ indicates the number of primes greater than $a$ and less than or equal to $b$, $m|a\#$ indicates $m$ divides $a\#$ where $a\#$ is the product of all primes less than or equal to $a$, $\mu(m)$ is the Möbius function, and $\big{[}{\frac{a+b}{m}}\big{]}$ is the floor function of $\frac{a+b}{m}$. – Steven Clark Aug 18 '19 at 2:18

Assume the following definitions where $$n$$ is a positive integer, $$p$$ is a prime, $$\mu(n)$$ is the Möbius function, and $$M(x)$$ is Mertens function:

(1) $$\quad \pi(x)=\sum\limits_{n\le x}a(n)\,,\qquad a(n)=\cases{1,& n\in\mathbb{P} \\ 0,& otherwise}\quad$$ (see https://oeis.org/A010051 for $$a(n)$$)

(2) $$\quad M(x)=\sum\limits_{n\le x}\mu(n)$$

(3) $$\quad Q(x)=\sum\limits_{n\le x}|\mu(n)|$$

The prime-counting function $$\pi(x)$$ can be expressed in a number of ways such as (4) to (6) below where:

• $$\nu(n)$$ is the number of distinct primes in the factorization of $$n$$,
• $$\omega(n)$$ is the number of prime factors counting multiplicities in the factorization of $$n$$, and
• $$rad(n)$$ is the radical of $$n$$ (also referred to as the square-free kernel of $$n$$),

(4) $$\quad \pi(x)=\sum\limits_{n\le x}b(n)\,\left\lfloor\frac{x}{n}\right\rfloor\,,\qquad b(n)=\sum\limits_{d|n} a(d)\,\mu\left(\frac{n}{d}\right)\quad$$ (see https://oeis.org/A143519 for $$b(n)$$)

(5) $$\quad \pi(x)=\sum\limits_{n\le x}\nu(n)\,M\left(\frac{x}{n}\right)$$

(6) $$\quad \pi(x)=\sum\limits_{n\le x} (-1)^{\Omega(n)+1}\, \nu(n)\,Q\left(\frac{x}{n}\right)$$

Any of the formulas (4) to (6) above can be used to evaluate $$\pi(a+b)-\pi(a)$$. Note all three of these formulas involve the Moebius function $$\mu(n)$$ (either directly or indirectly).

The $$b(n)$$ coefficient function referenced in formula (4) above can also be evaluated as follows.

(7) $$\qquad b(n)=\sum\limits_{p|n}\mu\left(\frac{n}{p}\right)\qquad\quad(p\in\mathbb{P})$$

(8) $$\qquad b(n)=\cases{-\mu(n)\,\nu(n) & \Omega(n)=\nu(n) \\ \mu(rad(n)) & \Omega(n)=\nu(n)+1 \\ 0,& otherwise}$$

• So, it sounds like this function is not of any real importance. – jmath Aug 17 '19 at 3:15
• Proofs ? And there is no Fourier representation of $\pi(x)$ – reuns Aug 17 '19 at 4:26
• @jmath Your formula is interesting but only valid in an interval. I thought I'd give you a few more formulas to consider that are more generally useful. – Steven Clark Aug 17 '19 at 4:36
• I see, thank you for those. I will read more about them. – jmath Aug 17 '19 at 5:29
• @reuns My website documents derivation of some of the formulas above, but you deleted the reference to my website. In general, I believe all functions of the form $f(x)=\sum_{n\le x} a(n)$ where $a(n)\in\mathbb{C}$ have a Fourier series representation (see primefourierseries.com/?page_id=7595). There formulas are generally only valid for $x>0$, and convergence of the Fourier series is dependent upon the growth rate of $f(x)$. – Steven Clark Aug 18 '19 at 19:28

Using inclusion-exclusion $$\sum_{m | N} \mu(m) \lfloor \frac{x}{m}\rfloor$$ is the number of integers $$\le x$$ that are coprime with $$N$$.

If $$a+b \le a^2$$ with $$a \# = \prod_{p \le a}p$$ then $$\pi(a+b)-\pi(a) = \sum_{2 \le n \le a+b, \gcd(n,a\#)=1} 1= -1+\sum_{m | \ a\#} \mu(m) \lfloor \frac{a+b}{m}\rfloor$$