Problem 126: Cuboid Layers

Detailed mathematical approach

Problem Summary

A cuboid \(a\times b\times c\) with whole sides \(a,b,c\ge1\) is built from unit cubes. Its first layer is the smallest set of extra unit cubes that covers every visible face; for \(3\times2\times1\) it has \(22\) cubes. Covering the new solid in the same way gives the second layer, and so on; for \(3\times2\times1\) the next layers need \(46\), \(78\) and \(118\) cubes. The first layer of \(5\times1\times1\) also has \(22\) cubes, and those of \(5\times3\times1\), \(7\times2\times1\) and \(11\times1\times1\) have \(46\). With \(C(n)\) the number of cuboids that have a layer of exactly \(n\) cubes, the statement gives \(C(22)=2\), \(C(46)=4\), \(C(78)=5\) and \(C(118)=8\), and says that \(154\) is the least \(n\) with \(C(n)=10\). We must find the least \(n\) with \(C(n)=1000\). ^[1] Since \(C(22)=2\), a cuboid is counted once, whatever the order of its sides, so we may always assume \(a\le b\le c\).

The whole solution in one sentence: the \(k\)-th layer consists of the cells at taxicab distance exactly \(k\) from the cuboid, which gives a formula for its size that grows with every side and with \(k\), so four nested loops can list every cuboid and layer with at most \(M\) cubes, tally the sizes, and report the first size whose tally is exactly \(1000\), doubling \(M\) if none qualifies.

Mathematical Approach

We first find out exactly which cells a layer occupies, then count them, and finally turn the definition of \(C(n)\) into a finite tally.

1. A single cube, layer by layer

Start with one cube. Its first layer puts a cube on each of the six faces, and the solid becomes a cross of \(7\) cubes whose six arms have \(5\) visible faces each, \(30\) in all. A cube at the end of an arm covers one of them; a cube in the corner between two arms at right angles touches both arms and covers two faces at once. There are \(6\) arm ends and \(12\) such corners, one for each pair of perpendicular arms, and \(6\cdot1+12\cdot2=30\), so the second layer has \(18\) cubes.

No cube can be saved: a visible face can only be covered by a cube in the cell directly in front of it, so every empty cell that shares a face with the solid must be filled, and these cells cover every visible face. A layer is therefore exactly the set of empty cells next to the solid. With the first cube at the origin, the second layer consists of the \(6\) cells such as \((2,0,0)\) and the \(12\) cells such as \((1,1,0)\): the cells with \(|x|+|y|+|z|=2\).

2. Layers are distance shells

Let the cuboid occupy the cells \((x,y,z)\) with \(1\le x\le a\), \(1\le y\le b\) and \(1\le z\le c\). For any integer \(x\), let \(d_a(x)\) be its distance from the range \(1,\dots,a\): it is \(1-x\) if \(x\lt1\), \(0\) if \(1\le x\le a\), and \(x-a\) if \(x\gt a\). The number

$$D(x,y,z)=d_a(x)+d_b(y)+d_c(z)$$

counts the face-to-face steps from the cell to the cuboid; it is the taxicab, or Manhattan, distance. ^[2] We claim that the \(k\)-th layer consists of the cells with \(D=k\), so that after \(k\) layers the solid is the set of cells with \(D\le k\).

The proof goes by induction on \(k\); for \(k=0\) the solid is the cuboid, where \(D=0\). Suppose that after \(k-1\) layers the solid is the set of cells with \(D\le k-1\). It encloses no empty cell: from a cell with \(D\ge k\), moving a coordinate that lies outside its range further away raises \(D\) at every step and leads off to infinity through empty cells. So every face between the solid and an empty cell is visible, and by Section 1 the \(k\)-th layer consists of the empty cells next to the solid. A step to a neighbouring cell changes \(D\) by at most \(1\), so these cells have \(D=k\). Conversely, a cell with \(D=k\ge1\) has a coordinate outside its range, and one step of that coordinate towards the range lowers \(D\) by \(1\) and reaches the solid.

