4
$\begingroup$

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!

$\endgroup$
3
  • 1
    $\begingroup$ There are infinitely many....There's If, Select, CoprimeQ, Range, Table to get you started $\endgroup$ – Michael E2 Feb 12 '15 at 14:12
  • $\begingroup$ @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 $\endgroup$ – user45220 Feb 12 '15 at 15:16
  • $\begingroup$ @user45220 See my answer below. I have changed it now to create the first 500 pairs. $\endgroup$ – ben18785 Feb 12 '15 at 15:27
3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ – user45220 Feb 12 '15 at 15:33
  • $\begingroup$ @user45220 I have now updated the answer above to allow you to order the answer as you desired. Hope that helps! Best, Ben $\endgroup$ – ben18785 Feb 12 '15 at 15:53
  • 1
    $\begingroup$ This is what I had in mind, but note that Pick[#, CoprimeQ @@@ #] &@Subsets[Range[500], {2}] will be faster than Select. $\endgroup$ – Michael E2 Feb 12 '15 at 16:08
6
$\begingroup$

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}} *)
$\endgroup$
6
$\begingroup$

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]
$\endgroup$
2
  • 1
    $\begingroup$ I don't understand the lack of upvotes - this is clearly the superior method of those posted as far as efficiency - +1 $\endgroup$ – ciao Feb 15 '15 at 2:27
  • $\begingroup$ 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. $\endgroup$ – KennyColnago Feb 15 '15 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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