## The Math Problem That 1,000 Math Teachers Couldn’t Solve

I spent a year working on Dandy Candies with around 1,000 educators.

In my workshops, once I stop learning through a particular problem, either learning about mathematics or mathematics education, I move on to a new problem. In my year with Dandy Candies, there was one question that none of us solved, even in a crowd that included mathematics professors and Presidential teaching awardees. So now I’ll put that question to you.

Here is the setup.

At the start of the task, I ask teachers to eyeball the following four packages. I ask them to decide which package uses the least packaging.

With the problem in this state, without dimensions or other information, lots of questions are available to us that numbers and dimensions will eventually foreclose. Teachers estimate and predict. They wonder how many unit cubes are contained in the packages. They wonder about descriptors like “least” and “packaging.”

After those questions have their moment, I tell the teachers there are 24 unit cubes inside each package. Eventually, teachers calculate that package B has the least surface area, with dimensions 6 x 2 x 2.

We then extend the problem. Is there an even better way to package 24 unit cubes in a rectangular solid than the four I have selected? It turns out there is: 4 x 3 x 2. When pressed to justify why this package is best and none better will be found, many math teachers claim that this package is the “closest to a cube” we can form given integer factors of 24.

The Problem We Never Solved

We then generalize the problem further to any number of candies. I tell them that as the CEO of Dandy Candies (DANdy Candies … get it?!) I want to take any number of candies â€“ 15, 19, 100, 120, 1,000,000, whatever â€“Â and use an easy, efficient algorithm to determine the package that uses the least materials.

Two solutions we reject fairly quickly:

2. Write down all the sets of dimensions that multiply to that number.
3. Calculate the packaging for that set of dimensions.
4. Write down the set that uses the least packaging.

And:

2. Have a computer do the previous work.

I need a rule of thumb. A series of steps that are intuitive and quick and that reveal the best package. And we never found one.

Here was an early suggestion.

2. Write down all of its prime factors from least to greatest.
3. If there are three or fewer prime factors, your dimensions are pretty easy to figure out.
4. If there are four or more factors, replace the two smallest factors with their product.
5. Repeat step four until you have just three factors.

This returned 4 x 3 x 2 for 24 unit candies, which is correct. It returned 4 x 5 x 5 for 100 unit candies, which is also correct. For 1,000 unit candies, though, 10 x 10 x 10 is clearly the most cube-like, but this algorithm returned 5 x 8 x 25.

One might think this was pretty dispiriting for workshop attendees. In point of fact it connected all of these attendees to each other across time and location and it connected them to the mathematical practice of “constructing viable arguments” (as the CCSS calls it) and “hypothesis wrecking” (as David Cox calls it).

These teachers would test their algorithms using known information (like 24, 100, and 1,000 above) and once they felt confident, they’d submit their algorithm to the group for critique. The group would critique the algorithm, as would I, and invariably, one algorithm would resist all of our criticism.

That group would name their algorithm (eg. “The Snowball Method” above, soon replaced by “The Rainbow Method”) and I’d take down the email address of one of the group’s members. Then I’d ask the attendees in every other workshop to critique that algorithm.

Once someone successfully critiqued the algorithm â€“ and every single algorithm has been successfully critiqued â€“ we emailed the author and alerted her. Subject line: RIP Your Algorithm.

So now I invite the readers of this blog to do what I and all the teachers I met last year couldn’t do. Write an algorithm and show us how it would work on 24 or another number. Then check out other people’s algorithms and try to wreck them.

Featured Comment

Big ups to Addison for proposing an algorithm and then, several comments later, wrecking it.

2015 Sep 25

We’re all witnessing incredible invention in this thread. To help you test the algorithm you’re about to propose, let me summarize the different counterexamples to different rules found so far.

20 should return 5 x 2 x 2
26 should return 13 x 2 x 1
28 should return 2 x 2 x 7
68 should return 2 x 2 x 17
222 should return 37 x 3 x 2
544 should return 4 x 8 x 17
720 should return 8 x 9 x 10
747 should return 3 x 3 x 83
16,807 should give 49 x 49 x 7
54,432 should return 36 x 36 x 42
74,634 should give 6 x 7 x 1777

I'm Dan and this is my blog. I'm a former high school math teacher and current head of teaching at Desmos. He / him. More here.

1. #### Mary

September 24, 2015 - 8:36 am -

My first thoughts are to take the cube root of the initial number of candies and then find the dimensions with the least collective “distance” to that root. So, the most efficient packaging is the package dimensions that have the least sum of the absolute value of the factors minus the cube root of the number of candies.

• #### Dan Meyer

September 24, 2015 - 8:38 am -

Thanks for the suggestion, Mary. Can you lay out how the algorithm would work for, say, 24?

September 24, 2015 - 8:41 am -

1. Take the cube root of the number of cubes.

2. Round up.

3.Count down from that number until you find a factor of the number of cubes greater than 1. This is your first dimension.

4. If that fails, count up until you find a factor. This is your first dimension.

5. To get the second dimension, repeat steps 3 and 4, but look for factors of the number of cubes divided by the first dimension.

6. The third dimension is obvious.

• #### Dan Meyer

September 24, 2015 - 8:42 am -

Thanks, Addison. Just for clarity, would you work your algorithm out on 24 or another number?

3. #### Alex

September 24, 2015 - 8:43 am -

Okay, I’ll bite.

I haven’t had time to test this (except on x=1 – it worked!), but the most obvious method seems to be:

1. Write down all factors of x
2. Pick the one closest to the cube root – that’s “a”
3. Write down the factors of x/a
4. Pick the one closest to the square root of x/a – that’s “b”
5. c = x/ab

September 24, 2015 - 8:56 am -

Sure. So, for 24, cube root is 2 and change, round to 3. 3 is a factor, so that’s our first dimension. 3 isn’t a factor of 24/3, though, so we move down to 2, which does work, leaving us with 4 for our third dimension.

I suspect that I’m just bad at picking counterexamples, since this feels like it should be breakable.

5. #### Mary

September 24, 2015 - 9:02 am -

For 24:

1. Find factor trios for 24
1x1x24
1x2x12
2x2x6
2x3x4
1x4x6
1x3x8

2. Find the cubed root of 24
2.88

3. Find the abs of the difference of each factor and 2.88
abs(1-2.88) = 1.88
abs(2-2.88) = 0.88
abs(3-2.88) = 0.12
abs(4-2.88) = 1.12
abs(6-2.88) = 3.12
abs(8-2.88) = 5.12
abs(12-2.88) = 9.12
abs(24-2.88) = 21.12

4. Find the sum of these for factor trios
1x1x24
1.88 + 1.88 + 21.12 = 24.88
1x2x12
11.88
2x2x6
4.88
2x3x4
2.12
1x4x6
6.12
1x3x8
7.12

5. Choose the least of these
2.12

So, the 2x3x4 box uses the least amount of packaging

September 24, 2015 - 9:07 am -

Got it. 7^5. This gives 7*7*343, and it ought to give 49*49*7.

Also, Mary, is that really a great improvement on the rejected option of just calculating all the packaging amounts?

7. #### Dan Meyer

September 24, 2015 - 9:14 am -

I agree that Mary’s, while not too time-consuming for 24, will wind up consuming a lot of time for larger numbers. Let’s hold onto it in case it’s the most efficient we can come up with. Let’s also try to wreck it.

8. #### Mary

September 24, 2015 - 9:14 am -

Nope! :) It was just my first thought when I read it. Maybe someone can incorporate the difference to the cube root into a better solution. Good luck! Possibly with your finding of the root if the rounding doesn’t give you an actual factor?

9. #### Jason Dyer

September 24, 2015 - 9:24 am -

If you just want an algorithm that definitely works, you would plot all the factor trios in 3-space and then find the closest point line-distance to the line where x = y = z.

While I doubt this would be most efficient, you probably could use matrix manipulations to tighten it up, but that would be “efficient to do on a computer”, not necessarily “efficient to do by hand”.

10. #### Mary

September 24, 2015 - 9:33 am -

Updating my initial thoughts:

1. Find the factors of the number
2. Find the factor with the least distance to the cube root. This becomes your first factor trio.
3. Divide the number by the first factor
4. Find the factors of this new number
5. Find the factor with the least distance to the square root. This is your second factor in the trio
6. Find the third factor

For 24:
1. 1,2,3,4,6,8,12,24
2. 3
3. 8
4. 1,2,4,8
5. 2
6. 4

So, 3x2x4

Again, still a lot of work but I’m stuck in distance to the cube root thoughts. This is easier to just find the factors though and not the factor trios from the start. Easy for a computer to calculate.

11. #### John Scammell

September 24, 2015 - 9:51 am -

I need a hypothesis to wreck, just so I get one of those “Dear John” emails from Dan.

September 24, 2015 - 9:54 am -

Haven’t checked many cases but my initial thought is:

1) Take the cube root of the number.
2) Round down to the nearest whole number.
3) Check if that number divides your volume.
4a) If it does then it is one of your dimensions, so take your volume and divide it by that dimension.
4b) If it does not, then reduce that number by 1 and continue to check if it divides your volume until you get one that does. When you do, that is one of your dimensions. So take your volume and divide it by that dimension.

5) Now take the square root of your result from 4. Repeat the process of either 4a and 4b until you arrive at a number that divides your result from 4. This will be your 2nd dimension.

6) If you have two dimensions you can find your 3rd.

Ex: 100
The cube root of 100 is 4.6412… so we will first check 4. 4 divides 100 so 4 is one of our dimensions.

We then take 100/4 = 25 and take the square root of 25. Since the square root of 25 is 5, then 5 is our second dimension.

We find our third dimension by doing 100/(5*4) = 5.

13. #### Matt

September 24, 2015 - 10:19 am -

I second Adam’s method. I haven’t broken it yet, though it feels like it might be breakable. I tried Dan’s cases of 24, 100, 1000, and several numbers between 20 and 125.

14. #### James Pearce

September 24, 2015 - 10:25 am -

Perhaps two (or more) algorithms could be used, decided by some boolean logic.

if cube root is an integer k,
– k^3 is most efficient
else
– use ‘early suggestion’ algorithm (that broke down for 1000)
end if

or is this not in the intended spirit!?

15. #### john chapin

September 24, 2015 - 10:44 am -

