Taking pairwise coprime integers from prescribed sets

Question

1. Given $m$ and $n$ in $\mathbb Z_{>0}$ what is the computational complexity of picking $n$ pairwise coprime integers each of $m$ bits when they exist?

2. Given $m$ and $n$ in $\mathbb Z_{>0}$ what is the computational complexity of deciding if there are $n$ pairwise coprime integers each of $m$ bits?

Answer 1

What exactly interests you? It might be more interesting to ask about finding $m$ pairwise relatively prime numbers between $s$ and $t$ when $t-s$ is "small" with respect to $s.$ The case $s=2^n$ and $t=2^{n+1}$ seems too broad. The best you can do is to take all the primes and prime powers in that range and augment that with some products $p\cdot p'$ where $p$ ranges over the primes less than $\sqrt{2^{n}}$ not used so far and, for each one, an appropriate prime cofactor $p'$.

Let me first discuss $n=20.$

The number of primes with exactly $20$ bits is $N=\pi(2^{21})-\pi(2^{20}) =73586$. Given that, the answer to your question 2 with $n=20$ is definitely yes for $m$ below $N+1$ Then you can use just primes. One can stuff in $234$ more using prime powers and semi-primes (detals below). Doing question 1 for $m=70000$ would be tedious. If you wanted $n=20$ and $m=481$ then one could find $k$ , a $20$ bit multiple of $2\cdot 3\cdot 5\cdot 7\cdot 11=2310$ and take it along with $k+j$ for the $480$ numbers $j$ less than $2310$ and relatively prime to it.

What about finding the absolute largest size set of pairwise relatively prime $20$-bit integers? I claim that it is not hard to find that it is $N+57+5+6+166$ the extra terms are for

• $57$ prime squares, $p^2$ for $1331 \leq p \leq 1447$.
• $5$ prime cubes, $p^3$ for $p=103,107,109,113,127$
• $6$ more: $37^4 ,17^5 ,11^6, 5^9,3^{13}$ and $2^{20}.$
• $166$ primes under $1024$ not yet used (we will give each one a prime cofactor)

If we pair each of the $166$ small ones with the largest possible large prime we get

$7 \cdot 299569, 13\cdot 161309, 19\cdot 110359, 23\cdot 91163, 29\cdot 72313, 31\cdot 67631, 41\cdot 5113$

and continue on to $991\cdot 2113, 997 \cdot 2099, 1009 \cdot \mathbf{2069},1013 \cdot 2069,1019 \cdot \mathbf{2053},1021 \cdot 2053 $

The only overlaps are the two shown in bold which can be replaced with somewhat smaller primes such as $1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039.$

The only "hard" step was perhaps that of computing $N=\pi(2^{21})-\pi(2^{20})=155611-82025=73586.$ Without that we wouldn't know exactly for what $m$ we pass from possible to not possible. But we would know how to get about where. For example easy estimates give $81519 \lt \pi(2^{20}) \lt 82158$ and $154701 \lt \pi(2^{21}) \lt 155852.$