Show that there is always one integer $t$ with a least prime factor $> 5$ where $x < t \le x+6$

Question

Let $p_k$ be the $k$th prime.

Let $f_2(x) = \lfloor x\rfloor - \left\lfloor\dfrac{x}{2}\right\rfloor$

For $k > 1$, let:

$f_{p_k}(x) = f_{p_{k-1}}(\lfloor x\rfloor) - f_{p_{k-1}}\left(\left\lfloor\dfrac{x}{p_k}\right\rfloor\right)$

Let $x \ge 1$ be an integer.

Show that $f_5(x+6) - f_5(x) > 0$

I find this problem easy to solve but challenging to answer concisely.

Please let me know if I made a mistake or if my answer could be more concise.

$f_5(x+6) - f_5(x) = \sum\limits_{i|30}\left(\left\lfloor\dfrac{x+6}{i}\right\rfloor-\left\lfloor\dfrac{x}{i}\right\rfloor\right)\mu(i)$

where $\mu(i)$ is the möbius function.

Let $r(x,d)$ be the remainder of $x$ when divided by $d$.

Clearly:

• $r(x+6,2) = r(x,2)$
• $r(x+6,3) = r(x,3)$
• $r(x+6,6) = r(x,6)$

So that:

$f_5(x+6) - f_5(x) = (x+6 - x) - \left(\dfrac{x+6 - x}{2}\right) - \left(\dfrac{x+6 - x}{3}\right)- \left(\dfrac{x+6 - x - r(x+6,5) + r(x,5)}{5}\right)+ \left(\dfrac{x+6 - x}{6}\right)+ \left(\dfrac{x+6 - x - r(x+6,10) + r(x,10)}{10}\right) + \left(\dfrac{x+6 - x - r(x+6,15) + r(x,15)}{15}\right) - \left(\dfrac{x+6 - x - r(x+6,30) + r(x,30)}{30}\right)$

$= 2 - \left(\dfrac{6 - r(x+6,5) + r(x,5)}{5}\right)+ \left(\dfrac{6 - r(x+6,10) + r(x,10)}{10}\right) + \left(\dfrac{6 - r(x+6,15) + r(x,15)}{15}\right) - \left(\dfrac{6 - r(x+6,30) + r(x,30)}{30}\right)$

It follows that if $x \not\equiv 4 \pmod 5$:

• $\dfrac{6 - r(x+6,5) + r(x,5)}{5} = 1$

If $x \equiv 4 \pmod 5$:

• $\dfrac{6 - r(x+6,5) + r(x,5)}{5} - \dfrac{6 - r(x+6,10) + r(x,10)}{10} = 1$

if $r(x,30) < 24$:

• $\dfrac{6 - r(x+6,30) + r(x,30)}{30} = 0$

if $r(x,30) \ge 24$:

• $\dfrac{6 - r(x+6,15) + r(x,15)}{15} - \dfrac{6 - r(x+6,30) + r(x,30)}{30} = 0$

So that:

$f_5(x+6) - f_5(x) \ge 2 - 1 + 0 = 1$

---

Edit 1:

I forgot to mention that $x$ is an integer. I have updated the question.

---

Edit 2:

Updated the recurrence relation in order to make it clearer. One commenter said that the relation wasn't clear.

---

Edit 3:

Apologies I have no idea why I wrote "kth integer" instead of $k$th prime. Thanks for your patience. Now fixed.

Answer 1

Whether or not an integer $n$ has a prime factor $\in\{2,3,5\}$ depends only on $n\bmod{30}$. Among the first $30$ positive integers, we find that $$\tag11,7,11,13,17,19,23,29$$ (and then $31=1+30$) do not have a such a small prime factor. The largest gap between these is of size $5$ and occurs between $1$ and $7$ as well as between $23$ and $29$. Hence among any six consecutive integers, one is congruent $\bmod{30}$ to a number in $(1)$ and therefore does not have a prime factor $\le 5$. Hence this number is either $\pm1$ or a has smallest prime factor $\ge 7$.

We conclude that the interval $(x,x+6]$ contains an integer with least prime factor $>5$, provided that $x\ge1$ or $x<-7$.

Answer 2

You can actually solve this using (almost) just very elementary set theory.

Let $X_5$ be the set of integers in $\{x+1,x+2,\ldots, x+6 \}$ that are a multiple of 5. Let $X_3$ be the set of integers in $\{x+1,x_2,\ldots, x+6 \}$ that are a multiple of 3, and let $X_2$ be the set of integers $\{x+1,x+2,x+3,\ldots, x+6 \}$ that are a multiple of 2.

Then $|X_5|$ is either 1 or 2, and if $|X_5|$ is 2 then $X|_5 \cap X_2|$ is at least 1.

Then $|X_3|$ is 2 and $|X_2|$ is 3. And $|X_2 \cap X_3|$ is 1

Case 1: $|X_5| = 2$. Then if $|X_3 \cap X_5 \cap X_2|$ is 1, then $|X_2 \cup X_3 \cup X_5| = |X_2| + |X_3| + |X_5| - |X_2 \cap X_3| - |X_2 \cap X_5| -|X_3 \cap X_5| + |X_2+X_3+x_5|$ $=3+2+2 -1 -1 -1 + 1 < 6$ so there is an element in $\{x+1,\ldots, x+6 \}$ that is not a multiple of 2, 3, or 5.

If $|X_3 \cap X_5 \cap X_2|$ is 0, then $|X_2 \cup X_3 \cup X_5| = |X_2| + |X_3| + |X_5| - |X_2 \cap X_3| - |X_2 \cap X_5| + |X_2+X_3+x_5|$ $\geq$ $3+2+2 -1 -1 < 6$ so there is an element in $\{x+1,\ldots, x+6 \}$ that is not a multiple of 2, 3, or 5.

Can you work through Case 2: $|X_5| =1$?