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.

  • $\begingroup$ Can you write matlab function that do this? $\endgroup$ – Mendi Barel Aug 17 '19 at 0:45
  • $\begingroup$ 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. $\endgroup$ – jmath Aug 17 '19 at 0:49
  • $\begingroup$ Can you post the pyton code in your question? $\endgroup$ – Mendi Barel Aug 17 '19 at 1:50
  • $\begingroup$ 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. $\endgroup$ – jmath Aug 17 '19 at 2:09
  • 1
    $\begingroup$ @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}$. $\endgroup$ – 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}$

  • $\begingroup$ So, it sounds like this function is not of any real importance. $\endgroup$ – jmath Aug 17 '19 at 3:15
  • $\begingroup$ Proofs ? And there is no Fourier representation of $\pi(x)$ $\endgroup$ – reuns Aug 17 '19 at 4:26
  • $\begingroup$ @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. $\endgroup$ – Steven Clark Aug 17 '19 at 4:36
  • $\begingroup$ I see, thank you for those. I will read more about them. $\endgroup$ – jmath Aug 17 '19 at 5:29
  • $\begingroup$ @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)$. $\endgroup$ – 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 $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.