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
Generate tuples of pairwise coprimes with limit on largest element
-
- Posts: 2
- Joined: Sun Jun 30, 2019 12:30 pm
Generate tuples of pairwise coprimes with limit on largest element
Last edited by mumofewoks on Tue Jul 02, 2019 4:52 am, edited 1 time in total.
Re: Generate tuples of pairwise coprimes with limit on largest element
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.
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.
-
- Posts: 2
- Joined: Sun Jun 30, 2019 12:30 pm
Re: Generate tuples of pairwise coprimes with limit on largest element
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)
(I'm new to number theory and coding in general)