Is this number theory conjecture known to be true?

587 Views Asked by At

I've been working on proving that there is always a prime between $n$ and $2n$, and also that there is always a prime between $n^2$ and $(n+1)^2$ (Legendre's conjecture).

I believe I've proven those two statements using the following fact:

The most consecutive integers divisible by a number less than or equal to $n$ is $p-2$, where $p$ is the first prime larger than $n$.

For example, if $n=8$ then $p=11$ and I can find at most $9$ consecutive integers divisible by numbers less than $8$. ($200$ through $208$ is one example of consecutive integers divisible by $2,3,5,$ or $7$)

My question is if this fact about consecutive integers divisibility is well known in number theory, or if it is something I will have to prove separately before the other two proofs are valid?

Update: This was proven false in the answer below by Qiaochu Yuan.

1

There are 1 best solutions below

1
On BEST ANSWER

When checking divisibility by numbers less than or equal to a number it suffices to check primes, so your claim is the following:

Let $p_i$ be the sequence of primes. Then there are at most $p_{i+1} - 2$ consecutive integers each of which is divisible by at least one of the primes $p_1, p_2, ... p_i$.

This claim is false. For example, there are $13 = p_{i+1}$ consecutive integers divisible by at least one of the primes up to $11$ (the claim predicts $11$), namely

$$114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126.$$

Continuing (at least if my script hasn't made a mistake): there are

  • $21 = p_{i+1} + 4$ consecutive integers divisible by at least one of the primes up to $13$ (ending in $9460$),
  • $33 = p_{i+1} + 10$ consecutive integers divisible by at least one of the primes up to $19$ (ending in $60076$)

and at this point I run out of memory.

The longest string of consecutive integers each of which is divisible by at least one of the numbers $p_1, ... p_i$ is certainly an interesting sequence $q_i$, but a priori we can only expect $q_i \ge p_{i+1} - 2$ (by taking $2, 3, ... p_{i+1} - 1$), and it's not surprising that it was possible to do better.