Detailed mathematical approach

Problem Summary

For \(n = 43!\), we seek ordered factor triples \((a,b,c)\) satisfying

$a \le b \le c,\qquad abc = n.$

The primary objective is to make the triple as balanced as possible, which means minimizing the ratio \(c/a\). If several triples achieve the same optimal ratio, the required output is the smallest possible value of \(a+b+c\).

The implementations do not enumerate every factor triple directly. Instead they work with the prime factorization of \(43!\), search balanced exponent distributions first, and then refine the best result with an exact divisor search.

Mathematical Approach

Step 1: Prime exponents of \(43!\)

For each prime \(p \le 43\), the exponent of \(p\) in \(43!\) is given by Legendre's formula

$e_p = \sum_{k \ge 1} \left\lfloor \frac{43}{p^k} \right\rfloor.$

Hence

$43! = 2^{39} 3^{19} 5^9 7^6 11^3 13^3 17^2 19^2 \cdot 23 \cdot 29 \cdot 31 \cdot 37 \cdot 41 \cdot 43.$

Every admissible triple is therefore equivalent to choosing, for each prime \(p\), three nonnegative exponents \(\alpha_p,\beta_p,\gamma_p\) such that

$\alpha_p + \beta_p + \gamma_p = e_p,$

and then setting

$a = \prod_{p \le 43} p^{\alpha_p},\qquad b = \prod_{p \le 43} p^{\beta_p},\qquad c = \prod_{p \le 43} p^{\gamma_p}.$

Step 2: The objective in logarithmic form

Because the logarithm is strictly increasing, minimizing \(c/a\) is equivalent to minimizing

$\Delta = \log c - \log a.$

This turns the multiplicative balancing problem into an additive one. If the three current factors have sorted logarithms

$L_1 \le L_2 \le L_3,$

then the current quality of the triple is exactly the log-range \(L_3 - L_1\). A perfectly balanced triple would make that range as small as possible.

Step 3: A greedy seed gives the first upper bound

Before the expensive search begins, the implementation constructs a valid triple greedily. Prime copies are processed from large to small, and each copy is assigned to the currently smallest logarithmic bucket. This is not guaranteed to be optimal, but it usually produces a fairly balanced triple very quickly.

That first triple provides an initial upper bound on \(\Delta\). Once such a bound exists, later search branches can be discarded as soon as they can no longer beat it.

Step 4: Phase A - branch-and-bound over exponent splits

For one prime power \(p^e\), the number of three-way exponent splits is

$\binom{e+2}{2},$

because we are counting nonnegative integer solutions of \(x+y+z=e\). Naively taking the Cartesian product over all primes would be enormous, so the implementation explores these choices with branch-and-bound.

The split candidates for a fixed exponent \(e\) are tried in an order that favors balanced distributions first. The priority is determined by a small spread

$\max(x,y,z) - \min(x,y,z),$

and then by closeness to \(e/3\), measured by

$|3x-e| + |3y-e| + |3z-e|.$

After each prime is assigned, the three partial factors are re-sorted by size. This is important: only the ordered triple matters in the end, so sorting removes symmetric duplicates and keeps the pruning formulas simple.

Step 5: Lower bound from the remaining logarithmic mass

Suppose the current sorted logarithms are \(L_1 \le L_2 \le L_3\), and the primes that have not been assigned yet contribute total logarithmic mass \(R\). Even if that remaining mass could be split continuously, the smallest possible final range is obtained by filling the smaller bins first. The resulting optimistic lower bound is

$\operatorname{LB}(L_1,L_2,L_3,R) = \begin{cases} L_3 - (L_1 + R), & R \le L_2 - L_1, \\ L_3 - \left(L_2 + \frac{R-(L_2-L_1)}{2}\right), & L_2 - L_1 \lt R \le L_2 - L_1 + 2(L_3-L_2), \\ 0, & R > L_2 - L_1 + 2(L_3-L_2). \end{cases}$

The meaning is straightforward. First use the remaining logarithmic mass to raise the smallest factor until it reaches the middle one. Then use any leftover mass to raise the two smaller factors together toward the largest one. If even that is not enough to beat the best known range, the entire branch is pruned.

