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 √231 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.
