       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;//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;//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

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; // Timing
relPrimes2; // Timing
relPrimes3; // Timing

{18.45 Second, Null}
{10.55 Second, Null}
{10.1333 Second, Null}
--------------------------------------------
relPrimes1; // Timing
relPrimes2; // Timing
relPrimes3; // 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; // Timing
relPrimes2; // Timing
relPrimes3; // Timing

{18.95 Second, Null}
{4.91667 Second, Null}
{9.65 Second, Null}
----------------------------------------
relPrimes1; // Timing
relPrimes2; // Timing
relPrimes3; // Timing

{28.85 Second, Null}
{5.55 Second, Null}
{14.2333 Second, Null}
---------------------------------------
relPrimes1; // Timing
relPrimes2; // Timing
relPrimes3; // Timing

{49.9833 Second, Null}
{12.9 Second, Null}
{25.4 Second, Null}
--------------------------------------

relPrimes1; // Timing
relPrimes2; // Timing
relPrimes3; // 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