algorithm - 将一个数分成三部分，并使 lcm(a,b,c) 尽可能小

Question

Suppose n be an integer > 2. How do we find 3 positive integers a, b, c, such that n = a+b+c and that their least common multiple, lcm(a,b,c), are as small as possible?

For example, 17 = 2+5+10 and lcm(2,5,10) = 10. However, 17=(1+8+8) and lcm(1,8,8)=8 also is possible. Thus, in this problem, the division of 17 into 1,8,8 is better than 2,5,10.

2 < n < 2^31

我不知道，因为这个数字可能会上升到 2^31 .
我已经知道如果 n%3=0然后 a=b=c=n/3 ，但我不知道该怎么做 n%3!=0 .

Answer 1

不失一般性假设 a ≥ b ≥ c。通过平均参数，a ≥ n/3。如果 lcm(a, b, c) < 2n/3，那么由于 a 整除 lcm(a, b, c)，我们必定有 lcm(a, b, c) = a，并且 b 和 c 整除 a。
如果 n 是 2 的幂，则最优解为 n/2、n/4、n/4。证明:引用的解是有效的，所以 lcm(a, b, c) ≤ n/2。由于 n/2 < 2n/3，因此 b 和 c 除 a ≤ n/2。因此，a 必须是偶数，b 和 c 必须都是奇数或都是偶数。如果 b 和 c 都是奇数，则 a/2 ≥ b ≥ c，因此 a + b + c = n 仅当 b = c = a/2 = n/4 时。如果 b 和 c 都是偶数，那么我们将所有内容除以 2 并通过归纳进行论证。
如果 n 不是 2 的幂，则令其最小奇素数除数为 p(使用 Pollard's rho 或筛选素数至 √231 并尝试除法求 p)；最优解是 (n/p) (p-1)/2, (n/p) (p-1)/2, n/p。证明:引用的解是有效的，所以 lcm(a, b, c) ≤ (n/p) (p−1)/2。由于 (n/p) (p-1)/2 < 2n/3，因此 b 和 c 可除 a ≤ (n/p) (p-1)/2。我们必须有 b = a，否则 a/2 ≥ b ≥ c 将意味着 n ≤ 2a ≤ 2 (n/p) (p−1)/2 = n (1 − 1/p)，这是错误的。因此，该解具有 (n - c)/2, (n - c)/2, c 的形式。最优解取 c 为与 n 具有相同奇偶性的 n 的最大自因数，即 c = n/p。