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)

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.

• Note that the left hand is always a multiple of $p_n$ so all you have to do is to rule out cases where it equals $p_n$ or is at least $3p_n$.
– lulu
Commented Sep 26, 2021 at 15:11
• Very roughly, $p_n\approx n\ln n$, so $p_{2n}/p_n$ should, in the limit at least, be slightly larger than $2$, hence $p_{2n}$ mod $p_n$ should be $p_{2n}-2p_n$. The trick will be to replace the limiting approximation with rigorous inequalities that hold for all $n$ (or at least all $n$ greater than some specified number, with mop-up calculations to handle the remaining smaller cases). Commented Sep 26, 2021 at 15:19
• @user10354138, I'm not sure that PNT by itself is enough to conclude that a ratio that's asymptotically close to $2+2\log2/\log n$ can't be less than $2$ for infinitely many $n$; you need to have an error term for the approximation. Commented Sep 26, 2021 at 15:25
• I want to note that your conjecture is equivalent to $\lfloor \dfrac{p_{an}}{p_n} \rfloor = a$ for the case $a = 2$. I did that by expanding the remainder you have going on into $p_{2n} - (p_{2n} - \lfloor \dfrac{ p_{2n}}{p_n} \rfloor p_n) = p_n \iff$ the shorter form . This is quite an elegant theorem then! Commented Oct 2, 2021 at 1:10

4 Answers

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.

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. Then $$q=2p+k$$ with $$0 and $$q-(q\bmod p)=q-k=2p.$$

The prime number theorem implies (I think) that more often than not $$2p_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.

• As Barry Cipra commented, to prove such results, we can test for small values of $n$, and then apply sufficiently accurate estimates for $p_n$. Those are beyond me. Leaving this oversized comment as a CW answer. Commented Sep 26, 2021 at 15:23

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.

• 23 seconds of Mathematica does confirm it :) It would be interesting to find a proof with less initial casework required. Commented Sep 26, 2021 at 19:59
• @MishaLavrov, thanks for the (quick!) confirmation. Agreed, it'd be nice to have something with less casework. (Did your computation tell you how close $p_{2n}/p_n$ actually ever came to $2$?) Commented Sep 27, 2021 at 1:01
• It depends on the range you look at! Small values of $n$ cause more trouble for us, but large values of $n$ cause more trouble for the inequality. Over $2 \le n \le 100000$, the minimum value is $\frac{2719531}{1285507} \approx 2.115$ when $n = 98997$. So I think the short answer is "not particularly close to $2$". Commented Sep 27, 2021 at 1:11

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.