In view of Chebyshev's approach to prime numbers, I would like to ask about the regularities and peculiarities of the two sequences $\ \beta(n)\ $ and $\ \gamma(n),\ $ which I define as follows:

  • $\ \beta(n)\ $ is the smallest integer $\ b\ $ such that $\ \binom bn\ $ has at least $\ n\ $ different prime divisors;
  • $\ \gamma(n)\ $ is the smallest integer $\ c\ $ such that $\ \binom cn\ $ has at least $\ n\ $ different prime divisors $\ p\gt n$.

Of course it would be nice (but not realistic?) to compute these two sequences or give a sharp estimate. Even not so sharp bounds but with explicit scope of application like for every $\ n\ge 720\ $ (or whatever the constant) rather than for almost all... would be still interesting, I'd think, and possibly can find some applications (say, combinatorial).

The properties under the consideration can be monotonicity of the sequences $\ \beta\ $ and $\ \gamma\ $ (including the deviations from the monotonicity); also the frequency of occurrences of prime numbers as $\ \beta(n)\ $ or $\ \gamma(n)\ $ respectively. Would they be more common in $\ \gamma\ $ then in $\ \beta\,$?

  • 1
    $\begingroup$ You should also consider B(n) and G(n), which are the smallest values of b and g such that for all c >= b or h >= g, one has c choose n have at least n different prime divisors or h choose n have at least n different prime divisors greater than n. Stoermer's Theorem suggests to me that these values also exist. Gerhard "Wants Really Explicit Application Scope" Paseman, 2014.10.01 $\endgroup$ Oct 2, 2014 at 6:50
  • $\begingroup$ @Gerhard, if you believe in the infinitude of Mersenne primes then the respective B(n) G(n) are not defined for $\infty$-many n. Perhaps there would be many other probable examples of B G not defined. $\endgroup$ Oct 2, 2014 at 7:36
  • $\begingroup$ (@Gerhard, there is more than one $\LaTeX$ way to write binomial coefficients. But once I learned \binom my life became easier, e.g. \binom {12}2 $\ = \binom {12}2$). $\endgroup$ Oct 2, 2014 at 7:41
  • 1
    $\begingroup$ Wlod, I only see that Mersenne primes prevent the definability of G(2). Indeed, I believe one can prove B(2)=4 and I think it is not hard to show B(3) and G(3) exist and are larger than 8, but not by much. Gerhard "Or We're On Different Pages" Paseman, 2014.10.03 $\endgroup$ Oct 3, 2014 at 17:44
  • $\begingroup$ @Gerhard, you're right, of course, that possible infinitude of Mersenne primes potentially precludes G(2), and not more (I was chaotic in my comment). I'd write a program but others have a much better computing environment (mine is poor). Gerhard, you could take your comment to formulate your own MO Question, I'd welcome it. $\endgroup$ Oct 3, 2014 at 21:39

1 Answer 1


I'll just consider the second of the two problems posed. Changing notation slightly, it asks for the least natural number $n=n(k)$ such that $(n+1)(n+2)\cdots (n+k)$ is divisible by $k$ primes all larger than $k$. First I claim that $n(k) \le Ck^{e}$ for some constant $C$. To see this note that $$ \sum_{n\le N} \sum_{p>k, p|(n+1)\cdots (n+k)} 1 = \sum_{k<p\le N} \sum_{j=1}^{k} \sum_{n\le N, p|(n+j)} 1 = \sum_{k< p \le N} k \Big( \frac{N}{p} +O(1)\Big), $$ and using $\sum_{p\le x} 1/p = \log \log x + B + O(1/\log x)$ this is $$ = kN \log \frac{\log N}{\log k} + O\Big(\frac{N}{\log k}\Big). $$ If $N >C k^e$ for some large $C$ then this exceeds $kN$, and we deduce that there is some $n \le N$ with $(n+1)\cdots (n+k)$ containing $k$ primes all larger than $k$. This easy argument may be found in Theorem 3.3 (part 3) of Erdos and Turk.

My guess would be that $n(k) \ge k^{e-\epsilon}$ for any $\epsilon >0$, but this seems difficult to show. One can see easily that $n(k) \ge c k^2$ for some small positive constant $c$. To prove this, note that if $n\le k^2-k$ then each $n+j$ (with $1\le j\le k$) can have at most one prime factor larger than $k$. So if we can show that there are integers in $[n,n+k]$ that are $k$-smooth (all prime factors below $k$) then clearly $(n+1)\cdots (n+k)$ cannot be divisible by $k$ primes larger $k$. Choose $r=\lceil \sqrt{n+k}\rceil$ and $s = \lceil \sqrt{r^2 - (n+k)}\rceil$. Then $r^2-s^2$ can be checked to be in $[n,n+k]$ (if $n\le ck^4$ for a suitable $c$), and $r^2-s^2=(r+s)(r-s)$ is clearly $(r+s)$-smooth. This shows that if $n\le ck^2$ then the interval $[n,n+k]$ will contain $k$-smooth numbers. (In fact, it shows that the interval $[x,x+cx^{1/4}]$ contains $\sqrt{x}$-smooth numbers.) Erdos and Turk (see Theorem 3.3 part 1) showed that $n(k) \ge k^{2+\delta}$ for some small $\delta>0$, and this remains the best known.

To show why the problem of getting lower bounds for $n(k)$ is difficult, let me isolate a consequence which is not yet known. If the bound $n(k) \ge k^A$ holds for all large $k$, then every interval $[x,x+x^{1/A}]$ must contain a $x^{1/A}$-smooth number. This consequence is only known for $A<2.5$; this follows from the argument involving $r^2-s^2$ given above, and was noted in a paper of Friedlander and Lagarias (which appeared in J Number Theory). So proving the expected lower bound of $n(k) \ge k^{e-\epsilon}$ would have interesting, as yet unknown, consequences.

  • $\begingroup$ Suppose I gave you the k primes (and, strangely, asked only for odd k). Other than that 2n was smaller than the product of the k primes, could you tell me how small n could be so that each of n+1,..,n+k was divisible by exactly one of those primes? Failing that, can you give bounds on n if the product (n+1)...(n+k) isnonzero and is divisible by the product of the k given primes? $\endgroup$ Oct 16, 2014 at 5:28
  • $\begingroup$ Thank you a lot. @Lucia, I enjoyed your answer. To follow the calculations I'd like to ask a volunteer (you?--I don't dare :-), if possible, to translate the common number-theoretical notation into set-theoretical way. I am talking about the style translation along the line: $\ \sum_{x\in A} 1 = |A|.\ $ Or, say, $\ \sum_{1\le k\le n,\ k\cdot n\le M} 1\ =\ \left|\{(k\ n)\in \mathbb N^2:k\cdot n\le M\ \ and\ \ k\le n\}\right|.\ $ And if I see $\ \sum_{k\ n\ge 1,\ k\cdot n\le M} 1\ $ then I am lost, I don't know how to read it uniquely. $\endgroup$ Oct 16, 2014 at 5:40
  • $\begingroup$ The number theoretical 1-summation formulas perhaps are compact but in my case they lead to strain on my eyes. Also, non-specialists especially may occasionally get confused when it is hard or impossible to decode the 1-notation formula. $\endgroup$ Oct 16, 2014 at 5:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.