Relatively prime numbers
- To: mathgroup at smc.vnet.net
- Subject: [mg19878] Relatively prime numbers
- From: Ranko Bojanic <bojanic at math.ohio-state.edu>
- Date: Sun, 19 Sep 1999 01:20:59 -0400
- Organization: Ohio State University
- Sender: owner-wri-mathgroup at wolfram.com
Allan Hayes <hay at haystack.demon.co.uk> wrote:
> Ranko,
> Another coding:
> rpLst1[n_]:=Fold[Complement[#,#2]&,Range[2,n-1],
> (Range[#,n-1,#])&/@First[Transpose[FactorInteger[n]]]]
> rpLst1[400000];//Timing
> {10. 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
> {19.85 Second,Null}
The problem discussed here is to find the most efficient way to
construct the list of integers < n and relatively prime to n.
An immediate candidate, the function
relPrimes[n_] := Select[Range[n],GCD[#,n]==1&]
is too slow. A better method is to look at the lists of all multiples
of prime divisors of n which are < n .If we denote by Mult(d) the list
of multiples < n of a prime divisor d, and if we agree that
Complement(A}=Range[n-1] \ A and if Union and Intersection are taken
over all prime divisors of n, then there are
two equivalent expressions for the list of integers < n and relatively
prime to n:
Intersection(Complement(Mult(d))) and Complement(Union(Mult(d)))
To simplify notations we shall use the function
primeDivisors[n_]:= First[Transpose[FactorInteger[n]]]
to obtain the list of prime divisors of n. Using the first expression
we obtain the formula for the
relPrimes1[n_]:=
Apply[Intersection, Map[Complement[Range[n-1],Range[#,n,#]]&,
primeDivisors[n]]]
This is essentially my formula with Allan's improvements. The second
expression leads to
relPrimes2[n_]:=
Complement[Range[n-1], Apply[Union, Map[Range[#,n-1,#]&,
primeDivisors[n]]
This is essentially Allan's formula in which Union is used instead of
Fold.
The original formula is
relPrimes3[n_]:=
Fold[Complement[#,#2]&,Range[2,n-1],Map[Range[#,n-1,#]&,
primeDivisors[n]]]
It turns out that relPrimes3 function is always faster than
relPrimes1
function and that relPrimes2 function is even faster.The function
relPrimes2 is usually faster that relPrimes3 function, but that depends
on how many prime divisors n has and how large these prime divisors are.
It seems that relPrimes3 function with Fold is faster than relPrimes2
function with Union only when n has a small number of
small prime divisors.
Here are some examples (on a Power Macintosh 7500/100 with OS System
8.6
and Mathematica 4.0):
relPrimes1[n_] :=
Apply[Intersection,
Map[Complement[Range[n - 1], Range[#, n, #]] &,
First[Transpose[FactorInteger[n]]]]]
relPrimes2[n_] :=
Complement[Range[n - 1],
Apply[Union,
Map[Range[#, n - 1, #] &, First[Transpose[FactorInteger[n]]]]]]
relPrimes3[n_] :=
Fold[Complement[#, #2] &,
Range[2, n - 1], (Range[#, n - 1, #]) & /@
First[Transpose[FactorInteger[n]]]]
----------------------------------------------
relPrimes1[400000]; // Timing
relPrimes2[400000]; // Timing
relPrimes3[400000]; // Timing
{18.45 Second, Null}
{10.55 Second, Null}
{10.1333 Second, Null}
--------------------------------------------
relPrimes1[1000000]; // Timing
relPrimes2[1000000]; // Timing
relPrimes3[1000000]; // Timing
{49.0833 Second, Null}
{28.2667 Second, Null}
{26.6 Second, Null}
------------------------------------------
In most of the other cases, the function relPrimes2 is much
faster then the other two functions. Here are some examples
------------------------------------------
relPrimes1[400003]; // Timing
relPrimes2[400003]; // Timing
relPrimes3[400003]; // Timing
{18.95 Second, Null}
{4.91667 Second, Null}
{9.65 Second, Null}
----------------------------------------
relPrimes1[400007]; // Timing
relPrimes2[400007]; // Timing
relPrimes3[400007]; // Timing
{28.85 Second, Null}
{5.55 Second, Null}
{14.2333 Second, Null}
---------------------------------------
relPrimes1[1000001]; // Timing
relPrimes2[1000001]; // Timing
relPrimes3[1000001]; // Timing
{49.9833 Second, Null}
{12.9 Second, Null}
{25.4 Second, Null}
--------------------------------------
relPrimes1[1000020]; // Timing
relPrimes2[1000020]; // Timing
relPrimes3[1000020]; // Timing
{124.25 Second, Null}
{37.1333 Second, Null}
{41.75 Second, Null}
-------------------------------------
There is probably a nice fgormula which can give an estimate
of the speed of each of these three functions in terms of
prime divisors of n
Ranko Bojanic
bojanic at math.ohio-state.edu