User:FUNG Cheok Yin/proof(i) A048597

A property of the set "2, 4, 6, 10, 12" (Proof of a statement by Ely Golden in Dec 2016)

link to A048597

On Dec 05 2016, Ely Golden stated in http://oeis.org/A048597 :

It appears that 2, 4, 6, 10, 12 are all the numbers $n$ with the property that every number $m$ in the range $n<m<2n$ that is coprime to $n$ is also prime.

We would like to state it as a lemma:

Lemma I:

2, 4, 6, 10, 12 are all the numbers $n$ with the property that every number $m$ in the range $n<m<2n$ that is coprime to $n$ is also prime.

Motivation

2, 4, 6, 10 and 12 are both small integers; it makes us naturally curious whether there are some inequalities relating to the number of primes − $\pi (n)$ − and the number of integers relatively prime − $\varphi (n)$ − to compose a proof on Golden's statement.

Outline of the Proof

If $n$ is odd and $n>3$, $n-1$ is relatively prime to $n$ but composite. Hence the possible $n$'s satisfy the stated property are all even.

Lemma I implies the following inequality:

$\varphi (2n)-\varphi (n)\leq \pi (2n)-\pi (n)$

does not hold for all even $n>12$.

The following three results in analytic number theory will be used:

${\frac {n}{\ln(n)}}<\pi (n)$ for $n\geq 17$.

$\pi (n)<1.25506{\frac {n}{\ln(n)}}$ for $n\geq 1$ .

$\varphi (n)=\varphi (2^{k}m)=n(1-{\frac {1}{2}})\prod _{p'\mid n}\left(1-{\frac {1}{p'}}\right)\leq {\frac {n}{2}}$ ,for even $n>4$ and $n\neq 2^{k}$, where the numbers $p'$ in the product are running from all odd prime divisors of $n$.

The first two results came from the paper Approximate formulas for some functions of prime numbers (J. Barkley Rosser ,Lowell Schoenfeld, Illinois J. Math., p.64-94 (1962), online view). The third result comes naturally from the definition of $\varphi (n)$.

Part A

For $n=2^{k}m$, where: $m$ is odd , larger than 1; and $k$ a positive integer; we have

$\varphi (2n)=\varphi (2^{k+1}m)=2^{k}\varphi (m)$

$\varphi (n)=\varphi (2^{k}m)=2^{k-1}\varphi (m)$

$\varphi (2n)-\varphi (n)=2^{k-1}\varphi (m)=\varphi (n)<n\cdot {\frac {1}{2}}$

Part B

For $n\geq 17$,

$\pi (2n)-\pi (n)>{\frac {2n}{\ln 2n}}-1.25506\cdot {\frac {n}{\ln n}}$

$={\frac {2n}{\ln 2+\ln n}}-1.25506\cdot {\frac {n}{\ln n}}$

$>{\frac {2n}{0.69315+\ln n}}-1.25506\cdot {\frac {n}{\ln n}}$

$=n({\frac {2}{0.69315+\ln n}}-{\frac {1.25506}{\ln n}})$

The Inequalities

Considering the part A and B, $\varphi (2n)-\varphi (n)\leq \pi (2n)-\pi (n)$ holds only if :

${\frac {n}{2}}\leq n({\frac {2}{0.69315+\ln n}}-{\frac {1.25506}{\ln n}})$ for $n\geq 17$. (*)

It remains to find for which values of $n$ the inequality

${\frac {1}{2}}\leq {\frac {2}{0.69315+\ln n}}-{\frac {1.25506}{\ln n}}$

holds.

Let

$K(x):={\frac {2}{0.69315+\ln x}}-{\frac {1}{\ln x}}$, defined on $n\in [3,\infty ]$

$K(n)\geq {\frac {2}{0.69315+\ln n}}-{\frac {1.25506}{\ln n}}$ for all $n\geq 3$

$K(n)={\frac {2\ln n-0.69315-\ln n}{(0.69315+\ln n)(\ln n)}}$

$={\frac {\ln n-0.69315}{(0.69315+\ln n)(\ln n)}}$

Being evaluated numerically, the maximum value of $K(x)$ is roughly 0.24753, at $x\approx 5.3303$.

Hence $K(x)<0.5$ for all $n\geq 3$.

To sum up, ${\frac {1}{2}}>K(n)>{\frac {2}{0.69315+\ln n}}-{\frac {1.25506}{\ln n}}$ for $n\geq 3$.

Hence $\varphi (2n)-\varphi (n)\leq \pi (2n)-\pi (n)$ may hold only for $n\in [2,16]$.

To Conclude

Reviewing the constraints in the previous parts, all we need to do now, is checking for the small interval $n$ = 2 to 17, $n$ even, which $n$'s have the stated property in Lemma I.

• 2: 2 < 3 < 4; 3 is prime.
• 4: 4 < 5 < 7 < 8; 5 and 7 are prime.
• 6: 6 < 7 < 9 < 11 < 12; 7 and 11 are prime, 9 and 6 have a common divisor 3.
• 8: 8 < 9 < ... < 16; 9 and 8 are relatively prime but 9 is composite.
• 10: 10 < 11 < 13 < 15 < 17 < 19 < 20; 11, 13, 17 and 19 are prime, 15 and 10 have a common divisor 5.
• 12: 12 < 13 < 15 < 17 < 19 < 21 < 23 < 24; 13, 17, 19 and 23 are prime, 12, 15 and 21 have a common divisor 3.
• 14: 14 < 15 ... < 28; 15 and 14 are relatively prime but 15 is composite.
• 16: 16 < 17 < 19 < 21 < ... < 25 < 27 < ... < 32; as a power of 2, 16 is relatively prime to 21, 25 and 27 but the three are composite.

After the above enumerations, we know those $n$'s satisfying the property suggested by Golden, what in the beginning of this disclosure, are 2, 4, 6, 10 and 12. $\square$

Draft began on Aug 11 2017

Finished on Dec 24 2020