Partition a number into three parts, and make lcm(a,b,c) as small as possible

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

I have no idea about it, because the number might go up to 2^31.

I already know if n%3=0 then a=b=c=n/3, but I don't know how to do it when n%3!=0.

Answer 1

Assume without loss of generality that a ≥ b ≥ c. By an averaging argument, a ≥ n/3. If lcm(a, b, c) < 2n/3, then since a divides lcm(a, b, c), we must have lcm(a, b, c) = a, and b and c divide a.

If n is a power of two, then the optimal solution is n/2, n/4, n/4. Proof: the quoted solution is valid, so lcm(a, b, c) ≤ n/2. Since n/2 < 2n/3, it follows that b and c divide a ≤ n/2. Accordingly, a must be even, and b and c must be both odd or both even. If b and c are both odd, then a/2 ≥ b ≥ c, and so a + b + c = n only if b = c = a/2 = n/4.  If b and c are both even, then we divide everything by 2 and argue by induction.

If n is not a power of two, then let its least odd prime divisor be p (find p using Pollard's rho or maybe sieving primes up to √2³¹ and trial division); the optimal solution is (n/p) (p−1)/2, (n/p) (p−1)/2, n/p. Proof: the quoted solution is valid, so lcm(a, b, c) ≤ (n/p) (p−1)/2. Since (n/p) (p−1)/2 < 2n/3, it follows that b and c divide a ≤ (n/p) (p−1)/2. We must have b = a, or else a/2 ≥ b ≥ c would imply that n ≤ 2a ≤ 2 (n/p) (p−1)/2 = n (1 − 1/p), which is false. Accordingly, the solution has the form (n − c)/2, (n − c)/2, c. The optimal solution takes c to be the largest proper divisor of n having the same parity as n, which is c = n/p.