# Largest common multiple equal or lower than max

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.

• 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. – vnp Jan 4 '16 at 23:51
• 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. – bdecaf Jan 6 '16 at 14:37

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)
}

• Not tested but I bet you can do lcm <- Reduce(Lcm, ms) as a replacement to implementing a Lcm.many. – flodel Jan 8 '16 at 12:15
• You're absolutely right, updated my answer, thanks a lot! – janos Jan 8 '16 at 13:26