Skip to main content
7 of 9
added 2605 characters in body
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

The first counter-example is for $p=17$. The interval of length $40$ starting at $87890$ only yields three integers with least prime factor greater than $17$: the primes $87911,87917$ and also $87929=23\cdot 3823$. So we can use the inteval of length $38$ starting at $87890$ or at $87891$.

I may be mistaken, but I think that there are not any examples for $p=19$ and $p=23$.

On the other hand, of the 89 consecutive integers from $43559563512434$ to $43559563512522$ inclusive, all but one have a prime factor $41$ or less. The exception is $43559563512481=9393910613\cdot 4637$

There are essentially 6 ways to get a run of length $39$ (or 3 up to reflection): One can start at $87890,177980,182342,328130,332492$ or $422582 \mod 510510$.

Discussion (Since somebody asked) For a prime $p$ call an integer $p$-good if it has a prime factor $p$ or less and $p$-bad otherwise. Let $M(p,b)$ be the longest possible run of consecutive integers which are all $p$-good except for $b$ exceptions (called holes). Note that $M(p,b)$ is odd. To find the values of $M(p,b)$ and all intervals attaining it, it suffices to look for runs in the integers from $0$ to $p\sharp-1$ where $p\sharp$ is the product of the primes up to $p$. That is true if we look cyclically or go a reasonable distance past $p\sharp$. I wondered at the particular question asked by the OP (" Is it the case that $M(p_{n-1},2)<2p_n$ for all $n$?" But now I realize that must be inspired by the fact that the $M(p_{n-1},2)\ge 2p_n-1$ is witnessed by the run from $p_{n-1}\sharp-p_n+1$ to $p_{n-1}\sharp+p_n-1$ (with the two bad numbers being $p_{n-1}\sharp \pm 1$).

For my computations I generated a list of the $p-bad$ numbers up to $p\sharp$. This can be done iteratively. I did this up to $p=23$ using a fairly uninspired Maple program on a unimpressive computer. $p=19$ took 9 seconds and $p=23$ took 250. The lists are centrally symmetric but I did not exploit that. A faster language, better program, faster machine, and storage in a file might allow one to go somewhat further. I then made the list of jumps from one $p$-bad number to the next. The jumps for $p=17$ with their multiplicities were

$[[2, 22274], [4, 22275], [6, 26630], [8, 6812], [10, 7734], [12, 4096]$

$[14, 1406], [16, 432], [18, 376], [20, 24], [22, 78], [24, 20], [26, 2]]$.

I then had Maple look for 3 successive gaps adding to at least $40$. There were 3 up to the middle.

I did not care to try $p=29$ by the same method! I looked for $M(23,3)$ using the same list of gaps in hopes of finding something good enough that I could get a good bound for $M(29,2)$ use the Chinese remainder theorem to shift everything preserving the 23-good members and plug a hole by making a 23-bad member 29-good. I didn't find anything by eyeballing. Similarly for $M(23,4)$ using $p=29,31$ and $M(23,5)$ using $p=29,31,37$. I did not think to look if there was something attaining $M(23,5)$ so that two of the holes were separated by 58 so that they could be plugged using up just one prime. But something with 2 of 6 holes separated by 62 did get noticed.

Note: I might have overlooked things. I did not really look at the two largish gaps around $p\sharp$. Also, The two holes with one prime trick might make a good example out of a run which is 2 or 4 less than $M(23,b)$.

Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104