1
$\begingroup$

I've been thinking about the total number of distinct primes and it occurred to me that for any integers $x > 0, n > 0$, there are at most $n+\pi(n-1)$ distinct primes that divide $\dfrac{(x+n)!}{x!}$

Here is my thinking:

(1) To simplify the discussion let $f(x,n) = \dfrac{(x+n)!}{x!}$

(2) There are exactly $\pi(n)$ primes $p$ such that $p \le n$

Where $\pi(n)$ is the prime counting function.

(3) For primes that are $n$ or greater, it follows that only one number in $x+1, x+2, \dots, x+n$ can be divisible by such a prime.

This is impossible because for any integer $0 < i < j < n$, $x + j - (x + i) = j-i < n$

(4) So, the result is that maximum number of distinct primes is $n+\pi(n-1)$

Is my reasoning correct? Is this well known? Is there an improvement to this result that I am missing?

$\endgroup$
6
  • $\begingroup$ Already for $n=1$ , we get $x+1$ which can have arbitary many prime divisors, since $x$ has not been restricted. $\endgroup$
    – Peter
    Commented May 11, 2020 at 8:37
  • $\begingroup$ You are right. $\pi(n-1)$ is not correct. Would it still work with $\pi(\sqrt{x+n}) + n$. In the case of $x+1$, there could only be a maximum of $\pi(\sqrt(x+1) +1$. Am I wrong with this update? $\endgroup$
    – Larry Freeman
    Commented May 11, 2020 at 8:41
  • 1
    $\begingroup$ As $n!|\frac{(x+n)!}{x!}$ it can be concluded that the number of dividing primes $p≤\pi(x+n)-\pi(x)+\pi(n) \leq n+\pi(n-1).$. $\endgroup$
    – Alapan Das
    Commented May 11, 2020 at 8:41
  • $\begingroup$ @AlapanDas I like your equation. It is not obvious to me why it is true. $\endgroup$
    – Larry Freeman
    Commented May 11, 2020 at 8:44
  • 1
    $\begingroup$ There cannot be an upper bound that is independent from $x$ $\endgroup$
    – Peter
    Commented May 11, 2020 at 8:45

0

Reset to default

You must log in to answer this question.