4
$\begingroup$

Let $N\ge 1$ be a natural number. The object is to find the longest possible sequence of prime numbers $p_1<p_2<...<p_n$ such that $p_{i+1}-p_i\leq 2N$ for $i=1,...,n-1$. In other words, there is no difference exceeding $2n$.

For $N=1$, the maximum length is $4$ because one of the numbers $n,n+2,n+4$ must be divisible by $3$, but $2,3,5,7$ is a sequence of length $4$ with the desired property.

For $N=2$, the sequence $2,3,5,7,11,13,17,19,23$ has the desired property, so the maximum length is at least $9$.

  • How can I get the maximum length for each given $N$ ?
$\endgroup$
6
$\begingroup$

For $N=2$, this is indeed the longest sequence. Consider primes mod 30. Exepted for 2,3,5, they are always 1, 7, 11, 13, 17, 19, 23, or 29 mod 30. The longest sequence we can get is indeed 7, 11, 13, 17, 19, 23 mod 30, with length 6. Unless 2,3,5 is part of the sequence. This establishes $f(2)=9$.


For $N=3$, it is again a good idea to look to the small primes. We get the sequence: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89. The next prime is 97 which is out of reach. Therefore $f(3) \geq 24$. Looking mod 210 showed that $f(3)=24$.


I plugged the sequence in OEIS. In general we can find some lower bounds in A005669 in combination with A005250.

  • $f(4) \geq 30$, $f(7) \geq 99$, $f(9) \geq 154$, $f(10) \geq 189$, $f(11) \geq 217$, $f(17) \geq 1183$, $f(738)\geq 34952141021660495$.

On the other hand, we have for al $a,n \in \mathbb N$ and $1 < k < p_n+1$ that $a(p_n\#)\pm k$ is composite. $a(p_n\#)\pm (p_n+1)$ is also not prime because it is even and greater taen 2. Therefore the largest sequence with max gap $p_n$ could be only from 2 to $p_n\#-p_n-1$.

This gives $f(p_n) < p_n\#-p_n-3$. For example $10^{16} < f(738) < f(739) < 739\# < 10^{2200}$. Clearly, there is some room for improvement.

$\endgroup$

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.