从给定的数字中，确定三个相近的数字，其乘积是原始数字

Question

我有一个数字 n，我想找到三个乘积为 n 但彼此尽可能接近的数字。也就是说，如果 n = 12 那么我想得到 3, 2, 2 作为结果，而不是 6, 1, 2。

另一种思考方式是，如果 n 是长方体的体积，那么我想找到边的长度，以使长方体尽可能像正方体（即长度尽可能相似）。这些数字必须是整数。

我知道这个问题不太可能有一个完美的解决方案，而且我很高兴使用大多数时候都能给出良好答案的东西，但我就是不知道该从哪里提出这个算法。有什么想法吗？

Answer 1

这是我的第一个算法草图，考虑到 n 相对较小：

• 计算 质因数 共n。
• 选出三个最大的并将它们分配给 f1、f2、f3。如果因素少于三个，则分配 1。
• 按降序循环剩余因子，将它们乘以当前最小的分区。

---

编辑

让我们采用n=60。

它的质因数是5 3 2 2。

设置f1=5、f2=3和f3=2。

剩余的 2 乘以 f3，因为它是最小的。

我们最终得到5 * 4 * 3 = 60。

---

编辑

此算法不会找到最佳值，请注意 btillys 评论：

考虑 17550 = 2 * 3 * 3 * 3 * 5 * 5
* 13. 当最好的结果是 25、26、27 时，你的算法会给出 15、30、39。

---

编辑

好的，这是我的第二个算法草图，具有稍微更好的启发式：

• 设置列表 L 到质因数 n。
• 将r设置为n立方根代码>.
• 创建三个因子 F 的集合，最初设置为 1。
• 按降序迭代素因数：
  • 尝试将当前因子L[i]与每个因子按降序相乘。
    • 如果结果小于r，则执行乘法并继续下一个
      质因数。
    • 如果没有，请尝试下一个F。如果超过 F，则乘以最小的一个。

这适用于 17550 的情况：

n=17550
L=13,5,5,3,3,3,2
r=25.98

F = { 1, 1, 1 }

迭代 1：

• F[0] * 13 小于 r ，将 F 设置为 {13,1,1}。

迭代 2：

• F[0] * 5 = 65 大于 r。
• F[1] * 5 = 5 小于 r，将 F 设置为 {13,5,1}。

迭代 3：

• F[0] * 5 = 65 大于 r。
• F[1] * 5 = 25 小于 r，将 F 设置为 {13,25,1}。

迭代 4：

• F[0] * 3 = 39 大于 r。
• F[1] * 3 = 75 大于 r。
• F[2] * 3 = 3 小于 r，将 F 设置为 {13,25,3}。

迭代 5：

• F[0] * 3 = 39 大于 r。
• F[1] * 3 = 75 大于 r。
• F[2] * 3 = 9 小于 r，将 F 设置为 {13,25,9}。

迭代 6：

• F[0] * 3 = 39 大于 r。
• F[1] * 3 = 75 大于 r。
• F[2] * 3 = 27 大于 r，但它是我们能得到的最小的 F。将 F 设置为 {13,25,27}。

迭代7：

• F[0] * 2 = 26比r大，但它是我们能得到的最小的F。将 F 设置为 {26,25,27}。

Answer 2

这是一种纯粹基于数学的方法，它返回最佳解决方案，并且不涉及任何类型的排序。天哪，它甚至不需要素因数。

背景：

1) 回想一下，对于多项式

根的和与积由

其中 x_i 是根。

2) 回忆一下优化理论的另一个基本结果：

即，给定两个变量，使其乘积为常数，当两个变量彼此相等时，总和最小。波形符变量表示最优值。

其推论是，如果乘积恒定的两个变量的总和是最小值，则这两个变量彼此相等。

重新表述原始问题：

您上面的问题现在可以重新表述为多项式求根练习。我们将构造一个满足您的条件的多项式，该多项式的根将是您的答案。如果您需要 k 个最佳数字，则您将拥有一个 k 次多项式。在这种情况下，我们可以用三次方程来讨论

我们知道：

1. c< /code> 是输入数字的负数（假设为正数）
2. a 是一个整数且为负数（因为因子都是正数）
3. b 是一个整数（它是总和一次取两个根）并且为正。
4. p 的根必须是实数（并且是正数，但这已经被解决了）。

为了解决这个问题，我们只需要在满足上述条件的情况下最大化a即可。现在唯一没有明确知道的部分是条件 4，我们可以使用多项式的判别式轻松执行该条件。

对于三次多项式 p，判别式为

和 p<如果 Δ>0，/code> 具有实数且不同的根；如果 Δ=0，则 /code> 具有实数且重合的根（两个或全部三个）。因此，约束 4 现在为 Δ>=0。现在这很简单并且易于编程。

Mathematica 中的解决方案

这是 Mathematica 中实现此功能的解决方案。

这是对其他答案/评论中使用的一些数字的测试。

左侧的列是列表，右侧列中的相应行给出了最优解。

笔记：

我只是注意到OP从未提到过这3个数字必须是整数，尽管每个人（包括我自己）都认为它们是整数（可能是因为他的第一个例子）。重新阅读这个问题，并以立方体为例，OP 似乎并不专注于整数。

这是一个重要的点，它将决定要追求哪一类算法并且需要定义。如果它们不需要是整数，可以提供几种基于多项式的解决方案，其中之一是我的（在放宽整数约束之后）。如果它们应该是整数，那么也许使用分支-n-绑定/分支-n-切割/切割平面的方法可能更合适。

以下内容是假设OP意味着三个数字是整数而编写的。

我现在实现它的方式，在某些情况下它可以给出非整数解决方案。

