How to calculate $N$ pairwise co-prime numbers, near a certain range? I'm working on a math problem where I'm using the Chinese remainder theorem to solve several equations, where I have control over the specific values used as the modulus divisor (How to solve simultaneous modulus / diophantine equations).
I'm currently using prime numbers to make sure that the modulus divisors are co-prime, but I'm curious if there is an easy way to calculate co-prime numbers, which would open up the number of solutions available to me quite a bit.
So, my question is, is there a way to calculate $N$ number of co-prime numbers that are near a specific range of values?
Like, say I wanted 16 co-prime numbers that were near 1000 in value?
I'd love there to be some equation that i can use, so that I can generate large amounts of co-primes, and be able to get the $N$th coprime without having to calculate the previous numbers.
Are there any methods or tricks for doing this?  I'd be looking for possibly up to $2^{16}$, $2^{32}$ coprimes, or possibly even more than that.
Since I'm looking for co-primes, if there was some known algorithm or equation for generating PRIMES that match this criteria, that would be helfpul too.
The "near a certain range" part is less important than the $O(1)$ calculation, because I could always scan through the values to find where my lowest value desired starts, and use that value as an offset.
Thanks!
 A: Say you want to generate mutually coprime numbers in the interval $[A, A + k)$. Note that the only primes $p_1, p_2, p_3 \dots, p_m$, we need to worry about are in the range $2 \leq p_i < k$, so in particular, $m < k$. For each of the $k$ numbers $A+n$ in the interval, form a subset $S_{A+n} \subseteq \{p_1, p_2, \dots, p_m\}$ of primes that divide $A+n$. 
Our goal is to find a collection of subsets $S_{A + n}$ that don't overlap. Unfortunately, in general, maximizing this number is a hard problem. There may still be hope that there is underlying structure here that avoids the NP-completeness, but I don't immediately see it.
You can, however, get a reasonably large set of mutually coprime numbers using some of the efficient heuristic/approximation algorithms for set packing.
A: Problem: find c, d such that the arithmetic sequence c+k*d for k in 0..15 consists of pairwise relatively prime numbers and c > 1000. If a prime p divides both c+k1*d and c+k2*d, then p divides (k2-k1)*d. To ensure that this is impossible, we must choose c so that it is not divisible by 2, 3, 5, 7, 11, or 13. d must be divisible by 2, 3, 5, and 7. Otherwise, the values in the sequence would rotate thru the residual classes at least twice and one could not avoid having two members of the sequence divisible by one of these primes. So we take d=210. Then we just need to make sure that there are not two members which are divisible by 11 or 13. For 11, it suffices to check c+d, c+2d, c+3d, and c+4d. For 13, we just need to check c+d and c+2d. Fortunately, we find the solution quickly with c=1003. The sequence is: 1003, 1213, 1423, 1633, 1843, 2053, 2263, 2473, 2683, 2893, 3103, 3313, 3523, 3733, 3943, and 4153. These numbers are pairwise relatively prime. -- James Richard Spriggs
