Solution

Answer: 1818

Let the cuboid have integer side lengths

$$a \le b \le c.$$

We want the shortest path along the surfaces from one corner to the opposite corner to have integer length.

The key observation is that when we unfold the cuboid, the three candidate shortest paths are:

$$\sqrt{(a+b)^2+c^2},\qquad \sqrt{(a+c)^2+b^2},\qquad \sqrt{(b+c)^2+a^2}.$$

Since $a \le b \le c$, we have

$$a+b \le a+c \le b+c,$$

so the shortest candidate is always

$$\sqrt{(a+b)^2+c^2}.$$

Therefore, we need integer solutions of

$$(a+b)^2 + c^2 = k^2$$

for some integer $k$.

1. Mathematical Analysis

Define

$$s = a+b.$$

Then we seek Pythagorean triples

$$s^2 + c^2 = k^2,$$

with constraints

$$1 \le a \le b \le c.$$

For a fixed maximum side length $M$, we count all cuboids with

$$c \le M.$$

So for each $c$, we count all values $s$ such that

$$s^2 + c^2$$

is a perfect square.

Then we count how many pairs $(a,b)$ satisfy

$$a+b=s,\qquad 1\le a\le b\le c.$$

Counting $(a,b)$ pairs

For fixed $s$ and $c$:

$$a+b=s,\qquad a\le b,\qquad b\le c.$$

Because $b=s-a$,

$$a \le s-a \quad\Rightarrow\quad a \le \frac{s}{2}.$$

Also,

$$s-a \le c \quad\Rightarrow\quad a \ge s-c.$$

Hence

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

So the number of valid pairs is

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

This simplifies into the standard compact form:

If $s\le c$:

$$#=\left\lfloor \frac{s}{2}\right\rfloor.$$

If $s>c$:

$$#=\left\lfloor \frac{s}{2}\right\rfloor-(s-c)+1.$$

2. Efficient Algorithm

We increment $M=c$ one at a time.

For each new $c$:

Loop through

$$s=2,3,\dots,2c$$

because $a,b\le c$. 2. Check whether

$$s^2+c^2$$

is a perfect square. 3. If yes, add the number of valid $(a,b)$ pairs.

Stop once the cumulative total exceeds $1,000,000$.

The complexity is roughly

$$O(M^2),$$

which is fast enough because the answer is only around $1800$.

3. Python Implementation

from math import isqrt

TARGET = 1_000_000

count = 0
M = 0

while count <= TARGET:
    M += 1

    # s = a + b
    for s in range(2, 2 * M + 1):

        # Check whether s^2 + M^2 is a perfect square
        n = s * s + M * M
        r = isqrt(n)

        if r * r == n:

            # Count valid (a,b) pairs
            if s <= M:
                count += s // 2
            else:
                count += (s // 2) - (s - M) + 1

print(M)

4. Code Walkthrough

Imports

from math import isqrt

isqrt(n) computes the integer square root efficiently and exactly.

Main variables

TARGET = 1_000_000

count = 0
M = 0

count stores the number of valid cuboids found so far.
M is the current maximum side length.

Main loop

while count <= TARGET:
    M += 1

We increase the allowed maximum dimension one step at a time until the total exceeds one million.

Enumerating possible sums

for s in range(2, 2 * M + 1):

Since $a,b \le M$,

$$2 \le s=a+b \le 2M.$$

Perfect-square test

n = s * s + M * M
r = isqrt(n)

if r * r == n:

This checks whether

$$s^2 + M^2$$

is a perfect square.

Counting valid decompositions

Case 1: $s \le M$

count += s // 2

Example:

$$s=6$$

Valid pairs:

$$(1,5),(2,4),(3,3)$$

Exactly $6//2=3$.

Case 2: $s > M$

count += (s // 2) - (s - M) + 1

This enforces $b \le M$.

Example:

$$M=5,\quad s=8$$

Possible pairs:

$$(3,5),(4,4)$$

Count $=2$.

Formula gives:

$$8//2-(8-5)+1 =4-3+1 =2.$$

5. Verification on the Given Example

The problem states:

For $M=99$, count $=1975$
For $M=100$, count $=2060$

Running the code reproduces these values exactly, confirming correctness.

Continuing until the count first exceeds $1,000,000$ gives:

$$M = 1818.$$

This magnitude is reasonable because the count grows roughly quadratically.

Answer: 1818

Project Euler Problem 86