Dan Meyer’s Really Really Really Difficult Puzzle

Dan Meyer offered this puzzle. The essence of it is, given an arbitrary number for volume, can we build an algorithm that will always generate the integer side lengths that give us the least surface area? He put it in more “real world” terms than that, but that’s the gist.

If we did it in two dimensions, the puzzle is so easy as to be trivial: Take the square root of the area, then decrement down integers until you reach a factor of the area. That’s one side.

But the third dimension makes it mind-bogglingly difficult. Sure, we could use brute force, but it feels like there ought to be a straightforward solution.

At some point, I’d like to write up my thought processes. If you go to that link, there are a lot of blind alleys that I and others went down. There’s a lot of fruit to be had here about how to approach a problem.

However, the purpose of this item is to write up the current state of my algorithm, which appears to work up to one million. I have a feeling that it will eventually break beyond that point, but maybe not.

• First of all, if the volume is a perfect cube, just take the cube value and you’re done.
• If the volume has three or fewer prime factors, that’s it. For instance, if \(V = pq\), then the ideal is \((p, q, 1)\). Jonah points out on Dan’s item that this is not needed as part of the algorithm, but it’s a quick solution.

If there are four or more prime factors, things get tricky if we don’t want to use brute force. A triple consists of three sides; a triple is ideal if it represents a lower surface area than any other triple of factors of the volume. We’re going to create four triple candidates and decide which candidate is best. In all cases, once we’ve identified one element of the triple, the other two will follow in the same way:

1. \(a\) is the candidate we’re going to use for an element.
2. \(b\) the largest factor of \(\frac{V}{a}\) that is less than \(\sqrt{\frac{V}{a}}\).
3. \(c = \frac{V}{ab}\).

• The Prime Factor candidate is found by identifying the largest prime factor of V.
• The Cube Root candidate is found by identifying the largest factor of V less than \(\sqrt[3]{V}\)

There are two more candidates which are confusing to explain, but are mirror images of each other.

• To find the Downward candidate: Given a Cube Root candidate \((a, b, c)\) (in least-to-greatest order), start at \(b – 1\) and find the next lower factor of \(V\). This is your new element candidate; build a new triple candidate from it. Then repeat the process with your new Downward candidate and compare the results. If you got a better triple, use the new triple and repeat the process; if you didn’t get a better triple, stop. This is your Downward candidate.
• To find the Upward candidate: Do the same thing, but start at \(b + 1\) and find the next higher factor of \(V\).

Generally, it only takes one or two cycles to stop this process. This is important, though: If you compare the Cube Root candidate to the Downward or Upward candidate, sometimes things get worse before they get better. For this to work in all cases, you have to complete at least one comparison of two Downward candidates and two Upward candidates.

Now that you have four candidates, find the one with the lowest surface area.

This is an awful lot of work, and is not particularly practical. For very large numbers, doing it this way is far easier than brute force. And you don’t even need the Prime Factor candidate until 238,392.

What’s fascinating about this puzzle, though, is how difficult it is, given how easy the 2D version is. And I can’t even say that this algorithm is always going to be successful; I just know that it works for all numbers with 15 or fewer prime factors less than one million. So I haven’t “proven” anything; from a mathematical perspective, this algorithm is still a conjecture, and is subject to being disproven by a single number, no matter how large.