How to prove than $p_{2n}-(p_{2n}\mod p_{n}) = 2p_{n}$ ? where $p_{n}$ is the $_{n}$th prime number ? (for $n$ > 1)

Question

Let the prime function $p_n$ be the $n$th prime number.

For example $p_1$ = 2, $p_2$ = 3, $p_3$ = 5, $p_4$ = 7, $p_5$ = 11 etc.

I noticed something with the prime function : it seems than $p_{2n}-(p_{2n}\mod p_{n}) = 2p_{n}$, for $n$ > 1

For example :

• $p_{4}-(p_{4}\mod p_{2})$ = 7 - (7 mod 3) = 6 = 2*3
• $p_{6}-(p_{6}\mod p_{3})$ = 13 - (13 mod 5) = 10 = 2*5
• $p_{8}-(p_{8}\mod p_{4})$ = 19 - (19 mod 7) = 14 = 2*7
• $p_{100}-(p_{100}\mod p_{50})$ = 541 - (541 mod 229) = 458 = 2*229

It seems than $p_{2n}$ is connected with $p_n$. This is something counter-intuitive for me because this is the first time I see a link with $p_{2n}$ and $p_n$ and I thought there was no link about these two numbers.

Is there a way to explain that ? I don't know how to start for proving it.

Answer 1

This does not really say anything special about the relation between $p_{2n}$ and $p_n$. Consider the following. Let $p$ be a prime, and let $q$ be any integer in the interval $2p<q<3p$. Then $q=2p+k$ with $0<k<p$ and $$ q-(q\bmod p)=q-k=2p. $$

The prime number theorem implies (I think) that more often than not $$2p_n<p_{2n}<3p_n$$ and that's all you are seeing.

---

If we take the prime number theorem super seriously, then $p_n\approx n\ln n$. Therefore we have every right to expect $$p_{2n}\approx(2n)\ln(2n)=2n\ln n+2n\ln 2\approx 2p_n+2n\ln2$$ to be in the interval $(2p_n,3p_n)$.

---

I tested the analogous conjecture relating $p_{3n}$ and $p_n$. For all $n>34$ we seem to have $$ p_{3n}-(p_{3n}\bmod p_n)=3p_n. $$ It fails, possibly for the last time, when $n=34$, $p_{34}=139$, $p_{102}=557\equiv1\pmod{139}$. In this case $p_{3n}$ exceeds $4p_n$ by a whisker.

Answer 2

To complete the proof, we must show that $2p_n < p_{2n} < 3p_n$ for all $n>1$.

Let's restate this in terms of the prime counting function $\pi(x)$. If $x = p_n$, then we want $2x < p_{2n}$ or $\pi(2x) < 2n = 2 \pi(x)$, as well as $3x > p_{2n}$ or $\pi(3x) > 2 \pi(x)$.

For this, I am going to borrow from Wikipedia a relatively clean bound from Dusart's "Estimates of Some Functions Over Primes without R.H": for $x \ge 60184$, $$ \frac{x}{\log x - 1} < \pi(x) < \frac{x}{\log x -1.1}. $$ This inequality means that for $x$ at least that large, $$ \frac{2x}{\log(2x)-1.1} < 2 \cdot \frac{x}{\log x - 1} \implies \pi(2x) < 2\pi(x) $$ and the first inequality holds for all $x$ for which the denominators are positive, since the difference between $1$ and $1.1$ is less than $\log (2x) - \log x = \log 2$. Using the same estimate, we have $$ \frac{3x}{\log(3x)-1} > 2 \cdot \frac{x}{\log(x)-1.1} \implies \pi(3x) > 2\pi(x). $$ The first inequality here says $3(\log x - \frac{11}{10}) > 2(\log(3x)-1)$ or $\log x > \frac{33}{10} + 2\log 3 - 2$, which in particular holds for $x \ge 34$.

---

So this says that when $p_n > 60184$, the bound we want holds. The largest prime below this range is $p_{6076} = 60169$, so we check the rest with brute force in Mathematica:

And @@ Table[2 Prime[n] < Prime[2 n] < 3 Prime[n], {n, 2, 6076}]

We get True i.e. the bound holds for all $n>1$.

---

Looking at the upper bound on $\pi(x)$ more carefully, it appears that $1.1$ is actually a uniquely bad value - in the sense that the requirements on $x$ are not worth it. Just from numerical tests (which we can limit to $x \le 60184$) it appears that $$ \pi(x) < \frac{x}{\log x - 9/8} $$ for all $x \ge 4$, but if we want to improve $\frac98$ to $\frac{10}{9}$, then we need to assume $x \ge 24140$.

Using Dusart's bounds to limit our tests to finitely many $x$, we can verify for all $x \ge 59$ the bounds $$ \frac{x}{\log x - 1/2} < \pi(x) < \frac{x}{\log x - 9/8}. $$ I stand by these bounds as being a good compromise between approximating $\pi(x)$ well, and not asking a lot from $x$.

We can use these in the same way as earlier to prove that $\pi(2x) < 2\pi(x)$ for all $x \ge 59$ and $\pi(3x) > 2\pi(x)$ for all $x \ge 97$. Therefore provided $p_n \ge 97$, we have $2p_n < p_{2n} < 3p_n$; now we only need to check $n=2, 3, \dots, 24$ separately.

Answer 3

Let's begin with an argument that doesn't quite work:

From the Wikipedia entry for PNT, we have

$$\log n+\log\log n-1\lt{p_n\over n}\lt\log n+\log\log n$$

for $n\ge6$. It follows that

$${\log2n+\log\log2n-1\over\log n+\log\log n}\lt{p_{2n}\over2p_n}\lt{\log2n+\log\log2n\over\log n+\log\log n-1}$$

(again for $n\ge6$). Now it's not too hard to show that the upper bound is less than $3/2$ for $n\gt32$:

$$\begin{align} {\log2n+\log\log2n\over\log n+\log\log n-1}\lt{3\over2} &\iff2(\log2+\log n+\log\log2 n)\lt3(\log n+\log\log n-1)\\ &\iff3+2\log2\lt\log n+\log\left((\log n)^3\over(\log n+\log2)^2\right) \end{align}$$

establishes the inequality eventually holds, and a little numerical experimentation confirms that

$$\log32+\log\left((\log32)^3\over(\log32+\log2)^2\right)\lt3+2\log2\lt\log33+\log\left((\log33)^3\over(\log33+\log2)^2\right)$$

This shows that $p_{2n}\lt3p_n$ for $n\ge33$, which is easily extended to $p_{2n}\lt3p_n$ for all $n$.

Now it would be nice if the lower bound were eventually greater than $1$. Unfortunately, it's not. To get a lower bound that works requires a closer look at the paper by Dusart that is the source of the bounds. Dusart states (without proof) a more exact upper bound

$${p_n\over n}\lt\log n+\log\log n-0.9484$$

for $k\ge39017$. This gives us

$${\log2n+\log\log2n-1\over\log n+\log\log n-0.9484}\lt{p_{2n}\over2p_n}$$

and this lower bound is greater than $1$, since $\log\log n$ is clearly less than $\log\log2n+\ln2-0.0516$ for all $n\ge1$.

In sum, we have $2p_n\lt p_{2n}\lt3p_n$ for all $n\ge39017$, from which it follows that

$$p_{2n}-(p_{2n}\text{ mod }p_n)=p_{2n}-(p_{2n}-2p_n)=2p_n$$

for $n\ge39017$. Thus if there are any counterexamples to the OP's observation, they would have to occur with $n\lt39017$. Presumably none exist; perhaps someone can confirm this.

Answer 4

I would like to just point out that while the case $a \neq 2$ it is not the case that the generalized conjecture is true (for all $n \gt 1$):

from sympy import primerange, prime

A = 100
N = 100

primes = list(primerange(2, prime(N*A) + 1))

