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$


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

  • 3
    $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Mar 29 '16 at 21:45

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.

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

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.