3
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ If you choose numbers at random and just test whether each new one is coprime to the (product of the) rest - and if so, include it with the rest - then you should find what you want pretty quickly. After all, testing whether numbers are coprime is faster than testing whether an integer is prime. $\endgroup$ – Greg Martin Sep 27 '15 at 1:19
  • $\begingroup$ Ah yeah true. Factoring vs euclidean algorithm (: $\endgroup$ – Alan Wolfe Sep 27 '15 at 3:41
  • $\begingroup$ Not good enough for my needs unfortunately, Ideally i'd want some $O(1)$ operation to get the $N$th co-prime, without having to calculate the previous ones. I need a large number of co-primes and would rather not have to test new numbers for co-primeness, have to calculate the previous numbers before the $N$th number, and don't want to have to store the numbers in memory or on disk. $\endgroup$ – Alan Wolfe Nov 7 '15 at 19:33
  • $\begingroup$ Ok, I understand better what you want now. It's a surprising fact that generating all the primes in an interval is incredibly fast, nearly $O(1)$ per prime: just use the sieve of Eratosthenes. So if you really want a bunch of pairwise coprime numbers, this might be the way to go (as opposed to generating the $N$th number from the $(N-1)$st). $\endgroup$ – Greg Martin Nov 7 '15 at 20:53
  • $\begingroup$ Thanks for the info Greg. it looks though like i have to store the numbers in memory and cull them away based on the rules right? I'm literally looking for like 2^32 co-primes, which would be a ton of numbers to store, check and cull. I'd really like to be able to evaluate f(5) and get the 5th co-prime in the list, and then f(6) to get the 6th co-prime in the list etc. If i need them greater than a minimum value, i can find the x in f(x) that is > than my minimum (by iteratively testing, that is fine), and then just use that as an offset. Do you know of anything that works like this? $\endgroup$ – Alan Wolfe Nov 7 '15 at 20:57
2
+100
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If the minimum $A$ is dropped, does that help anything? I was looking at Sylvester's squence and Fermat numbers which give infinite length pairwise co-prime sequences. It looks like you can calculate the $N$th fermat number using a simple formula but the numbers grow pretty huge, pretty fast. Same with Sylvester, but I haven't seen a way to get the $N$th sylvester number without calculating the previous ones. With an infinite sequence, i could always find the smallest index that is larger than my minimum, and then use that as an offset to getting the $N$th one larger than my minimum. $\endgroup$ – Alan Wolfe Nov 7 '15 at 21:14
  • $\begingroup$ "You can, however, get a reasonably large set of mutually coprime numbers using some of the efficient heuristic/approximation algorithms for set packing." -perhaps a greedy algorithm would work? Start by choosing all the empty sets in the interval, then all the singleton sets etc., eliminating any overlaps as you go. It may not be optimal, but might be within some bound of the optimal solution? $\endgroup$ – Colm Bhandal Nov 10 '15 at 15:19
  • $\begingroup$ @ColmBhandal I think the best known approximation to set packing would give an $O(\sqrt{k})$ approximation. $\endgroup$ – Michael Biro Nov 10 '15 at 19:31
  • $\begingroup$ @AlanWolfe Dropping $A$ does make the problem easier, but only in the trivial sense that generating a list of primes gives a list of coprime integers. $\endgroup$ – Michael Biro Nov 10 '15 at 19:32
  • $\begingroup$ @AlanWolfe: I can't see a simple way to generate a large dense set of pairwise coprimes one by one, apart from simply using the primes, which could be generated using (say) a deterministic form of Miller-Rabin, but that's time-consuming compared to sieving. And since you only want coprimes, a simple segmented Eratosthenes-style sieve that only removes multiples of primes $< k$ can be quite fast if $ k \ll \sqrt{A}$, and of course such a sieving will return more numbers than a pure prime sieve would. $\endgroup$ – PM 2Ring Nov 11 '15 at 12:49
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.