All the products of common factors

Fox, Gordon <gfox <at> cas.usf.edu> writes:

Example: 40 and 80 have these factors: c(1,2,2,2,5) and c(1,2,2,2,2,5).
We can use match() to get the common factors c(1,2,2,2,5). What we want
to be able to get from this is the list of all the possible products,
which should be the concatenation of the original list, the products of
all the pairs, of all the triplets, and so forth:
c(1,2,2,2,5,4,8,10,20,40). 

This is somewhat brute force, but how about

commfac <- c(1,2,2,2,5)
cfun <- function(i) { combn(commfac,i,prod) }
L <- lapply(as.list(1:length(commfac)),cfun)
unique(sort(unlist(L)))

  ?

  Ben Bolker

An embedded and charset-unspecified text was scrubbed...
Name: not available
URL: <https://stat.ethz.ch/pipermail/r-help/attachments/20090224/b18b9708/attachment-0001.pl>

This is a seemingly simple problem - hopefully someone can help.
Problem: we have two integers. We want (1) all the common factors, and
(2) all the possible products of these factors. We know how to get (1),
but can't figure out a general way to get (2).

Your problem statement is rather complicated, but I believe it reduces
to simply:

   Find the factors of the greatest common divisor of A and B.

Note: *factors*, not *prime factors*.  Finding the prime factors first
is unnecessary.

Euclid's algorithm straightforwardly finds GCDs:

   gcd <- function(a,b) {if (a>b) gcd(b,a) else if (a==0) b else gcd(a,b%%a)}
   gcd(40,80) => 40

Now find all the factors of 40.  Might as well use a simple, naive
algorithm for such small numbers:

   num <- 40
   which(num/1:num == floor(num/1:num))
   [1]  1  2  4  5  8 10 20 40

Or if you want to get really fancy and efficient:

   smallfacs <-  which( (q <- num/1:sqrt(num)) == floor(q) )
   c(smallfacs,rev(num/smallfacs))

You do *not* need to factor the original numbers.  You do *not* need
to iterate through combinations.

Treating your specification as a draft program leads to some rather
complicated and inefficient code...:

system.time({commfac <- c(1,rep(2,20))   # about 1e6
   cfun <- function(i) { combn(commfac,i,prod) }
   L <- lapply(as.list(1:length(commfac)),cfun)
   unique(sort(unlist(L)))})
   user  system elapsed
  24.71    0.01   24.89

system.time({num <- 2^20; which(num/1:num == floor(num/1:num))})

user  system elapsed
   0.17    0.00    0.17

num <- prod(1:16)
format(num,digits=20)

[1] "20922789888000"

system.time( { smallfacs <-  which( (q <- num/1:sqrt(num)) == floor(q) ); c(smallfacs,rev(num/smallfacs))})

user  system elapsed
   0.64    0.06    0.70

Hope this helps,

         -s

"L'esprit de l'escalier" strikes again....

An even simpler statement of your original problem:

      Find the factors that A and B have in common.

If A and B are fairly small (< 1e7, say), a very direct approach is:

       which(  ! (A %% 1:min(A,B)) &  !(B %% 1:min(A,B)) )

Is this "brute force"?  Well, I suppose, but it is simple and direct
and fast enough for A=B=1e7 (5 sec).  It doesn't involve factorization
into prime factors, GCDs, or combinations.

If your goal is concision and not clarity or speed, you can do even better:

       which(  !(A %% 1:B & B %% 1:A) )

which is still practical (though it gives a warning).

How big do your A and B get, and how many different A's and B's do you
need to run this calculation for?

               -s

Argh!  The second (concise) version should have |, not & !!!

          -s

"L'esprit de l'escalier" strikes again....

An even simpler statement of your original problem:

      Find the factors that A and B have in common.

If A and B are fairly small (< 1e7, say), a very direct approach is:

       which(  ! (A %% 1:min(A,B)) &  !(B %% 1:min(A,B)) )

Is this "brute force"?  Well, I suppose, but it is simple and direct
and fast enough for A=B=1e7 (5 sec).  It doesn't involve factorization
into prime factors, GCDs, or combinations.

If your goal is concision and not clarity or speed, you can do even better:

       which(  !(A %% 1:B & B %% 1:A) )

which is still practical (though it gives a warning).

How big do your A and B get, and how many different A's and B's do you
need to run this calculation for?

               -s

Thanks for all the suggestions!

The tricky part isn't finding the common factors -- we knew how to do
that, though not in so concise a fashion as some of these suggestions.
It was finding all their products without what I (as a recovered Fortran
programmer) would call "truly brute force." Several of these suggestions
solve the problem nicely!

Gordon

P.S. The numbers involved will never be very large -- these are
dimensions of areas in which trees were sampled, in meters. They'll
always be on the order of 50-100m or so on a side.
--
Dr. Gordon A. Fox       Voice: (813)974-7352       Fax: (813)974-3263
Dept. of Integrative Biology ((for US mail:)SCA 110) ((for FedEx
etc:)NES 107)
Univ. of South Florida                 4202 E. Fowler Ave.
Tampa, FL 33620, USA                   http://foxlab.cas.usf.edu

"All the fun of sitting still, being quiet, writing down numbers. Yes,
science has it all." -- Principal Skinner


-----Original Message-----
From: macrakis at gmail.com [mailto:macrakis at gmail.com] On Behalf Of
Stavros Macrakis
Sent: Wednesday, February 25, 2009 2:02 AM
To: Fox, Gordon; r-help at r-project.org
Subject: Re: [R] All the products of common factors

Argh!  The second (concise) version should have |, not & !!!

          -s

"L'esprit de l'escalier" strikes again....

An even simpler statement of your original problem:

      Find the factors that A and B have in common.

If A and B are fairly small (< 1e7, say), a very direct approach is:

       which(  ! (A %% 1:min(A,B)) &  !(B %% 1:min(A,B)) )

Is this "brute force"?  Well, I suppose, but it is simple and direct
and fast enough for A=B=1e7 (5 sec).  It doesn't involve factorization
into prime factors, GCDs, or combinations.

If your goal is concision and not clarity or speed, you can do even

better:

       which(  !(A %% 1:B & B %% 1:A) )

which is still practical (though it gives a warning).

How big do your A and B get, and how many different A's and B's do you
need to run this calculation for?

               -s

The tricky part isn't finding the common factors -- we knew how to do
that, though not in so concise a fashion as some of these suggestions.
It was finding all their products without what I (as a recovered Fortran
programmer) would call "truly brute force." Several of these suggestions
solve the problem nicely!

Are you sure you are not confusing *prime factors* with *factors*?  My
understanding is that you are looking for all the factors of A which
are also factors of B, i.e. the common factors of A and B.  Why else
would you be computing all those products?

               -s

An embedded and charset-unspecified text was scrubbed...
Name: not available
URL: <https://stat.ethz.ch/pipermail/r-help/attachments/20090225/d3a622d5/attachment-0001.pl>