Covering the primes with pairs of consecutive integers

Question

Is it true that for every sufficiently large positive integer $n$, one can always find at most $k=\lfloor\pi(n)/2\rfloor$ integers, $a_1,a_2,a_3,a_3,\dots a_k$, between $1$ and $n$, such that each of the $\pi(n)$ primes not greater that $n$ divides at least one of the integers $a_1,a_1+1,a_2,a_2+1,a_3,a_3+1,\dots,a_k,a_k+1$?

Answer 1

For large enough $n$ no such set of integers exist. First of all, let us say that $a$ covers prime $p$ if $a$ or $a+1$ is divisible by $p$. Now, if $p$ is a prime with $\frac{n+1}{2}<p\leq n$, $a\leq n$ can cover $p$ only if $a=p$ or $a=p-1$, because otherwise $a\geq 2p-1>n$. Let $p_1,p_2,\ldots,p_m$ be the set of all primes between $\frac{n+1}{2}$ and $n$. By the previous observation, no $a\leq n$ can cover two such primes and all the primes must be covered.

For $1\leq i\leq m$ let $a_i$ be the only number in our set that covers $p_i$ (so $a_i=p_i$ or $p_i-1$). As $\pi(x)=\frac{x}{\ln x}+O\left(\frac{x}{\ln^2 x}\right)$, we have $k=\frac{n}{2\ln n}+O\left(\frac{n}{\ln^2 n}\right)$ and also $m=\pi(n)-\pi((n+1)/2)=\frac{n}{2\ln n}+O\left(\frac{n}{\ln^2 n}\right)$. So, our desired set $a_1,\ldots,a_k$ consists of the numbers $a_i$ with $i\leq m$ and at most $O\left(\frac{n}{\ln^2 n}\right)$ other numbers.

For $1\leq i\leq k$ let $f(i)$ be the number of $p>(n+1)/3$ that are covered by $a_i$. As $a_i$ should cover all primes, we should have

$$ \sum_{1\leq i\leq k} f(i)\geq \pi(n)-\pi((n+1)/3)=\frac{2n}{3\ln n}+O\left(\frac{n}{\ln^2 n}\right). $$

Now, obviously, $f(i)\leq 2$ for all $i$, because otherwise $a_i$ or $a_i+1$ will be divisible by at least two different primes $p>n/3$, which is impossible. Therefore we have

$$ \sum_{1\leq i\leq m} f(i)\geq \frac{2n}{3\ln n}+O\left(\frac{n}{\ln^2 n}\right), $$

as $f(i)=O(1)$ and $k-m=O\left(\frac{n}{\ln^2 n}\right)$. Now, I claim that there are at most $O\left(\frac{n}{\ln^2 n}\right)$ indices $i\leq m$ with $f(i)=2$. Indeed, if $f(i)=2$ then there are two possibilities: either $a_i=p$ and $a_i+1=2q$ with $(n+1)/3<q<(n+1)/2<p\leq n$ or $a_i=2q$ and $a_i+1=p$ with the same conditions. So we either have $p=2q-1$ or $p=2q+1$. But there are $O\left(\frac{n}{\ln^2 n}\right)$ primes $q\leq n$ with either $2q-1$ or $2q+1$ prime, and the claim follows. From this we get

$$ \sum_{1\leq i\leq m} f(i)=m+\#\{i: f(i)=2\}=m+O\left(\frac{n}{\ln^2 n}\right), $$

which is a contradiction, because $m+O\left(\frac{n}{\ln^2 n}\right)\geq \frac{2n}{3\ln n}+O\left(\frac{n}{\ln^2 n}\right)$ cannot hold for large $n$, as $m\sim \frac{n}{2\ln n}$.

Answer 2

I suspect not. Here is intuition (not a proof) for why this cannot be done for large n.

Fun prime fact: if the first k primes are all at most n, then the next k primes are all less than 3n. You can verify this by hand for small k and n, and appeal to a Chebyshev type estimate for the rest. For a positive solution to this problem for large n, there is a b not much smaller than n/2 so that primes in (b,n) determine most of the pairs: many of the pairs cover a prime in (b,n), and most of the rest cover twice a prime in (b,n/2). By the time you have picked candidates to handle the primes in (b,n), you don't have many options left to pick a new number to cover (some multiple of some) primes in b.

In particular, many of the pairs chosen have no odd multiples of three. Now you don't need to cover many odd multiples of three, but if you start building a cover to take care of the large primes first, I believe you will run out of options (and your cover will fail) before the time you reach primes the size of n/4. More specifically, the existence of the type of cover proposed suggest to me too many pairs of consecutive numbers of the form (2p,3q) for p and q prime.

Edit 2019.04.11:

Here is a combinatorial argument which can be turned into one with explicit bounds, and can be resolved by a small amount of machine-assisted computation. It gives the stronger assertion that for all sufficiently large $n$, using the requested number of pairs, one can't even cover all the primes in $(n/4,n]$ ( or even $(A,n]$ if one looks at how many primes are $+-13 \bmod 30$).

