# Taking pairwise coprime integers from prescribed sets

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?

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

• There are so many issues with this obvious answer that everyone is first aware of 1. What is the gap between primes? 2. What is the complexity of choosing a prime? 3. What is the gap between coprime versus gap between prime numbers? 4. It is easier to choose two coprimes in $m+1$ time complexity while it is unclear how to choose even two primes and many other issues such as not quantifying 'might be as good as it gets'. – Brout Oct 8 '18 at 7:47
• OK, I made it less vague. – Aaron Meyerowitz Oct 8 '18 at 20:04
• What is the complexity of picking one prime of $m$ bits? – Brout Oct 9 '18 at 0:49
• To find $m$ pairwise relatively prime $n$ bit integers is not hard for manageable size $m.$ For $m=1$ anything will do. For $m=3$ use $\{2^n+j \mid j=1,2,3\}.$ Instead of primes take probable primes (or numbers with no small prime factors) and just check gcds. Or find $km$ primes each with $n/k$ bits and take products. – Aaron Meyerowitz Oct 9 '18 at 3:46
• Please answer my question. Do you know the complexity of choosing a probable prime? Are you aware of polymath project on deterministic selection of primes? Please take a look. The last point you mention is the most relevant. – Brout Oct 9 '18 at 7:18