I was thinking about consecutive integers and I wondered if anyone had done work exploring whether a sequence of $2n$ consecutive integers (i.e. 101,102,103,...,100+2n) always contains at least one integer with a least prime factor $p > n$.

I had been thinking about it for some time when I noticed this post: question in prime numbers

Using complete residue systems for $p$# and the Chinese Remainder Theorem, I noticed that it is possible to find a sequence of $38$ (2*19) consecutive integers that has only one least prime factor greater than $19$. It is also true of a sequence of $62$ (2*31) that you can find a sequence with only one least prime factor greater than $31$.

For any sequence where $n \le 23$ with the exception of $19$, there are at least two integers where the least prime factor is greater than $2$.

The fact that any sequence of $46$ (2*23) integers always has at least $2$ such integers while a sequence of $38$ (2*19) integers might just have $1$ suggested to me that there might be an elementary argument there.

I did a Google search and could find very little on least prime factors. As you can probably tell from this write up, I am an amateur very interested in learning more about number theory.

I would greatly appreciate any help that can be provided in showing me a proof or an example that there exists integers $x,n$ such that $x+1, x+2,$ ... $, x+2n$ are all divisible by some prime $p \le n$

Thanks very much


  • 7
    $\begingroup$ This conjecture seems very natural but in fact it is wrong. The keyword you want to google to find more information is "Jacobsthal's function". $\endgroup$ – zeb Jun 21 '11 at 9:12
  • 2
    $\begingroup$ What zeb said. Further, recent researchers include Hagedorn and Saradha. Gerhard "Ask Me About Jacobsthal's Function" Paseman, 2011.06.21 $\endgroup$ – Gerhard Paseman Jun 21 '11 at 12:15
  • $\begingroup$ Thanks very much! One additional thought seems to be that the number where the 2n sequence fails seems to be very high. Is there any work on estimating at which point the number fails. Based on Jacobsthal's function, for n=43, it is possible to find a sequence of 89 consecutive integers where each integer is divisible by a prime 43 or less (oeis.org/A058989). I wrote a computer program to find this sequence. For a sequence starting at $8.4 x 10^11$ or less, the most I am finding is $72$ integers before an integer is found with a least prime factor greater than 43. $\endgroup$ – Larry Freeman Jun 21 '11 at 13:50
  • $\begingroup$ A necessary condition is that the gap between actual primes must be larger than 2n. You could look up the tables in Hagedorns paper to find a number, with no guarantee of it being the first such. If m is the product of the primes involved, I can only guarantee the first such is less than m/2, which is weak. It might be possible to show an upper bound like O(m/(n!)) where n is the number of prime factors, but it might be smarter to understand the sieves used by Hagedorn. Gerhard "Email Me About System Design" Paseman, 2011.06.21 $\endgroup$ – Gerhard Paseman Jun 21 '11 at 18:25
  • $\begingroup$ Larry, I used a refined version of your comment above in ArXiv preprint arxiv.org/abs/1311.5944, with a weak form of attribution. If you need me to fix the attribution, let me know. Also, I am interested in pursuing the question about where such intervals occur, and want to know if you wish to devote some resources to it. Gerhard "Thanks For The Interesting Idea" Paseman, 2013.12.10 $\endgroup$ – Gerhard Paseman Dec 10 '13 at 22:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.