My approach is similar to Addison’s but I round down
1) Find the largest cube you can make by taking the cube root and rounding down. If the remainder is 0 you are done. This is your first dimension = dim1
2) The second dimension has to be at least 1 greater, so the second dimension is dim2= dim1+1
3) Divide the size by the dim1*dim2 (it will be either dim1 or dim2). Round up. This is your third dimension.

For 24
1) cube root of 24 rounded down is 2.
2) second dimension is 3
3) 24/(3*2) = 4
2X3X4.

For 720
1) cube root of 720 rounded down is 8
2) Second dimension is 9
3) Third dimension is 720/(8*9) = 10
8X9X10

16. #### Mary

September 24, 2015 - 11:10 am -

Building on John’s hypothesis, I revise again:

1. Find the factors of the number
2. Find the factor with the least distance to the cube root. This becomes your first factor trio.
3. The next largest factor is your second trio
4. Find the third factor

For 24:
1. 1,2,3,4,6,8,12,24
2. 3
3. 4
4. 2

17. #### Mary

September 24, 2015 - 11:18 am -

Sorry, last one from me (for now). Calculating all the factors in my previous attempt is unnecessary.

1. Find the cube root of the number
2. Find the largest factor smaller than the cube root – this is the first trio.
3. Find the smallest factor greater than the cube root – this is trio two.
4. Find trio three.

18. #### Dan Meyer

September 24, 2015 - 11:21 am -

@Josh G., no, because my customers will assume that someone on the production line ate some of their candy.

19. #### Darin

September 24, 2015 - 11:27 am -

Others have been using the cube root, but I don’t think I’ve seen this algorithm yet:

1. List the factors of the number, N, that are less than the cube root of N
2. The largest factor less than or equal to the cube root of N is A, your first dimension.
3. The largest factor less than or equal to the square root of (N/A) is your second dimension, B.
4. The final dimension, C, equals N/(A*B)

20. #### Martin Strauss

September 24, 2015 - 11:50 am -

On the wrecking side:

There is no known efficient way to factor, and cryptography protecting trillions of dollars depends on this.

We can pose the problem assuming we are given a prime factorization of the number, N, of candies. In that case, the problem seems similar to the 3-partition problem https://en.wikipedia.org/wiki/3-partition_problem which is NP-hard, so there should not be an efficient algorithm for this, either. (Here, we’d be partitioning the logarithms of the factors.) Still, I don’t have a specific reduction in mind and the logarithms may help somehow.

On the algorithm side (sorry, no proposed algorithm yet):

There are many approximation algorithms for bin-packing https://en.wikipedia.org/wiki/Bin_packing_problem that might apply here, with more work. Here the goal is related to packing the logarithms of the factors into 3 bins, so that the sum in each bin is close to log(N)/3. By contrast, the standard bin-packing problem doesn’t allow any more than the nominal amount in each bin but seeks to optimize the number of extra bins, so more work is needed.

21. #### Paul Hartzer

September 24, 2015 - 1:10 pm -

@Martin Strauss: There is no efficient way to factor numbers with lots of digits, but presumably we’re looking at numbers less than, say, one million. All numbers in that range can be factored fairly efficiently with a list of the first 168 primes. Obviously, it’s a lot easier with a computer.

The examples I see in this item are less than 1000 (except 1000 itself, with is very easy to factor). Those only require testing 11 primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31.

22. #### Dan Meyer

September 24, 2015 - 1:23 pm -

@Paul & Martin, as the CEO of the company, I am willing to accept an efficient, simple algorithm that only works up to, say, 2,500 candies.

• #### Clara

September 25, 2015 - 1:19 am -

Does the box always have to be six-sided? Could we use a quadratic or triangular pyramid to reduce lost space for odd or prime numbers of candy?

23. #### Jonah

September 24, 2015 - 1:29 pm -

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.

24. #### Jonah

September 24, 2015 - 1:41 pm -

Or, for a smaller example, 68.

The problem is numbers that factor into p*p*q, where q is roughly p^4. p-p-q is more efficient than 1-p^2-q, so you don’t want to choose p^2 as a dimension, even though it’s close to the cube root of your number.

25. #### Dan Meyer

September 24, 2015 - 1:49 pm -

@Jonah, breaking four algorithms in one swoop. You’re on the Dy/Dan Lil Wonder Scholar board.

26. #### Paul Hartzer

September 24, 2015 - 1:55 pm -

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.

27. #### Dylan Kane

September 24, 2015 - 2:02 pm -

1. Define the function f(x,a)=x-sqrt(a/x).
2. Plug in the number of dandy candies for a. A sample function in Desmos is here: https://www.desmos.com/calculator/lg8nzv1jnw
3. Round the x-intercept to the nearest integer factor of a, call it m. That is one of your factors.
4. Find the number such that n=a/m, the product of the other two factors.
5. Take the square root of n, round to the nearest integer factor of a, and that is your second factor.
6. Find the third factor.

Does this count as a computer doing work for you? I tested it for a few, not sure if it will work for more.

28. #### josh g.

September 24, 2015 - 2:19 pm -

Would a guess-and-improve algorithm be acceptable, if it can be shown to be efficient and correct? (ie. no local minima getting us stuck somewhere before we get to the true best answer)

29. #### Jonah

September 24, 2015 - 2:26 pm -

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

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:

â€¢ 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”?

30. #### Brian S.

September 24, 2015 - 2:43 pm -

Neat script @Paul. I’ll have to keep thinking of a simple algorithm – my answer would have been a brute force computer generated solution (not allowed).

31. #### Patty

September 24, 2015 - 3:55 pm -

Here are my thoughts so far for finding the optimum dimensions a*b*c for a box of volume V:

1. Find the cube root of V.
2. Find the nearest factor of V greater than or equal to the cube root of V. This is dimension a.
3. Find the nearest factor of V/a less than or equal to the square root of V/a. This is dimension b.
4. V/(a*b) = c

32. #### Tim

September 24, 2015 - 4:00 pm -

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.

33. #### Jonah

September 24, 2015 - 4:25 pm -

Tim: Ooh, what are the examples with multiple terminal solutions? I tried to find one but couldn’t.

I’m afraid the sphere idea fails on 747, since (1,9,83) is closer to the center than (3,3,83).

34. #### Paul Hartzer

September 24, 2015 - 4:53 pm -

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.

35. #### Paul Hartzer

September 24, 2015 - 4:55 pm -

However, if 68 was a problem, so should 544 be (since that’s the result of multiplying all sides by 2), and that does have more than three prime factors.

36. #### Patty

September 24, 2015 - 5:01 pm -

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

37. #### Jonah

September 24, 2015 - 5:07 pm -

Aw, now I gotta wreck Paul’s wreckage: doubling the sides of an optimal box doesn’t necessarily give an optimal box. 1x1x7 is clearly optimal, but 2x2x14 is worse than 2x4x7.

74634 is a four-factor way to wreck all the cube root algorithms, though. The cube root is about 42, but 6x7x1777 is better than 1x42x1777.

38. #### Jeff Morrison

September 24, 2015 - 5:08 pm -

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.

39. #### Mary

September 24, 2015 - 5:12 pm -

Thanks for the redemption Paul.

I think 544 now works in my hypothesis with 4x8x17 (or is this not the most efficient package?). Though I somehow need to add the test for a count of three when prime factorization is computed into my algorithm – something along the line of James’ idea: If count of prime factorization is three, use those numbers, else use “factors above and below the cube root” solution.

40. #### Mark Amasuga

September 24, 2015 - 5:15 pm -

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.

41. #### Mark Amasuga

September 24, 2015 - 5:21 pm -

Nevermind, I broke it on 720 – but I think the minimize-range-of-dimensions goal is still correct.

42. #### Matt

September 24, 2015 - 5:30 pm -

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.

43. #### Patty

September 24, 2015 - 5:42 pm -

Jonah, I had already noticed the problem when 4 was the nearest factor to the cube root and volume/4 is prime, but it’s a more general problem.

Seems to me this algorithm works for cases except when a is a composite number and V/a=a prime number:
1. Find the cube root of V.
2. Find the factor of V closest to the cube root of V. This is dimension a.
3. Find the factor of V/a closest to the square root of V/a. This is dimension b.
4. V/(a*b) = c

So if a is the factor of V closest to the cube root of V and V/a isn’t prime, use this. I’ll have to think more about the “else” part.

44. #### MQ

September 24, 2015 - 6:04 pm -

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].

45. #### Daniel

September 24, 2015 - 6:12 pm -

How about thinking about the dimensions of the box as three holding bins for a set of prime factors each. Start by ordering the prime factors greatest to least. Now put the factors in the bins, starting with the three largest: Bin 1, bin 2 and then bin 3. Now, continue to fill the bins with thr next largest starting with bin 3, then bin 2, then bin 1. Continue in this pattern until all prime factors have been used.
In summary, fill from bin 1 to bin 3 for the three largest factors then from bin 3 to bin 1 forever (or until you run out of factors).

24 works like this: 3, 2, 2
2
So, the dimensions are 3, 2, 4

1000 would be: 5, 5, 5
2,2,2
For: 10,10,10

This works for perfect cubes since they have triplicates of each prime factor. It even seems to worn for numbers like 720:
5, 3, 3
2, 2, 2
2

Or 10,6,12

46. #### Jonah

September 24, 2015 - 6:21 pm -

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.

47. #### Jonah

September 24, 2015 - 6:22 pm -

Aaaaand my idea doesn’t work either. 3840 is best as 15x16x16, so you want to put the 3 and 5 in the same bin.

48. #### MQ

September 24, 2015 - 6:27 pm -

@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.)

49. #### Daniel

September 24, 2015 - 6:28 pm -

108 would be:
Bin 1: 3
Bin 2: 3Ã—2=6
Bin 3:3Ã—2=6

1200 would be:
Bin 1: 5Ã—2=10
Bin 2:5Ã—2=10
Bin 3: 3Ã—2Ã—2=12

Typesetting did not come out right on previous examples, sorry.

50. #### Howard Phillips

September 24, 2015 - 6:39 pm -

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.

51. #### Matt

September 24, 2015 - 7:20 pm -

Yeah, I ran into that issue too.

3 => 1,1,3
24 => 2,3,4 (not 2,2,6)

