Detailed mathematical approach

Problem Summary

A cuboid with side lengths \(a\), \(b\), and \(c\) is wrapped by successive outer layers of unit cubes. If the dimensions are ordered as \(a \le b \le c\) and the layer index is \(\ell \ge 1\), let \(L(a,b,c,\ell)\) be the number of cubes in the \(\ell\)-th layer. The problem asks for the smallest integer \(m\) such that exactly 1000 ordered cuboids-and-layers produce \(m\) cubes.

It is convenient to write the counting function as

$C(m)=\#\{(a,b,c,\ell): a \le b \le c,\ \ell \ge 1,\ L(a,b,c,\ell)=m\}.$

The goal is therefore to find the least \(m\) for which \(C(m)=1000\). The ordering \(a \le b \le c\) removes rotational duplicates, but different shapes and different layer numbers are all counted separately.

Mathematical Approach

The implementations are built around one explicit formula for the size of a cuboid layer and one exhaustive counting pass over all admissible states \((a,b,c,\ell)\).

The first layer is just the surface of the cuboid

The outermost layer touching the original cuboid covers its six faces. Two faces have area \(ab\), two have area \(ac\), and two have area \(bc\), so

$L(a,b,c,1)=2(ab+ac+bc).$

This is the smallest layer attached to that cuboid, so any search bounded by \(m\) only needs cuboids satisfying \(2(ab+ac+bc) \le m\).

How one layer grows into the next

Moving from layer \(\ell\) to layer \(\ell+1\) adds a one-cube-thick border around the current shell. The linear part comes from the 12 edge bands: each of the three edge lengths appears four times, so the edge contribution is always \(4(a+b+c)\).

There is also a corner contribution. Once the shell is thicker than the first layer, the stepped patches near the eight corners keep widening, and together they contribute \(8(\ell-1)\) new cubes when the layer index increases from \(\ell\) to \(\ell+1\). Therefore

$L(a,b,c,\ell+1)-L(a,b,c,\ell)=4(a+b+c)+8(\ell-1)=4(a+b+c+2\ell-2).$

For a fixed cuboid, the successive differences form an arithmetic progression. That monotonicity is exactly why the inner loop over layers can stop as soon as it passes the current search limit.

Summing the recurrence gives the closed form

Starting from \(L(a,b,c,1)=2(ab+ac+bc)\) and summing the previous increment for \(\ell-1\) steps gives

$L(a,b,c,\ell)=2(ab+ac+bc)+4(\ell-1)(a+b+c)+4(\ell-1)(\ell-2).$

The last two terms are often combined into

$L(a,b,c,\ell)=2(ab+ac+bc)+4(\ell-1)(a+b+c+\ell-2).$

This is the exact formula used by the C++, Python, and Java implementations. Several useful facts are immediate:

\(L(a,b,c,\ell)\) is always even, it is strictly increasing in \(\ell\) for fixed \(a,b,c\), and it is also increasing in each of \(a\), \(b\), and \(c\) when the other variables are fixed.

Worked example: the \(1 \times 2 \times 3\) cuboid

For \(a=1\), \(b=2\), \(c=3\), the first layer contains

$L(1,2,3,1)=2(1\cdot2+1\cdot3+2\cdot3)=2(11)=22.$

The recurrence then says

$L(1,2,3,2)-L(1,2,3,1)=4(1+2+3)=24,$

so \(L(1,2,3,2)=46\). For the next layer, the increment has grown by 8:

$L(1,2,3,3)-L(1,2,3,2)=4(1+2+3+2)=32,$

hence \(L(1,2,3,3)=78\). The pattern continues with increments \(24,32,40,\dots\), exactly as predicted by the linear recurrence.

From one cuboid to the global counting function

Once \(L(a,b,c,\ell)\) is known, the problem becomes a frequency table over all valid states. For each integer \(m\), count how many quadruples \((a,b,c,\ell)\) satisfy \(L(a,b,c,\ell)=m\). The first \(m\) with frequency 1000 is the desired answer.

No deeper number-theoretic transform is needed here. The decisive observation is that the true state space is already small enough once we exploit the order \(a \le b \le c\), the monotonic growth in \(c\) and \(\ell\), and the fact that only cuboids with first layer at most the current limit can matter.

How the Code Works

Count every layer size up to a temporary limit

The implementation keeps a temporary upper bound \(M\) and allocates an array of frequencies for \(0,1,\dots,M\). It then enumerates all ordered triples \(a \le b \le c\) whose first layer fits inside that bound, evaluates \(L(a,b,c,\ell)\) for \(\ell=1,2,3,\dots\), and increments the frequency of each layer size that does not exceed \(M\).

Use monotonicity to stop each nested loop early

The loops over \(a\), \(b\), and \(c\) stop as soon as the smallest possible first layer in that branch exceeds \(M\). Concretely, the outer loop needs only \(a\) such that \(L(a,a,a,1) \le M\); for fixed \(a\), the next loop needs only \(b\) such that \(L(a,b,b,1) \le M\); and for fixed \(a,b\), the loop over \(c\) stops when \(L(a,b,c,1) \gt M\). Inside a chosen cuboid, the layer loop stops as soon as \(L(a,b,c,\ell) \gt M\).

This structure matches the mathematics exactly: because the layer formula is increasing in every search variable, nothing beyond the first violation can ever come back below the limit.

Expand the search window until the target frequency appears

The search begins with a moderate limit and scans the completed frequency table from left to right. If no value has frequency 1000 yet, the limit is doubled and the whole count is repeated. Since the limits grow geometrically, the total work over all failed passes stays within a constant factor of the final successful pass.

One implementation also includes simple checkpoints: \(L(1,1,1,1)=6\), and the well-known sample count \(C(154)=10\). Those checks confirm both the layer formula and the counting logic before the full target of 1000 is attempted.

Complexity Analysis

For a successful final limit \(M\), the frequency table uses \(O(M)\) memory. The scan that looks for the first value with frequency 1000 also costs \(O(M)\).

The enumeration cost is best described in output-sensitive form. Let \(A(M)\) be the set of ordered cuboids with \(L(a,b,c,1) \le M\), and let \(r(a,b,c;M)\) be the largest layer index with \(L(a,b,c,\ell) \le M\). Then one counting pass costs

$O\!\left(M+\sum_{(a,b,c)\in A(M)} r(a,b,c;M)\right).$

Because \(L(a,b,c,\ell)\) is quadratic in \(\ell\), each \(r(a,b,c;M)\) is \(O(\sqrt{M})\) as a safe upper envelope. In practice the runtime is much better than that crude bound suggests, because the monotone breaks in \(b\), \(c\), and \(\ell\) prune the search aggressively. The repeated doubling of the limit changes only the constant factor, not the overall behavior.

Footnotes and References

1. Problem page: Project Euler 126 - Cuboid Layers
2. Cuboid geometry: Wikipedia - Cuboid
3. Surface area: Wikipedia - Surface area
4. Arithmetic progressions: Wikipedia - Arithmetic progression
5. Quadratic functions: Wikipedia - Quadratic function