3
$\begingroup$

Let $p_n$ denote the $n$th prime number. Let $p_n \lt a \lt b \lt p_{n+1}^2$ be any such integers. Their oddness or divisibility does not matter as in my previous posts, which makes this formula particularly nice.

An inclusion-exclusion based & modular-arithmetical counting formula for the twin primes is:

$$f(a,b) = b - a + \sum_{1 \ \neq \ d \ \mid \ p_n\#} (-1)^{\omega(d)}\sum_{2 \ \nmid \ c \ \mid \ d}\left( \left\lfloor\dfrac{b - x_{c,d}}{d}\right\rfloor + \left\lfloor\dfrac{x_{c,d} - a}{d}\right\rfloor \right)$$

where $x = x_{c,d} =$ any solution in $\Bbb{Z}$ to the simultaneous & CRT system:

$$ x = 1 \pmod c \\ x = -1 \pmod {d/c} $$

Note that the purpose of this formula is purely theoretical and is in no way optimal for counting up the twin primes in an interval.

Questions.

How can we relate this to the inclusion-exclusion formula for $\pi(x)$?

Found here: "Algorithms evaluating $\pi(x)$". It's very close because the alternating sum over divisors of $p_n\#$ does the same thing as that sum, except our sum is missing $d = 1$ and inside of our sum is another sum, and not just a floor of a fraction.

Many other MSE users including mathlove, BillyJoe, and JyrkiLahtonen have been helpful in developing this formula.


Attempt.

We know that $\sum_{d \mid p_n\#} (-1)^{\omega(d)} \lfloor\dfrac{z}{d} \rfloor = x + \sum_{1 \neq d \mid p_n\#} (-1)^{\omega(d)} \lfloor \dfrac{z}{d}\rfloor = \pi(z) - \pi(\sqrt{z}) + 1$ by the given link.

Thus $\sum_{1 \neq d \mid p_n\#} (-1)^{\omega(d)}\lfloor\dfrac{ z}{d} \rfloor =\pi(x) - x - \pi(\sqrt{x}) + 1$ if we can get the double sum into a sum of sums of this form.


The double summation naturally has the form of:

$$ -\sum_{1\ \neq\ cd \ \mid\ p_n\# \\ 2 \ \nmid\ c} (-1)^{\omega(d)} \left(\lfloor \dfrac{b - x_{c,d}}{cd}\rfloor + \lfloor \dfrac{x_{c,d} - a}{cd}\rfloor \right) $$

where $x = x_{c,d} \in \Bbb{Z}$ is any solution to the simultaneous CRT system:

$$ x = 1 \pmod {c} \\ x = -1 \pmod {d} $$


Here's what an example computation looks like, with the equivalent ceil's in place of floor around $a$'s expression:

$$ f(a,b) = - a + b - \left\lceil{\frac{a}{6} - \frac{5}{6}}\right\rceil - \left\lceil{\frac{a}{6} - \frac{1}{6}}\right\rceil + \left\lceil{\frac{a}{3} - \frac{1}{3}}\right\rceil + \left\lceil{\frac{a}{3} + \frac{1}{3}}\right\rceil + \left\lceil{\frac{a}{2} - \frac{1}{2}}\right\rceil + \left\lfloor{\frac{b}{6} - \frac{5}{6}}\right\rfloor + \left\lfloor{\frac{b}{6} - \frac{1}{6}}\right\rfloor - \left\lfloor{\frac{b}{3} - \frac{1}{3}}\right\rfloor - \left\lfloor{\frac{b}{3} + \frac{1}{3}}\right\rfloor - \left\lfloor{\frac{b}{2} - \frac{1}{2}}\right\rfloor \\ = f(5,23) = 3 $$

There are precisely $3$ twin prime averages in the range $[5, 23]$. See verification code link for larger examples.

Here is actually the next example (as $n$ grows):

$$ f(a,b) = - a + b + \left\lceil{\frac{a}{30} - \frac{29}{30}}\right\rceil + \left\lceil{\frac{a}{30} - \frac{1}{30}}\right\rceil + \left\lceil{\frac{a}{30} + \frac{11}{30}}\right\rceil + \left\lceil{\frac{a}{30} + \frac{19}{30}}\right\rceil - \left\lceil{\frac{a}{15} - \frac{11}{15}}\right\rceil - \left\lceil{\frac{a}{15} - \frac{1}{15}}\right\rceil - \left\lceil{\frac{a}{15} + \frac{1}{15}}\right\rceil - \left\lceil{\frac{a}{15} + \frac{11}{15}}\right\rceil - \left\lceil{\frac{a}{10} - \frac{9}{10}}\right\rceil - \left\lceil{\frac{a}{10} - \frac{1}{10}}\right\rceil - \left\lceil{\frac{a}{6} - \frac{5}{6}}\right\rceil - \left\lceil{\frac{a}{6} - \frac{1}{6}}\right\rceil + \left\lceil{\frac{a}{5} - \frac{1}{5}}\right\rceil + \left\lceil{\frac{a}{5} + \frac{1}{5}}\right\rceil + \left\lceil{\frac{a}{3} - \frac{1}{3}}\right\rceil + \left\lceil{\frac{a}{3} + \frac{1}{3}}\right\rceil + \left\lceil{\frac{a}{2} - \frac{1}{2}}\right\rceil - \left\lfloor{\frac{b}{30} - \frac{29}{30}}\right\rfloor - \left\lfloor{\frac{b}{30} - \frac{1}{30}}\right\rfloor - \left\lfloor{\frac{b}{30} + \frac{11}{30}}\right\rfloor - \left\lfloor{\frac{b}{30} + \frac{19}{30}}\right\rfloor + \left\lfloor{\frac{b}{15} - \frac{11}{15}}\right\rfloor + \left\lfloor{\frac{b}{15} - \frac{1}{15}}\right\rfloor + \left\lfloor{\frac{b}{15} + \frac{1}{15}}\right\rfloor + \left\lfloor{\frac{b}{15} + \frac{11}{15}}\right\rfloor + \left\lfloor{\frac{b}{10} - \frac{9}{10}}\right\rfloor + \left\lfloor{\frac{b}{10} - \frac{1}{10}}\right\rfloor + \left\lfloor{\frac{b}{6} - \frac{5}{6}}\right\rfloor + \left\lfloor{\frac{b}{6} - \frac{1}{6}}\right\rfloor - \left\lfloor{\frac{b}{5} - \frac{1}{5}}\right\rfloor - \left\lfloor{\frac{b}{5} + \frac{1}{5}}\right\rfloor - \left\lfloor{\frac{b}{3} - \frac{1}{3}}\right\rfloor - \left\lfloor{\frac{b}{3} + \frac{1}{3}}\right\rfloor - \left\lfloor{\frac{b}{2} - \frac{1}{2}}\right\rfloor \\ = f(7,47) = 4 $$

As you can see, the number of terms we directly consider in the double summation seems to grow exponentially. This doesn't matter, however. The twin prime conjecture doesn't care.


The floor-free formula can be derived as follows. Clearly $\lfloor \dfrac{z}{d}\rfloor = \dfrac{z - z_{(d)}}{d},$ for all $z \in \Bbb{Z}$ and $d \in \Bbb{Z}, d \neq 0$.

$$ f(a,b) = b - a - \\ \sum_{1 \neq cd \mid p_n\# \\ 2 \nmid c} (-1)^{\omega(d)}\left(\dfrac{b - x_{c,d} - (b - x_{c,d})_{(cd)}}{cd} + \dfrac{x_{c,d} - a - (x_{c,d} - a)_{(cd)}}{cd} \right) = \\ -\sum_{1 \neq cd \mid p_n\# \\ 2 \nmid c} \left((-1)^{\omega(d)}\dfrac{ (b - x_{c,d})_{(cd)} + (x_{c,d} - a)_{(cd)}}{cd}\right) $$

But for minimal residues $z_{(e)},z'_{(e)} \in \Bbb{Z}$ we clearly have that $(z + z')_{(e)} \leq z_{(e)} + z_{(e)}'$, and thus we have a lower bounding mechanism (perhaps?).


Here is proof of the formula.

$\endgroup$
6
  • 1
    $\begingroup$ Is $\omega()$ the distinct prime factor counting function? $\endgroup$
    – PM 2Ring
    Nov 7 '21 at 10:54
  • 1
    $\begingroup$ And is a twin prime average $p+1$, where $(p, p+2)$ is a twin prime pair? $\endgroup$
    – PM 2Ring
    Nov 7 '21 at 10:57
  • 2
    $\begingroup$ I don't think I've seen a formula like this before. But as you say, it's not a practical way of counting twin primes, and although it may be theoretically interesting, it may not be so easy to use even for theoretical work, due to the CRT stuff. $\endgroup$
    – PM 2Ring
    Nov 7 '21 at 11:00
  • $\begingroup$ It appears such summations are already known about in practice, though not directly shown in the above form: arxiv.org/pdf/1909.02205.pdf $\endgroup$ Nov 9 '21 at 1:26
  • $\begingroup$ That linked paper in particular doesn't add or subtract in the solutions $x_{c,d}$ in the numerator. $\endgroup$ Nov 9 '21 at 3:35
2
$\begingroup$

Too long to insert in a comment. I don't think the formula can have any practical use.

Also, for large values ​​of n it does not give an exact result.

Yet this exact formula which has a similar complexity but which has no practical use:

$\pi_{\text{twin}} (n) = 1 + \\ \sum \limits_{k=1}^{\left\lfloor{\frac{n-1}{6}}\right\rfloor} {\left\lfloor \left( \displaystyle 1 + \displaystyle\sum_{a=1}^{\left\lfloor\frac{1+\sqrt{-1+6\cdot k}}{6}\right\rfloor} {\left( \left\lfloor\frac{-1+6\cdot k}{-1+6\cdot a}\right\rfloor - \left\lfloor\frac{-2+6\cdot k}{-1+6\cdot a}\right\rfloor \right)} + \displaystyle\sum_{a=1}^{\left\lfloor\frac{-1+\sqrt{-1+6\cdot k}}{6}\right\rfloor} {\left( \left\lfloor\frac{-1+6\cdot k}{1+6\cdot a}\right\rfloor - \left\lfloor\frac{-2+6\cdot k}{1+6\cdot a}\right\rfloor \right)} \\ + \displaystyle\sum_{a=1}^{\left\lfloor\frac{1+\sqrt{1+6\cdot k}}{6}\right\rfloor} {\left( \left\lfloor\frac{1+6\cdot k}{-1+6\cdot a}\right\rfloor - \left\lfloor\frac{6\cdot k}{-1+6\cdot a}\right\rfloor \right)} + \displaystyle\sum_{a=1}^{\left\lfloor\frac{-1+\sqrt{1+6\cdot k}}{6}\right\rfloor} {\left( \left\lfloor\frac{1+6\cdot k}{1+6\cdot a}\right\rfloor - \left\lfloor\frac{6\cdot k}{1+6\cdot a}\right\rfloor \right)} \right)^{-1}\right\rfloor}$

$\endgroup$
1

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.