Re: Subject: Re: RE: Finding a relative prime

• To: mathgroup at smc.vnet.net
• Subject: [mg19798] Re: Subject: [mg19798] [mg19725] Re: [mg19694] RE: [mg19682] Finding a relative prime
• From: "Allan Hayes" <hay at haystack.demon.co.uk>
• Date: Fri, 17 Sep 1999 01:36:50 -0400
• References: <7rnk4a\$ela@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

```Ranko Bojanic <bojanic at math.ohio-state.edu> wrote in message
news:7rnk4a\$ela at smc.vnet.net...
>
>
>
> Timur Tabi,timur at tabi.org wrote:
> > I'm using Mathematica 3.0 for the Mac,and I'm trying to figure out how
>
> > to get it to pick a random number that is relatively prime to another
> > number,p-1,where p is prime.In other words,pick a random number k
> > such that 1) k is between 2 and p-1,and 2) k is relatively prime to
> p-1.
> > How can I do that in Mathematica 3.0?
>
> There was a very lively and interesting discussion of this problem in
> the MathGroup.
> It is clearly irrelevant here whether p is a prime or not. So we can
> reformulate the problem
> as follows: given an integer n >2, select at random an integer k < n
> such that k is relatively
> prime to n.. A simple solution , which will insure that the numbers are
> selected with equal
> probability, is to find the rpLst of all numbers k < n which are
> relatively prime to n and
> then to select a random element of that list with
>
>     rpLst[[Random[Integer,{1,Length[rpLst}]]]
>
> The main problem is, consequently, to find the most efficient way to
> construct the list.
> of integers < n and relatively prime to n.An immediate candidate is the
> function
>
>       relPrimes[n_] = Select[Range[n],GCD[#,n]==1&];
>
> This function clearly cannot be very fast for large values of n because
> it has to examine
> every element of the list Range[n].
>
>      relPrimes[100000];//Timing
>      {17.0333 Second,Null}
>
> A faster function can be constructed by using Eratosthenes Sieve and the
> fact  that  an
> integer < n is relatively prime to n if it is not divisible by any prime
> divisor of n. The
> list of  prime divisors of n is obtained by
>
>      pdLst[n_]:=First[Transpose[FactorInteger[n]]
>
> If d is a prime divisor of n, then
>
>      Complement[Range[n], d Range[n / d]]
>
> is a list of numbers between 1 and n which are not divisible by d.We
> have to take all these
> lists, for all prime divisors of n, and their intersection will be then
> the list of all numbers
> k<n which are relatively prime to n.
>
> It is now easy to see that the rpLst of integers < n and relatively
> prime to n can be defined
> as follows:
>
>         rpLst[n_] :=
>         Module[{g=Complement[Range[n],#  Range[n / #]]&,
>                pLst=First[Transpose[FactorInteger[n]]]},
>              Apply[Intersection,Map[g,pLst]]]
>
> With this function we have
>   rpLst[100000];//Timing
>              {4.11667 Second,Null}
>
> Finally, a list of 1000 randomly selected and uniformly distributed
> integers < 100 and
> relatively prime to 100 can be defined by
>
> aLst=rpLst[100];
> Table[aLst[[Random[Integer,{1,Length[aLst]}]]],{1000}]
>
> Ranko Bojanic
> bojanic at math.ohio-state.edu
>

Ranko,

Another coding:

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

rpLst1[400000]; // Timing

{10.32 Second, Null}

Comparison (I have changed  Range[n] to Range[2, n - 1])

rpLst[n_] :=
Module[{g = Complement[Range[2, n - 1], # Range[n/#]] &,
pLst = First[Transpose[FactorInteger[n]]]},
Apply[Intersection, Map[g, pLst]]]

rpLst[400000]; // Timing

{18.07 Second, Null}

Allan
---------------------
Allan Hayes
Mathematica Training and Consulting
Leicester UK
www.haystack.demon.co.uk
hay at haystack.demon.co.uk
Voice: +44 (0)116 271 4198
Fax: +44 (0)870 164 0565

{18.07 Second, Null}

```

• Prev by Date: Re: Some problems with DSolve and NDSolve
• Next by Date: Re: Sound and Mathematica
• Previous by thread: Subject: Re: RE: Finding a relative prime
• Next by thread: Excel numerical import