So f(p^3 *A) != p * f(A)

52. #### Howard Phillips

September 24, 2015 - 7:42 pm -

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.

53. #### Matt

September 24, 2015 - 8:30 pm -

I broke it.

7776 (6^5). Factors of 2,2,2,2,2,3,3,3,3,3

After a few steps:
32 – 2,2,2,2,2
27 – 3,3,3
9 – 3,3

You then move a two from 32 to 9 to get:
16 – 2,2,2,2
27 – 3,3,3
18 – 2,3,3

Where the algorithm stops.

However, 18-18-24 is a smaller solution

54. #### Matt

September 24, 2015 - 8:39 pm -

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

55. #### Greg

September 24, 2015 - 9:41 pm -

It’s an interesting problem, though interest is a personal function, right? It seems to be slipping pretty far into “fake world math.” In any real world context, dimensions for packaging for any conceivable quantity of candies would be pre-determined and simply looked up. Granted that this problem was given to math teachers and not math students, but I just wanted to point out for the record that I think we’ve strayed from the path of real world contexts motivating problem solving.

Carry on, algorithm lovers. :)

56. #### Howard Phillips

September 25, 2015 - 3:16 am -

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.

57. #### Howard Phillips

September 25, 2015 - 3:19 am -

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.

September 25, 2015 - 4:30 am -

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.

59. #### Robert

September 25, 2015 - 6:26 am -

Try 222

1) Cube root is 6.05. Smallest factor greater than that is 37.
2) Next factor closest to 6.05 is 6.

222 = 37 x 6 x 1

But the answer should be 222 = 37 x 3 x 2

60. #### Roxanne

September 25, 2015 - 6:34 am -

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.

61. #### Paul Hartzer

September 25, 2015 - 6:55 am -

Robert:

As I commented before, if a number has exactly three prime factors, that’s the end of it and therer’s no need for further algorithms.

(Granted, I don’t think anyone’s proven that yet, so I’m off to do that now. ;) )

62. #### Paul Hartzer

September 25, 2015 - 7:28 am -

… 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.

63. #### Dan Meyer

September 25, 2015 - 7:42 am -

I’m also pinning this comment to the post itself.

We’re all witnessing incredible invention in this thread. To help you test the algorithm you’re about to propose, let me summarize the different counterexamples to different rules found so far.

20 should return 5 x 2 x 2
26 should return 13 x 2 x 1
28 should return 2 x 2 x 7
68 should return 2 x 2 x 17
222 should return 37 x 3 x 2
544 should return 4 x 8 x 17
720 should return 8 x 9 x 10
747 should return 3 x 3 x 83
16,807 should give 49 x 49 x 7
54,432 should return 36 x 36 x 42
74,634 should give 6 x 7 x 1777

64. #### Roxanne

September 25, 2015 - 8:31 am -

@Jonah OOOooooOOO nice find, so should there be a check between the first factor and the last two?

i.e.

1. Multiply F1 * F2
2. Square root the product
3. List the factors of the product
4. Select the factor closest to the square root and its multiplier
5. If the difference between abs(F1′-F2′) is less than abs(F1-F2) then use F1′ and F2′, else use F1 and F2.
(repeat for F1 and F3)

65. #### Jair

September 25, 2015 - 9:50 am -

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

66. #### Paul Hartzer

September 25, 2015 - 10:25 am -

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.

67. #### Paul Hartzer

September 25, 2015 - 10:27 am -

Jair: Dan has already said the box can’t have any gaps. 2x2x2 is not permitted for a box of seven candies.

Of course, to Greg’s point, in the real world a candy company would probably decide what sort of package sizes they want, and then decide how many candies to put in each. They wouldn’t put 728 candies in a box just to tormenter the package design team.

68. #### Paul Hartzer

September 25, 2015 - 10:36 am -

I’ve removed some useless lines from the second script, so “line 74” is now line 56. It’s the one that looks like this:

for MyTestValue in range(1,2501):

Put in the minimum and one more than the maximum. For instance, if you want to spelunk from 3500-4000, change it to:

for MyTestValue in range(3500,4001):

69. #### Robert

September 25, 2015 - 11:23 am -

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

70. #### Paul Hartzer

September 25, 2015 - 11:26 am -

One more script. This one lists all the unique triples, not including those containing a value of 1, along with the respective surface areas. This way, you can see how far off errors in your algorithm are. (Also, this will show if two different parameter sets have the same surface area.)

https://trinket.io/library/trinkets/a5eb42d4d1

This is how I spend my day off. :)

71. #### Roxanne

September 25, 2015 - 11:27 am -

@Robert

F1=12
F2=3
F3=37

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

September 25, 2015 - 11:32 am -

OK, I’ve changed my steps a bit.

1. Identify factor >= cube root of candies.
2. Identify factor >= square root of remaining factors.
3. Combine remaining factors.

e.g. 732 – factors 2.2.3.61
1. 61 >= 9.01 (cube root)
2. 4 >= 3.46 (square root of 2.2.3)
3. 3 is remaining factor

61 x 4 x 3 is optimum

This works for all the numbers in Dan’s pinned post and 738.

Thanks to Robert for 222 and Paul H for his proof.

73. #### Roxanne

September 25, 2015 - 11:58 am -

I really think this works now with the addendum. I mean it is not elegant, but it seems to work.

Thoughts?

—-
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)

Confirm the first factor (F1), the second factor (F2) and the third factor (F3) are the optimal solution:
1. Multiply F1 * F2
2. Square root the product
3. List the factors of the product
4. Select the factor closest to the square root and its multiplier (F1′ and F2′)
5. If the absolute difference between F1â€²-F2â€² is less than F1-F2 then use F1â€² and F2â€², else use F1 and F2.
(repeat for F1 and F3)

Pardon the lack of mathematical proof language, I am not a mathematician.

74. #### Sonny van Westen

September 25, 2015 - 11:58 am -

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

75. #### Jonah

September 25, 2015 - 12:20 pm -

Roxanne: That seems pretty reasonable to me, and I think it’s a faster version of my algorithm in post #35. But I still have a nagging suspicion that there’s some case where you *can’t* improve the result by changing two numbers, but you can by changing all three. I haven’t been able to construct one yet, though.

Sonny: The number of computations for a brute force calculation is on the order of V, since you can just look at all pairs x,y â‰¤ sqrt(V).

76. #### Paul Hartzer

September 25, 2015 - 12:37 pm -

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.

77. #### Paul Hartzer

September 25, 2015 - 12:39 pm -

Here’s how it works for 720, for instance:
[2, 2, 180]
[2, 3, 120]
[2, 4, 90]
[2, 5, 72]
[2, 6, 60]
[2, 8, 45]
[2, 9, 40]
[2, 10, 36]
[2, 12, 30]
[2, 15, 24]
[2, 18, 20]
[3, 3, 80]
[3, 4, 60]
[3, 5, 48]
[3, 6, 40]
[3, 8, 30]
[3, 10, 24]
[3, 12, 20]
[3, 15, 16]
[4, 4, 45]
[4, 5, 36]
[4, 6, 30]
[4, 9, 20]
[4, 10, 18]
[4, 12, 15]
[5, 6, 24]
[5, 8, 18]
[5, 9, 16]
[5, 12, 12]
[6, 6, 20]
[6, 8, 15]
[6, 10, 12]
[8, 9, 10]

78. #### Paul Hartzer

September 25, 2015 - 12:49 pm -

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.

79. #### Kent Haines

September 25, 2015 - 1:05 pm -

Let n be the # of candies

Step 1: find the cube root of n

Step 2: find the integer nearest to the cube root that is a factor of n. That number is the first dimension.

Step 3: divide n by the first dimension.

Step 4: take that result and find its two factors that are nearest to each other. For example, 6 and 4 for 24. Those two factors are your second and third dimensions.

Maybe? I tried it a lot and it seemed to work.

80. #### Sonny van Westen

September 25, 2015 - 1:10 pm -

@ 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)

81. #### Sonny van Westen

September 25, 2015 - 1:19 pm -

@ 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.

82. #### Paul Hartzer

September 25, 2015 - 1:40 pm -

@Kent: Other people have suggested that, and it doesn’t work. The problem is that it doesn’t account for significant outliers. For instance, 2412 = (2, 2, 3, 3, 67). That method means you should start with 12, but the ideal set is (6, 6, 67).

83. #### Paul Hartzer

September 25, 2015 - 1:47 pm -

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.

84. #### Paul Hartzer

September 25, 2015 - 1:54 pm -

Erg, the cube root strategy also fails for 2400, and those prime factors are very close together.

1. (2, 2, 2, 2, 2, 3, 5, 5)
2. (2400)^(1/3) = 13.4, so use 12: 3 * 2 * 2

… but the ideal set is (10, 15, 16). We could only salvage this if we had a reasonable explanation as to why we ought to go to the next highest, rather than to the closest integer. 13.4/12 < 15/13.4, for that matter.

