Let $p \ge 5$ be a prime. Let $x \ge 20$ be an integer. Let $p\#$ be the primorial for $p$.
Let $|\{ i \le x \, \wedge \gcd(i,p\#)=1\}|$ be the count of integers less than or equal to $x$ that are relatively prime to $p\#$.
Is it true that:
$$|\{ i \le x \, \wedge \gcd(i,p\#)=1\}| \le \dfrac{x-2}{3}$$
If it is true, is there a more concise argument than my reasoning below?
Here's my reasoning:
- $\gcd(i,p\#)=1$ only if $\gcd(i,5\#)=1$
- $|\{ i \le x \, \wedge \gcd(i,p\#)=1\}| \le |\{ i \le x \, \wedge \gcd(i,5\#)=1\}|$
- $|\{ i \le 20 \, \wedge \gcd(i,5\#)=1\}| = 6 = \dfrac{20-2}{3}$
- Assume it is true up to $x \ge 20$
- If $\gcd(x+1,5\#) > 1$, then $|\{ i \le x+1 \, \wedge \gcd(i,5\#)=1\}| = |\{ i \le x \, \wedge \gcd(i,5\#)=1\}|$
- So, we can assume that $\gcd(x+1,5\#)=1$
- There exists $c,d$ such that $x+1 = 30d+c$ where $c \in \{1,7,11,13,17,19,23,29\}$
- We can assume $d \ge 1$ since:
$$|\{ i \le 23 \, \wedge \gcd(i,5\#)=1\}| = 7 = \dfrac{23-2}{3}$$ $$|\{ i \le 29 \, \wedge \gcd(i,5\#)=1\}| = 8 < \dfrac{29-2}{3}$$
- We can now show it is true for each value of $c$:
$$|\{ i \le 30d+1 \, \wedge \gcd(i,5\#)=1\}| = 8d+1 < \dfrac{30d-1}{3} = 10d - \dfrac{1}{3}$$
$$|\{ i \le 30d+7 \, \wedge \gcd(i,5\#)=1\}| = 8d+2 < \dfrac{30d+5}{3} = 10d + \dfrac{5}{3}$$
$$|\{ i \le 30d+11 \, \wedge \gcd(i,5\#)=1\}| = 8d+3 < \dfrac{30d+9}{3} = 10d + 3$$
$$|\{ i \le 30d+13 \, \wedge \gcd(i,5\#)=1\}| = 8d+4 < \dfrac{30d+11}{3} = 10d + \dfrac{11}{3}$$
$$|\{ i \le 30d+17 \, \wedge \gcd(i,5\#)=1\}| = 8d+5 < \dfrac{30d+15}{3} = 10d + 5$$
$$|\{ i \le 30d+19 \, \wedge \gcd(i,5\#)=1\}| = 8d+6 < \dfrac{30d+17}{3} = 10d + \dfrac{17}{3}$$
$$|\{ i \le 30d+23 \, \wedge \gcd(i,5\#)=1\}| = 8d+7 < \dfrac{30d+21}{3} = 10d + 7$$
$$|\{ i \le 30d+29 \, \wedge \gcd(i,5\#)=1\}| = 8d+8 < \dfrac{30d+27}{3} = 10d + 9$$
Yes, it is true.
For $x = 6k \equiv 0 \bmod 6$, there are exactly $2k=\frac{x}{3}$ numbers $i\le x$ that are coprime to $6 = 3\#$ - every $i\equiv 1 \text{ or }5 \bmod 6$. Clearly for $x=3k$ it is also true that there are exactly $\frac{x}{3}$ numbers $i\le x$ that are coprime to $6$.
If we assume $x\ge 5$ and we also eliminate numbers that are multiples of $5$ (ie. only count numbers that are coprime to $5\#$), we have eliminated at least one more number ($5$) and the total drops to $\frac{x}{3}-1 < \frac{x-2}{3}$ for multiples of $3$. The only troublesome case in between multiples of $3$ occurs at $x\equiv 1 \bmod 6$, when a new coprime case is introduced before $\frac{x-2}{3}$ has reached the next integer.
Once we reach $x \ge 25$ we know that the maximum possible total at $x=3k$ is $\frac{x}{3}-2$ (because two multiples of $5$ that are coprime to $6$ have been included) and so the condition will always hold. The next smallest case of $x\equiv 1 \bmod 6 $ is $x=19$ so by choosing $x\ge 20$ we eliminate that last case.