[Date Index]
[Thread Index]
[Author Index]
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**
| |