For, in order to cover all the large primes in $ (n/4,n] $ with $k$ pairs of consecutive numbers (where $2k$ is real close to $\pi(n)$, there is an $A \in (n/3,n/2]$ such that all $k$ pairs have to cover primes in $(A,n]$. Indeed, since primes of the form $p=30j +- 13$ map to numbers of the form $2p=30j +-26$, we need at minimum to cover all those primes with pairs which are less than $n/2$. (I am implicitly using a result similar in nature to that in Asymptotiac K's post, which implies that primes in any residue class mod 30 in $(n/3,n/2)$ eventually out number $k$ minus the number of primes in $ [n/2,n]$. I could stop here with a rigorous proof of the value of $A$ and get something stronger, but I decided to be silly and beat a dead herd below.)

Even if we are lucky enough to cover those primes in $(A,n]$, we now have to deal with primes from the set $S=(n/4,A]$. Every prime q from $S$ must have either 2q near a prime or else 3q near twice a prime from $(A,n/2]$. This means every prime q from $S$ must have 2q or 3q/2 near a prime. However, for q of the form $60j +- 17$, neither of these map to near a prime. As $n$ gets large, $S$ contains a positive density of all primes less than $n$ and is guaranteed to contain one of these residue classes mod 60. So one can't use just $k$ pairs for a cover.

Even though the previous paragraph is somewhat redundant for the given problem, it is a start on estimating the number of actual pairs needed to cover primes. I offer it as a prototemplate for tackling some generalizations of Bernardo's problem.

End Edit 2019.04.11.

Gerhard "Doesn't Quite Cover It, Unfortunately" Paseman, 2019.04.09.

Answer 3

Yes. Consider the list $p_1, \dots, p_r$ of primes less than $n$. Since $p_1$ is prime to $p_2$, we can find an integer $l$ such that $p_2l \equiv 1$ mod $p_1$. Then $p_2l = 1 + kp_1$ for some integer $k$. If we let $a_1=kp_1$ then $p_1$ divides $a_1$ and $p_2$ divides $a_1+1$. If $r=2m$ is even you just have do this for each pair of primes $(p_{2i+1}, p_{2i})$ for $0 \leq i \leq \frac{r}{2}$. If $r=2m+1$ is odd, just do the same for the pairs $(p_{2i}, p_{2i+1})$ for $1 \leq i \leq m$, and since $p_1=2$, then either $a_1$ or $a_1+1$ is even so $p_1$ divides at least one of them.

Answer 4

Even with relaxing the conditions , the answer is no for $n=44$ and most $94 \leq n \leq 200.$ I didn't check any further but I doubt it is true ever again. (I relaxed the condition even further than when I first wrote this and haven't rechecked.) We will say that $b$ covers the prime $p$ if $p \mid b.$

To review, we want a set of $k$ integers,$A=\{a_1,\cdots a_k\}$ where $k=\lfloor \frac{\pi(n)}2 \rfloor$ so that every prime less than $n$ is covered by at least one of the $2k$ members of $B=\{a_1,a_1+1,\cdots,a_k,a_k+1\}.$

The task is the same for $n=2m-1$ and $n=2m$ so there is no loss in assuming that $n$ is even. Actually, we could also restrict to the case that $2n-1$ is prime. Otherwise it is the same set of $\pi(n-2)=\pi(n)$ primes and the task is the same.

As noted, if $m \lt p \lt 2m$ is prime then one of the chosen $a_i$ must be either $p$ or $p-1.$ The issue will be that there are only a relatively few more primes in $\{2 \cdots m\}$ compared to $\{m+1,\cdots 2m-1\}$ and this doesn't allow us enough flexibility to cover all the smaller primes.

So if $\pi(2m)-\pi(m)=j$ we have $2^j$ starts to $A$ to consider. To simplify that we relax the problem:

We will set $k=\lceil \frac{\pi(n)}2 \rceil.$ We will build the sets $A$ and $B$ as follows: Start with a list $L$ of the primes in question in decreasing order and $A=B=\emptyset$ . Take, p, the first so far uncovered prime in the list, choose a multiple $a=cp\leq n$ to add to $A.$ Add $a-1,a,a+1$ to $B$ and then move down $L$ to the largest still uncovered prime. Repeat until either all the primes are covered or $A$ is too big.

Clearly this relaxed condition gives bigger sets $B$ and lets us cover anything we could cover in the original problem.

In the case $m=22,n=44$ there are $8$ primes up to $22$ and $6$ more primes after that, $$23, 29, 31, 37, 41, 43.$$ These are all but one of of the members of $A.$

So, with the relaxed conditions, we so far have $B=\{22,23,24,28,29,20,31,32,36,37,38,40,41,42,43,44\}$ and can pick one more member of $A.$ Next down is $19$ which is already covered. For $p=17$ we need to pick an $a \in\{17,34\}$ But then we have all $7$ members of $A$ and $13$ is still uncovered.

For $n=43,45,46$ we have the same primes to consider so those are also a failure.

---

In the case above we had all but one prime covered. As $n$ increases, so does the discrepancy.