3. Faces, edges and corners

To count the cells with \(D=k\), look at one coordinate at a time. Exactly \(a\) values of \(x\) have \(d_a(x)=0\), and for every \(t\ge1\) exactly two values have \(d_a(x)=t\), one below the range and one above it. A cell of the \(k\)-th layer is therefore described by three distances \(t_1+t_2+t_3=k\), one per coordinate, and a choice of side for each nonzero distance. Sorting by the number of nonzero distances gives three kinds of cells:

• one nonzero distance, equal to \(k\): the cells straight above one of the six faces, \(2bc+2ca+2ab\) cells;
• two nonzero distances, for example \(t_1=0\) and \(t_2+t_3=k\) with \(t_2,t_3\ge1\): there are \(k-1\) such pairs, each with \(a\cdot2\cdot2\) cells, which makes \(4(k-1)a\) cells along the four edges of length \(a\) and \(4(k-1)(a+b+c)\) along all twelve edges;
• three nonzero distances: writing \(k\) as a sum of three positive integers is the same as cutting a row of \(k\) dots at two of the \(k-1\) gaps between them, so by the stars-and-bars count there are \(\binom{k-1}{2}\) such triples, ^[3] none for \(k\le2\); for \(k=4\) they are \((2,1,1)\), \((1,2,1)\) and \((1,1,2)\). Each comes with \(8\) cells, one per choice of sides, which makes \(4(k-1)(k-2)\) cells near the eight corners.

Adding the three kinds gives the size of the \(k\)-th layer:

$$\begin{aligned}L(a,b,c,k)={}&2(ab+bc+ca)\\&+4(k-1)(a+b+c)\\&+4(k-1)(k-2).\end{aligned}$$

For \(3\times2\times1\) the faces give \(22\) cubes in every layer, the edges \(24(k-1)\), and the corners \(0\), \(0\), \(8\) and \(24\) for \(k=1,2,3,4\), so the four layers have \(22\), \(46\), \(78\) and \(118\) cubes, as in the statement. The first layers of the other cuboids agree too: \(2(5+5+1)=22\) for \(5\times1\times1\), while \(2(15+5+3)\), \(2(14+7+2)\) and \(2(11+11+1)\) all equal \(46\). For a single cube the formula gives \(4k^2+2\), that is \(6\), \(18\), \(38\), \(66\), the number of points at taxicab distance \(k\) from a point of the cubic lattice. ^[4]

4. Three properties of the formula

• Every layer is even. Every term of \(L\) is even, so \(C(n)=0\) for every odd \(n\).
• Layers grow. The step from layer \(k\) to layer \(k+1\) is \(4(a+b+c)+8(k-1)\), which is positive; for \(3\times2\times1\) the steps are \(24\), \(32\), \(40\) and \(48\). Each step is \(8\) larger than the one before, because each of the eight corner triangles of \(\binom{k-1}{2}\) cells gains one cell more than in the previous step.
• Bigger cuboids have bigger layers. Increasing \(a\) by \(1\) adds \(2(b+c)+4(k-1)\ge4\) cubes, and the same holds for \(b\) and \(c\), so \(L\) grows strictly with every side.

By the second property a cuboid never has two layers of the same size. So \(C(n)\) is the number of quadruples \((a,b,c,k)\) with \(1\le a\le b\le c\), \(k\ge1\) and \(L(a,b,c,k)=n\), and these quadruples are what the program tallies.

5. Where each loop can stop

Fix a bound \(M\). If \(L(a,b,c,k)\le M\) with \(a\le b\le c\), the third property gives

$$\begin{aligned}6a^2&=L(a,a,a,1)\le L(a,b,b,1)\\&\le L(a,b,c,1)\\&\le L(a,b,c,k)\le M,\end{aligned}$$