这为 x 提供非整数解决方案的原因是因为我只有最大化a，而实际上，b也需要最小（不仅如此，还因为我没有对x_i施加约束> 可以使用整数根定理，这将涉及寻找素因数，但会使事情变得更复杂。）

文本中的 Mathematica 代码

Clear[poly, disc, f]
poly = x^3 + a x^2 + b x + c;
disc = Discriminant[poly, x];
f[n_Integer] := 
 Module[{p, \[CapitalDelta] = disc /. c -> -n}, 
  p = poly /. 
     Maximize[{a, \[CapitalDelta] >= 0, 
        b > 0 && a < 0 && {a, b} \[Element] Integers}, {a, b}][[
      2]] /. c -> -n;
  Solve[p == 0]
  ]

Answer 3

正如安德斯·林达尔（Anders Lindahl）所追求的那样，可能有一种聪明的方法可以找到最紧密的三元组，但我将专注于一种更基本的方法。

如果我生成所有三元组，那么我可以在之后根据需要过滤它们，所以我将从这里开始。我知道生成这些的最好方法是使用递归：

---

f[n_, 1] := {{n}}

f[n_, k_] := Join @@
    Table[
      {q, ##} & @@@ Select[f[n/q, k - 1], #[[1]] >= q &],
      {q, #[[2 ;; ⌈ Length@#/k ⌉ ]] & @ Divisors @ n}
    ]

此函数 f 接受两个整数参数，因子 n 的数量以及产生 k 的因子数量。

#[[2 ;; 部分⌈ 长度@#/k ⌉ ]] & @Divisors@n 使用 Divisors 生成 n 的所有除数列表（包括 1），然后从中获取从第二个（去掉 1）到除以 k 的除数的上限。

例如，对于 {n = 240, k = 3}，输出为 {2, 3, 4, 5, 6, 8}

Table code> 命令在累积结果的同时迭代此列表，将每个元素分配给 q。

Table 的主体是 Select[f[n/q, k - 1], #[[1]] >= q &]。这会递归调用 f，然后从结果中选择所有以数字 >= q 开头的列表。

{q, ##} & @@@（也在正文中）然后将 q“添加到”每个选定的列表中。

最后，Join @@ 合并 Table 每个循环生成的这些选定列表的列表。

---

结果是按字典顺序将 n 的所有整数因子分解为 k 部分。示例：

In[]:= f[240, 3]

Out[]= {{2, 2, 60}, {2, 3, 40}, {2, 4, 30}, {2, 5, 24}, {2, 6, 20},
        {2, 8, 15}, {2, 10, 12}, {3, 4, 20}, {3, 5, 16}, {3, 8, 10},
        {4, 4, 15}, {4, 5, 12}, {4, 6, 10}, {5, 6, 8}}

---

根据上面给出的函数/算法的输出，可以根据需要测试三元组的质量。

请注意，由于排序，输出中的最后一个三元组是具有最大最小因子的三元组。这通常是最“立方”的结果，但有时并非如此。

如果必须找到真正的最佳值，那么从列表的右侧开始测试是有意义的，如果不能快速找到更好的结果，则放弃搜索，因为结果的质量随着向左移动而降低。

---

显然，此方法依赖于快速的 Divisors 函数，但我认为这要么是标准库函数，要么您可以在 StackOverflow 上找到一个很好的实现。有了这个，这应该相当快。上面的代码在我的机器上在 1.26 秒内找到 n 从 1 到 10,000 的所有三元组。

Answer 4

人们应该认识到这是众所周知的NP完全问题的一种变体，而不是重新发明轮子。

• 计算n的质因数。
• 计算这些因素的对数
• 该问题转化为将这些对数划分为三个尽可能接近的总和。
• 此问题被称为 Bin Packing 问题的变体，已知作为多处理器调度

鉴于多处理器调度问题是NP完全，难怪很难找到一种不搜索整个问题空间并找到最优解的算法。

但我猜想已经有几种算法可以处理装箱或多处理器调度，并以有效的方式找到接近最佳的解决方案。

另一个相关问题（概括）是作业车间调度。请参阅维基百科描述，其中包含许多已知算法的链接。

---

维基百科所描述的（常用的 LPT 算法（最长处理时间）正是 Anders Lindahl 首先提出的。

Answer 5

编辑
这是使用更高效代码的简短说明， KSetPartitions 大大简化了事情。 Mr.W. 的一些建议也是如此。整体逻辑保持不变。

假设n至少有3个质因数，

1. 查找n的质因数的三元组KSetPartitions列表。
2. 将每个子集中的每个元素（质因数）相乘，生成 n 三个除数的所有可能组合（相乘时产生 n）。您可以将除数视为正交平行六面体的长度、宽度和高度。
3. 最接近立方体的平行六面体将具有最短的空间对角线。将每种情况的三个除数的平方相加，并选择最小的。

---

这是 Mathematica 中的代码：

Needs["Combinatorica`"]
g[n_] := Module[{factors = Join @@ ConstantArray @@@ FactorInteger[n]},
  Sort[Union[Sort /@ Apply[Times, Union[Sort /@ 
      KSetPartitions[factors, 3]], {2}]] 
      /. {a_Integer, b_Integer, c_Integer} :>  
           {Total[Power[{a, b, c}, 2]], {a, b, c}}][[1, 2]]]

---

它可以处理相当大的数字，但随着 n 的因子数量的增加，速度会显着减慢。下面的示例显示了 240、2400、...24000000 的计时。
原则上可以通过考虑质因数在除数中出现多次的情况来加快速度。我还不知道如何做到这一点。

In[28]:= g[240]

Out[28]= {5, 6, 8}

In[27]:= t = Table[Timing[g[24*10^n]][[1]], {n, 6}]

Out[27]= {0.001868, 0.012734, 0.102968, 1.02469, 10.4816, 105.444}