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!
Best Answer
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.