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). 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). The application is this: we have an area that is, say, 40 x 80 units. We want to find all the possible grids (of square integer-valued units) that can be placed over that area that cover it completely. The list at the end of the preceding paragraph is the right answer - the question is how to get it from our list of common factors, other than by brute force. Thanks for any advice. Gordon -- 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 [[alternative HTML version deleted]]
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
Dear Gordon, Try also,> unique(apply(expand.grid(commfac,commfac),1,prod))[1] 1 2 5 4 10 25 HTH, Jorge On Mon, Feb 23, 2009 at 9:52 PM, Fox, Gordon <gfox@cas.usf.edu> wrote:> 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). > > > > 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). > > > > The application is this: we have an area that is, say, 40 x 80 units. We > want to find all the possible grids (of square integer-valued units) > that can be placed over that area that cover it completely. The list at > the end of the preceding paragraph is the right answer - the question is > how to get it from our list of common factors, other than by brute > force. > > > > Thanks for any advice. > > > > Gordon > > > > -- > > 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 > > > > > [[alternative HTML version deleted]] > > ______________________________________________ > R-help@r-project.org mailing list > https://stat.ethz.ch/mailman/listinfo/r-help > PLEASE do read the posting guide > http://www.R-project.org/posting-guide.html > and provide commented, minimal, self-contained, reproducible code. >[[alternative HTML version deleted]]
On Mon, Feb 23, 2009 at 9:52 PM, Fox, Gordon <gfox at cas.usf.edu> wrote:> 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