2
$\begingroup$

Is there a way to generate a list of parametrized length, say $L$, of integers which are relatively prime among them? I would like to take into account their word-length as well, so for example the list would contain only 32-bit numbers.

$\endgroup$
  • 1
    $\begingroup$ Prime@Range[L] will have that property. It feels as if you had omitted something important from the question ... which would explain why Prime@Range[L] is not what you want ... $\endgroup$ – Szabolcs Mar 27 '17 at 13:38
  • $\begingroup$ You can also use RandomPrime if you want big numbers. $\endgroup$ – happy fish Mar 27 '17 at 14:07
  • $\begingroup$ I wouldn't like to have only prime numbers, but rather a list of relatively prime numbers. I tried though your command and I get something weird: Prime@Range[2^31, 2^31 + 22] outputs numbers that are larger than $2^{31}+22$. Any idea why is that? $\endgroup$ – Jimakos Mar 27 '17 at 22:33
1
$\begingroup$

Are you looking for a list of mutually coprime integers? The function CoprimeSet[n,m] finds sets of m mutually coprime integers from the first n>m integers.

CoprimeSet[n_, m_] := Pick[#, CoprimeQ @@@ #] &[Subsets[Range[n], {m}]]

For example,

CoprimeSet[8,5]

{{1, 2, 3, 5, 7}, {1, 3, 4, 5, 7}, {1, 3, 5, 7, 8}}

Alternatively, CoprimeSetRandom[n,m,kmin,kmax] finds sets of m mutually coprime integers from a random selection of n integers between kmin and kmax.

CoprimeRandomSet[n_, m_, kmin_, kmax_] := 
    Pick[#, CoprimeQ @@@ #] &[Subsets[RandomInteger[{kmin, kmax}, n], {m}]]

For example,

CoprimeRandomSet[10, 5, 1800, 2000]

{{1803, 1888, 1811, 1961, 1951}, {1803, 1930, 1811, 1961, 1951}}

$\endgroup$
  • $\begingroup$ Nice effort thanks, although I can't seem to make it work for 32-bit numbers. I tried for example CoprimeRandomSet[50, 22, 2^32, 2^32-1] but I got a message for insufficient memory (16GB + 16GB swap in Ubuntu) $\endgroup$ – Jimakos Mar 27 '17 at 22:37
  • $\begingroup$ You have asked for subsets of 22 integers from a list of 50 integers, which is a list of billions of sublists. So memory will always be insufficient for such large cases. Assuming you reduce n and m, you must have kmin less than kmax, whereas your example in the comment has kmax less than kmin. $\endgroup$ – KennyColnago Apr 1 '17 at 15:13
  • $\begingroup$ Correct, that was a typo. I used CoprimeRandomSet[22,22,2^31,2^32-1] to get just 1 set of 22 coprime numbers but I got no output. $\endgroup$ – Jimakos Apr 4 '17 at 12:29

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.