4
$\begingroup$

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)

Improve this question
$\endgroup$
1
  • 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
    Commented Mar 29, 2016 at 21:45

1 Answer 1

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ GH from MO, it is nice solution! $\endgroup$
    – Shahrooz
    Commented Mar 30, 2016 at 10:48
  • $\begingroup$ Thank you very much; a related problem (math.stackexchange.com/questions/1720346/…) $\endgroup$
    – Brad Graham
    Commented Mar 30, 2016 at 14:11
  • $\begingroup$ @BradGraham: See my Added section. $\endgroup$
    – GH from MO
    Commented Mar 30, 2016 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
    Commented Mar 30, 2016 at 16:46
  • $\begingroup$ @GHfromMO I've done that! Thank you so much for your answer, has really helped! $\endgroup$
    – Brad Graham
    Commented Mar 30, 2016 at 17:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .