4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What is the range of $ i $? $\endgroup$ – Αλέξανδρος Ζεγγ Dec 19 '18 at 13:52
  • $\begingroup$ @ΑλέξανδροςΖεγγ Arbitrary positive integer. $\endgroup$ – Kiro Dec 19 '18 at 13:54
6
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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]]
                             ]
$\endgroup$
1
$\begingroup$
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.

$\endgroup$

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.