Wolfram Cloud – functions, do iteration, if and lists

Iwas reading about group theory recently, for basic cryptography, and wanted a function for computing the set , i.e. the set of integers with greatest common divisor (gcd) with equal to , formally .

And I wanted to do it “quickly”, in a math engine, so what better place than on Wolfram’s Development Platform!

It’s not rocket science how to compute the set, but I thought this’d serve as a nice reference, with examples, to basic operations in the Wolfram Language on the Wolfram Cloud.

I needed to be able to check the gcd between numbers, this is built in as GCD, example

in: GCD[4,6];
out: 2

Checking from 1..n-1 is tedious however, where Do comes in handy. Do[ expr, { var, limit } ], loops var from 1 to limit (inclusive), example

In: Do[GCD[n,6], {n,6}];
Out: // nothing's output as Do just performs the calculation.

Time for Print[expr]! Example

In: Do[Print[GCD[n,6]], {n,6}];
Out: 1
  2
  3
  2
  1
  6

But this is badly formatted, and also it includes the check of gcd(6,6), and it has a hardcoded variable. First, into a function, example

In: f[x_] := 42 + x;
  f[2];
Out: 44

Calculates the answer to life, the universe and everything, plus x, i.e. 2. Our function looks like, (variable factored out, removed gcd(n,n) check with g-1)

In: CalcSet[g_]:= Do[Print[GCD[n,g]], {n,g-1}]; 
  CalcSet[6];
Out: 1
    2
    3
    2
    1
    6

Still badly formatted, and actually it doesn’t output the set, just a list of tests where it prints the restult of GCD; enter If. If[ expr, t, f], where t is evaluated if expr is true, and f is an optional expression, evaluated if expr evaluates to false. (If no f is provided, and the If is used in something bigger, say a list, it’ll return null). Start small:

In: If[ 1==1, Print["true"], Print["false"]]; (* prints "true" *)
  If[ 1==2, Print["true"], Print["false"]]; (* prints "false" *)
  If[ 1==2, Print["true"]];(* does nothing *)
  If[ 1==1, Print["true"]];  (* prints "true" *)
Out: "true"
  "false"
  "true"

Redefine function with the If-condition

In: CalcSet[g_]:= Do[If[GCD[n,g] == 1, Print[n]], {n,g}];
  CalcSet[6];
Out: 1
    5

I love it, I can compute the set! Still it isn’t very nicely formatted; I want it in a list. So I need a list, and the AppendTo function,

In: l = {1, 2};
  AppendTo[l, 3];
  Print[l];
out: {1, 2, 3}

Putting it all together in a ()-clause, extracting the Print I get the final code:

In: GenSet[g_]:= (
  l={};
  Do[If[GCD[n,g] == 1, AppendTo[l,n]], {n,g-1}];
  Return[l];
);
  Print[GenSet[6]];
Out: {1, 5}
  Print[GenSet[5]];
Out: {1, 2, 3, 4}
  Print[GenSet[10]];
Out:  {1, 3. 7, 9}

This could probably be optimized further by adding 1 to the initial set, and skip the first check, like below (Do with a { var, start, end }-constraint),

In: GenSetOptimized[g_]:= (
  l={1};
  Do[If[GCD[n,g] == 1, AppendTo[l,n]], {n,2,g-1}];
  Return[l];
);
  Print[GenSetOptimized[6]];
Out: {1, 5}

But it’s not a race!!.. I wonder if this can be done with a map somehow, in a sane way. In my head it doesn’t seem faster(, or less involved!)

Also, I totally know that I’m cheating by not calculating gcd(n,n), but I made the clever observation that it’ll never be 1 unless n is 1 (I’ll leave it up to the reader to prove this.) The function doesn’t work for generating either; suppose we’ll have to wonder for eternity what the result of this is.

Edit: lol wait, it actually does work in the optimized version, since it adds 1 to the set initially and just skips the Do-loop. I totally knew this; which is why I made the optimized version, I promise.