I believe Mary, Adam, Darin, and John’s methods break on 747. They all give 1-9-83 since the cube root is a little more than 9, but 3-3-83 is more efficient.

And, actually, the script works for all numbers up to 10,000 (change 1001 to 10001 in line 14). So that would satisfy Bossman’s requirements, once you think you have an algorithm you want to exhaustively test.

Kudos, Jonah!

I guess I should do something constructive and suggest an algorithm too.

1. Start with an arbitrary box with the correct volume.

2. You can “improve” a pair of dimensions a and b by replacing them with the two factors of ab closest to sqrt(ab). Do this until you can’t do it any more.

Example with 24:

– Start with 1,1,24.
– We can improve 1 & 24 by replacing them with 4 and 6, so now we have 4,1,6.
– We can improve 1 & 6 by replacing them with 2 and 3, so now we have 4,2,3.
– We can’t make any more improvements.

There are other paths we could take, though: (1,1,24) -> (4,1,6) -> (2,2,6) -> (2,3,4), for example. Do we always end up at the same place? In other words, is there only one “local minimum”?

@Dylan, the x-intercept is the cube root of a, so it’ll also fail on 68 and 747.

Is there a way to do the problem with squares and perimeters?

The path point of view could end up with two different stopping points that aren’t reachable from one another but I’m not sure about whether they’d always correspond to different surface areas yet. I fiddled with a few examples from this partially ordered set point of view (espoused by josh and Jonah) and there looks like there can be multiple terminal points.

I have a naive idea for an algorithm. Go to the point in three space with all three coordinates equal to the cube root of N. Create a sphere (with growing radius) centered at that point. Identify all lattice points within the sphere and check to see if their product is N. Symmetry probably even allows us to only check some of the points, or at least we learn as we go and don’t recheck. The upside: we don’t need to know any factors at the outset. The downside: this algorithm is terrible if N is prime. The terrible side: a quick google search says that a count of lattice points in a sphere is only known asymptotically.

I busted my algorithm, it doesn’t work for 20.

Jonah did not actually break the algorithm if we include the step mentioned by Dan himself: If there are only three prime factors, nothing further needs to be done.

68 and 747 each have three prime factors.

Here is my revised algorithm for finding the optimum dimensions a*b*c for a box of volume V:

1. If V/4 is a prime number, the dimensions are 2*2*(that prime number).

Otherwise:
2. Find the cube root of V.
3. Find the factor of V closest to the cube root of V. This is dimension a.
4. Find the factor of V/a closest to the square root of V/a. This is dimension b.
5. V/(a*b) = c

If we’re limiting ourselves to 2500 candies, a table to look it up would be quite efficient. A binary search of the table for the number of candies would be very reasonable, even manually. An interesting question would be packaging – how would you orient it and why when applying logos/labels? Where would they open the packaging from? Would a smaller side be better than pure minimization of surface area? Think cereal boxes.

I think the key to this problem isn’t so much finding dimensions that come closest to the cube root, but simply finding dimensions where the difference between the longest and shortest dimensions is minimized.

This probably doesn’t work, but here would be my algorithm:

1) If the number prime factorizes into 3 or fewer primes, you’re done.
2) If the number is a cube, you’re done. (use the cube-root dimensions)
3) Otherwise, use the same algorithm as the ‘early suggestion’ noted in the original post.

I’ve been working on the assumption that the minimum packaging has the smallest diagonal (it seems correct, but I’m not quiet convinced of the rigour of my proof). If so, then we just need to find some integer coordinates on a curved surface.

RE: take the cube root and round down…

Perhaps 108 is a good test case.

If you begin by looking for factors less than or equal to its cube root, then you will suspect 108 should use a triplet containing 4; but 108 seems to be optimized with [3, 6, 6].

Daniel, that doesn’t quite work for 616 = 11*7*2*2*2. You really want to put the 2s in the same bin.

Perhaps rather than following a set order, you could put the next prime number in whichever bin is the smallest.

@Daniel:

How does your method work with 504?

504’s prime factorization:
7, 3, 3, 2, 2, 2

In the first three bins:
7, 3, 3

Putting in the 2s (as I understand) gives:
14, 6, 6

Surface area: 2(14*6 + 14*6 + 6*6) = 408

But 504 could have used:
7, 8, 9

Surface area: 2(7*8 + 7*9 + 8*9) = 382

(I’m sorry if I have misunderstood.)

I have a sort of solution, but the most important thing is that the problem can be simplified. If the volume number has a prime factor p of multiplicity 3 or more, then the volume number can be divided by p cubed. Only need to multiply each side by p at the end for the solution to the original volume.

Oh dear, it’s not true : 120 gives 4,5,6

