Smallest number divisible by first few natural numbers (using the R foreach package) [duplicate]

Tag: r , foreach , iterator Author: a5220265 Date: 2013-09-25

This question already has an answer here:

I am trying to solve the following (Project Euler) problem using R (and iterators and the foreach package),

What is the smallest positive number that is divisible by all of the numbers from one to fifteen?

and while I think that my code should do the job, it does not seem to:

library(foreach)
library(iterators)

# function to check sequence of natural numbers for  
#   divisibility by a given list of factors
fnDivision = function(maxNum, vFactors) {
  foreach(i = icount(factorial(15))) %do% {
    if(!i %% 100 ) cat(sprintf("Done with the first %i natural numbers.\n", i))
    if(all(! i %% vFactors)) { 
      return(i)
    }
  } 
}

# test the function
vFactors = c(8, 9, 10, 11, 12, 13, 14, 15)
fnDivision(15, vFactors)

Note that I have reduced the number of factors by which I test the division of the sequence of natural numbers from all the natural numbers from 1-15, to the ones above.

Just in case, the correct answer to this is given in A003418, as 360360, and this

all(! 360360 %% vFactors)

evaluates to TRUE.

@James I would like to answer this question using the the foreach package. Indeed this question is closer to the spirit of my question than the one that you have linked.
Then you need to ensure you get the correct divisors to divide by. 2^3 is missing from vFactors.
If your question is really about how to use the foreach package, you should flag that by changing the title, which makes it seem like you're asking about how to calculate the least common multiple
If you are asking about how to solve project euler problems then tsk tsk! It's against the spirit of the game!
@James Thanks and done.

Other Answer1

help.search("least common multiple") 

library(gmp)
Reduce(lcm.bigz, 1:15)
# Big Integer ('bigz') :
# [1] 360360

Other Answer2

Here you go.

x <- 8:15
p <- prod(x)
min(Reduce(intersect, lapply(x,function(i) seq(i,p,i))))

[1] 360360

And you're probably getting the wrong answer because you're forgetting to include 8.

comments:

+1 good debugging skillz.

Other Answer3

Given your set of reduced divisors, this should be very fast (yes, even though it's a for loop - it only has iterations equal to the length of divisors) and relies on multiplying the greatest power of each of the prime factors in your divisors...

#  For primeFactors function
require( surveillance )
x <- c( 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 )
#  Output vector
out <- numeric(0)
#  Maths magic
for( i in x ){
  tmp <- primeFactors(i)
  out <- c( out , tmp[ ! tmp %in% out ] ) 
}
prod( out )
[1] 360360

Other Answer4

So after some thought, I figured that my attempt at using the foreach package to access the iterator stream was misguided. Instead, here is the (highly Pythonic) solution that I am happy with:

library(iterators)

# function to check sequence of natural numbers for  
#   divisibility by a given list of factors
fnDivision = function(maxNum, vFactors) {
    i = icount(factorial(15))
    while(TRUE) {
        currentlyTesting = nextElem(i)
            if(all(! currentlyTesting %% vFactors)) { 
            return(currentlyTesting )
            }
    } 
}

# test the function
vFactors = c(8, 9, 10, 11, 12, 13, 14, 15)
sprintf('The smallest natural number divisible by the first 15 natural numbers is %i.', 
    fnDivision(15, vFactors))

comments:

Why don't you test this for speed against the other solutions (especially Josh's - I found his to be twice as fast as mine). I'd be interested to see how they compare. But +1 for answering your own question.
@SimonO101 Unlikely that my code is going to be faster than Josh's given that the lcm.bigz probably uses an efficient algorithm to compute the LCM, whereas mine is a brute force approach.
Perhaps at least test mine against your parallel solution. The point here is that you can reduce the complexity of the problem by thinking a little about the maths! My for loop runs in 0.0002 seconds compared to say 26 seconds for @Thomas' solution on my computer (a factor of 130,000 times faster) :-)
@SimonO101 Well, my code is serial, since I discarded use of foreach. Anyway, system.time(fnDivision(15, vFactors)) takes 7.10s, system.time(replicate(10000, Reduce(lcm.bigz, 1:15))) takes 1.22s, essentially a speedup of about 5e4 times. :)
@SimonO101 130k times faster! Now I want to see if I can come up with an even slower solution. :)