3
$\begingroup$

It is well known from Sylvester-Schur that in any sequence of $x$ consecutive integers, there is always at least one integer divisible by a prime greater than $x$.

I am interested in counting the number of integers in a sequence of $x$ consecutive integers with a least prime factor greater than $x$.

Let:

  • $k$ be any positive integer
  • $x$ be a positive integer
  • $\text{lpf}(x)$ be the least prime factor for x.
  • $\mu(x)$ be the möbius function
  • $r(m,d)$ be the remainder of $m$ divided by $d$
  • $x\#$ be the primorial for $x$
  • $d(k,x,i) = r(k,i) + r(x,i) - r(k+x,i)$

Does it follow that the number of integers $t$ such that $k < t \le (k+x)$ and $\text{lpf}(t) > x$ is equal to:

$$1+\sum_{i|x\#\text{ and } 1 < i \le x+k}\left(\frac{d(k,x,i)}{i}\right)\mu(i)$$

Here is my thinking. Please let me know if I made a mistake or if anything is unclear:

(1) The number of integers $k < t \le (k+x)$ and $\text{lpf}(t)>x$ is $\sum\limits_{i|x\#}\left(\left\lfloor\dfrac{x+k}{i}\right\rfloor - \left\lfloor\dfrac{k}{i}\right\rfloor\right)\mu(i)$

  • The number of integers $t\le k$ that are divisible by a prime $p$ is $\left\lfloor\dfrac{k}{p}\right\rfloor$

  • The number of integers $t\le k$ divisible by prime $p$ or prime $q$ is $\left\lfloor\dfrac{k}{p}\right\rfloor+\left\lfloor\dfrac{k}{q}\right\rfloor-\left\lfloor\dfrac{k}{pq}\right\rfloor$

  • The number of integers $t\le k$ not divisible by a prime $p$ or a prime $q$ is: $k - \left\lfloor\dfrac{k}{p}\right\rfloor-\left\lfloor\dfrac{k}{q}\right\rfloor+\left\lfloor\dfrac{k}{pq}\right\rfloor$

  • The number of integers $t \le k$ not divisible by any prime $p \le x$ is: $\sum\limits_{i|x\#}\left(\left\lfloor\dfrac{k}{i}\right\rfloor\right)\mu(i)$

  • The number of integers $k < t \le (x+k)$ not divisible by any prime $p \le x$ is: $\sum\limits_{i|x\#}\left(\left\lfloor\dfrac{x+k}{i}\right\rfloor\right)\mu(i) - \sum\limits_{i|x\#}\left(\left\lfloor\dfrac{k}{i}\right\rfloor\right)\mu(i) =\sum\limits_{i|x\#}\left(\left\lfloor\dfrac{x+k}{i}\right\rfloor - \left\lfloor\dfrac{k}{i}\right\rfloor\right)\mu(i)$

(2) $\sum\limits_{i|x\#}\left(\left\lfloor\dfrac{x+k}{i}\right\rfloor - \left\lfloor\dfrac{k}{i}\right\rfloor\right)\mu(i)=\sum\limits_{i|x\#}\left(\dfrac{x - r(x,i) + d(k,x,i)}{i}\right)\mu(i)$

  • $\sum\limits_{i|x\#}\left(\left\lfloor\dfrac{x+k}{i}\right\rfloor - \left\lfloor\dfrac{k}{i}\right\rfloor\right)\mu(i)=\sum\limits_{i|x\#}\left[\left(\dfrac{(x+k)-r(x+k,i)}{i}\right) - \left(\dfrac{k - r(k,i)}{i}\right)\right]\mu(i) = \sum\limits_{i|x\#}\left(\dfrac{x-r(x+k,i) + r(k,i)}{i}\right)\mu(i)$

  • $r(x+k,i) = r(k,i) + r(x,i)-[r(k,i) + r(x,i) - r(k+x,i)]=r(k,i) + r(k,i) - d(k,x,i)$

  • $\sum\limits_{i|x\#}\left(\dfrac{x-r(x+k,i) + r(k,i)}{i}\right)\mu(i)=\sum\limits_{i|x\#}\left(\dfrac{x-[r(k,i) + r(x,i) - d(k,x,i)] + r(k,i)}{i}\right)\mu(i) = \sum\limits_{i|x\#}\left(\dfrac{x - r(x,i) + d(k,x,i)}{i}\right)\mu(i)$

(3) $\sum\limits_{i|x\#}\left(\dfrac{x - r(x,i) + d(k,x,i)}{i}\right)\mu(i) = 1+\sum\limits_{i|x\#}\left(\dfrac{d(k,x,i)}{i}\right)\mu(i)$

  • $\sum\limits_{i|x\#}\left(\dfrac{x - r(x,i) + d(k,x,i)}{i}\right)\mu(i) = \sum\limits_{i|x\#}\left(\dfrac{x - r(x,i)}{i}\right)\mu(i) + \sum\limits_{i|x\#}\left(\dfrac{d(k,x,i)}{i}\right)\mu(i)$

  • $\sum\limits_{i|x\#}\left(\dfrac{x - r(x,i)}{i}\right)\mu(i) = \sum\limits_{i|x\#}\left(\left\lfloor\dfrac{x}{i}\right\rfloor\right)\mu(i)=1$ from step(1) above.

(4) $1+\sum\limits_{i|x\#}\left(\dfrac{d(k,x,i)}{i}\right)\mu(i) =1+\sum\limits_{i|x\#\text{ and } 1 < i \le x+k}\left(\frac{d(k,x,i)}{i}\right)\mu(i)$

  • $d(k,x,1) = r(k,1) + r(x,1) - r(k+x,1) = 0$

  • if $i > k+x$,then $d(k,x,i) = r(k,i) + r(x,i) - r(k+x,i) = k + x - (k+x) = 0$

$\endgroup$
2
$\begingroup$

Everything looks correct. You did an excellent job, but I have just a few, relatively minor, points. For your (1), you could have just provided a link to an existing explanation, such as A question about the Mobius Function. Nonetheless, I appreciate what you wrote since it is a more simple & basic explanation than anything I've seen elsewhere. My only comment is regarding your fourth bullet point of

The number of integers $t \le k$ not divisible by any prime $p \le x$ is: $\sum\limits_{i|x\#}\left(\left\lfloor\dfrac{k}{i}\right\rfloor\right)\mu(i)$

You may wish to prepend it with something like "Extending the principle of inclusion-exclusion, " to make it clear this is what you're using, although it should already be relatively clear from the context that this is the basic principle you're using.

In your step (2), here is what I believe is a somewhat simpler way of explaining it. After your first bullet point, I would take the numerator of what you're trying to prove on the RHS and expand it instead to get:

\begin{align} x - r(x, i) + d(k, x, i) &= x - r(x, i) + r(k, i) + r(x, i) - r(x + r, i) \\ & = x + r(k, i) - r(x + r, i) \end{align}

I don't believe you even really need a third bullet point, but if you use one, you could then just indicate the RHS of your first bullet point is equal to the RHS of point (2).

In your point (3), at the end of the second bullet point, you may wish to add something like "since $1$ is the only integer $t \le x$ which is not divisible by any prime $p \le x$". At least for me, this wasn't immediately clear & it took me a short while to figure it out.

$\endgroup$

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.