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$?



Covering the primes with pairs of consecutive integers
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}$.


