18
$\begingroup$

It is well known that:

$$\zeta(s):=\prod_{n=1}^{\infty} \frac{1}{1-p_n^{-s}} \qquad \Re(s) \gt 1$$

with $p_n =$ the $n$-th prime. It also known that:

$$\zeta(2n):= \frac{(-1)^{n+1} B_{2n}(2\pi)^{2n}}{2(2n)!}$$

where $B_{2n}$ is the $2n$-th Bernoulli number.

Now define the function:

$$f(k,N,x):= \zeta(2k) - \left(\prod_{n=1}^{N} \frac{1}{1-p_n^{-2k}}\right)\cdot \left(\frac{1}{1-x^{-2k}}\right) \qquad \Re(s) \gt 1$$

where $k, N \in \mathbb{N}$ and $x$ is the unknown next prime ($p_{N+1}$) to be computed.

I found numerically that solving $x$ in $f(k,N,x)=0$ for some $N$, yields an increasingly accurate approximation of $p_{N+1}$ when $k$ increases. For example take the first 6 primes and try to derive the 7th prime (17):

$f(6, 6, x) = 0 \rightarrow x = 16.64054...$

$f(12, 6, x) = 0 \rightarrow x = 16.95214...$

$f(24, 6, x) = 0 \rightarrow x =16.99830...$

The key question is how high $k$ needs to go to ensure that $x=p_{N+1}$ after rounding. In the following Maple code, I simply used $k=2N$ and it already correctly generates all 'next' primes up to $N=60$:

Digits:=600
for N from 1 to 60 do ithprime(N), ithprime(N+1), round(fsolve(f(2*N, N, x), x = 0 .. 300)) end do

I immediately acknowledge that this is a highly inefficient and impractical algorithm to generate primes. However, is there more to say about the minimally required value of $k$ (maybe as a function of $N$) to ensure that rounding $x$ will correctly yield $p_{N+1}$?

$\endgroup$
  • 5
    $\begingroup$ this is cool. its like an analytic approach to finding primes $\endgroup$ – frogeyedpeas Jul 10 at 17:20
  • 1
    $\begingroup$ It's not too difficult to show that $k=p_N$ works, and that we need $k\ge c p_N$ for some positive constant $c$ in case $p_{N+2}=p_{N+1}+2$. $\endgroup$ – Andreas Weingartner Jul 10 at 23:44
15
$\begingroup$

$2k=1+p_N$ works for $N>1$, but $2k\le 0.56 \, p_N$ will fail if $p_{N+2}=p_{N+1}+2$.

With $q=p_{N+1}$, we have $$ \frac{1}{1-q^{-2k}} < \frac{1}{1-x^{-2k}} = \frac{1}{1-q^{-2k}} \prod_{p>q} \frac{1}{1-p^{-2k}} . $$ It follows that $$ q^{-2k} < x^{-2k} < q^{-2k} + \sum_{j\ge 2} (q+j)^{-2k} < q^{-2k} +\frac{1}{(q+1)^{2k-1}(2k-1)}. $$ Taking logarithms, and using $\log(1+y)\le y$, we get $$ -2k \log q < -2k \log x < -2k\log q + \frac{q+1}{\exp\{(1-o(1)) 2k/q\} (2k-1)}. $$ Dividing by $-2k$ and exponentiating, we have $$ q > x > q - \frac{q(q+1)}{\exp\{(1-o(1))2k/q\} 2k (2k-1)}. $$ We want the last expression to be less than $1/2$. Since $q/p_N \to 1 $ as $N\to \infty$, we need $k\ge (1+o(1)) c \, p_N$, where $c=0.45...$ is the solution to $e^{2c}4 c^2=2$. So $2k=1+p_N$ works for large $N$. We can check with a computer that it also works for small $N$. Similar calculations show that when $p_{N+2}=p_{N+1}+2$, it is necessary that $k>0.28 \, p_N$ when $N$ is large.

Edit: Using the inequality $\log(1+y)\le y$ was somewhat wasteful and not necessary. Also, as the OP points out in the comments, we can use the ceiling function instead of rounding, since $x<q$. With those two modifications, we find that $k\ge \frac{1}{3}p_N$ works for $N\ge 1$, but $k\le 0.19 \, p_N$ fails at twin primes $p_{N+2}=p_{N+1}+2$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Many thanks, Andreas! One more observation that could maybe help sharpening these bounds. Numerical evidence suggests (I have no proof) that when $k$ increases, $x$ always approaches $p_{N+1}$ from 'below'. So, if this is true, could using the ceiling instead of rounding $x$ improve the bound by a factor $2$? $\endgroup$ – Agno Jul 11 at 14:59
  • 1
    $\begingroup$ Yes, the last display of my answer shows that $x<q=p_{N+1}$. Using the ceiling instead of rounding will always work if $2k \ge 0.71 \, p_N$, but will fail at twin primes if $2k\le 0.38 \, p_N$. $\endgroup$ – Andreas Weingartner Jul 11 at 16:00

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.