So if there IS a successful strategy (other than "throw the puzzle pieces on the table and put them together until they fit"… which isn't a big deal for smaller numbers, anyway), I think it's some variation of "insert into seeded columns".

85. #### Roxanne

September 25, 2015 - 2:46 pm -

@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

86. #### Roxanne

September 25, 2015 - 3:12 pm -

@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

87. #### Zach

September 25, 2015 - 5:04 pm -

This is a very project euler-esque question, so my first attempt at it is pretty brutish:

0: if n is a cube, we’re done.

1: check for a factor q below sqrt(n)
2: check for a factor k of n//q
3: test the box [q, k, n//(q*k)], if less than the current record, update
4: repeat 1-3 until exhaustion (make a computer do it)

5: return the solution

it’s pretty simple, but it (again,) very brutish, but correct. I’m interested in the absolute value arguments from above. I’ll be testing variations of these against my current solution. It would be nice to get some real bounds on the values, but given the constraints, everything has to be pretty loosey goosey without exhausting infinitely many cases.

I’ll try anyway.

88. #### Chester Draws

September 25, 2015 - 5:51 pm -

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.

89. #### Paul Hartzer

September 25, 2015 - 6:29 pm -

This works for all cases 1-2500. It uses the cube root strategy, but accounts for the large outliers and uses my observation that the largest sorted triple will be the ideal. This is a strategy for reducing what could be a long list of triple candidates to three.

Let A be the area.
1. Create a candidate for a by taking x = A^(1/3) and testing each integer from x to 1, stopping when A mod x = 0.
2. Create a second candidate for a by taking x = A^(1/3) and testing each integer from x to A, stopping when A mod x = 0.
3. Create a third candidate by taking a = largest prime factor of A.
4. For each candidate, B = A/a and y = A^(1/2). Test each integer from y to 1, stopping when B mod y = 0. This is b. c = B/b. Sort these values from smallest to largest.
5. You will now have three triples. Select the triple where a is largest. If a is the same, select the triple where b is largest.

90. #### Scott

September 25, 2015 - 6:29 pm -

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…

91. #### Paul Hartzer

September 25, 2015 - 6:32 pm -

Corrected comment: y = B^(1/2), not y = A^(1/2). I wish I could edit/delete. :p

This works for all cases 1-2500. It uses the cube root strategy, but accounts for the large outliers and uses my observation that the largest sorted triple will be the ideal. This is a strategy for reducing what could be a long list of triple candidates to three.

Let A be the area.
1. Create a candidate for a by taking x = A^(1/3) and testing each integer from x down to 1, stopping when A mod x = 0.
2. Create a second candidate for a by taking x = A^(1/3) and testing each integer from x to A, stopping when A mod x = 0.
3. Create a third candidate by taking a = largest prime factor of A.
4. For each candidate, B = A/a and y = B^(1/2). Test each integer from y down to 1, stopping when B mod y = 0. This is b. c = B/b. Sort these values from smallest to largest.
5. You will now have three triples. Select the triple where a is largest. If a is the same in multiple triples, select the triple where b is largest.

92. #### Paul Hartzer

September 25, 2015 - 6:34 pm -

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

Time to go do something else for a while.

93. #### Aran Glancy

September 25, 2015 - 7:10 pm -

All my algorithms have failed so far, so I’ve resorted to just trying to understand the problem better. Specifically I was looking for some other property of the triple (a,b,c) which is minimized when the surface area is minimized.

I first thought of the diagonals of the prisms, which can be represented by the vector (a,b,c) where the prism has one corner at the origin and the opposite one at the point (a,b,c). My next thought was that perhaps the optimal triple is the one that has the smallest angle between it and the diagonal of a cube (i.e. (t,t,t) where t = (Volume)^1/3). Sadly this fails for 68 (among others). The angle for (1,4,7) is ~43 degrees, while the angle for the optimal solution (2,2,7) is ~45.

Ok, so what about the length of the diagonals? Maybe the best solution also has the shortest diagonal. This works for that pesky 68: (2,2,7) is a shorter vector than (1,4,7)!

Alas, this also fails at 360 and 1008. The optimal solution for 360 is (6,6,10) w/ SA = 312. The length of the diagonal is 13.11. But (5,8,9) w/ SA = 314 (so close!!) has the slightly SHORTER diagonal of 13.04. 1008 is similar. I’m sure there are more, but I only tested up to 2500.

94. #### Timteachesmath

September 25, 2015 - 8:04 pm -

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.

95. #### Dan Meyer

September 25, 2015 - 8:34 pm -

Timteachesmath

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.

Love this question. Love that we’re here. I’d love to hear opinions from Paul, Roxanne, Mary, Jonah, and the other people who have invested so much of their brain juice on this thread.

96. #### Chester Draws

September 25, 2015 - 9:54 pm -

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.

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

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.

97. #### Roxanne

September 25, 2015 - 10:49 pm -

@Dan and @Timteachesmath

I still have not found a case for #93 that doesn’t work. So break it – if you can :)

@Chester Draws et al

I think we may want to focus on the sum of the differences between the factors instead of solely the sum of the factors.

e.g.

min[|F1-F2|+|F1-F3|+|F2-F3|]

That way, we will have the largest factors that are approximately the same value ~ cube roots

98. #### Jonah

September 25, 2015 - 11:32 pm -

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.

99. #### Nick

September 26, 2015 - 12:51 am -

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.

100. #### Paul Hartzer

September 26, 2015 - 4:01 am -

I think both 93 and 113 will work for all cases 1-2500. What Roxanne’s method is doing for cases like 2190 is pulling out the large prime and then finding the best solution for the remainder.

I’m not sure if either of these will fail for numbers above 2500. If both of them succeed up to, say, one million that leads to the question of which one is “better”. Mine is easier to explain to a non-mathematician, but hers has a clear start and end point (instead of “choose between these three”).

101. #### Rene Grothmann

September 26, 2015 - 5:27 am -

I like the game touch you gave this challenge. It is almost like in the ancient times when people published in the following form: “I have solved problem X, can someone solve that too?”.

I believe this problem does not have a nice solution. If we compute all divisors of the total number of cubes (n cubes yields phi(n) divisors), we can find the desired optimum fairly easily by checking all of them with an effort of roughly O(log(phi(n))). If we do not do this, we cannot solve the problem at all.

By the way, your last algorithm breaks for 5850, where according to my computer, you use (15,15,26). And for each of these numbers there is a divisor closer to the cube root (the closest ones are 18 and 25), and none is a prime. 14280 is another example. (Yes, it was fun to program this!)

102. #### Roxanne

September 26, 2015 - 6:24 am -

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|].

103. #### Paul Hartzer

September 26, 2015 - 6:29 am -

My conjecture is that the two algorithms will break at the same numbers. So that’s something to test, too. ;)

More later when I’m not typing on my phone.

104. #### Rene Grothmann

September 26, 2015 - 7:01 am -

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.

105. #### Dan Anderson

September 26, 2015 - 7:26 am -

The “Roxanne Method” of cube root -> square root -> recheck once is pretty sturdy (although I’m sure it eventually fails). Passes all of Dan’s checks in post 77. Want to check it yourself?
Take this code: http://pastebin.com/0Cr6JWCk and paste it in python 2.7. You can run it in a browser at: http://www.tutorialspoint.com/execute_python_online.php

Or python file: https://dl.dropboxusercontent.com/u/3646828/candies.py
and
Image of passes of Dan’s Test from post 77: https://dl.dropboxusercontent.com/u/3646828/roxannetest.png

106. #### Dan Anderson

September 26, 2015 - 8:54 am -

(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]

107. #### Sara

September 26, 2015 - 9:05 am -

Trying to think about it as my students might…I need to clarify the question.

Are we liking for the box with the least packaging (surface area), or the arrangement of the units in a rectangular prism that when wrapped would have the least packaging (surface area).

It appears to me, that we are approaching the latter concept. To which I have no easy process…

We have identified that using as close to a cube as possible is yielding the least packaging. Why do the units have to be the exact shape of the packaging? If we are focused on a way to find the least packaging possible consistently, why can’t we just always make a cube?

Take the cube root of the number of units to be packaged, round up to the next even number, and make a cube out of that. All the units will fit inside, and it should yield the least packaging.

I’m probably over simplifying it, but I could imagine a student trying to go this route because the real life connection is that we are trying to minimize the packaging, and this is an easy solution to that problem.

108. #### Jonah

September 26, 2015 - 9:19 am -

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.

109. #### Jonah

September 26, 2015 - 9:24 am -

Oh, I should also mention that 5850, Rene’s counterexample to Roxanne’s method (#93) also breaks my method (#35), and is also the first counterexample to Chester’s observation (#116) that minimizing the sum of the dimensions gives the minimum surface area.

110. #### MQ

September 26, 2015 - 11:36 am -

@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.

111. #### Jonah

September 26, 2015 - 11:43 am -

@MQ, correct! The square root replacement method can never increase the largest number, so it can get stuck at 360.

I guess I was reading Roxanne’s method as also checking all three pairs of numbers, but perhaps that’s not the case. And even then, it would only be the same as my method if my method actually worked–if there’s more than one terminal set of dimensions, then it certainly matters where you start.

September 26, 2015 - 12:30 pm -

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?

113. #### Jonah

September 26, 2015 - 12:54 pm -

It seems like you would want to go for a cube-like configuration, so the solutions are of the form [n,n,n], [n,n,n+1], or [n,n+1,n+1].

But, no! 6 is better as 3 x 2 x 1, not 2 x 2 x 2.

The numbers where it doesn’t help to leave gaps are: 1, 2, 3, 4, 5, 6, 8, 9, 12, 16, 18, 20, 24, 27, 30, 32, 36, 40, 45, 48, 50, …

If you have a number on that list, do the usual thing. If not, round up to the next number on the list and use its solution. So for example with 22 candies, you really want to just leave two gaps in the 2 x 3 x 4 configuration for 24 candies.

Neither this list nor its complement appears on OEIS, which is pretty surprising to me.

114. #### MQ

September 26, 2015 - 12:55 pm -

@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.

115. #### Jonah

September 26, 2015 - 1:02 pm -

A brute force search runs in polynomial time, so it’s not NP-hard. (Unless it turns out that P = NP, but that’s probably not what you mean.)

116. #### Timteachesmath

September 26, 2015 - 4:36 pm -

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.

117. #### MQ

September 26, 2015 - 4:42 pm -

@Jonah

Ah, good point (I now see your sub-linear time comment in #120 from 1/2+1/3 = 5/6 < 1). My mind had wandered off too far; thanks for the correction & yes, your parenthetical remark is certainly not what I mean! M.Q.

118. #### Paul Hartzer

September 26, 2015 - 4:51 pm -

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. :)

119. #### Paul Hartzer

September 26, 2015 - 6:12 pm -

134 Jonah: A modification fixes this. The ideal triple (a, b, c) is the one with the smallest a + b + c. If there are two triples with the same a + b + c, choose the one with the largest a.

E.g. 360 has a minimal sum of 22. (5, 8, 9) and (6, 6, 10) both have sums of 22, so choose (6, 6, 10).

E.g. 3168 has a minimal sum of 45. (11, 16, 18) has a sum of 45, while (12, 12, 22) has a sum of 46.

120. #### Paul Hartzer

September 26, 2015 - 6:37 pm -

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]

121. #### Paul Hartzer

September 26, 2015 - 8:44 pm -

This has been tested up to 50000. I shall call it Two Candidate High-Low.