So, here’s my effort:
(dots used for separation)
Three columns, to hold the factors of each of the edges.
Column one starts with the factors of the volume number, in order, cols 2 and 3 get a 1 each. The bottom row has the products
Take 120 as the example.
factors are 1 2 2 2 3 5, so
1……1…..1
2
2
2
3
5
———–
120..1…..1

The rule is: From the col with highest product take the last factor (5) and swap it with the highest factor less than it, in the column with lowest product. If this dives a column with product even higher then move up to the next highest factor.
So 5 swaps with one of the 1’s (still need a 1 there(!)
1……1…..1
2……5…..1
2
2
3
(5 not here any longer)
———–
24….5…..1
Repeat, this time it’s the 3, swap with the other 1
1……1…..1
2……5…..3
2
2
(3 not here any longer)
———–
24….5…..3
Repeat, this time it’s a 2, swap with the 1 in the product=3 column
1……1…..1
2……5…..2
2………….3
( this 2 not here any longer)
———–
4……5…..6

I have tried this on numerous examples, and it is easily programmable.

Wait, no, I made a mistake in copying your algorithm. It actually breaks for 54432 (7*6^5).

You end up with 27-32-63, when 27-42-48 is a more optimal solution. The problem arises because all of the 2’s are caught in the middle column, and you need to exchange some 3’s with them to reduce the solution further

Matt:
Modification to my algorithm.
If a swap between largest and smallest total columns has no effect then try a swap between largest and middle total columns.

My algorithm is very similar to others.

1. Identify the smallest factor >= cube root of candies.
2. Identify the next nearest factor.

If you take a step back and think logically (or geometrically) about the problem, then these steps fit. You NEED the first dimension to be greater than or equal to the cube root.

e.g. 24:
1. 3rd root = 2.88. The smallest factor greater is 3.
2. The next factor closest to 2.88 is 2

e.g. 54432
1. The smallest factor greater than 37.90 is 42.
2. The next factor closest to 37.90 is 36.

1. Take the cube root of the given number – if it is an integer, stop
2. List the factors of the given number
3. Select the factor closest to the cube root of the number
4. Divide the given number by this number
5. Check to see if result is prime – if not complete the following with the result, if so complete the following with the first factor
6. Take its square root – if it is an integer, stop
7. List its the factors
8. Select the factor closest to the square root (and its multiplier)

Exceptions: Prime numbers as they would be themselves, 1, 1

747 Example//
1. 747^(1/3) = 9.07
2. 1,3,9,83,249,747
3. Selected 9
4. 747/9=83
5. 83 is prime so complete the following with 9 (from #3)
6. 9^(1/2) = 3 STOP
Solution: 8, 3, 3

900 Example//
1. 900^(1/3) = 9.65
2. 1,2,3,4,5,6,9,10,12,15,18,20,25,30,36,45,50,60,75,90,100,150,180,225,300,450,900
3. Selected 10
4. 900/10=90
5. 90 is not prime so complete the following with 90
6. 90^(1/2) is 9.48
7. 1,2,3,5,6,9,10,15,18,30,45,90
8. Selected 9 and its multiplier 10
Solution: 10, 9, 10

24 Example//
1. 24^(1/3) = 2.88
2. 1,2,3,4,6,8,12,24
3. Selected 3
4. 24/3 = 8
5. 8 is not prime so complete the following with 8
6. 8^(1/2) is 2.82
7. 1,2,4,8
8. Selected 2 and its multiplier 4
Solution: 3,2,4

Really, you don’t have to list out all the factors, only the ones near the resulting cube or square roots.

… and here’s that proof.

Conjecture: Given a, b, and c, all natural numbers 2 or greater, the surface area of a box with dimensions a x b x c will be less than the surface area of a box with dimensions ab x c x 1.

Proof: The first box will have a surface area of 2(ab + bc + ac). The second box will have a surface area of 2(abc + c + ab).

By the conjecture, 2(ab + bc + ac) < 2(abc + c + ab)
Implied: ab + bc + ac < abc + c + ab
Implied: bc + ac < abc + c
Implied: c(b + a) < c(ab + 1)
Since c is positive, implied: b + a < ab + 1
Since ab < ab + 1, b + a < ab + 1 if a + b <= ab
If a and b are both 2 or greater, than a + b <= ab. Therefore, a + b < ab + 1. QED.

So, if a given number has three or more prime factors, our algorithm can contain the step of rejecting any solution with a dimension of 1.

If a given number has exactly one prime factor, there is only one possible solution (p x 1 x 1 and the two symmetries). Here is a proof that if a given number has exactly two prime factors, p x q x 1 is superior to pq x 1 x 1:

Conjecture: 2(pq + p + q) < 2(pq + pq + 1)
Then: pq + p + q < pq + pq + 1
Then: p + q < pq + 1
The rest of the proof is as above.

Obviously, a rectangular prism with a volume of 1 and integer sides can only have one solution.

So all of the above numbers work on the process I outlined on thread 75.

Roxanne, how about 738? Your process gives 9 x 2 x 41, but 3 x 6 x 41 is better.

I did not take the stated problem to imply that we must use each candy space. By wasting candy space, we optimize what the problem does state: efficient algorithm to determine the package that uses the least materials. Assuming there are no additional details (weight limit before the candy collapses on itself), the package that uses the least materials is a square one. We can achieve this by:

1. Getting the cube root of our candy quantity
2. Rounding the cube root value up to the nearest whole number
3. Use this value for each of our cube sides

I have created a Python script which allows you to check any number from 1 to 1,000,000 (if you want more than that, you can modify the script by adding more primes). This way, you can check your algorithm against whatever numbers you please. :D

https://trinket.io/python/cd39920471

Here is the script adapted to list all the values in a given range that have more than three prime factors, and what the ideal parameters are:

https://trinket.io/python/d0d012de06

Right now, it’s set for 1 – 2500, but you can change that by modifying line 74. However, even doing 2500 tends to lag up the website, so I don’t recommend going too crazy.

These are for brute force testing. The way I tend to approach problems like these is to do the programming/brute force first to see if I can see a pattern, and then build a generalization.

Sweet piece of code Paul!

Roxanne –

Try 1332

The cube root is 11.00275

The factor closest to that is 12

1332 = 12 x 111

The square root of 111 is 10.53565

The factor closest to that is 3

111 = 3 x 37

Your method yields 1332 = 3 x 12 x 37

But the answer should be 1332 = 6 x 6 x 37

********

As his been pointed out already, algorithms that rely on finding the number which is closest to the cube root of the volume are doomed to fail.

If the volume is (p^2)q and q>p^4, then the factor closest to the cube root will lead you to choose p^2 x q when you should instead use p x p x q

Here are some counterexamples which any cube root algorithm needs to overcome:
68 = 2 x 2 x 17
76 = 2 x 2 x 19
592 = 4 x 4 x 37
656 = 4 x 4 x 41
747 = 3 x 3 x 83
801 = 3 x 3 x 89
828 = 6 x 6 x 23
1044 = 6 x 6 x 29

@Robert

That is why I added an addendum (post #81). When I use the addendum, it works:

F1=12
F2=3
F3=37

1. 12*3=36
2. sqrt(36)=6 stop;
Solution 6,6,37

Sadler, how do you choose which factor to use in step 1? Why 61 rather than 12?

Notation: Volume = V, Area = A,
Length = x, Width = y, Height = z

1. Check if V is a prime number, if so the optimal solution is:
P=(x=1, y=1, z=V)
=(x=1, y=v, z=1)
=(x=V, y=1, z=1)
A=1*1+1*V+1*V=2*V+1
This is always true, because z = V/(xy) needs to be an integer. But V is only divisible by a prime or by 1, the result follows.

2. If V is not a prime number, the following algorithm ensures the optimal solution:

We first approximate the problem as if the variables are continuous. Using Lagrange we find the optimal solution:
x = V^(1/3)
y = V^(1/3)
z = V^(1/3)

We now continue the problem by acknowledging that the variables are restricted to be integers only.

We have the restriction z=V/(x*y) which is a curve in three dimensions. Our original solution is a point on this curve z(x,y) for which the area of the rectangle given the volume is minimized.

The next step is to build a circle with radius epsilon with the optimum centerd in this circle. All the integer pairs (x,y) within this circle are “candidates” for the optimum.
Given an integer pair (x,y) that lies within the circle we calculate the height z=V/(x*y).
We can check if z is an integer and only keep the triplets(x,y,z) for which z is an integer. This results in a set bounded above by (2*epsilon+1)^2 triplets, but usually the number of triplets is very small.
We can further reduce the number of triplets, by sorting the vector of triplets by size and only keeping the unique ones.
For example (1,5,3) = (1,3,5)..
Using the set of triplets we can calculate the area of the resulting rectangle. Now choose the triplet with the smallest area. This triplet is the optimum.

Important:
Now the question is, what should epsilon be in order for this to work?

Well I tested this algorithm for a square (not a circle) and I let the epsilon continue to grow until the algorithm gave the correct answer given a volume V. I tested this for V=1 till V=2000 and I stored all the epsilon in a vector.

It appears that the epsilon in the case of a square is bounded by (V^(1.15/2)-1)/2. Note however that most of the time a very small epsilon is sufficient! This algorithm is very efficient and i suspect that the algorithm in the case of a circle is even more efficient.

The number of permutations of a brute force calculation are in the order of V^2.
The number of permutations of this algorithm has an upperbound in the order of V^1.15.

Cheers, Sonny

This appears to work. Somebody please tell me if it’s breakable.

1. Create all positive integer triples (a, b, c) such that a*b*c is equal to the target number and a <= b <= c.
2. Pick out the triple(s) where a is highest.
3. If there are multiple such triples, pick out the triple where b is highest.

Done.

My Python script says it works for all numbers from 1-2500.

Incidentally, if my steps work, step 1 can be greatly streamlined. For instance, for 720, the factors are (2, 2, 2, 2, 3, 3, 5). We know that the three members of the triple must all be at least 3, so we can ignore the 2s. We can note that each 3 is going to be multiplied by 2 or all the 2s have to be multiplied together, in which case the lowest possible value in the triple will be 5. That reduces a daunting list down to only eight possibilities. So we don’t *really* have to list all the triples.

Rather:
1. Create a list of all the prime factors.
2. Multiply them together until a is the highest it can be while still being no more than b or c.
3. Multiply the remaining factors together until b is maximal but no more than c.

Still a bit of plug-and-chug in some cases, but less than the “figure out the surface area of every combo” from the rejected cases in the original post.

@ Jonah:
Sorry this is not true.
I checked the results, with V = 1 till 1000 with x <= y <= z.
and x <= sqrt(V) is correct), but y <= sqrt(V) is not true!
In fact when we do a brute force calculation we have X * Y combinations (X = 1 till V, Y = 1 till V). And of course there are symmetric solutions. Therefore we would only have to check the upper or lower triangle of the matrix of pairs (x,y). If so the number of unique pairs is (X*Y-#diagonal elements)/2 + #diagonal elements/2 which is approximately X*Y/2. Therefore the order of a brute force calculation is approximately X^2. (don't mind the constant)

@ Jonah
You’re right I made a mistake by looking at y <= V^(1/3) instead of V^(1/2). My bad, sorry for the mistake.

For a more formal algorithm than what I said before, I have pieces of it:

1. List all the prime factors.
2. Seed three columns with the largest, the smallest, and the one closest to the mean of the factors.
3. … fill in the rest, but how? …

720:
1. (2, 2, 2, 2, 3, 3, 5)
2. (2, 3, 5), (2, 2, 3, 3)
3. …?

1000:
1. (2, 2, 2, 5, 5, 5)
2. (2, 2*5, 5), (2, 2)
3. …?

I also wonder if we might have to have a split strategy: Use the cube root if the max(p) – min(p) is below a certain threshold, and use the “column seed-and-fill” strategy if there are outliers.

@Paul

The cube root strategy laid out in post #93 still holds with 2400

1. 2400^(1/3)= 13.38
2. …10, 12, 15, 16…
3. Select 12
4. 2400/12 = 200
5. 200 is not prime, complete the rest with 200
6. 200^(1/2) = 14.14
7. …8,10,20,25…
8. Looking at 12,10,20
Now to test if optimal
[F1 &F2]
1. 12*10 = 120
2. 120^(1/2)=10.9
3. …8,10,12,15…
4. Select 10 and 12
5. The difference are the same, as they are the same numbers
[F1 & F3]
1. 12*20 = 240
2. 240^(1/2)= 15.49
3. …12,15,16,20…
4. Select 15 and 16
5. |15-16|=1 < |12-10|, use 15 and 16
Final answer is 12,15,16

@Paul

I mistyped, it is indeed 10,15,16

As @ initial was
F1=12
F2=10
F3=20

After the check it became
F1=15
F2=10
F3=16

Am I right in assuming that if we have one correct dimension that the rest is trivial?

We merely arrange the remaining factors so as to give as close to a square as possible. That’s what I get if I differentiate for minimum surface area of a volume with one known dimension and a known volume.

Are any of these algorithms being exclusively broken when the factors of n contains a perfect square?

Seems like the majority of counter examples being provided include a repeated factor.

If the number of cubes has a factorization that includes any perfect squares, and you use the square root of the largest perfect square factor as the first two factors, this helps in several cases, but would return 6x6x20 for 720 instead of the superior 8x9x10. Needs some restrictions…

And of course I meant, “Let A be the volume….”

Time to go do something else for a while.

Which broken algorithm is best so far? An algorithm that fails for ‘720’ but works for 95% of really composite numbers less than 720 might be better than one that works for ‘720’ but only works for 80% of really composite numbers less than 720.

Um, is the answer always the smallest sum of possible solutions for non-huge numbers?

That is a close approximation to the nearest solution to a true cube, hence smallest surface area.

——————————————————

Factorise your number.

Take the cube root of the number.

Go up and down from there until you find the nearest two integers that can be made from available factors.

Divide the starting number by those two integers, and square root those number.

From those two squares, find the nearest two integers up and down that can be built from available factors.

The third dimension is whatever factors left multiplied.

We now have four potential solutions.

It will be the one with the lowest sum.

In practice once we get to clearly higher sums we can stop, so we don’t have to find all four solutions.

We have to check manually for ties. It will clearly stop working for very large numbers, although the error will be tiny.

I believe that the guess-then-correct methods (e.g. #35 and #93) still haven’t been broken. They might work for everything.

But, computationally, I’m having a hard time preferring them over a brute force algorithm. Paul’s observation in #96 seems correct (I haven’t seen a proof yet, but it’s a corollary to #35 working), and that leads us to this solution:

for x from cuberoot(V) to 1:
for y from sqrt(V) to x:
if V/(xy) is an integer, return [x,y,V/(xy)]

This runs in O(V^(5/6)) time. You could argue that it’s a brute force approach (we’re really looping through all reasonable triples until we find the first one that works), but it’s faster than most of the other procedures we’ve seen. I can’t really complain about a 3-line algorithm that runs in sublinear time.

That’s the best problem hook ever: “they couldn’t solve this problem, wanna try it?” I couldn’t resist. But I also want to know what the best package dimensions are. I have another https://repl.it/BLGc/13 (brute force algorithm) to add to the mix. 7 seconds for the first 1000 packages, 20 seconds to get the next thousand, and 30 more seconds to get the next thousand.

The difficulty is not the raw-size of the number but the number of prime factors. And I handle that difficulty with no skill whatsoever.

Anyway, thanks for posting this problem, it was fun to work on! Impressed by everyone’s comments.

I made a Geogebra interactive for V=24. Not sure it suggests an approach, but it was fun to make. Basically it shows half of the surface of the box and uses sliders to change the base and height.

https://tube.geogebra.org/material/simple/id/1699825

Confirmed, #93 is broken with 5850! :P

@Paul

It seems like you are able to find the triples for a given number easily (although I am unsure how – brute force?).

If it is easy, then we just need to find the set that minimizes the differences among the factors, i.e., min[|F1-F2|+|F1-F3|+|F2-F3|].

I believe the best algorithm possible is the following:

(1) Set up a list of all divisors of n (the number of cubes). There are fast algorithms for this using a modified sieve.

(2) For all elements x of the list, determine the y=n/x. You have the divisors of y already in your list. Select the two that are closest to the square root of y (or twice the square root if it happens to be integer).

(3) Compare all triplets you get this way.

(did this comment get lost?) Wrote some quick (and inefficient) code to check Roxanne’s method. Here’s where it breaks for numbers <= 10,000.
(code: https://dl.dropboxusercontent.com/u/3646828/candies_check.py )
Roxanne's method breaks at: 360. Ideal is [6, 6, 10] and Roxanne is [5, 8, 9]
Roxanne's method breaks at: 600. Ideal is [6, 10, 10] and Roxanne is [5, 10, 12]
Roxanne's method breaks at: 1764. Ideal is [9, 14, 14] and Roxanne is [7, 14, 18]
Roxanne's method breaks at: 2100. Ideal is [10, 14, 15] and Roxanne is [7, 15, 20]
Roxanne's method breaks at: 3696. Ideal is [12, 14, 22] and Roxanne is [11, 16, 21]
Roxanne's method breaks at: 4752. Ideal is [12, 18, 22] and Roxanne is [11, 18, 24]
Roxanne's method breaks at: 4950. Ideal is [15, 15, 22] and Roxanne is [11, 18, 25]
Roxanne's method breaks at: 5040. Ideal is [15, 16, 21] and Roxanne is [14, 18, 20]
Roxanne's method breaks at: 5808. Ideal is [12, 22, 22] and Roxanne is [11, 22, 24]
Roxanne's method breaks at: 5850. Ideal is [15, 15, 26] and Roxanne is [13, 18, 25]
Roxanne's method breaks at: 6240. Ideal is [15, 16, 26] and Roxanne is [13, 20, 24]
Roxanne's method breaks at: 6300. Ideal is [15, 20, 21] and Roxanne is [14, 18, 25]
Roxanne's method breaks at: 6930. Ideal is [15, 21, 22] and Roxanne is [11, 21, 30]
Roxanne's method breaks at: 7020. Ideal is [15, 18, 26] and Roxanne is [13, 20, 27]
Roxanne's method breaks at: 7056. Ideal is [16, 21, 21] and Roxanne is [14, 21, 24]
Roxanne's method breaks at: 7260. Ideal is [15, 22, 22] and Roxanne is [11, 22, 30]
Roxanne's method breaks at: 7700. Ideal is [14, 22, 25] and Roxanne is [11, 25, 28]
Roxanne's method breaks at: 8100. Ideal is [18, 18, 25] and Roxanne is [15, 20, 27]
Roxanne's method breaks at: 8580. Ideal is [15, 22, 26] and Roxanne is [13, 22, 30]
Roxanne's method breaks at: 9100. Ideal is [14, 25, 26] and Roxanne is [13, 25, 28]

Ok, last thing for a while:
Here’s a plot of the number of candies vs:
smallest factor: https://dl.dropboxusercontent.com/u/3646828/smallest.png
medium factor: https://dl.dropboxusercontent.com/u/3646828/medium.png
largest factor: https://dl.dropboxusercontent.com/u/3646828/largest.png

Wow, great discoveries everyone!

I wrote some Sage code and found that Paul’s conjecture (#96, that the surface area is minimized when the shortest dimension is maximized) fails for the first time at 3168: 11 x 16 x 18 is better than 12 x 12 x 22.

So we’re back to brute force. Which is still not bad! It also runs in sublinear time. You just have to actually record the results, rather than simply picking the largest x.

@Jonah

I think your method is broken already by 360, i.e., well before 5850.

As D. Anderson writes:
“360. Ideal is [6, 6, 10] and Roxanne is [5, 8, 9]”

Perhaps I have misunderstood, but it seems that the square root replacement method also gets stuck at [5, 8, 9] and cannot arrive at the ideal of [6, 6, 10].

Also, from your earlier post [#95]:
“Roxanne: That seems pretty reasonable to me, and I think it’s a faster version of my algorithm in post #35.”

As I understand, your algorithm and Roxanne’s are different.

Again, D. Anderson writes:
“600. Ideal is [6, 10, 10] and Roxanne is [5, 10, 12]”

But the sqrt replacement method will not stop on [5, 10, 12]; it will check sqrt(5*12) and replace {5, 12} with {6, 10} for the ideal [6, 10, 10] as desired.

Sara, that works for some of them, but not all. Someone else mentioned 2 earlier, but in general anything that’s a little bit more than a cube is going to run into the same problem.

Which raises the interesting question: if we’re allowed to pack empty spaces, how should we determine how many empty spaces we should pack? Is there a better way than just checking each number between the number of candies and the next cube?

@Jonah

I did not read the details of Roxanne’s algorithm, but I did spend a bit of time considering if yours is optimal. Of course, the answer is no, since there are counterexamples.

But it became clear to me that if an ideal is [a,b,c] and yours terminates on [x,y,z] then those two triples must be totally distinct.

For, WLOG, suppose a=x; since the volume is fixed, we then have bc=yz.

To minimize SA is equiv. to minimize SA/2, i.e.,:
xy+xz+yz = x(y+z) + yz;

If bc=yz and [a,b,c] << [x,y,z], then b+c<y+z.

And so {y, z} would be replaced by {b, c} in your method.

Anyway, I've abused notation slightly, but this is how I recognized the 600 pairs could not occur in your method: [5,10,12] and [6,10,10] share a factor of 10; impossible for your method.

As another example, D. Anderson writes:
"4752. Ideal is [12, 18, 22] and Roxanne is [11, 18, 24]"

Because there is a shared 18 here, I am sure that your method could not have had this issue.

We can still check by hand:
sqrt(11*24) = 16.248…; so replace {11, 24} with {12, 22} for the ideal.

Even for the biggest example:
"9100. Ideal is [14, 25, 26] and Roxanne is [13, 25, 28]"

The shared 25 indicates that your method would not have terminated at [13, 25, 28].

—

Actually, I think the problem here is NP-hard (as alluded to by M. Strauss in #24) which explains why it hasn't been "solved" (in some sense). [Doable for a fixed bound, though: Already a couple of answers give ideas that work beyond 2,500 candies.] Even still, the challenge has the nice feature of allowing bounds to be proposed, broken, and improved — repeatedly.

Here’s a preliminary comparison of some algorithms for volumes from 1 to 100000.

Name errors avg. inc. error examples
Snowball 12758 17.3% 108, 144, 180, 192, 216 . . .
56 Daniel 15240 40.3% 160, 200, 224, 240, 280 . . .
57 Jonah 1924 3.3% 432, 504, 576, 648, 720 . . .
5 Alex 37608 81.4% 28, 44, 52, 68, 76 . . .
3 Addison 33038 67.7% 28, 44, 52, 68, 76 . . .
81 Roxanne 187 4.2% 360, 600, 1764, 2100, 3696 . . .

The Snowball algorithm in the original post fares well in the pack. Out of all boxes with volumes 1 thru 100000, 58526 are products of at most 3 primes, not necessarily distinct. Of the rest, 12758 of them aren’t formed most efficiently with this method, with an average of 17.3% more packaging required by each not-optimal box. A box with volume 108 for example has 4% more packaging with (L, W, H)=(3, 4, 9) than the optimal box (3, 6, 6).

The method described in posts like 5 Alex, 12 Mary, 32 Dylan, and 54 Patty picks the first dimension closest to the cube root of volume then selects the next dimension closest to the square root of what’s left. The average percent increase in packaging for an error is 81.4%, especially boxes (L, W, H)=(1, 77, 1109) or (1, 77, 1297) which have 332% more packaging than optimal boxes.

3 Addison’s method is a slight improvement to both the number and severity of errors, adding Price is Right bidding rules. About 36% of the errors by Alex and Addison’s algorithms occur when volume is a product of 3 primes, not necessarily distinct and not necessarily repeated either.

The problem with the cube-root approach is the first choice. So far, the conjecture in 110 Chester and 128 Rene holds, that the method for second choice here would be fine if the first choice was better, but it’s not much of a computational shortcut. In a more ‘rule of thumb’ way, this first choice is taken into account by 129 Dan Anderson’s implementation of Roxanne’s posts 81 and 93; this method adds an additional consideration.

56 Daniel’s algorithm distributes factors in decreasing order: the largest 3 go to H, W, L then the rest go in the opposite order, L, W, H. The improvement suggested by 57 Jonah to give the next factor to the smallest dimension makes a big difference, fixing 87% and improving 11% of the errors by 56 Daniel.

If I’m reading the comments correctly, my Three Candidate algorithm is the only one that works for Dan’s threshold of 2500, failing around 3000. That’s something. :)

134 Jonah: My modification now works at least up to 50000. It still involves mathematics to check candidates, but at least a + b + c is faster to calculate than ab + ac + bc. Also, the sum alone is usually sufficient to find the ideal. Here are the cases where it isn’t (in each match, the two triples have the same sum, while the second one is the ideal).

Match at 360[5, 8, 9][6, 6, 10]
Match at 1008[7, 12, 12][8, 9, 14]
Match at 3696[11, 16, 21][12, 14, 22]
Match at 3960[11, 18, 20][12, 15, 22]
Match at 5040[14, 18, 20][15, 16, 21]
Match at 5850[13, 18, 25][15, 15, 26]
Match at 6240[13, 20, 24][15, 16, 26]
Match at 6552[13, 21, 24][14, 18, 26]
Match at 7425[11, 25, 27][15, 15, 33]
Match at 10800[18, 24, 25][20, 20, 27]
Match at 12285[13, 27, 35][15, 21, 39]
Match at 13464[17, 24, 33][18, 22, 34]
Match at 13600[17, 25, 32][20, 20, 34]
Match at 14280[17, 28, 30][20, 21, 34]
Match at 14688[17, 27, 32][18, 24, 34]
Match at 15120[20, 27, 28][21, 24, 30]
Match at 15300[17, 30, 30][18, 25, 34]
Match at 19008[22, 27, 32][24, 24, 33]
Match at 19152[19, 28, 36][21, 24, 38]
Match at 19800[22, 30, 30][24, 25, 33]
Match at 19950[19, 30, 35][21, 25, 38]
Match at 20064[19, 32, 33][22, 24, 38]
Match at 20520[19, 30, 36][20, 27, 38]
Match at 20790[21, 30, 33][22, 27, 35]
Match at 21280[19, 32, 35][20, 28, 38]
Match at 21600[24, 30, 30][25, 27, 32]
Match at 22491[17, 27, 49][21, 21, 51]
Match at 26775[17, 35, 45][21, 25, 51]
Match at 30240[27, 32, 35][28, 30, 36]
Match at 30800[22, 35, 40][25, 28, 44]
Match at 31050[23, 30, 45][25, 27, 46]
Match at 31200[25, 32, 39][26, 30, 40]
Match at 32760[26, 35, 36][28, 30, 39]
Match at 33696[26, 36, 36][27, 32, 39]
Match at 34398[21, 39, 42][26, 27, 49]
Match at 34776[23, 36, 42][27, 28, 46]
Match at 35880[23, 39, 40][26, 30, 46]
Match at 36432[23, 36, 44][24, 33, 46]
Match at 36800[23, 40, 40][25, 32, 46]
Match at 38475[19, 45, 45][25, 27, 57]
Match at 41895[19, 45, 49][21, 35, 57]
Match at 45000[25, 40, 45][30, 30, 50]

Paul! I regret to inform you that 50000 cases is not enough. Somehow. This problem is ridiculous.

Let V = 118755. Your method yields [29,63,65]. The correct answer is [35,39,87], even though the value sum is higher.

The next counterexamples are 139860, 188928, 191880, and 192372.

These are all also counterexamples to Matt’s observation (#53) that you want to minimize the length of the diagonal. Since (a+b+c)^2 = [Surface area] + [length of diagonal]^2, any box which minimizes the second and third must also minimize the first.

Way to go Jonah.
It looks like my Four Candidate method will survive 118755.
The two factors smaller than the third root of 118755 (49.15) are 45 and 39.
Although I need to retract the a+b+c test. I would like to replace that with “Now calculate the surface area of these eligible triples and find the smallest surface area.”

Okay, my algorithm finds the ideal solution, but it doesn’t pick it out from the candidates. The problem is in the last set; the sum doesn’t work. So we’ll have to compare ab + bc + ac for the four candidates. This is true for all the cases you listed.

What value should I try? 118755
More than three prime factors.
First Candidate: [29, 63, 65] sum: 157
Second Candidate: [29, 45, 91] sum: 165
Third Candidate: [35, 39, 87] sum: 161
Fourth Candidate: [29, 63, 65] sum: 157
[35, 39, 87]
I’m done.

What value should I try? 139860
More than three prime factors.
First Candidate: [37, 60, 63] sum: 160
Second Candidate: [42, 45, 74] sum: 161
Third Candidate: [42, 45, 74] sum: 161
Fourth Candidate: [37, 54, 70] sum: 161
[42, 45, 74]
I’m done.

What value should I try?188928
More than three prime factors.
First Candidate: [41, 64, 72] sum: 177
Second Candidate: [48, 48, 82] sum: 178
Third Candidate: [1, 47, 4019] sum: 4067
Fourth Candidate: [41, 64, 72] sum: 177
[48, 48, 82]
I’m done.

What value should I try?191880
More than three prime factors.
First Candidate: [41, 65, 72] sum: 178
Second Candidate: [45, 52, 82] sum: 179
Third Candidate: [45, 52, 82] sum: 179
Fourth Candidate: [41, 60, 78] sum: 179
[45, 52, 82]
I’m done.

What value should I try?192372
More than three prime factors.
First Candidate: [41, 68, 69] sum: 178
Second Candidate: [46, 51, 82] sum: 179
Third Candidate: [46, 51, 82] sum: 179
Fourth Candidate: [41, 68, 69] sum: 178
[46, 51, 82]
I’m done.

Alas, my new algorithm fails at 141,284.

What value should I try? 141284
More than three prime factors.
First Candidate: [19, 52, 143] sum: 214
Second Candidate: [19, 52, 143] sum: 214
Third Candidate: [19, 44, 169] sum: 232
Fourth Candidate: [13, 76, 143] sum: 232
[26, 38, 143]
I’m done.

Other failures are 143748, 165308, and 184756. (Also, the Python code I’m using can’t handle more than 15 prime factors, so 65536, 98304, 131072, and so on have to be checked by hand… which isn’t a big deal, just annoying. :) )

Still, only four failures less than 200,000 is pretty darn good.

Paul, one quick note: you don’t actually need Step 1 in your algorithm.

If Candidate 2 is [1,1,pqr], then Candidate 4 will be [p,q,r]. If Candidate 2 is [1,pq,r] or [1,r,pq], then Candidate 3 will be [p,q,r].

I have been finding contour maps like this useful to think about the problem:

https://dl.dropboxusercontent.com/u/38989444/cont90.png

It’s a plot of

z = 2*x*y + 2*V/x + 2*V/y

z is the area, V is the volume (in this case 90) and x and y are two of the sizes of the box. Instead of plotting the entire surface, contours at each 10 surface area units are plotted. The smallest contour is in the well and the others going outward are higher values of area.

It suggests to me:

1) Another way to look at the questions is which contour is going to be lowest with integer values for x and y.

2) looking at xy = V^(2/3) is a productive direction to look, but certainly not a guarantee to find a minimum.

I’ve seen problems like the original come up on SBAC as applying to cereal boxes. It seems to me that the premise of using the least amount of surface area for the greatest amount of volume is a flawed one – there are other considerations that can trump this kind of analysis. I suspect this is true for most consumer goods packaging. Cubes (or near cubes) are not the best shapes for kitchen shelves. I can’t recall seeing a cereal box anything near such a shape. It wouldn’t be practical.

Although these problems (and especially the variant suggested by Dan in this post) can be really interesting and fun, they are often not true real world situations, but rather math concepts dressed up with words that make them seem like they are real world.

@Jeff DeMarco: Indeed, in the real world, packages are often designed to rely on people not understanding volume. I noticed that some liquids, such as dish soap, come in vaguely conical bottles. When I ask my students, they say that cones have half the volume of cylinders (same height and radius), which of course they don’t.

B. Whichever package had the most closely equal length sides

My second attempt is corrupted as well.

Note that one is trying to minimize the spread (range) between a and c.