Page 1 of 1

Generate tuples of pairwise coprimes with limit on largest element

Posted: Sun Jun 30, 2019 4:42 pm
by mumofewoks
I'm trying to find an efficient way to find tuples or arrays with 10 elements of pairwise coprime integers below a given limit M. How would I write the following program?

loop over all (a,b,c,d,e,f,g,h,i,j) such that 0 < a < b < c <d < e < f < g < h < i <j <M and gcd(a,b,c,d,e,f,g,h,i,j) == 1
.. do something
end loop

I already have a function compute gcd and my code works using nested for loops for small values of M need code for values as large as M = 10^6

Re: Generate tuples of pairwise coprimes with limit on largest element

Posted: Sun Jun 30, 2019 8:28 pm
by v6ph1
You may work with a check-list for the primes:
1. Generate a list of all primes up to the limit
2. generate the first number by selecting primes (and powers) and cancel them out
3. go on for the 2nd, 3rd, ... number.

Re: Generate tuples of pairwise coprimes with limit on largest element

Posted: Tue Jul 02, 2019 3:09 am
by mumofewoks
I'm not sure I quite understand step 2. I managed to write code to obtain all prime numbers (factors) up to my limit. I don't know how to proceed because I don't understand the suggested second step you provided.
(I'm new to number theory and coding in general)