5
$\begingroup$

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!

Improve this question
$\endgroup$
9
  • 4
    $\begingroup$ 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 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. $\endgroup$
    – Yonatan N
    Commented Jun 15, 2018 at 17:56
  • $\begingroup$ @YonatanN Thank you very much for the comment!! This is great. :) $\endgroup$
    – Michael Wehar
    Commented Jun 16, 2018 at 3:30
  • 1
    $\begingroup$ @user124864 Wow, I never knew about the Buchstab function. This is really neat!! $\endgroup$
    – Michael Wehar
    Commented Jun 16, 2018 at 4:08
  • 1
    $\begingroup$ 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., en.wikipedia.org/wiki/Prime_gap, en.wikipedia.org/wiki/Cram%C3%A9r%27s_conjecture. $\endgroup$
    – D.W.
    Commented Jun 17, 2018 at 16:55
  • 2
    $\begingroup$ 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). $\endgroup$
    – D.W.
    Commented Jun 17, 2018 at 17:51

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.