Let V be the Volume. A triple (a, b, c) is sorted such that a <= b <= c. Whenever one value is found, the other two values are determined using the square root method: Take the square root of the remainder, find the factor of the remainder that's less than the square root but closest to it, and then find the remainder of that.

1. If V has three or fewer prime factors, those are the sides. Nothing else is done.
2. If V is a cube (8, 27, etc.), then a, b, and c are the cube roots. Nothing else is done.
3. Create Candidate 1 by using the largest prime factor of V. Find the other two values using the square root method.
4. Create Candidate 2 by using the cube root of V. Take the factor of V less than but closest to the cube root. Find the other two values using the square root method, then sort the triple from smallest to largest.
5. Create Candidate 3. Start with Candidate 2. Use the largest factor of V that is less than b. Find the other two values using the square root method.
6. Create Candidate 4. Start with Candidate 2. Use the smallest factor of V that is more than b. Find the other two values using the square root method.
7. Assess the four candidates to find the ideal. First, add up all their values. If there is one that has a smallest value, that's the ideal. If there is more than one, take the one that has the largest a value.

122. #### Jonah

September 26, 2015 - 10:45 pm -

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.

123. #### Doug Bruce

September 26, 2015 - 11:00 pm -

Looking at lists like 130 and 146, I notice that ideal dimensions have one face of the box that is square or almost-square. Up until volumes above 10,000, is seems the difference in the two closest dimensions is less than 6. For instance 6552=14*18*26, and 18-14 is 4.
It seems that forming a square or almost-square is sometimes more appealing than forming an almost-cube.

I propose an algorithm similar to Paul Hartzer. I will call it a Four Candidate algorithm.

First, if there are only 3 (preferably non-one) prime factors, use those.

Else, for a given volume, V. Take the third root of V, which we will call x.
If x is an integer you have found the dimensions.
If x is not an integer:
1. Create two candidates for a by taking x and testing each integer from x down to 1, stopping when V mod x = 0.
2. Create two more candidates for ‘a’ by taking x and testing each integer from x to V, stopping when V mod x = 0.

We have found four factors of V, two smaller than x and two larger than x.

Each of these candidates is a Case. We have four Cases.
For each Case:
1. Find b
Take a and test each integer from a down to 1, stopping when (V/a) mod b = 0.
Next, take a and test each integer from a to (V/a), stopping when (V/a) mod b = 0.
Between these two possible values for b (testing integers below and above a) use the b such that |b-a| is minimized.
(If there are two b that give the same |b-a|, use both b and resulting triples)
2. Find c
V/(ab) = c
Sort a, b, and c, such that a<=b<=c.

Each Case will give you a triple: a, b, c.

For these four triples, perform the a+b+c test.
The smallest a+b+c is ideal.
If there is a tie, then the triple with the larger a, is ideal.

Please let me know when this algorithm wrecks.
If it wrecks at a very large volume, then it may require 6 Candidates. 3 above x and 3 below x.

124. #### Doug Bruce

September 26, 2015 - 11:16 pm -

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.”

125. #### Paul Hartzer

September 27, 2015 - 4:17 am -

148 Jonah: My algorithm does work for 118755:

What value should I try? 118755
More than three prime factors.
First Candidate: [29, 63, 65]
Second Candidate: [29, 45, 91]
Third Candidate: [35, 39, 87]
Fourth Candidate: [29, 63, 65]
[35, 39, 87]
I’m done.
https://trinket.io/python/df31da6fa1

1. (More than three prime factors.)
2. (Not a cube.)
3. The largest prime factor is 29. Therefore a = 29 and the remainder = 4095. The square root of 4095 is 63 and change. 63 is a factor, so the candidate is (29, 63, 65).
4. 118755^(1/3) = 49 and change. 49, 48, 47, and 46 are not factors. Therefore a = 45 and the remainder = 2639. The square root of 2639 is 51 and change, which has factors less than 51 of 7, 13, and 29. So the candidate is (29, 45, 91).
5. Starting with 45, look for the next factor less than this. This is 39. Therefore a = 39. Using the square root method, b = 35 and c = 87. The candidate is (35, 39, 87).
6. Starting with 45, look for the next factor more than this. This is 63, which leads back to (29, 63, 95).
7. Of these four, the ideal is (35, 39, 87), which is also the overall ideal.

126. #### Paul Hartzer

September 27, 2015 - 4:31 am -

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.

127. #### Paul Hartzer

September 27, 2015 - 4:35 am -

So here’s where the algorithm currently stands. I’ll keep the same name, since this is a change only to the last step.

This has been tested up to 50000 by me, and apparently to 200000 by Jonah. I shall call it Two Candidate High-Low.

Let V be the Volume. A triple (a, b, c) is sorted such that a <= b <= c. Whenever one value is found, the other two values are determined using the square root method: Take the square root of the remainder, find the factor of the remainder that's less than the square root but closest to it, and then find the remainder of that.

1. If V has three or fewer prime factors, those are the sides. Nothing else is done.
2. If V is a cube (8, 27, etc.), then a, b, and c are the cube roots. Nothing else is done.
3. Create Candidate 1 by using the largest prime factor of V. Find the other two values using the square root method.
4. Create Candidate 2 by using the cube root of V. Take the factor of V less than but closest to the cube root. Find the other two values using the square root method, then sort the triple from smallest to largest.
5. Create Candidate 3. Start with Candidate 2. Use the largest factor of V that is less than b. Find the other two values using the square root method.
6. Create Candidate 4. Start with Candidate 2. Use the smallest factor of V that is more than b. Find the other two values using the square root method.
7. Assess the four candidates to find the ideal, using the half-volume formula of ab + bc + ac.

128. #### Paul Hartzer

September 27, 2015 - 5:41 am -

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.

129. #### Paul Hartzer

September 27, 2015 - 7:52 am -

Looking at the values that fail my algorithm, I don’t see a way that would improve the algorithm that wouldn’t create more work on the low values than brute-force would entail. That goes back to a question Dan asked a while back about optimization. Which is better: A reasonably simple algorithm that rarely fails, or a fairly complex algorithm that never fails? I don’t think we’re going to find a reasonably simple algorithm that never fails.

I set my algorithm to test up to one million; it’s still going, having passed 600,000, and here’s its current list of problems. Assuming all the ones with too many primes turn out to be fine, that leaves 35/600000 as an error rate, or 0.00583%. I might still be missing something but I can’t imagine we can get any better without such a complex algorithm candidate list that we might as well just do it by brute force.

Too many prime factors at: 65536
Too many prime factors at: 98304
Too many prime factors at: 131072
Failed at: 141284
Failed at: 143748
Too many prime factors at: 147456
Too many prime factors at: 163840
Failed at: 165308
Failed at: 184756
Too many prime factors at: 196608
Failed at: 206492
Too many prime factors at: 221184
Failed at: 222530
Too many prime factors at: 229376
Too many prime factors at: 245760
Failed at: 257600
Failed at: 267540
Too many prime factors at: 294912
Failed at: 310284
Failed at: 319124
Failed at: 320892
Too many prime factors at: 327680
Too many prime factors at: 331776
Failed at: 335478
Too many prime factors at: 344064
Failed at: 345644
Too many prime factors at: 360448
Failed at: 362406
Too many prime factors at: 368640
Failed at: 374946
Failed at: 379236
Failed at: 386308
Too many prime factors at: 393216
Too many prime factors at: 409600
Too many prime factors at: 425984
Failed at: 438702
Failed at: 440572
Too many prime factors at: 442368
Too many prime factors at: 458752
Failed at: 467636
Failed at: 487084
Failed at: 490314
Too many prime factors at: 491520
Too many prime factors at: 497664
Failed at: 500916
Failed at: 505172
Failed at: 505362
Failed at: 514998
Too many prime factors at: 516096
Failed at: 518466
Failed at: 520676
Failed at: 522652
Too many prime factors at: 524288
Too many prime factors at: 540672
Failed at: 547998
Too many prime factors at: 552960
Failed at: 554268
Too many prime factors at: 557056
Failed at: 564604
Too many prime factors at: 573440
Failed at: 579462
Too many prime factors at: 589824
Failed at: 592020
Failed at: 594720

130. #### Jonah

September 27, 2015 - 9:40 am -

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].

131. #### Paul Hartzer

September 27, 2015 - 11:04 am -

Jonah, good point, although at some point I’d noted that we only have to go from b to V/8 (and, now that I think of it, from b down to 4) if a, b, and c are all not 1.

For whatever it’s worth, there appear to be 79 fails, not including the cases with 16 or more prime factors, from 1 to 1,000,000. Looking at the first few and playing around a bit, I can’t find any way to modify for these cases without making the algorithm unwieldly (e.g., “continue to use Candidate 3 to seed itself until it stops changing”).

132. #### IanR

September 27, 2015 - 11:31 am -

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.

133. #### Jeff DeMarco

September 27, 2015 - 3:17 pm -

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.

134. #### Paul Hartzer

September 27, 2015 - 3:21 pm -

This is interesting. I was worried that iterating through Candidates 3 and 4 would make them worse sometimes, better sometimes, before approaching the ideal, but that doesn’t seem to be the case EXCEPT at the very first step. That is, if we build Candidate 2 and then build Candidate 3 (and 4) off of that, sometimes Candidate 3 (and 4) is worse than Candidate 2. But the second round (Candidate 3 built from Candidate 3, Candidate 4 built from Candidate 4) is safe.

That is, if we iterate at least once through Candidate 3 and through Candidate 4, but stop any time after that first round where we get “not better”, we will wind up with four candidates, one of which is always the ideal.

I was really hoping that we could use this method to get rid of the “Largest Prime Factor” candidate altogether, but unfortunately using only the cube root-and-derived candidates fail at 238292.

So I can edit and use LaTeX in my explanation, I’ve put the current state of things here: http://curiouscheetah.com/BlogMath/dan-meyers-rrrd-puzzle/

135. #### Paul Hartzer

September 27, 2015 - 3:24 pm -

@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.

136. #### Bruce Schardt

September 27, 2015 - 4:10 pm -

Let V be the Volume. A triple (a, b, c) is sorted such that a <= b = cube root of V then assign the maximum prime factor to c in our triple (a,b,c).
Otherwise calculate the minimum product of the prime factors that is >= cube root of V and assign this product to c.

