# Code for (a,b) with gcd(a,b)=1?

I am trying to make a big table that includes all ordered pairs (a,b) with a

(1,2) (1,3) (2,3) (1,4) (3,4) (1,5) (2,5) (3,5) (4,5) (1,6) (5,6) ...

Any ideas?

Thanks!

• There are infinitely many....There's If, Select, CoprimeQ, Range, Table to get you started Commented Feb 12, 2015 at 14:12
• @MichaelE2: Sorry, I meant the first 500 or so, not all. :p Can you help me with the commands? I'm completely new to mathematica. Thanks a lot Commented Feb 12, 2015 at 15:16
• @user45220 See my answer below. I have changed it now to create the first 500 pairs. Commented Feb 12, 2015 at 15:27

I have found a solution here. First of all create a list of all possible ordered pairs, in a range of choice (I have chosen a range of 1 to 500):

pairData = Subsets[Range[500], {2}]


Then I apply Select to the resultant dataset, where the criteria for whether or not the pairs are Coprime is given by CoprimeQ:

pairDataCoprime = Select[pairData, CoprimeQ[#[[1]], #[[2]]] &]


Now sorting it by the second value in each sublist, followed by the first:

SortBy[pairDataCorime, {Last, First}]


Hope that helps!

Best,

Ben

• Hello, thank you very much for this. I just tried it but the output came out in an order that I don't want: First all the (1,x), then all the (2,x), etc. I want to switch this around to order it as follows: (1,x), (2,x), (3,x), etc. Then (1,x+1), (2,x+1), (3,x+1), etc. Can you help me do this? Commented Feb 12, 2015 at 15:33
• @user45220 I have now updated the answer above to allow you to order the answer as you desired. Hope that helps! Best, Ben Commented Feb 12, 2015 at 15:53
• This is what I had in mind, but note that Pick[#, CoprimeQ @@@ #] &@Subsets[Range[500], {2}] will be faster than Select. Commented Feb 12, 2015 at 16:08

A good opportunity for the lowly procedural loop.

Reap[Clear[h]; n = 10;
Do[If[TrueQ[h[i/j]], , h[i/j] = True; Sow[{i, j}]],
{j, 2, n}, {i, j - 1}]][[2, 1]]

(* {{1, 2}, {1, 3}, {2, 3}, {1, 4}, {3, 4}, {1, 5}, {2, 5}, {3, 5}, {4,
5}, {1, 6}, {5, 6}, {1, 7}, {2, 7}, {3, 7}, {4, 7}, {5, 7}, {6,
7}, {1, 8}, {3, 8}, {5, 8}, {7, 8}, {1, 9}, {2, 9}, {4, 9}, {5,
9}, {7, 9}, {8, 9}, {1, 10}, {3, 10}, {7, 10}, {9, 10}} *)


A simple way to find numbers k relatively prime to a given number n is to systematically check for GCD[k,n]=1 for all k from 1 to n-1.

Select[Range[n - 1], GCD[#, n] == 1 &]


CoprimeQ is about as fast as GCD. Using Pick and the listability of GCD improves the speed.

RelativePrimesGCD[n_] := With[{r = Range[n - 1]}, Pick[r, GCD[r, r[[-1]] + 1], 1]]


A 1999 MathGroup posting discussed faster ways. Allan Hayes contributed an algorithm below, RelativePrimesHayes[n], which is 15 times faster than the RelativePrimesGCD method above. Ranko Bojanic made some comments about, and improvements to, the code from Allan Hayes.

RelativePrimesHayes[n_] :=
Fold[Complement[#, #2] &, Range[n - 1], (Range[#, n - 1, #]) & /@
First[Transpose[FactorInteger[n]]]]


They both used First[Transpose[FactorInteger[n]]] to find the prime divisors of n, but FactorInteger[n][[All,1]] is faster and cleaner. Alternatively, when memory limits are not a concern,

RelativePrimes[n_Integer] :=
Complement[Range[n - 1], Apply[Sequence, Map[Range[#, n - 1, #] &,
FactorInteger[n][[All, 1]]]]]


Pairs of relative primes with maximum of n are generated as follows.

Flatten[Table[Thread[List[RelativePrimes[n], n]], {n, 1, 500}], 1]

• I don't understand the lack of upvotes - this is clearly the superior method of those posted as far as efficiency - +1
– ciao
Commented Feb 15, 2015 at 2:27
• Thanks, @rasher, it is genuinely heartening to see your comment. I've learned a lot from answers by people like you here on Mma SE. Project Euler is notoriously unforgiving of casual coding, and this gem from Allan Hayes helped a great deal with generating primitive Pythagorean triples. Commented Feb 15, 2015 at 17:22