# Consecutive integers with many prime factors

This question is inspired by Project Euler's Problem 47.

Let m and n be positive integers. Consider the following four (related) statements:

1. There exists m consecutive integers, each of which has at least n distinct prime factors.
2. There exists m consecutive integers, each of which has precisely n distinct prime factors.
3. There exists m consecutive integers, each of which has at least n prime factors (counted with multiplicity)
4. There exists m consecutive integers, each of which has precisely n prime factors (counted with multiplicity).

Question $i$: For which pairs $(m,n)$ is statement $i$ true?

For $n = 2$ and any $m$, statement 3 is obviously true (it is just the elementary fact that there are prime gaps of arbitrary length). I suppose it is not too hard to avoid prime powers, so that statement 1. is also true for $n=2$ and arbitrary $m$ (although at the moment I cannot see if this follows by an easy modification of the usual $(m+1)!+2, \ldots, (m+1)!+m+1$ argument). Are there other elementary cases? In particular, is there an easy proof that Problem 47 (which is to find the first instance of Statement 1 for $m=n=4$) is actually solvable? The actual answer is small enough that it is found rather quickly by a naive brute force approach, but it would be nice to know in advance that there is an answer (perhaps even having an upper bound, so that one also knows that one may find the answer before the heat death of the universe).

Statement $i$ can be strengthened by requiring the existence of infinitely many $m$-tuples; call this Statement $i'$.

Statements 2 and 4 are probably too hard to say anything about in general (but maybe not?), but for $m=2$, Statements $2'$ and $4'$ are both weaker versions of this question.

-
Apologies for pushing my own agenda. Please see  mathoverflow.net/questions/29280/…  The two versions that David's question splits into for my purposes, for some fixed prime $q \equiv 7 \pmod 8$ can we solve your question 1 such that:  (weak) whenever $(p | q) = -1$ and $p$ divides one of the $m$ consecutive integers, the exponent of $p$ is even  (strong) no number of the $m$ is divisible by any $p$ with $(p | q) = -1.$ – Will Jagy Aug 12 '10 at 18:00
There are some pairs $m,n$ for which 2 and 4 are trivially false, e.g., 2 is false for $m=5$, $n=1$, and 4 is false for $m=3$, $n=1$. – Gerry Myerson Aug 12 '10 at 23:45

Answer for the first question. Let $w_k$ be the product $p_{nk+1} p_{nk+2} \cdots p_{nk+n}$ where $p_i$ is $i$-th prime. So each $w_k$ is equal to product of $n$ distinct primes and $w_k$ and $w_q$ are coprime for $k \ne q$. Now take $t$ such that $t \equiv -k \pmod {w_k}$ for $k = 1, 2, \cdots, m$. Such $t$ exists by Chinese Remainder Theorem. Now $t + k$ has at least $n$ primes because $t + k$ is a multiple of $w_k$. Hence numbers $t + 1, t + 2, \cdots, t + m$ satisfy requirements in the first question.

-
This (very elegant) answer provides an upper bound for (1) as well - namely, $\prod_{k=1}^m w_k = \prod_{k=1}^m \prod_{i=1}^n p_{nk+i} = \prod_{j=n+1}^{(m+1)n} p_j$. Admittedly, this is horrifically large, but it is an upper bound. In case $m = n = 4$, this upper bound is merely 2656861095841423623654359, but hey - it exists. – dvitek Aug 12 '10 at 16:26
And of course 1 implies 3. – Qiaochu Yuan Aug 12 '10 at 16:38
Please see  mathoverflow.net/questions/29280/…  The two versions that David's question splits into for my purposes, for some fixed prime $q \equiv 7 \pmod 8$ can we solve villemoes question 1 such that:  (weak) whenever $(p | q) = -1$ and $p$ divides one of the $m$ consecutive integers, the exponent of $p$ is even  (strong) no number of the $m$ is divisible by any $p$ with $(p | q) = -1.$ – Will Jagy Aug 12 '10 at 17:57
in falagar's proof,if m&n are significant or not,since if we assume $t+1=N$ and $t+m>2N$,at least one of the $t+i$ is prime – Hashem sazegar Aug 14 '10 at 17:01
@drvitek: I agree that this is a very elegant answer. Thanks for observing that it also provides an upper bound. It's actually about 5 orders of magnitude better in the case $m=n=4$, but still too large to be of practical value. We can just let k run from 0 to m-1 instead and get $\prod_{i=1}^{16} p_i$ which is around 3E19. – villemoes Aug 17 '10 at 13:34

Regarding questions 1 and 3: the counting function of the set of integers with at most n-1 prime factors is $O(x(\log\log x)^{n-2}/\log x)$, where the implicit O-constant depends on n. (This is true for either distinct prime factors or factors counted with multiplicity. See the references in this problem to Montgomery and Vaughan or to Tenenbaum.) In particular, the set of numbers with only a few prime factors has density zero, which implies the existence of arbitrarily large gaps, hence implies 1 and 3 are true.

Regarding questions 2 and 4, for suitable values of m and n (as noted in other comments, 2 and 4 aren't true for all m and n) they should follow from conjectures on prime k-tuples. For example, to get three consecutive integers each with exactly two prime factors (which will be different, so addressing both 2 and 4), one "only" needs to find integers n such that 10n+1, 15n+2, and 6n+1 are simultaneously prime, for then 30n+3, 30n+4, and 30n+5 will each have exactly two prime factors.

-

This is not a direct answer to your question, but see here for some results along these lines by Goldston, Graham, Pintz, and Yildirim.

-