and \(L(a,b,b,1)=2b(2a+b)\). Each of these lower bounds grows with the variable that it introduces: \(6a^2\) with \(a\), \(2b(2a+b)\) with \(b\), \(L(a,b,c,1)\) with \(c\), and \(L(a,b,c,k)\) with \(k\). So four nested loops over \(a\), \(b\ge a\), \(c\ge b\) and \(k\ge1\) can each stop at the first value whose bound exceeds \(M\), because every larger value exceeds it too. The loops tally every quadruple with \(L\le M\) exactly once and nothing else (the first value beyond the bound in each loop is tested but not tallied), so afterwards the tally of every \(n\le M\) is exactly \(C(n)\).

6. Worked example: every layer with at most 46 cubes

Take \(M=46\). Since \(6\cdot3^2=54\gt46\), only \(a=1\) and \(a=2\) occur. For \(a=1\) the bound \(2b(2+b)\le46\) allows \(b\le3\), and for \(a=2\) the bound \(2b(4+b)\le46\) allows \(b=2,3\). For fixed \(a\), \(b\) and \(k\) the layer size is a linear function of \(c\):

• \(a=b=1\): the first layers \(4c+2\) give \(6,10,14,\dots,46\) for \(c=1,\dots,11\); the second layers \(8c+10\) give \(18\), \(26\), \(34\) and \(42\) for \(c=1,\dots,4\); the only third layer is \(38\), that of the single cube.
• \(a=1\), \(b=2\): the first layers \(6c+4\) give \(16\), \(22\), \(28\), \(34\), \(40\) and \(46\) for \(c=2,\dots,7\); the second layers \(10c+16\) give \(36\) and \(46\) for \(c=2,3\).
• \(a=1\), \(b=3\): the first layers \(8c+6\) give \(30\), \(38\) and \(46\) for \(c=3,4,5\).
• \(a=b=2\): the first layers \(8c+8\) give \(24\), \(32\) and \(40\) for \(c=2,3,4\).
• \(a=2\), \(b=3\): only \(2\times3\times3\) fits, with a first layer of \(42\).

These are \(31\) layers. The tally gives \(C(22)=2\), from \(1\times1\times5\) and \(1\times2\times3\), and \(C(46)=4\), from the first layers of \(1\times1\times11\), \(1\times2\times7\) and \(1\times3\times5\) and the second layer of \(1\times2\times3\), as in the statement. It also gives \(C(18)=2\), from \(1\times1\times4\) and the second layer of the single cube, so the least \(n\) with \(C(n)=2\) is \(18\), not \(22\). Among the even numbers up to \(46\), the sizes \(2\), \(4\), \(8\), \(12\), \(20\) and \(44\) do not occur at all.

7. Why the counts jump

The tally looks irregular, and the reason is arithmetic. Since \((a+b)(a+c)=a^2+ab+bc+ca\), a first layer of \(n\) cubes is the same as a factorization

$$\begin{aligned}(a+b)(a+c)&=a^2+\tfrac n2,\\2a\le a+b&\le a+c.\end{aligned}$$