Step 2. To get the value of b
the remaining prime factors not used in c are the prime factors of the product of a times b.
if any of the prime factors of (ab) is >= square root of (ab) then assign the maximum prime factor of (ab) to b
Otherwise calculate the minimum product of the prime factors that is >=square root of (ab) and assign this to b.

Step 3. to get the value of a

The value of a is the product of the remaining factors of V not used in the calculation of either b or c which is also equal to V/(bc).

137. #### Bruce Schardt

September 27, 2015 - 4:22 pm -

For some reason that post is corrupted.

Let V be the Volume. A triple (a, b, c) is sorted such that a = to the cube root of V then
then assign the maximum prime factor to c in our triple (a,b,c).

Otherwise calculate the minimum product of the prime factors that is >= cube root of V and assign this product to c.

Step 2. To get the value of b

The remaining prime factors not used in c are the prime factors of the product of a times b.

If any of the prime factors of (ab) is >= square root of (ab) then assign the maximum prime factor of (ab) to b
Otherwise calculate the minimum product of the prime factors that is >=square root of (ab) and assign this to b.

Step 3. to get the value of a

The value of a is the product of the remaining factors of V not used in the calculation of either b or c which is also equal to V/(bc).

138. #### Bruce Schardt

September 27, 2015 - 4:24 pm -

factor V into prime factors.

Step 1. determine value for c

if any of the prime factors are >= to the cube root of V then
then assign the maximum prime factor to c in our triple (a,b,c).

Otherwise calculate the minimum product of the prime factors that is >= cube root of V and assign this product to c.

139. #### Ryan Cropper

September 27, 2015 - 5:01 pm -

Dan,

Although I think hunting for this algorithm is interesting, I think we are missing the real point of the task. The goal is to find the box with the least surface area that will contain the contents. We are pretending that we are working for a packaging company that wants to use a minimal amount of material. Let’s pretend we wanted to ship 25 cubic units. We would settle on two options: a) 1,1,25 or b) 1,5,5. The surface area of a) is 102 square units and b) is 70 square units. We would all agree that we should b) and move on to the next one. However, that is certainly not the best box to use. A 3,3,3 box would have a volume of 27 cubic units which is plenty of room for the 25 cubes. It also has a surface area 54 square units, much lower than our previous two options. The packaging company does not care that there is extra room in the box if it is cheaper and large enough. So it seems that there are definitely times when the best box may use numbers that aren’t factors of the original volume at all.

Can we create an algorithm that answers the question of what the true best box would be, even if it has a larger volume then necessary?

Sincerely,
Cropper

September 27, 2015 - 5:19 pm -

Answering that question requires that we have answered this one first. An efficient algorithm for solving the problem of packing with spacers looks more or less like “find the spaceless packing for n, n+1, n+2, … k^3 for the smallest possible integer k, choose the one with the smallest surface area.”

The only open question is whether we can get away with stopping earlier than a cube, or rather how we tell when to stop.

140. #### Mark Eichenlaub

September 27, 2015 - 5:18 pm -

Here I’ll assume that all the factors of the number of candies are known.

We can easily solve the two-dimensional problem of finding the rectangle with integer side lengths and smallest perimeter given fixed area. (The method is simply to choose the integers nearest the square root of the area as the side lengths.)

In three dimensions with volume V and integer sides lengths a,b, c, let the c be less than or equal to a and b. If we know c, our problem is then reduced to the previous problem with area = V/c. Therefore, we need only determine c.

Begin by assuming c to be the largest factor of V smaller than or equal to the cube root of V and determine a and b under this assumption. (If a is smaller than c, throw this out and choose the next-largest factor greater than the cube root of V as c. Repeat until a is greater than or equal to c). Call this guess for c “c_1” and the corresponding guesses for a and b “a_1” and “b_1”. Call the surface area A_1

It has previously been shown that this package is not necessarily optimal. However, we now know that the ideal package has a surface area less than or equal to A_1.

Given c, the minimum area for the box if we don’t require a and b to be integers is when a=b, so A_min = 2(V/c*2 sqrt[V*c]). Therefore, if we solve for c when A_min = A_1, we obtain a minimum for c, c_min.

We now know c_min <= c <= c_1. This substantially reduces the magnitude of the brute force check. It may be that we are now done because only one factor of V is in the allowed range.

If not, choose the largest factor of V in the allowed range as c_2. Calculate an area A_2. If A_2 = A_1, simply choose the next-largest factor of V in the range and repeat this until we have tested every factor of c in the range.

This algorithm should be an improvement over brute force and is guaranteed to find the correct answer.

141. #### Arthur

September 27, 2015 - 5:21 pm -

1. Take the number, n, write out all the prime factors.
2. Take the cuberoot of the number, then round to the nearest factor a. a is one of your side lengths.
3. Now find all the factors of n/a.
4. Take the squareroot of (n/a). The nearest factor of n/a let’s call that b.
5. The last side is c = n/(a*b).

142. #### Mark Eichenlaub

September 27, 2015 - 5:31 pm -

typos in #170

A_min should be 2(V/c + 2 sqrt[V*c])

at the end, it should be A_2 greater than or equal to A_1, but the text got parsed incorrectly somehow

143. #### Sam

September 27, 2015 - 9:41 pm -

This seems like a trick question, because to get a decent sample size on the infinite combinations, wouldn’t you need a sample size close to infinity? I don’t see this ever having a legit answer…

144. #### Paul J

September 28, 2015 - 11:56 am -

Knowing that finding a balanced solution closest to a cube is going to be the best or top candidate is a good heuristic, but the problem of combining all of the available prime factors into three sets to find most balanced one is an NP-complete problem I believe, not very from from similar problems of:

Thus no guaranteed to work every time short-cut exists, other than brute force of trying all reasonable in scope options and evaluating their values against all others candidates combinations of near balanced prime factor combinations.

trick problem, QED

145. #### Robert

September 28, 2015 - 12:07 pm -

In response to #168 “Note that one is trying to minimize the spread (range) between a and c.”

Try 1008 = 8 x 9 x 14
The range is 6
The surface area is 620

Which is better than 1008 = 7 x 12 x 12
The range is 5
The surface area is 624

146. #### Jonah

September 28, 2015 - 12:24 pm -

Paul: bin-packing takes an exponential number of steps in terms of the number of factors. But the number of factors grows logarithmically with respect to the volume. So this problem isn’t actually that hard: a^(log_b(x)) is bounded by a polynomial.

147. #### Scott Farrar

September 28, 2015 - 11:40 pm -

I believe that we have broken new ground for OEIS.

They have an algorithm similar to what some people have proposed here (divisors near cube roots, then divisors near square roots of n/firstside). But that algorithm fails at some of the points illustrated above: 68, 1332, 74634…

https://oeis.org/A075777

So it seems then that the algorithm for the sequence on OEIS is incorrect.

I registered for an account with them to try to ask more about it, but does anyone see a mistake on my part?

148. #### vzn

September 29, 2015 - 7:16 am -

really great to see all the energetic/ fruitful cyber collaboration here. fyi this problem has been posted to CS stackexchange forum by DW moderator & invite further answers/ discussion there. hope to see some there. personally currently think this reduces to 3-way number partitioning (minimizing the deviation from average of the sums). there is some CS study of this problem & references are contained in answer in the 1st link.

http://cs.stackexchange.com/questions/47638/algorithm-to-minimize-surface-area-given-volume

http://chat.stackexchange.com/rooms/2710/computer-science

more on the theme of math/ CS cyber collaboration

https://vzn1.wordpress.com/volunteer/

https://vzn1.wordpress.com/category/open-science-collab-collective-intel/

149. #### vzn

September 29, 2015 - 7:22 am -

ps Dmeyer writes “Once someone successfully critiqued the algorithm â€“ and every single algorithm has been successfully critiqued â€“ we emailed the author and alerted her. Subject line: RIP Your Algorithm.”

alas, unfortunately it seems likely there is significant duplicate effort in this comment thread vs all the work that has been done in workshops/ email to date of the blog. aka “reinventing the wheel”. ofc some who have participated in this pre-post may be involved in this comment thread, but anyway it would surely be very helpful to the overall collaboration if Dmeyer posted the stack of sample algorithms and some of that email dialog on why they have failed. ofc there is something to be said for independence also.

150. #### Ethan

September 29, 2015 - 7:05 pm -

Are there allowed to be empty spaces? For example for 999 candies a package of 10x10x10 would fit the pieces with one open space, and a surface area of 600. A package of 3x9x37 would fit all the candies without voids, but has a surface area 666. It seems as if allowing voids allows for more efficient packaging.

151. #### Richard Vahrman

September 30, 2015 - 5:29 am -

Re: Comment 20 and missing candies

Dear Mr Meyer

Thank you for your order of 747 candies. Please accept with our compliments an extra 63 free of charge.

Rgds
Smartie Candy Store

Which begs the question, if the supplier insisted on supplying free sweets rather than settling for a silly packaging solution, how much would he be out of pocket?

152. #### Paul

September 30, 2015 - 8:36 am -

Had students in my class suggest algorithms. They identified the following simple algorithm as giving correct answers to the 11 test cases. Would welcome RIP feedback.

a = factor of n nearest to the cube root of n
b = factor of n/a nearest to the square root of n/a
c = n/(a*b)
Side lengths are a,b,c

153. #### Dan Meyer

September 30, 2015 - 12:29 pm -

vzn:

anyway it would surely be very helpful to the overall collaboration if Dmeyer posted the stack of sample algorithms and some of that email dialog on why they have failed. ofc there is something to be said for independence also

Those algorithms were intentionally omitted here.

Paul, please give 28 one more try. I get 1 x 4 x 7 with your algorithm when 2 x 2 x 7 is more efficient. Let me know if I’m misunderstanding.

154. #### Calvin Lin

September 30, 2015 - 12:41 pm -

I’m not sure what your definition of algorithm is. I am assuming that we know the factors of n.

1. Start off with 1, 1, n
2. Fix one of the positions. For the other 2, if the numbers are x, y, then replace them with a, b where a is the smallest factor of xy that is just larger than or equal to (xy)^.5
3. Repeat step 2 (by fixing different positions), until it no changes the value.

Claim: This gives us the minimium.

155. #### Calvin Lin

September 30, 2015 - 12:46 pm -

