Prime Numbers – Answering Common Questions

prime numbers

Is it true that in any successive (natural) $2p_n$ numbers there are at least three numbers that are not divisible by any prime less (not equal) than $p_n$? Here, $p_n$ denotes the $n$-th prime number.

For
example in any six successive numbers there are at least 3 numbers that are not divisible by 2,in any 10 successive numbers there are 3 numbers that are not divisible by 2 or 3, in any 14 successive numbers there are at least 3 that are not divisible by 2, 3, or 5.

Best Answer

Late update A better question might be; "What is the Largest number of consecutive integers such that each is divisible by a prime $\le p_n$ ? Computing a few values and checking the handy OEIS yields the link above. Matching the values with the appropriate primes shows that one can get over twice (at p=67) or even thrice the next prime with no gaps.

[2, 1], [3, 3], [5, 5], [7, 9], [11, 13], [13, 21], [17, 25], [19, 33], [23, 39], [29, 45], [31, 57], [37, 65], [41, 73], [43, 89], [47, 99], [53, 105], [59, 117], [61, 131], [67, 151], [71, 173], [73, 189], [79, 199], [83, 215], [89, 233], [97, 257], [101, 263], [103, 281], [107, 299], [109, 311], [113, 329], [127, 353], [131, 377], [137, 387], [139, 413], [149, 431], [151, 449], [157, 475], [163, 491], [167, 509], [173, 537], [179, 549], [181, 573], [191, 599], [193, 615], [197, 641], [199, 657], [211, 685], [223, 717], [227, 741]

older answer 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)$.

Related Question