Detailed mathematical approach

Problem Summary

Take a cuboid with integer side lengths \(m \ge b \ge c \ge 1\). A spider starts at one corner and wants to reach the opposite corner while staying on the surface. For some cuboids the shortest surface route has integer length; for others it does not. If \(C(M)\) denotes the number of such cuboids with largest side at most \(M\), the task is to find the least \(M\) for which \(C(M) \gt 10^6\).

A naive search over every triple \((m,b,c)\) is already large, and checking all surface routes for each triple is unnecessary. The implementations use two facts: once the sides are ordered, only one unfolding can be shortest, and the geometry depends on \(b+c\) rather than on \(b\) and \(c\) separately.

Mathematical Approach

The whole method is a counting argument built on a planar unfolding. Instead of tracing a path on a 3D surface, we flatten two faces into a rectangle and turn the shortest route into a straight segment.

Unfolding the Cuboid

With side lengths ordered as \(m \ge b \ge c\), there are three natural ways to unfold two adjacent faces around the start and end corners. They lead to three candidate lengths:

$d_1=\sqrt{m^2+(b+c)^2}, \qquad d_2=\sqrt{b^2+(m+c)^2}, \qquad d_3=\sqrt{c^2+(m+b)^2}.$

Every shortest surface route on a cuboid comes from one of these rectangles, so the problem is to identify which candidate is minimal and when that minimal value is an integer.

Why Only \(m^2+(b+c)^2\) Matters

Because the sides are sorted, \(d_1\) is always the smallest of the three candidates. It is enough to compare squares:

$d_2^2-d_1^2=b^2+(m+c)^2-\bigl(m^2+(b+c)^2\bigr)=2c(m-b)\ge 0,$

$d_3^2-d_1^2=c^2+(m+b)^2-\bigl(m^2+(b+c)^2\bigr)=2b(m-c)\ge 0.$

So for ordered sides the shortest surface route is always

$d=\sqrt{m^2+(b+c)^2}.$

That is the key invariant used by all three implementations.

Compressing the Search to \(m\) and \(s=b+c\)

Now set

$s=b+c.$

Since \(1 \le c \le b \le m\), the sum \(s\) satisfies \(2 \le s \le 2m\). The shortest route is integral exactly when

$m^2+s^2=d^2$

for some integer \(d\). In other words, \((m,s,d)\) must be a Pythagorean triple. Once \(m\) is fixed, the geometry no longer cares how \(s\) was split into \(b\) and \(c\); it only cares whether \(m^2+s^2\) is a perfect square.

Counting How Many Pairs \((b,c)\) Produce the Same Sum

For a fixed admissible pair \((m,s)\), we must count the integer pairs \((b,c)\) with

$b+c=s, \qquad m \ge b \ge c \ge 1.$

Writing \(b=s-c\), the inequalities become

$c \ge 1, \qquad s-c \le m, \qquad c \le s-c.$

So \(c\) must lie in the interval

$\max(1,s-m) \le c \le \left\lfloor \frac{s}{2} \right\rfloor.$

Therefore the number of cuboids contributed by this single value of \(s\) is

$\left\lfloor \frac{s}{2} \right\rfloor-\max(1,s-m)+1.$

The same count can be written piecewise:

$ \#(m,s)= \begin{cases} \left\lfloor \dfrac{s}{2} \right\rfloor, & 2 \le s \le m,\\[6pt] \left\lfloor \dfrac{s}{2} \right\rfloor-s+m+1, & m \lt s \le 2m. \end{cases} $

This is exactly the interval-length calculation performed in the implementations.

Worked Example

Take \(m=6\) and \(s=8\). Then

$6^2+8^2=36+64=100=10^2,$

so any valid split of \(8\) into \(b+c\) gives a cuboid whose shortest surface route has length \(10\). The bounds for \(c\) are

$\max(1,8-6)=2 \le c \le \left\lfloor \frac{8}{2} \right\rfloor=4.$

Hence \(c\in\{2,3,4\}\), giving the three cuboids

$6\times 6\times 2,\qquad 6\times 5\times 3,\qquad 6\times 4\times 4.$

All three share the same shortest route length \(10\), because they all correspond to the same pair \((m,s)=(6,8)\).

The Running Count

If \(N(m)\) is the number of new cuboids whose largest side is exactly \(m\), then

$ N(m)=\sum_{\substack{2 \le s \le 2m\\ m^2+s^2\text{ is a square}}} \left(\left\lfloor \frac{s}{2} \right\rfloor-\max(1,s-m)+1\right). $

The cumulative total up to \(M\) is

$C(M)=\sum_{m=1}^{M} N(m).$

The answer is the first \(M\) with \(C(M) \gt 10^6\).

How the Code Works

Iterating the Largest Side

The C++, Python, and Java implementations process cuboids by increasing largest side. For each current value they iterate every possible sum of the two smaller sides, from \(2\) up to twice the largest side.

Testing the Geometric Condition

For each candidate sum they form \(m^2+s^2\) and test whether it is a perfect square. The Python implementation uses an integer square root directly. The C++ and Java implementations take the square root numerically, truncate it to an integer, and verify the result by squaring it back. In all three cases the effect is the same: only Pythagorean pairs \((m,s)\) survive.

Adding the Correct Number of Cuboids

When a square is found, the implementation computes the lower and upper bounds for \(c\), namely \(\max(1,s-m)\) and \(\min(m,\lfloor s/2 \rfloor)\), and adds the size of that interval. Because the loop already restricts \(s\) to \(2 \le s \le 2m\), the interval is mathematically valid; the code still keeps an explicit guard before adding, which is a harmless safety check.

Stopping Rule

A running total is maintained across all largest-side values. As soon as that total exceeds the target, the current largest side is returned. The Python implementation uses a fixed outer bound that is comfortably above the true answer, while the C++ and Java implementations keep going until the stopping condition is met. One implementation also includes a small checkpoint: with target \(2000\), the correct least value is \(100\).

Complexity Analysis

For a fixed largest side \(m\), the inner loop visits \(2m-1\) possible sums. Therefore the total number of square tests up to \(M\) is

$\sum_{m=1}^{M}(2m-1)=M^2,$

so the running time is \(O(M^2)\). No sorting, recursion, or large auxiliary tables are needed.

The memory usage is \(O(1)\): each implementation stores only a few integers, a square-root result, and the cumulative count.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=86
2. Cuboid: Wikipedia - Cuboid
3. Net of a polyhedron: Wikipedia - Net (polyhedron)
4. Pythagorean triple: Wikipedia - Pythagorean triple
5. Integer square root: Wikipedia - Integer square root