Oh, never mind, I see cases with large enough primes where my approach doesn’t allow for a good mixing of these primes.

156. #### Paul

September 30, 2015 - 2:41 pm -

Calvin.
Here is what I get.
For a: The factors of n=28 are 2,2,7. The factor closest to the cube root on 28 is therefore 2.
For b: The factors of n/a=14 are 2,7. The one closest to the square root of 14 is therefore 2.
For c: 28/(2*2)=7

157. #### Scott Farrar

September 30, 2015 - 3:01 pm -

Here is some data generated by the algorithm I coded. It is described here: http://scottfarrar.com/blog/dandy-candies-and-oeis/

It looks for the cube root, then tests all s1s under that, that also divide n. Then it looks for the square root of each n/s1 and finds all s2s under that that also divide n/s1.

So its limited brute force.

First 5000 as a csv sequence:

First 30000 as a csv table n, s1, s2, s3, minSA:

158. #### Dan Meyer

September 30, 2015 - 3:26 pm -

@Paul, If I understand your algorithm correctly, you aren’t looking at any factor for your first two dimensions but rather prime factors. Which makes me wonder how your algorithm runs through 32.

159. #### Paul

October 1, 2015 - 10:24 am -

Dan 189
Thanks for the RIP. For n=32 the proposed algorithm would yield 2x2x8 which is not correct.

160. #### LS

October 1, 2015 - 11:17 am -

Not perfect answer, errors beginning at 3,168 and 19 errors out of first 30,000 so not bad for first try I reckon. Doesn’t look like any errors before 2,500, please let me know otherwise. There’s some pattern to the errors which could potentially be improved upon.

Logic: Using 10164 as example.

2a) Take MIN and MAX (1,10164) and look for next factor greater than the smaller factor and less than the larger factor. This would be 2,5082. Resulting in (1,2,5082)
2a) Loop till it can’t be improved anymore. Resulting in (11,12,77)

3a) Take MID and MAX (12,77) and do the same. This would be 14,66. Resulting in (11,14,66)
3b) Loop till it can’t be improved anymore. Still resulting in (11,28,33)

4a) Take MIN and MID (11,28) and do the same. This would be 14,22. Resulting in (14,22,33)
4b) Loop till it can’t be improved anymore. No further improvement. Resulting in (14,22,33)

5) Loop steps 2 to 4 till there are no more changes. Final answer (21,22,22)

Error locations:
3168 [12,12,22=1344] [11,16,18=1324]
4620 [11,20,21=1742] [15,14,22=1696]
5460 [14,15,26=1928] [13,21,20=1906]
8775 [15,15,39=2790] [13,25,27=2702]
10800 [18,24,25=2964] [20,20,27=2960]
11016 [18,18,34=3096] [17,24,27=3030]
12240 [18,20,34=3304] [24,17,30=3276]
12852 [18,21,34=3408] [17,28,27=3382]
15200 [20,20,38=3840] [25,19,32=3766]
15960 [20,21,38=3956] [19,28,30=3884]
17556 [21,22,38=4192] [19,28,33=4166]
18240 [20,24,38=4304] [19,30,32=4276]
25137 [21,21,57=5670] [27,19,49=5534]
26496 [24,24,46=5568] [23,32,36=5432]
27600 [24,25,46=5708] [30,23,40=5620]
28704 [24,26,46=5848] [23,32,39=5762]
29106 [22,27,49=5990] [21,33,42=5922]
29808 [24,27,46=5988] [23,36,36=5904]
29925 [21,25,57=6294] [19,35,45=6190]

161. #### Timteachesmath

October 1, 2015 - 7:18 pm -

Re: josh g., Jonah,
Tim, Calvin Lin, and LS, who suggest approaches similar to the following rule . . .

1) save one number,
2)fix the other two closest to each other, then
3) repeat
For example, if we save the median every time, from (1,1,360), save 1 and turn 1*360 into 18,20. Now with (1, 18, 20), save 18 and turn 1*20 into 4,5. With (4, 5, 18), save 5 and turn 4*18 into 8,9, arriving at (5,8,9), which in this case is not the minimum surface area.

. . . here’s graph1 and graph2 which show the first few pitfalls for similar approaches. Can anyone use them to decide which numbers to save each round?

For the first 100,000 volumes:
41554 fails: save the median every round.
440 fails: save the median repeatedly, then save the maximum once
252 fails: save the min, then the max, then the median repeatedly, then the max, then the min
142 fails: repeat this sequence: (save the median, then the max, then the min)
123 fails: repeat this sequence: (save the median repeatedly, then the min, then the max)

A ‘dead end’ is like (11, 27, 35) where any save results in no change but the box with minimum surface area has dimensions (15, 21, 33). I found 264 dead ends among the first 100,000 volumes.

162. #### Emmanuel Goldstein

October 2, 2015 - 8:14 am -

The following algorithm works in all cases. It’s search, with (lots of) pruning. In practice it usually considers just a few divisors of n, performs a simple calculation for each, then produces a definitive answer (even when n has many divisors). For example, n=594720 has 144 divisors, and only 7 are considered.

First, I’ll present the justification for the pruning method used. Then, I’ll present the algorithm. Finally, I’ll show an example run.

-Justification-
We want to minimize f = xy + xz + yz, subject to xyz=n. Suppose we’ve decided to try a given value for z, taken from the set of divisors of n. Then we can rewrite y = n/(xz), and f = n/z + xz + n/x, which is now a function of x only. This has a minimum at x = sqrt(n/z). You can see this by checking that f goes to large values at its endpoints, then calculating where its derivative (with respect to x) is 0. Of course, sqrt(n/z) isn’t necessarily an integer divisor of n/z, but we can still use it to calculate an optimistic estimate of f, at z. Here is the formula, obtained by setting x = sqrt(n/z):

opt-est(z) = n (sqrt(nz) + 2z^2) / (z sqrt(nz))

With this, if we already have a pretty good candidate value f’ = f(x’, y’, z’) (calculated with integer divisors), we can quickly rule out a new z: if opt-est(z) > f’, z won’t yield anything good.

But not only can we rule out just that z. We can also rule out every z further away from the cube root of n, because -their- optimistic estimates are only going to get worse. This is because opt-est(z) has a minimum at z = n^(1/3), and is increasing on either side of it. Again you can see this by analyzing opt-est(z) at its endpoints, then calculating where its derivative (with respect to z, this time) is 0.

This suggests the following algorithm outline. First try the divisor z of n closest to n^(1/3), and calculate the best value of f there (take x to be the divisor of n/z closest to sqrt(n/z)). Then continue trying divisors, progressively moving away from n^(1/3), and do the following:
– whenever we find that opt-est(z) is greater than the best value of f so far, remove z and all z further away from n^(1/3), from the list of divisors;
– otherwise calculate f there, and check if it’s better than the best value so far;
– whenever we calculate the actual value of f for a triplet of divisors, remove all three of them from the list of divisors. This is not a trivial step, because although this triplet is locally optimal at this value of z, it doesn’t have to be optimal for those x and y. However, suppose there is a better triplet with the same x. Then the other pieces must be different (from this triplet), so we’re not removing anything essential: those different divisors will get examined, either in the past or in the future;
– stop when the list of divisors is empty.

-Algorithm-

Let D be the list of divisors d of n, in ascending order of the absolute value of (d – n^(1/3)).
Initialize bestVal = infinity.
While D is not empty:
..Let z be the first item in D.
..If opt-est(z) > bestVal, then:
….If z > n^(1/3), remove from D all d >= z; else, remove from D all d <= z.
….Go to the next iteration.
..Let x be the divisor of n/z closest to sqrt(n/z).
..Let y = n/(xz).
..Remove {x,y,z} from D.
..If f(x,y,z) < bestVal, then set bestVal = f(x,y,z), bestx = x, besty = y, bestz = z.
Return (bestx, besty, bestz).

-Example run-

p(594720);

144 divisors: [84, 80, 90, 96, 72, 70, 105, 63, 60, 59, 112, 56, 118, 120, 48, 45, 126, 42, 40, 36, 35, 32, 30, 140, 28, 144, 24, 21, 20, 18, 16, 15, 14, 12, 10, 9, 160, 8, 7, 6, 5, 4, 3, 2, 1, 168, 177, 180, 210, 224, 236, 240, 252, 280, 288, 295, 315, 336, 354, 360, 413, 420, 472, 480, 504, 531, 560, 590, 630, 672, 708, 720, 826, 840, 885, 944, 1008, 1062, 1120, 1180, 1239, 1260, 1416, 1440, 1652, 1680, 1770, 1888, 2016, 2065, 2124, 2360, 2478, 2520, 2655, 2832, 3304, 3360, 3540, 3717, 4130, 4248, 4720, 4956, 5040, 5310, 5664, 6195, 6608, 7080, 7434, 8260, 8496, 9440, 9912, 10080, 10620, 12390, 13216, 14160, 14868, 16520, 16992, 18585, 19824, 21240, 24780, 28320, 29736, 33040, 37170, 39648, 42480, 49560, 59472, 66080, 74340, 84960, 99120, 118944, 148680, 198240, 297360, 594720]

cube root: 84.09513032

———-
z: 84
value: 22032
removed: [60, 84, 118]
———-
z: 80
value: 21914
removed: [63, 80, 118]
———-
z: 90
removed: [59, 90, 112]
———-
z: 96
removed: [59, 96, 105]
———-
z: 72
value: 21796
removed: [70, 72, 118]
———-
z: 56
removed all z = 120, bounded by: 21851.72727
———-

divisors examined: 7
[70, 72, 118]

163. #### Emmanuel Goldstein

October 2, 2015 - 8:26 am -

A bit frustrating: we’re supposed to see that at z=56, all divisors = 120 get eliminated. I’ll try one last time:

z: 84
value: 22032
removed: [60, 84, 118]

z: 80
value: 21914
removed: [63, 80, 118]

z: 90
removed: [59, 90, 112]

z: 96
removed: [59, 96, 105]

z: 72
value: 21796
removed: [70, 72, 118]

z: 56
removed all z = 120, bounded by: 21851.72727

divisors examined: 7
[70, 72, 118]

164. #### Emmanuel Goldstein

October 2, 2015 - 8:28 am -

I see, everything between a less than sign and a greater than sign, is getting interpreted as an html tag. Apologies, and here we go, then:

