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}