// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (6 votes, average: 5.00 out of 5)

Project Euler Solutions

Project Euler 86 Solution

Project Euler 86 Solution

Project Euler 86: Exploring the shortest path from one corner of a cuboid to another

Problem Description

A spider, S, sits in one corner of a cuboid room, measuring 6 by 5 by 3, and a fly, F, sits in the opposite corner. By travelling on the surfaces of the room the shortest "straight line" distance from S to F is 10 and the path is shown on the diagram.

Project Euler 86 Solution

However, there are up to three “shortest” path candidates for any given cuboid and the shortest route is not always integer.

By considering all cuboid rooms with integer dimensions, up to a maximum size of M by M by M, there are exactly 2060 cuboids for which the shortest distance is integer when M=100, and this is the least value of M for which the number of solutions first exceeds two thousand; the number of solutions is 1975 when M=99.

Find the least value of M such that the number of solutions first exceeds one million.


After discovering the sequence A143714 all that was required was to add the sequence until the sum exceeded the target, one million.

Project Euler 86 Solution

Runs < 0.800 seconds in Python 2.7.
import math
L, c, a = 1000000, 0, 2

while c < L:
    a += 1
    for bc in range(3, 2*a):
        if (bc*a) % 12 == 0:
            s = math.sqrt(bc*bc + a*a)
            if not s % 1:    # check if s is an perfect square (integer)
                c += min(bc, a+1) - (bc+1)//2 
print "Project Euler 86 Solution =", a
download arrowUse this link to get the Project Euler 86 Solution Python 2.7 source.


Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.


Project Euler 86 Solution last updated


3 Responses to “Project Euler 86 Solution”

  1. Nice. I’m not sure I’m a fan of the “looking-up-the-sequence-school-of-problem-solving”. But, it’s sure effective.

    Posted by jorge | November 23, 2013, 5:25 PM
  2. There’s a mistake in your program.
    The c += min(bc, a+1) – (bc+1)/2 should be c += min(bc, a+1) – int((bc+1)/2).

    Posted by Spirit | May 3, 2011, 7:27 PM
    • All of the math in python is Integer unless specified explicitly. So, the int() function is not required in Python, but may be required for other languages.

      I’ll change it as to remove any confusion. Thanks for the suggestion.

      Posted by Mike | May 12, 2011, 12:17 PM

Post a comment