for x in range(2, N+1):
    p = primes[x-1]
    for a in range(2,A+1):
        q = primes[a*x-1]
        
        diff = q - a*p
        modulo = q % p
        
        if modulo != diff:
            print(f'Counter-example: p({a}*{x}) - {a}*p({x}) = {diff}, but p({a}*{x}) % p({x}) = {modulo}')
    

Which prints:

Counter-example: p(3*2) - 3*p(2) = 4, but p(3*2) % p(2) = 1
Counter-example: p(4*2) - 4*p(2) = 7, but p(4*2) % p(2) = 1
Counter-example: p(5*2) - 5*p(2) = 14, but p(5*2) % p(2) = 2
Counter-example: p(6*2) - 6*p(2) = 19, but p(6*2) % p(2) = 1
Counter-example: p(7*2) - 7*p(2) = 22, but p(7*2) % p(2) = 1
Counter-example: p(8*2) - 8*p(2) = 29, but p(8*2) % p(2) = 2
Counter-example: p(9*2) - 9*p(2) = 34, but p(9*2) % p(2) = 1
Counter-example: p(10*2) - 10*p(2) = 41, but p(10*2) % p(2) = 2
Counter-example: p(11*2) - 11*p(2) = 46, but p(11*2) % p(2) = 1
Counter-example: p(12*2) - 12*p(2) = 53, but p(12*2) % p(2) = 2
Counter-example: p(13*2) - 13*p(2) = 62, but p(13*2) % p(2) = 2
Counter-example: p(14*2) - 14*p(2) = 65, but p(14*2) % p(2) = 2
Counter-example: p(15*2) - 15*p(2) = 68, but p(15*2) % p(2) = 2
Counter-example: p(16*2) - 16*p(2) = 83, but p(16*2) % p(2) = 2
Counter-example: p(17*2) - 17*p(2) = 88, but p(17*2) % p(2) = 1
Counter-example: p(18*2) - 18*p(2) = 97, but p(18*2) % p(2) = 1
Counter-example: p(19*2) - 19*p(2) = 106, but p(19*2) % p(2) = 1
Counter-example: p(20*2) - 20*p(2) = 113, but p(20*2) % p(2) = 2
Counter-example: p(21*2) - 21*p(2) = 118, but p(21*2) % p(2) = 1
Counter-example: p(22*2) - 22*p(2) = 127, but p(22*2) % p(2) = 1
Counter-example: p(23*2) - 23*p(2) = 130, but p(23*2) % p(2) = 1
Counter-example: p(24*2) - 24*p(2) = 151, but p(24*2) % p(2) = 1
Counter-example: p(25*2) - 25*p(2) = 154, but p(25*2) % p(2) = 1
Counter-example: p(26*2) - 26*p(2) = 161, but p(26*2) % p(2) = 2
Counter-example: p(27*2) - 27*p(2) = 170, but p(27*2) % p(2) = 2
Counter-example: p(28*2) - 28*p(2) = 179, but p(28*2) % p(2) = 2
Counter-example: p(29*2) - 29*p(2) = 184, but p(29*2) % p(2) = 1
Counter-example: p(30*2) - 30*p(2) = 191, but p(30*2) % p(2) = 2
Counter-example: p(31*2) - 31*p(2) = 200, but p(31*2) % p(2) = 2
Counter-example: p(32*2) - 32*p(2) = 215, but p(32*2) % p(2) = 2
Counter-example: p(33*2) - 33*p(2) = 218, but p(33*2) % p(2) = 2
Counter-example: p(34*2) - 34*p(2) = 235, but p(34*2) % p(2) = 1
Counter-example: p(35*2) - 35*p(2) = 244, but p(35*2) % p(2) = 1
Counter-example: p(36*2) - 36*p(2) = 251, but p(36*2) % p(2) = 2
Counter-example: p(37*2) - 37*p(2) = 262, but p(37*2) % p(2) = 1
Counter-example: p(38*2) - 38*p(2) = 269, but p(38*2) % p(2) = 2
Counter-example: p(39*2) - 39*p(2) = 280, but p(39*2) % p(2) = 1
Counter-example: p(40*2) - 40*p(2) = 289, but p(40*2) % p(2) = 1
Counter-example: p(41*2) - 41*p(2) = 298, but p(41*2) % p(2) = 1
Counter-example: p(42*2) - 42*p(2) = 307, but p(42*2) % p(2) = 1
Counter-example: p(43*2) - 43*p(2) = 314, but p(43*2) % p(2) = 2
Counter-example: p(44*2) - 44*p(2) = 325, but p(44*2) % p(2) = 1
Counter-example: p(45*2) - 45*p(2) = 328, but p(45*2) % p(2) = 1
Counter-example: p(46*2) - 46*p(2) = 341, but p(46*2) % p(2) = 2
Counter-example: p(47*2) - 47*p(2) = 350, but p(47*2) % p(2) = 2
Counter-example: p(48*2) - 48*p(2) = 359, but p(48*2) % p(2) = 2
Counter-example: p(49*2) - 49*p(2) = 374, but p(49*2) % p(2) = 2
Counter-example: p(50*2) - 50*p(2) = 391, but p(50*2) % p(2) = 1
Counter-example: p(51*2) - 51*p(2) = 404, but p(51*2) % p(2) = 2
Counter-example: p(52*2) - 52*p(2) = 413, but p(52*2) % p(2) = 2
Counter-example: p(53*2) - 53*p(2) = 418, but p(53*2) % p(2) = 1
Counter-example: p(54*2) - 54*p(2) = 431, but p(54*2) % p(2) = 2
Counter-example: p(55*2) - 55*p(2) = 436, but p(55*2) % p(2) = 1
Counter-example: p(56*2) - 56*p(2) = 445, but p(56*2) % p(2) = 1
Counter-example: p(57*2) - 57*p(2) = 448, but p(57*2) % p(2) = 1
Counter-example: p(58*2) - 58*p(2) = 467, but p(58*2) % p(2) = 2
Counter-example: p(59*2) - 59*p(2) = 470, but p(59*2) % p(2) = 2
Counter-example: p(60*2) - 60*p(2) = 479, but p(60*2) % p(2) = 2
Counter-example: p(61*2) - 61*p(2) = 490, but p(61*2) % p(2) = 1
Counter-example: p(62*2) - 62*p(2) = 497, but p(62*2) % p(2) = 2
Counter-example: p(63*2) - 63*p(2) = 512, but p(63*2) % p(2) = 2
Counter-example: p(64*2) - 64*p(2) = 527, but p(64*2) % p(2) = 2
Counter-example: p(65*2) - 65*p(2) = 538, but p(65*2) % p(2) = 1
Counter-example: p(66*2) - 66*p(2) = 545, but p(66*2) % p(2) = 2
Counter-example: p(67*2) - 67*p(2) = 556, but p(67*2) % p(2) = 1
Counter-example: p(68*2) - 68*p(2) = 565, but p(68*2) % p(2) = 1
Counter-example: p(69*2) - 69*p(2) = 580, but p(69*2) % p(2) = 1
Counter-example: p(70*2) - 70*p(2) = 599, but p(70*2) % p(2) = 2
Counter-example: p(71*2) - 71*p(2) = 608, but p(71*2) % p(2) = 2
Counter-example: p(72*2) - 72*p(2) = 611, but p(72*2) % p(2) = 2
Counter-example: p(73*2) - 73*p(2) = 620, but p(73*2) % p(2) = 2
Counter-example: p(74*2) - 74*p(2) = 635, but p(74*2) % p(2) = 2
Counter-example: p(75*2) - 75*p(2) = 638, but p(75*2) % p(2) = 2
Counter-example: p(76*2) - 76*p(2) = 653, but p(76*2) % p(2) = 2
Counter-example: p(77*2) - 77*p(2) = 656, but p(77*2) % p(2) = 2
Counter-example: p(78*2) - 78*p(2) = 677, but p(78*2) % p(2) = 2
Counter-example: p(79*2) - 79*p(2) = 692, but p(79*2) % p(2) = 2
Counter-example: p(80*2) - 80*p(2) = 701, but p(80*2) % p(2) = 2
Counter-example: p(81*2) - 81*p(2) = 710, but p(81*2) % p(2) = 2
Counter-example: p(82*2) - 82*p(2) = 725, but p(82*2) % p(2) = 2
Counter-example: p(83*2) - 83*p(2) = 734, but p(83*2) % p(2) = 2
Counter-example: p(84*2) - 84*p(2) = 745, but p(84*2) % p(2) = 1
Counter-example: p(85*2) - 85*p(2) = 758, but p(85*2) % p(2) = 2
Counter-example: p(86*2) - 86*p(2) = 763, but p(86*2) % p(2) = 1
Counter-example: p(87*2) - 87*p(2) = 772, but p(87*2) % p(2) = 1
Counter-example: p(88*2) - 88*p(2) = 785, but p(88*2) % p(2) = 2
Counter-example: p(89*2) - 89*p(2) = 794, but p(89*2) % p(2) = 2
Counter-example: p(90*2) - 90*p(2) = 799, but p(90*2) % p(2) = 1
Counter-example: p(91*2) - 91*p(2) = 818, but p(91*2) % p(2) = 2
Counter-example: p(92*2) - 92*p(2) = 821, but p(92*2) % p(2) = 2
Counter-example: p(93*2) - 93*p(2) = 830, but p(93*2) % p(2) = 2
Counter-example: p(94*2) - 94*p(2) = 841, but p(94*2) % p(2) = 1
Counter-example: p(95*2) - 95*p(2) = 866, but p(95*2) % p(2) = 2
Counter-example: p(96*2) - 96*p(2) = 875, but p(96*2) % p(2) = 2
Counter-example: p(97*2) - 97*p(2) = 890, but p(97*2) % p(2) = 2
Counter-example: p(98*2) - 98*p(2) = 899, but p(98*2) % p(2) = 2
Counter-example: p(99*2) - 99*p(2) = 916, but p(99*2) % p(2) = 1
Counter-example: p(100*2) - 100*p(2) = 923, but p(100*2) % p(2) = 2
Counter-example: p(3*3) - 3*p(3) = 8, but p(3*3) % p(3) = 3
Counter-example: p(4*3) - 4*p(3) = 17, but p(4*3) % p(3) = 2
Counter-example: p(5*3) - 5*p(3) = 22, but p(5*3) % p(3) = 2
Counter-example: p(6*3) - 6*p(3) = 31, but p(6*3) % p(3) = 1
Counter-example: p(7*3) - 7*p(3) = 38, but p(7*3) % p(3) = 3
Counter-example: p(8*3) - 8*p(3) = 49, but p(8*3) % p(3) = 4
Counter-example: p(9*3) - 9*p(3) = 58, but p(9*3) % p(3) = 3
Counter-example: p(10*3) - 10*p(3) = 63, but p(10*3) % p(3) = 3
Counter-example: p(11*3) - 11*p(3) = 82, but p(11*3) % p(3) = 2
Counter-example: p(12*3) - 12*p(3) = 91, but p(12*3) % p(3) = 1
Counter-example: p(13*3) - 13*p(3) = 102, but p(13*3) % p(3) = 2
Counter-example: p(14*3) - 14*p(3) = 111, but p(14*3) % p(3) = 1
Counter-example: p(15*3) - 15*p(3) = 122, but p(15*3) % p(3) = 2
Counter-example: p(16*3) - 16*p(3) = 143, but p(16*3) % p(3) = 3
Counter-example: p(17*3) - 17*p(3) = 148, but p(17*3) % p(3) = 3
        

Programatically, it does seem to hold for $a = 2$.

I think you'll keep on seeing counter examples for say $a = 3$, as you let $N$ increase in the program. Therefore, this conjecture only holds when $a = 2$.

But according to Jyrki Lahtonen in another answer, there probably exists some point at which you'll stop seeing counter-examples for each given $a$. Thus a general conjecture should start out saying that there exists some $N_a$ such that for all $n \geq N_a$ the statement is true.