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

Question

假设n是一个整数> 2。我们如何找到正3整数，使得 和 的最小公倍数尽可能小？a, b, c,n = a+b+clcm(a,b,c)

例如，17 = 2+5+10和lcm(2,5,10) = 10。然而，17=(1+8+8)并且lcm(1,8,8)=8也是可能的。17因此，在这个问题中， into的除法比in的除法1,8,8更好2,5,10。

2 < n < 2^31

我不知道，因为这个数字可能会增加到2^31。

我已经知道如果n%3=0那时a=b=c=n/3，但我不知道何时该怎么做n%3!=0。

Answer 1

不失一般性地假设 a \xe2\x89\xa5 b \xe2\x89\xa5 c.\xc2\xa0 通过平均参数，a \xe2\x89\xa5 n/3。如果 lcm(a, b, c) < 2n/3，那么由于 a 整除 lcm(a, b, c)，所以我们必须有 lcm(a, b, c) = a，并且 b 和 c 整除 a。

\n

如果n是2的幂，那么最优解是n/2、n/4、n/4。证明：所引用的解是有效的，因此 lcm(a, b, c) \xe2\x89\xa4 n/2。由于 n/2 < 2n/3，因此 b 和 c 除 a \xe2\x89\xa4 n/2。因此，a 必须是偶数，b 和 c 必须都是奇数或都是偶数。如果 b 和 c 都是奇数，则 a/2 \xe2\x89\xa5 b \xe2\x89\xa5 c，因此仅当 b = c = a/2 = n/4 时 a + b + c = n。\xc2\xa0如果 b 和 c 都是偶数，那么我们将所有值除以 2 并通过归纳法进行论证。

\n

如果 n 不是 2 的幂，则设其最小奇素因数为 p（使用 Pollard's rho 求 p，或者筛选素数直至 \xe2\x88\x9a2 ³¹并试除）；最优解为 (n/p) (p\xe2\x88\x921)/2, (n/p) (p\xe2\x88\x921)/2, n/p.\xc2\xa0证明：引用的解有效，因此 lcm(a, b, c) \xe2\x89\xa4 (n/p) (p\xe2\x88\x921)/2。由于 (n/p) (p\xe2\x88\x921)/2 < 2n/3，因此 b 和 c 除 a \xe2\x89\xa4 (n/p) (p\xe2\x88\x921) /2。我们必须有 b = a，否则 a/2 \xe2\x89\xa5 b \xe2\x89\xa5 c 将意味着 n \xe2\x89\xa4 2a \xe2\x89\xa4 2 (n/p) ( p\xe2\x88\x921)/2 = n (1 \xe2\x88\x92 1/p)，这是假的。因此，解的形式为 (n \xe2\x88\x92 c)/2, (n \xe2\x88\x92 c)/2, c.\xc2\xa0 最优解取 c 为n 与 n 具有相同的奇偶校验，即 c = n/p。

\n