将一个数字分成三个部分，使得它们的最小公倍数(lcm)尽可能小。

Question

将一个数字分成三个部分，使得它们的最小公倍数(lcm)尽可能小。

4

假设 n 是大于 2 的整数，我们如何找到三个正整数 a, b, c，使得它们的和等于 n = a+b+c，且这三个数的最小公倍数 lcm(a,b,c) 最小呢？

例如，17 = 2+5+10 且 lcm(2,5,10) = 10，但是 17 = (1+8+8) 且 lcm(1,8,8)=8 也是可能的。因此，在这个问题中，将 17 分成 1,8,8 比分成 2,5,10 更好。

注意：2 < n < 2^31。

当 n%3!=0 时我不确定怎么做，但当 n%3=0 时，我们有 a=b=c=n/3。

- Jack

我证明了昨晚的猜想。 - David Eisenstat

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Eisenstat · Accepted Answer

假设不失一般性，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，因此只有当b=c=a/2=n/4时，才有a+b+c=n。如果b和c都是偶数，则我们将所有内容除以2并进行归纳论证。

如果n不是2的幂，则其最小奇素数因子为p（使用Pollard的rho或者筛选√2³¹内的质数并进行试除法查找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同奇偶性的最大真约数，即c=n/p。