MathGroup Archive 1999

[Date Index] [Thread Index] [Author Index]

Search the Archive

Relatively prime numbers

Allan Hayes <hay at> 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

    Apply[Intersection, Map[Complement[Range[n-1],Range[#,n,#]]&,

This is essentially my formula with Allan's improvements. The second
expression leads to

  Complement[Range[n-1], Apply[Union, Map[Range[#,n-1,#]&,

This is essentially Allan's formula in which Union is used instead of
The original formula is


It turns out that  relPrimes3 function is always  faster than
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
 and Mathematica 4.0):

relPrimes1[n_] :=
    Map[Complement[Range[n - 1], Range[#, n, #]] &,

relPrimes2[n_] :=
  Complement[Range[n - 1],
      Map[Range[#, n - 1, #] &, First[Transpose[FactorInteger[n]]]]]]

relPrimes3[n_] :=
  Fold[Complement[#, #2] &,
    Range[2, n - 1], (Range[#, n - 1, #]) & /@

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

  • Prev by Date: Re: please help with plot
  • Next by Date: Solving equations involving Ln function
  • Previous by thread: Re: questions about delayed expression.
  • Next by thread: Solving equations involving Ln function