Return to Answer

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.

End Edit 2019.04.11.

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

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.

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]$.)

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.

End Edit 2019.04.11.

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

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.

End Edit 2019.04.11.

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

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.

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

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]$.)

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.

End Edit 2019.04.11.

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