5
\$\begingroup\$

I made this small and easy function that returns the largest common multiple of the elements of ms that is equal to or lower than max:

LCMLthan = function(ms,max) {
    ms = sort(ms, decreasing =TRUE)
    max2 = c()
    for (m in ms)
    {
        max2=append(max2,m*floor(max/m))
    }
    max2=min(max2)
    while (T)
    {
        maxOld = max2
        for (m in ms)
        {
            if(max2%%m!=0){
                max2 = max2 - 1
                break
            }
        }
        if (maxOld==max2){
            return (max2)
        }
    }
}

### Examples
LCMLthan(c(3,5),52)
[1] 45
LCMLthan(c(178,124,17),520000)
[1] 375224

Looking at my code, it feels like there must have a cleaner and more efficient way to code this function. There is also probably a better way to name it too.

\$\endgroup\$
  • 1
    \$\begingroup\$ Largest common multiple is necessarily a multiple of a least common multiple. So the solution is to find the least common multiple lcm and compute the result as lcm * (max / lcm) (integer division assumed). I don't know r to give a proper review. \$\endgroup\$ – vnp Jan 4 '16 at 23:51
  • \$\begingroup\$ As mentioned there's a better algorithm. To review your original algorithm I see two points: 1) the sorting is unnecessary. 2) the update of max2 = max2-1 is very inefficient - you could save a lot by updating it the way you calculate the initial max2 instead. \$\endgroup\$ – bdecaf Jan 6 '16 at 14:37
6
\$\begingroup\$

Looping is generally not recommended in R. And it's not really needed here.

As @vnp pointed out in a comment, all you need is simply calculate the least common multiple of the values in the input vector, let's call it lcm, and apply the formula lcm * (max // lcm) (with integer division).

The pracma library already has an implementation of the least common multiple. If installing that library is not an option for you, you can use this instead:

gcd <- function(a, b) {
  stopifnot(is.numeric(a), is.numeric(b))
  if (a > b) gcd(b, a)
  else if (a == 0) b
  else gcd(b %% a, a)
}

Lcm <- function(a, b) {
  stopifnot(is.numeric(a), is.numeric(b))
  a / gcd(a, b) * b
}

To calculate the least common multiples for a vector of numbers:

Lcm.many = function(values) {
  stopifnot(values)
  if (length(values) == 2) {
    Lcm(values[1], values[2])
  } else {
    Lcm.many(c(Lcm(values[1], values[2]), tail(values, -2)))
  }
}

Then with these helper functions the implementation of your function becomes much simpler:

LCMLthan = function(ms, max) {
  lcm <- Lcm.many(ms)
  lcm * (max %/% lcm)
}

Update

As @flodel pointed out in a comment, there's actually no need for Lcm.many at all, the call to it can be simply replaced with Reduce(Lcm, ms):

LCMLthan = function(ms, max) {
  lcm <- Reduce(Lcm, ms)
  lcm * (max %/% lcm)
}
\$\endgroup\$
  • \$\begingroup\$ Not tested but I bet you can do lcm <- Reduce(Lcm, ms) as a replacement to implementing a Lcm.many. \$\endgroup\$ – flodel Jan 8 '16 at 12:15
  • \$\begingroup\$ You're absolutely right, updated my answer, thanks a lot! \$\endgroup\$ – janos Jan 8 '16 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.