-Example run-

p(594720);

144 divisors: [84, 80, 90, 96, 72, 70, 105, 63, 60, 59, 112, 56, 118, 120, 48, 45, 126, 42, 40, 36, 35, 32, 30, 140, 28, 144, 24, 21, 20, 18, 16, 15, 14, 12, 10, 9, 160, 8, 7, 6, 5, 4, 3, 2, 1, 168, 177, 180, 210, 224, 236, 240, 252, 280, 288, 295, 315, 336, 354, 360, 413, 420, 472, 480, 504, 531, 560, 590, 630, 672, 708, 720, 826, 840, 885, 944, 1008, 1062, 1120, 1180, 1239, 1260, 1416, 1440, 1652, 1680, 1770, 1888, 2016, 2065, 2124, 2360, 2478, 2520, 2655, 2832, 3304, 3360, 3540, 3717, 4130, 4248, 4720, 4956, 5040, 5310, 5664, 6195, 6608, 7080, 7434, 8260, 8496, 9440, 9912, 10080, 10620, 12390, 13216, 14160, 14868, 16520, 16992, 18585, 19824, 21240, 24780, 28320, 29736, 33040, 37170, 39648, 42480, 49560, 59472, 66080, 74340, 84960, 99120, 118944, 148680, 198240, 297360, 594720]

cube root: 84.09513032

z: 84
value: 22032
removed: [60, 84, 118]

z: 80
value: 21914
removed: [63, 80, 118]

z: 90
removed: [59, 90, 112]

z: 96
removed: [59, 96, 105]

z: 72
value: 21796
removed: [70, 72, 118]

z: 56
removed all z less than or equal to 56, bounded by: 22161.97904

z: 120
removed all z greater than or equal to 120, bounded by: 21851.72727

divisors examined: 7
[70, 72, 118]

165. #### Dave Marain

October 6, 2015 - 9:10 am -

Until there’s a valid proof of any algorithm we can’t be sure it’ll work in all cases. Some truly ingenious offerings thus far which shows how we can provoke some of our students with math conundrums!
OK, here’s mine and of course it needs rigorous verification. It does pass all the counterexamples but check that!
Let C=V^(1/3). Most suggestions work around this cube root but I think there are 2 cases. Case 1 is critical to the general solution!
Case1: The largest prime factor, P_max, of V IS GREATER THAN C. In this case, P_max MUST be one of the dimensions. From this point, process as in Case 2, Step 2 to find the other dimensions.
Case 2: All prime factors of V are â‰¤ C
Step 1. Choose the factor, F_1, closest to C. If there’s a choice, choose one arbitrarily.
Step 2. Divide V by F_1 (or P_max from Case 1). Call the quotient Q
Step 3. Find the factors of Q. This refactoring is key.
Step 4. Choose a factor, F_2, of Q “closest” to âˆšQ.
Step 5. Divide Q by F_2 to obtain the final dimension, F_3.
Note that F_2 and F_3 will also be close to C, the cube root of V since Q is approx VÃ·V(^1/3)=V^(2/3), so âˆšQâ‰ˆV^(1/3)!!
A la Fermat, not enough room in this box to prove or demo it! I may post in my blog, MathNotations. However, I did verify it for (2^2)(3^5)(7)(11^4)

166. #### Bob

November 2, 2015 - 2:54 pm -

Didn’t read every post so may have missed this oneâ€¦..

– Obtain the prime factorization and put in descending order.

– Begin filling three bins, A, B, and C by placing the largest prime factor in A, the next largest in B, and third largest in C.

– The next prime factor in descending order will be placed in the bin whose product of prime factors already contained in that bin is the smallest.

– Continue in descending order until all prime factors are binned.

(To handle the cases where there are fewer than three prime factors, start with a 1 in each bin.)

Example: 1260 = 2 x 2 x 3 x 3 x 5 x 7

Bin A: 7 x 2 = 14
Bin B: 5 x 2 = 10
Bin C: 3 x 3 = 9

7, 5 and 3 would go in first. Then the second 3 would go into Bin C with the first 3, then a 2 would go in Bin B with the 5 and the last 2 would go in Bin A with the 7.

If there are two bins with the same product of primes, you could select the “lower” letter (A over B, etc.).

-Bob

January 10, 2016 - 7:35 am -

Hi,

I was looking at the problem and, as many already have, realise it’s based on integer factorisation. In effect what you are doing is finding all integer factorizations of the number and finding the one with the most similar numbers (most cube), as in closest to cbrt(k^3) sides. You want to find an algorithm which can do this quickly (scaling nicely) and works with all integers with no error. In affect what you were trying to find is a Polynomial [P] algorithm for integer factorization.

If the 1000 teachers had been able to solve this problem outright with a Polynomial [P] algorithmn (not brute force – NP) that works for all numbers then they might have earned \$1 million dollars, saved millions of lives and changed our society irrevocably. They would have definitely in the process have made most of the encryption methods used on the internet irrelevant. It is an open problem in the field of computer science by itself (Wikipedia [1] – “Can integer factorization be done in polynomial time on a classical computer?â€.) Granted with this problem it would not have to find all factors of the number just 3 that work but letâ€™s say we had a semiprime number (made by multiplying two primes â€“ Wikipedia [2] â€“ as is used in Public Key Cryptography – Wikipedia [3]) the algorithm;
Letâ€™s say 3 * 5 as both primes produce 15 a semiprime.
If we use this supposed algorithm on it would produce 3 * 5 * 1 as that is the only way you can factor 15.
We can generalise this to any semiprime.
Let a and b be the number multiplied to get the semiprime
When passed through the algorithm we would expect some permutation of (a, b, 1)

In effect we can find the prime factorization of any semiprime. If this algorithm worked fast, it means that public key cryptography which relies on one-way feature of multiplication + factorisation of semiprimes would be broken. This would contribute to another open problem in computer science which is whether one way functions exist: Wikipedia [4] â€“ One-way function.

The reason this might earn \$1-million-dollars and save millions of lives is because: depending on the solution some believe it would also solve P vs. NP which a \$1-million-dollar solution prize is awarded if they find a solution by the clay maths institute as part of their 7 millennium maths problems (Clay-Math [5].) If it did prove P = NP it would mean things like protein folding would be possible instantly (or at least very fast) undoubtedly saving millions of lives. It would mean that hypothetically a computer would be able create a masterpiece in any art form (as currently creating a masterpiece is in effect a brute force for computers which is an NP problem.)

Looking at the responses to this problem currently it seems most of the responses algorithms work with numbers up to a certain value then start faltering. If they want to be able to do this with all numbers with no faults and with an improved brute force – the best algorithm that we have for integer factorization at the moment is the general number field sieve (Wikipedia [6] – GNFS.) If you wanted to solve the problem for this, then you would find all factors for this number with this algorithm and then compare them and choose ones which are closest to together to create the number (closest to cbrt(k^3) sides.)

In effect what I am saying is there is currently no way to create a non-brute force solution that works with all sizes of cuboid without solving the semiprime factorization problem in computer science, something that has been baffling computer scientists and mathematicians alike for centuries.
So in short if the collection of 1000 teachers / various people viewing this on the web had found a fast algorithm to do this then they would have:
– Broken most cryptography used on the web (PKC)
– Contributed to solving whether one-way functions really exist
– Save millions of lives
– Contributed to solving P vs. NP and possibly depending on the algorithm found may have won \$1 million dollars from solving it
– In the process saving society irrevocably â€“ all artistic pieces would be able to be remade using a computer hypothetically
– Made a huge discovery in the field of computer science, computational complexity and mathematics as a whole!
So, if anyone actually finds a fast algorithm for this then seriously tell someoneâ€¦ now!

For those unfamiliar with P vs. NP I recommend this video:
https://youtu.be/YX40hbAHx3s

If you are interested in looking at current challenges related to semiprime factorization:
https://en.wikipedia.org/wiki/RSA_Factoring_Challenge

Please do check this for yourself I am only a secondary school student so may be wrong!

168. #### Jonah

January 10, 2016 - 9:45 am -

George, we’re using different definitions of “easy” and “hard”. I’m happy with an algorithm that’s polynomial in V, the volume of the box, and brute force does that well enough: just try all the triples of numbers less than V (there are only V^3 of them) and see which is best. Cryptographers want (or, perhaps, don’t want) an algorithm that’s polynomial in the *number of digits* of V. I think that’s the source of confusion here.

169. #### Neeraj

January 27, 2016 - 4:11 pm -

For all the above cases my solution is working perfectly fine.

Steps

1) Find all the factors possible for the number

2) Take cuberoot of the given number

3) If it’s not an integer then ceil it to next value.

4) Find all the numbers starting from that number which can perfectly divide that number, if you get a prime number then that’s your first number else the minimum number from all the possible divisors is the first number.

5) Next for remaining 2 numbers divide and find the remaining amount for which we need to solve.

6) Then take the square root, and if it’s not an integer then ceil it to next value.

7) Repeat step 4 and you will get your second number

8) Now you can easily find the third number.

170. #### JoeBod

March 11, 2016 - 11:09 am -

2. Write down all of its prime factors from least to greatest.
3. If there are three or fewer prime factors, your dimensions are pretty easy to figure out.
4. If there are four or more factors, divide by the rounded down and rounded up value of the cube root of the number.
5. If a perfect cube, this is the three dimensions.
6. If neither divisions produce an integer quotient, subtract one from the rounded down value and add one to the rounded up value and divide again.
7. Repeat this step 6 until you find at least one division that produces an integer quotient.
8. If both divisions produce an integer quotient, then these are the first two dimensions.
9. Divide by their product for the third dimension.
10. If only one division produces an integer quotient, then this is the first dimension.
11. Divide by the first dimension and find the square root of the quotient.
12. Divide the quotient by the rounded down and rounded up value of the square root of the number.
13. If a perfect square, this is the second and third dimension.
14. If both divisions produce an integer quotient, then these are the last two dimensions.
15. If one division produces an integer quotient, this is the second dimension.
16. Divide the quotient by the second dimension to find the third dimension.
17. If neither divisions produce an integer quotient, subtract one from the rounded down value and add one to the rounded up value and divide again.
18. Repeat this step 17 until you find at least one division that produces an integer quotient.