<p><strong>Informal Question</strong></p>

<p>How hard is it to generate a set of relatively prime numbers between two given bounds?</p>

<p><strong>Decision Problem</strong></p>

<p>Given $a$, $b$, and $k \in \mathbb{N}$.  Does there exist a set $S \subseteq \mathbb{N}$ satisfying the following:</p>

<p>(a) for every $x \in S$, $a \leq x \leq b$</p>

<p>(b) for every $x, y \in S$, $x$ and $y$ are relatively prime</p>

<p>(c) $\vert S \vert = k$</p>

<p><strong>Questions</strong></p>

<p>(1) How hard is this decision problem?  Is it as hard as factoring or any other well studied problems in NP?  @YonatanN in the comments below explains why it is at least as hard as prime counting.</p>

<p>(2) In terms of $k$, how large does $b - a$ have to be to guarantee that such a set exists?</p>

<p>Any references would be greatly appreciated.  Thank you!</p>

CC BY-SA 4.0
2018-06-15T17:56:44.623Z
A trivial observation: the natural prime counting decision problem is a special case of your problem with $a=2$. Thus, the prime counting function can be computed in poly-time with binary search and oracle access to your problem. Primality testing reduces to the prime counting function by computing $\pi(n)-\pi(n-1)$. Primality testing wasn’t known to have a poly-time algorithm until recently, but according to the response here https://math.stackexchange.com/questions/939/counting-primes the current best algorithm is from the 1800s. Hence, we likely don’t know a good algorithm for your problem.
Yonatan N
CC BY-SA 4.0
2018-06-16T03:30:43.090Z
@YonatanN Thank you very much for the comment!!  This is great.  :)
Michael Wehar
CC BY-SA 4.0
2018-06-16T04:08:36.543Z
@user124864 Wow, I never knew about the Buchstab function.  This is really neat!!
Michael Wehar
CC BY-SA 4.0
2018-06-16T04:19:58.193Z
Consider the function $f : \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ such that $f(a, b)$ is the size of a maximum set of relatively prime numbers between $a$ and $b$.

I think that we have $\pi(b) - \pi(a) \leq f(a, b) \leq \pi(b)$.
Michael Wehar
CC BY-SA 4.0
2018-06-16T04:29:09.043Z
I suspect now that this problem is no harder than factoring, but I'm not completely sure.
Michael Wehar
CC BY-SA 4.0
2018-06-17T16:55:50.480Z
Are you OK with randomized algorithms, or do you insist on a deterministic algorithm?  Are you OK with assuming some standard conjectures (e.g., the Riemann hypothesis) or do you insist on a solution that is unconditionally known to hold?  See, e.g., https://en.wikipedia.org/wiki/Prime_gap, https://en.wikipedia.org/wiki/Cram%C3%A9r%27s_conjecture.
D.W.
CC BY-SA 4.0
2018-06-17T17:51:40.083Z
I doubt this problem has any relationship to the hardness of factoring.  The problem is a special case of independent set on a graph where vertices are numbers in the range $a..b$ and you draw an edge $(i,j)$ iff $\gcd(i,j)\ne 1$; all of the structure is encoded in that graph, and there's no need to factor (and solving your problem doesn't seem to help with factoring).  I don't think you've fully appreciated YonatanN's comment: he's not saying this is as hard as primality testing, he's saying this is as hard as prime counting (which seems much harder than primality testing).
D.W.
CC BY-SA 4.0
2018-06-17T19:44:26.690Z
@D.W. Thank you very much for the comments!!  The connection with independent set is great!!  And your clarification about prime counting being harder than primality testing is great as well.  Thank you!!  :)
Michael Wehar
CC BY-SA 4.0
2018-06-17T19:47:50.417Z
@D.W. I'm open to randomized algorithms and solutions conditioned on conjectures.
Michael Wehar
<cc.complexity-theory><cr.crypto-security><lower-bounds><nt.number-theory><primes>
How hard is it to generate a set of relatively prime numbers between two given bounds?
Michael Wehar
# How hard is it to generate a set of relatively prime numbers between two given bounds?

(Asked by: username_0 on 2018-06-15)

**Informal Question**

How hard is it to generate a set of relatively prime numbers between two given bounds?

**Decision Problem**

Given $a$, $b$, and $k \in \mathbb{N}$. Does there exist a set $S \subseteq \mathbb{N}$ satisfying the following:

(a) for every $x \in S$, $a \leq x \leq b$

(b) for every $x, y \in S$, $x$ and $y$ are relatively prime

(c) $\vert S \vert = k$

**Questions**

(1) How hard is this decision problem? Is it as hard as factoring or any other well studied problems in NP? @YonatanN in the comments below explains why it is at least as hard as prime counting.

(2) In terms of $k$, how large does $b - a$ have to be to guarantee that such a set exists?

Any references would be greatly appreciated. Thank you!

**Tags:** cc.complexity-theory, cr.crypto-security, lower-bounds, nt.number-theory, primes

> **Comments:**
> **username_1**: A trivial observation: the natural prime counting decision problem is a special case of your problem with $a=2$. Thus, the prime counting function can be computed in poly-time with binary search and oracle access to your problem. Primality testing reduces to the prime counting function by computing $\pi(n)-\pi(n-1)$. Primality testing wasn’t known to have a poly-time algorithm until recently, but according to the response here https://math.stackexchange.com/questions/939/counting-primes the current best algorithm is from the 1800s. Hence, we likely don’t know a good algorithm for your problem.  
> **username_0**: @YonatanN Thank you very much for the comment!!  This is great.  :)  
> **username_0**: @user124864 Wow, I never knew about the Buchstab function.  This is really neat!!  
> **username_0**: Consider the function $f : \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ such that $f(a, b)$ is the size of a maximum set of relatively prime numbers between $a$ and $b$.  I think that we have $\pi(b) - \pi(a) \leq f(a, b) \leq \pi(b)$.  
> **username_0**: I suspect now that this problem is no harder than factoring, but I'm not completely sure.  
> **username_2**: Are you OK with randomized algorithms, or do you insist on a deterministic algorithm?  Are you OK with assuming some standard conjectures (e.g., the Riemann hypothesis) or do you insist on a solution that is unconditionally known to hold?  See, e.g., https://en.wikipedia.org/wiki/Prime_gap, https://en.wikipedia.org/wiki/Cram%C3%A9r%27s_conjecture.  
> **username_2**: I doubt this problem has any relationship to the hardness of factoring.  The problem is a special case of independent set on a graph where vertices are numbers in the range $a..b$ and you draw an edge $(i,j)$ iff $\gcd(i,j)\ne 1$; all of the structure is encoded in that graph, and there's no need to factor (and solving your problem doesn't seem to help with factoring).  I don't think you've fully appreciated YonatanN's comment: he's not saying this is as hard as primality testing, he's saying this is as hard as prime counting (which seems much harder than primality testing).  
> **username_0**: @username_2 Thank you very much for the comments!!  The connection with independent set is great!!  And your clarification about prime counting being harder than primality testing is great as well.  Thank you!!  :)  
> **username_0**: @username_2 I'm open to randomized algorithms and solutions conditioned on conjectures.  

---

## 0 answers

