# The values of $n$ which satisfy an inequality about prime numbers

For which values of $n$ does the following inequality hold for?

$$2(n-2) < Ap_n\prod_{i=3}^n \left(\frac{p_i-1}{p_i}\right)$$

$p$ are prime numbers and the notation $p_i$ indicates the $i$-th prime number as per convention.

$A$ is defined by the following relationship $p_n = 6A + r$ and $0\leq r<6$

Context

The inequality comes from this question (https://math.stackexchange.com/questions/1718774/a-necklace-problem-related-to-the-modulo-function)

• Since A is greater than n/6, you should show by elementary means ( using a theorem of Mertens if needed ) that A times the product is greater than 1 for n greater than 5. This and a small amount of computation should establish the inequality for n greater than 3. Gerhard "Mertens Often Makes Things Simpler" Paseman, 2016.03.29. – Gerhard Paseman Mar 29 '16 at 21:45

## 1 Answer

Here is a proof that the inequality holds for $n\geq 9$. I let you verify the remaining cases $n\leq 8$.

Let $x:=p_n$ so that $x\geq 23$ by $n\geq 9$. Then the inequality can be rewritten as $$2\bigl(\pi(x)-2\bigr)<\left\lfloor\frac{x}{6}\right\rfloor x \prod_{3\leq p\leq x}\frac{p-1}{p}.$$ By increasing the LHS and decreasing the RHS, we get the following stronger inequality: $$2\pi(x)<\frac{(x-5)x}{6}\prod_{3\leq p\leq x}\frac{p-1}{p}.$$ We shall further increase the LHS and decrease the RHS by using the bounds in the famous paper of Rosser-Schoenfeld (1961): Approximate formulas for some functions of prime numbers. Using (3.6) and (3.27) in this paper, we see that it suffices to show $$\frac{8 x}{3\log x}<\frac{(x-5)x}{6\log x}\left(1-\frac{1}{\log^2 x}\right),$$ that is, $$16 < (x-5) \left(1-\frac{1}{\log^2 x}\right).$$ However, this last inequality is clear by $x\geq 23$. Done.

Added. The OP mentioned in a comment the following related problem. This can be solved in much the same way, using that $$\left(\frac{p-1}{p}\right)^3<\frac{p-2}{p}.$$ So, unless $x$ is very small, the sharper inequality in the above related problem is also true.

• GH from MO, it is nice solution! – Shahrooz Janbaz Mar 30 '16 at 10:48
• Thank you very much; a related problem (math.stackexchange.com/questions/1720346/…) – Brad Graham Mar 30 '16 at 14:11
• @BradGraham: See my Added section. – GH from MO Mar 30 '16 at 16:19
• @BradGraham: In your 2 stackexchange posts, please mention the above response of mine (to avoid duplicate efforts). – GH from MO Mar 30 '16 at 16:46
• @GHfromMO I've done that! Thank you so much for your answer, has really helped! – Brad Graham Mar 30 '16 at 17:35