Consecutive integers with many prime factors - MathOverflow

Consecutive integers with many prime factors

2010-08-12T14:26:50Z

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

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

There exists m consecutive integers, each of which has at least n distinct prime factors.
There exists m consecutive integers, each of which has precisely n distinct prime factors.
There exists m consecutive integers, each of which has at least n prime factors (counted with multiplicity)
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.

Answer by falagar for Consecutive integers with many prime factors

2010-08-12T15:18:30Z

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.

Answer by Frank Thorne for Consecutive integers with many prime factors

2010-08-13T01:21:18Z

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

Answer by Greg Martin for Consecutive integers with many prime factors

2010-08-19T18:53:01Z

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.