如何添加可能的除数？

Question

如何检索可能的除数的最大和？

我有一个下面的函数，它将给出可能的数字除数。

码

divisors <- function(x) {
  y <- seq_len(ceiling(x / 2))
  y[x %% y == 0]
}

示例除法器99将给出以下可能的值。

divisors(99)
[1]  1  3  9 11 33

我期望的逻辑:

从最后一个数字到除数值中的第一个数字

1. 最后一个数字是33，这里下一个可被33整除的直接数是11。所以我选择了11，现在从11开始遍历下一个可以被11整除的直接数是1。所以选择1。现在把所有的数字加起来。45
2. Move = 33 + 11 + 1 =下一个数字11，现在下一个可以被11整除的直接数字是1。所以选择1。现在把所有的数字加起来。immediate
3. Move这里的11 + 1 = 12到下一个数字9，现在下一个可以被11整除的直接数字是1。所以选择1。现在把所有的数字加起来。13
4. Move 9+3+ 1 =到下一个数字3，现在下一个可以被3整除的直接数字是1。所以选择1。现在把所有的数字加起来。3+1=4

现在最多的是45个。

现在我在努力用R来写逻辑。非常感谢你的帮助/建议。

注意:素数可以忽略。

Answer 1

更新

对于大整数，例如最大整数.Machine$integer.max (素数)，您可以运行下面的代码(注意，我修改了函数divisors和f )。

divisors <- function(x) {
    y <- seq(x / 2)
    y[as.integer(x) %% y == 0]
}

f <- function(y) {
    if (length(y) <= 2) {
        return(as.integer(sum(y)))
    }
    l <- length(y)
    h <- y[l]
    yy <- y[-l]
    h + f(yy[h %% yy == 0])
}

你会看到

> n <- .Machine$integer.max - 1

> x <- divisors(n)

> max(sapply(length(x):2, function(k) f(head(x, k))))
[1] 1569603656

您可以定义一个递归函数f，它提供连续的除数。

f <- function(y) {
    if (length(y) == 1) {
        return(y)
    }
    h <- y[length(y)]
    yy <- y[-length(y)]
    c(f(yy[h %% yy == 0]), h)
}

您将看到所有可能的连续除数元组。

> sapply(rev(seq_along(x)), function(k) f(head(x, k)))
[[1]]
[1]  1 11 33

[[2]]
[1]  1 11

[[3]]
[1] 1 3 9

[[4]]
[1] 1 3

[[5]]
[1] 1

然后，我们将f应用到sapply中，如下所示

> max(sapply(rev(seq_along(x)), function(k) sum(f(head(x, k)))))
[1] 45

它提供了所需的输出。

Answer 2

您还可以使用以下解决方案。这听起来可能有点复杂，当然总有一个更简单、更有效的解决方案。不过，我觉得这对你有用。我将从您的divisors输出中获取它：

> x
[1]  1  3  9 11 33

# First I created a list whose first element is our original x and from then on
# I subset the first element till the last element of the list

lst <- lapply(0:(length(x)-1), function(a) x[1:(length(x)-a)])

> lst 
[[1]]
[1]  1  3  9 11 33

[[2]]
[1]  1  3  9 11

[[3]]
[1] 1 3 9

[[4]]
[1] 1 3

[[5]]
[1] 1

然后，我编写了一个自定义函数，以实现您的条件并收集所需的输出。为此，我创建了一个函数工厂，它实际上是一个创建函数的函数：

正如您可能已经注意到的，

• 最外层的函数不带任何参数。它只设置一个空向量out来将我们想要的元素保存在。它是在最外层函数的执行环境中创建的，以保护它不受全局environment
• The内部函数中可能影响它的任何更改的影响，这是一个采用向量x的内部函数，因此通常我们将整个设置称为fnf()(x)。我们的out向量的第一个元素实际上是原始x(33)的第一个元素。然后，我找到了第一个元素的所有因子，其商数为0。在找到它们之后，我将第二个元素(11)作为第一个元素(33)，并将其存储在我们的out载体中。然后，我修改了原始的x向量，省略了max值(33)，重复了同样的max--我们将再次重复这个过程，我认为这可能是使用递归的一个很好的例子。递归是一种编程技术，函数实际上是从它的身体或内部调用它自己。正如您可能已经注意到的，我使用函数内部的fn再次重复这个过程，但是每次少一个值，这可能听起来有点复杂，但我相信可能有一些好的地方供您将来探索，因为我发现它们非常有用，希望您也是这样。

fnf <- function() {
  out <- c()
  
  fn <- function(x) {
    out <<- c(out, x[1])
    z <- x[out[length(out)]%%x == 0]
    
    if(length(z) >= 2) {
      out[length(out) + 1] <<- z[2]
    } else {
      return(out)
    }
    x <- x[!duplicated(x)][which(x[!duplicated(x)] == z[2]):length(x[!duplicated(x)])]
    fn(x)
    
    out[!duplicated(out)]
  }
}

# The result of applying the custom function on `lst` would result in your
# divisor values
lapply(lst, function(x) fnf()(sort(x, decreasing = TRUE)))

[[1]]
[1] 33 11  1

[[2]]
[1] 11  1

[[3]]
[1] 9 3 1

[[4]]
[1] 3 1

[[5]]
[1] 1

最后，我们对每个元素进行求和并提取max值。

Reduce(max, lapply(lst, function(x) sum(fnf()(sort(x, decreasing = TRUE)))))
[1] 45

对于一个非常大的整数，我使用了@ThomasIsCoding的修改后的divisors函数：

divisors <- function(x) {
    y <- seq(x / 2)
    y[as.integer(x) %% y == 0]
}

x <- divisors(.Machine$integer.max - 1)

lst <- lapply(0:(length(x)-1), function(a) x[1:(length(x)-a)])
Reduce(max, lapply(lst, function(x) sum(fnf()(sort(x, decreasing = TRUE)))))

[1] 1569603656

Answer 3

你需要恢复。如果我理解正确，这应该能做你想做的事：

fact <- function(x) {
  x <- as.integer(x)
  div <- seq_len(abs(x)/2)
  factors <- div[x %% div == 0L]
  return(factors)
}

maxfact <- function(x) {
  factors <- fact(x)
  
  if (length(factors) < 3L) {
    return(sum(factors))
  } else {
    return(max(factors + mapply(maxfact, factors)))
  }
}

maxfact(99)
[1] 45