Generate tuples of pairwise coprimes with limit on largest element

Primes, divisors, arithmetic, number properties, ...
Post Reply
mumofewoks
Posts: 2
Joined: Sun Jun 30, 2019 12:30 pm

Generate tuples of pairwise coprimes with limit on largest element

Post 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
Last edited by mumofewoks on Tue Jul 02, 2019 4:52 am, edited 1 time in total.
v6ph1
Posts: 134
Joined: Mon Aug 25, 2014 7:14 pm

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

Post 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.
Image
mumofewoks
Posts: 2
Joined: Sun Jun 30, 2019 12:30 pm

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

Post 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)
Post Reply