This bound is safe because the real problem is more restrictive than the continuous relaxation: prime exponents are discrete and tied to specific primes, so the true achievable range can only be larger.

Step 6: Phase B - exact refinement over the smallest factor

Phase A already produces an excellent ratio \(R^\ast = c^\ast / a^\ast\). The second phase turns that ratio into a search window for the smallest factor \(a\).

From \(a \le b \le c\) and \(abc = n\), we always have

$a \le n^{1/3}.$

Now assume a candidate triple is at least as good as the current best, so \(c/a \le R^\ast\). Because \(b \le c\),

$n = abc \le a c^2 \le a(R^\ast a)^2 = (R^\ast)^2 a^3,$

which yields

$a \ge \left(\frac{n}{(R^\ast)^2}\right)^{1/3}.$

Therefore phase B only needs to inspect divisors \(a\) inside the narrow interval

$\left(\frac{n}{(R^\ast)^2}\right)^{1/3} \le a \le n^{1/3}.$

The implementation enumerates precisely those divisors by walking through the exponent choices for \(a\), again pruning with logarithmic lower and upper bounds.

Step 7: For fixed \(a\), the optimal \(b\) is the largest divisor below the square root

Once \(a\) is fixed, define

$q = \frac{n}{a} = bc.$

For this fixed \(a\), minimizing \(c/a\) is the same as minimizing \(c\), and since \(bc=q\), that is equivalent to maximizing \(b\). The ordering constraint \(b \le c\) becomes

$b \le \sqrt{q}.$

So the best possible companion factor is simply the largest divisor of \(q\) that does not exceed \(\sqrt{q}\). Once that \(b\) is found, the third factor is forced:

$c = \frac{q}{b}.$

The residual factorization of \(q\) is already known from the chosen exponents of \(a\), so the implementation searches that divisor space directly. It also uses an upper bound from the remaining prime powers to prune branches that cannot improve the current best \(b\).

Step 8: Exact comparison and a small checkpoint

Logs are used only for pruning. The final comparison between candidate triples is exact. To compare the current candidate \((a,b,c)\) with the best-known triple \((a^\ast,b^\ast,c^\ast)\), it is enough to compare

$c a^\ast \quad \text{and} \quad c^\ast a.$

If the ratios are equal, the tie is resolved by the smaller sum \(a+b+c\).

A simple checkpoint is \(n=165=3\cdot 5 \cdot 11\). The only ordered factor triple is \((3,5,11)\), so the optimal sum is \(19\). The implementations verify themselves on small checkpoints of this kind before moving to \(43!\).

How the Code Works

The C++, Python, and Java implementations all follow the same structure. First they compute the prime exponents of \(43!\) and precompute prime powers. Then they generate every three-way split for each exponent value and sort those splits so balanced choices are examined first. A greedy construction gives the initial admissible triple.

After that, phase A performs a depth-first branch-and-bound search in log-space, always keeping the three partial factors sorted. Phase B then enumerates only the admissible divisors for the smallest factor, reconstructs the residual factorization, and finds the largest allowed companion divisor below the square-root threshold. The final choice is made with exact integer arithmetic, so floating-point approximation never decides correctness.

Complexity Analysis

If \(n = \prod p^{e_p}\), phase A would naively examine

$\prod_p \binom{e_p+2}{2}$

branches, which is exponential in the prime-exponent structure. Phase B is also combinatorial: in the worst case it may inspect many divisors in the admissible interval for \(a\), and for each one it performs a recursive search for the best residual divisor \(b\).

So there is no simple polynomial worst-case bound in \(\log n\). The method is practical here because four ideas remove most of the search space: a strong greedy seed, balanced ordering of exponent splits, the continuous lower bound on the attainable log-range, and pruning inside the residual divisor search. Memory use remains modest and is dominated by the stored prime powers, split tables, and recursion state.

References

1. Problem page: https://projecteuler.net/problem=418
2. Legendre's formula for prime exponents in \(n!\): Wikipedia - Legendre's formula
3. Branch and bound: Wikipedia - Branch and bound
4. Prime factorization and divisor structure: Wikipedia - Prime factor