Generate numbers relatively prime with a given number

Question

I am interested in a function such that f[m, i] = n where m, n are positive integers and n is the i-th number relatively prime with m.

Getting a sample of the possible outputs of f is straightforward. For example, let m = 30. Now we can use

list = 2 Range[0,29] + 1;
list = Pick[list, GCD[30, list], 1]
(*{1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59}*)

where I'm picking from odd numbers since m happens to be even. There should be a pattern in these numbers given by EulerPhi[30] (this is 8) and indeed, list[[;;8]] + 30 coincides with list[[9;;16]]. How to continue from here?

Answer 1

To find relative primes, I've found Complement to be generally faster than GCD or CoprimeQ.

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

Your function f becomes the following.

f[m_, i_] :=
   Block[{n = RelativePrimes[m], e = EulerPhi[m]},
      n[[Mod[i, e, 1]]] + m * Quotient[i - 1, e]
   ]
SetAttributes[f,Listable]

Thus,

f[30,Range[20]]

{1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73}

f[902,555]

1251

Answer 2

I give a naive implementation

ithCoprime[m_, i_] := Module[{coprimes, j = 1},
                             coprimes = {1};
                             While[Length[coprimes] < i,
                                   j++;
                                   If[CoprimeQ[m, j], AppendTo[coprimes, j]]
                                  ];
                             Last[coprimes]
                            ]

ithCoprime[30, #] & /@ Range[16]

{1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59}

---

Update

Here is a better version:

ithCoprime2[m_, i_] := Module[{j = 1, k = 1},
                              While[k < i, j++;
                                    If[CoprimeQ[m, j], k++]
                                   ];
                              j
                             ]

---

Update 2

Another version

ithCoprime3[m_, i_] := Module[{iterate, predicate, initial},
                              iterate = # + {1, Boole[CoprimeQ[m, First[#]]]} &;
                              predicate = Last[#] <= i &;
                              initial = {1, 1};
                              NestWhile[iterate, initial, predicate, 1, \[Infinity], -1][[1]]
                             ]

Answer 3

f[m_, i_] := (
    m*#[[1]] + 
      Select[Range[m], GCD[#, m] == 1 &][[ #[[2]] ]] 
  )& [ QuotientRemainder[i, EulerPhi[m]] ]

RepeatedTiming[f[223 227, 4021987]]
(*  {0.058, 4057980}  *)

As long as m is not too big and you repeat ms, you can trade some memory for time.

fTable[m_] := fSmall[m] = 
  Select[Range[m], GCD[#, m] == 1 &];
f[m_, i_] := (m*#[[1]] + fTable[m][[#[[2]] ]]
  )& [ QuotientRemainder[i, EulerPhi[m]] ]

RepeatedTiming[f[223 227, 4021987]]
(*  {0.0000110, 4057980}  *)

If you are repeating ms, but you still have too many different ms, discarding "old" fTables is a good idea.