5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ By "the next largest prime above $\,n\,$" , do you mean "the first prime larger than $\,n\,$ ? $\endgroup$ – DonAntonio May 1 '13 at 1:53
  • $\begingroup$ Yes, thank you. I've edited it. $\endgroup$ – user1860611 May 1 '13 at 1:55
14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Reference for your "interesting sequence" $q_i$ = A058989(i). The first terms are 1, 3, 5, 9, 13, 21, 25, 33, 39, 45, 57. The conjecture here that $q_i = p_{i+1}-2$ was wrong. The OEIS contains another wrong conjecture $q_i = 2p_{i-1}-1$. $\endgroup$ – Jeppe Stig Nielsen Oct 16 '18 at 20:32

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.