For \(a=1\) the cuboids \(1\times b\times c\) whose first layer has \(n\) cubes correspond to the ways of writing \(n/2+1\) as a product of two factors that are at least \(2\): \(24=2\cdot12=3\cdot8=4\cdot6\) gives \(1\times1\times11\), \(1\times2\times7\) and \(1\times3\times5\) of \(C(46)\), while \(23\) is prime, so no such cuboid has a first layer of \(44\) cubes, and Section 6 shows that no other layer has \(44\) cubes either. Later layers work the same way: with \(u=k-1\), \(a'=a+u\), \(b'=b+u\) and \(c'=c+u\), expanding gives

$$\begin{aligned}L(a,b,c,k)={}&2(a'b'+b'c'+c'a')\\&-2u(u+2),\end{aligned}$$

so a \(k\)-th layer of \(n\) cubes is a factorization

$$\begin{aligned}(a'+b')(a'+c')={}&a'^2+\tfrac n2\\&+u(u+2)\end{aligned}$$

with \(u\ge0\), \(a'\ge u+1\) and \(2a'\le a'+b'\le a'+c'\); conversely, each factor pair \(d\le e\) of the right-hand side with \(d\ge2a'\) gives back exactly one cuboid, \(a=a'-u\), \(b=d-a'-u\) and \(c=e-a'-u\). So \(C(n)\) counts certain divisors of numbers built from \(n\), and divisor counts jump between \(2\) for a prime and large values for numbers with many small factors. ^[5] In particular \(C\) is not monotone: \(C(142)=11\), yet the least \(n\) with \(C(n)=10\) is \(154\). The search must therefore test equality, not \(C(n)\ge1000\).

8. Searching with a growing bound

The least \(n\) with \(C(n)=T\) is not known in advance, so the program guesses a bound \(M\), tallies all layers with at most \(M\) cubes, and scans \(n=1,2,\dots,M\) for the first tally equal to \(T\). The tallies up to \(M\) are exact, so the first hit is the answer; if there is none, the answer exceeds \(M\), and the program doubles \(M\) and starts again, the idea of exponential search. ^[6] A pass with bound \(M\) costs \(O(M^2)\) steps, as the complexity section shows. Since \(1+\frac14+\frac1{16}+\dots=\frac43\), all passes up to a final bound \(M\) together cost \(O(M^2)\) as well, and by the measured counts a failed pass costs about a quarter of the next one. For the targets \(1000\) and \(10\) the first bound \(M=50000\) is already large enough.

The factorizations of Section 7 could also give a single \(C(n)\) without a tally, and a check confirms them for every \(n\le3000\), but the search needs \(C(n)\) for all \(n\) up to the answer, and one tally gives all of them at once.

How the Code Works

The C++ program ^[7] evaluates the formula of Section 3 in layer_size(a, b, c, n), whose last argument is the layer number \(k\). solve(target) starts with limit = 50000. Each pass allocates a fresh std::vector<int> count of limit + 1 zeros and runs the four loops of Section 5, comparing \(L(a,a,a,1)\), \(L(a,b,b,1)\), \(L(a,b,c,1)\) and \(L(a,b,c,k)\) with limit and adding \(1\) to the entry of every layer size it meets. It then returns the first index from \(1\) to limit whose entry equals the target, as Section 7 demands; otherwise it doubles limit and repeats the pass, as in Section 8.

run_checkpoints checks that layer_size(1, 1, 1, 1) is \(6\) and that solve(10) returns the value \(154\) from the statement; a failure ends the program with exit code \(2\). parse_arguments, helped by parse_int_after_prefix, accepts --skip-checkpoints and --target=T for a decimal \(T\ge1\) and otherwise exits with code \(1\); the digits are accumulated in an int without an overflow check, so an out-of-range target is not reliably rejected. The main program runs the checkpoints unless they are skipped and prints solve(target).

Python, with layer_size and solve(), and Java, with layerSize and main, use the same formula and loops with the fixed target \(1000\) and no checkpoints or options; the tally is a list count or an int[] count, and the first matching index is printed. Python writes the loops as for loops over generous ranges that always end with a break, and its integers never overflow. C++ and Java use 32-bit int; the largest value evaluated in the pass with limit \(50000\) is \(100002\), the second layer of \(1\times1\times12499\) tested by the layer loop, far below \(2^{31}\).

Complexity and Verification

Let \(Q(M)\) be the number of quadruples with \(a\le b\le c\) and \(L(a,b,c,k)\le M\), the number of tallied layers. Each evaluation of the formula tallies a layer, admits a new value of \(a\), \(b\) or \(c\), which leads to at least one tallied layer, or ends a loop, so a pass costs \(O(Q(M))\) steps plus \(O(M)\) for the array and the scan. For \(a\le b\le c\) we have \(L\ge2c(a+b+2k-2)\), so for fixed \(a\), \(b\) and \(k\) at most \(M/(2s)\) values of \(c\) qualify, where \(s=a+b+2k-2\). Moreover \(L\ge2b^2\) and \(L\ge L(1,1,1,k)=4k^2+2\) give \(a,b\le\sqrt{M/2}\) and \(2k-2\lt\sqrt M\), hence \(s\lt3\sqrt M\), and at most \(s^2\) triples \((a,b,k)\) share a given \(s\). Summing,

$$Q(M)\le\sum_{s\lt3\sqrt M}s^2\cdot\frac{M}{2s}=O(M^2).$$

The order is right: with \(r=\lfloor\sqrt{M/22}\rfloor\), every quadruple with \(a\le b\le c\le r\) and \(k\le r\) has \(L\le6r^2+12r^2+4r^2\le M\), and there are at least \(r^4/6\) of them, so \(Q(M)\) grows like \(M^2\). The measured \(Q(1000)=10970\), \(Q(8000)=644977\) and \(Q(64000)=39877433\) are about \(0.0110M^2\), \(0.0101M^2\) and \(0.0097M^2\). For \(M=50000\) the program tallies \(24401921\) layers of \(1341466\) cuboids with \(27098706\) evaluations of the formula; the C++ program makes this pass twice, once more for the checkpoint. The tally takes \(O(M)\) memory, \(50001\) entries, about 200 kB of 32-bit integers in C++ and Java. On a desktop computer the C++ program, checkpoint pass included, and the Java program finish in a small fraction of a second, the Python program in a few seconds.

The C++ checkpoints test the formula on the single cube and the whole search on the value \(154\). For this article, a separate program grew layers cell by cell, as the statement describes and without the formula: it agrees with the formula for all \(300\) cases with \(a\le b\le5\), \(b\le c\le6\) and \(k\le6\), and every cell it adds to the \(k\)-th layer has taxicab distance \(k\). A tally built only from grown layers equals the formula tally for every \(n\le160\), including \(C(22)=2\), \(C(46)=4\), \(C(78)=5\), \(C(118)=8\), \(C(142)=11\) and \(154\) as the least \(n\) with \(C(n)=10\). With --target=2 and --target=100 the C++ program prints \(18\), as in Section 6, and \(1662\), the value of a separately written tally. All three programs print the same value for the target \(1000\). Apart from the two C++ checkpoints, these checks are not part of the published solutions.

Footnotes and References

The references below supply the background facts used above. The description of a layer as a distance shell, the layer formula, the loop bounds and the factorization view of \(C(n)\) are derived explicitly in this article.

1. Project Euler 126 — Cuboid Layers. The official statement: covering every visible face of a 3 × 2 × 1 cuboid takes at least 22 cubes, and the next layers take 46, 78 and 118. C(n), the number of cuboids with n cubes in one of their layers, has C(22) = 2, C(46) = 4, C(78) = 5 and C(118) = 8; 154 is the least n with C(n) = 10, and the task asks for the least n with C(n) = 1000.
2. Wikipedia — Taxicab geometry. The taxicab distance, also called Manhattan or L1 distance, is the sum of the absolute differences of the coordinates, in any number of dimensions, as used in Section 2.
3. Wikipedia — Stars and bars (combinatorics). Theorem one: there are C(n − 1, k − 1) k-tuples of positive integers with sum n. For three summands with sum k this is C(k − 1, 2), the number of corner positions in Section 3.
4. OEIS A005899 — Number of points on surface of octahedron; also coordination sequence for cubic lattice. The terms are 1, 6, 18, 38, 66, 102, …, with a(n) = 4n² + 2 for n > 0, and their partial sums are the centred octahedral numbers. From n = 1 on they are the layer sizes of a single cube.
5. Wikipedia — Divisor function. It counts the divisors of an integer: for a product of prime powers pᵃ it is the product of the numbers a + 1, so a prime has two divisors, while 24 = 2³ · 3 has (3 + 1)(1 + 1) = 8. Section 7 expresses C(n) through such divisor counts.
6. Wikipedia — Exponential search. In a sorted list, the search doubles a bound until the key lies below it and then runs a binary search in the last interval; Section 8 borrows only the doubling of the bound and recomputes the whole tally at each bound.
7. C++ — Euler126.cpp. The linked immutable C++ revision contains layer_size, solve, run_checkpoints and the options described above. It is the implementation record for this article.