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$
3
  • 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, 2017 at 13:38
  • $\begingroup$ You can also use RandomPrime if you want big numbers. $\endgroup$
    – vapor
    Mar 27, 2017 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, 2017 at 22:33

1 Answer 1

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$
3
  • $\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, 2017 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$ Apr 1, 2017 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, 2017 at 12:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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