## Dandy Candies and OEIS

Dan has an quite successful open problem going on over at his blog.

If I give you some cubical candies, what is the least amount of packaging needed for them?

Lots of great problem solving happening in the comments of his thread. I took a few stabs at it myself. Beginning with making a list of the first few entries and trying to find solutions manually. 1 candy, (1,1,1) cube: surface area 6. 3 candies can be done with (3,1,1). Surface area 14. But something like 20 has a few options. (10,2,1) has a surface area of 64 but (5,2,2) has a surface area of 48.

From that paper-work I was able to generate the beginning of this sequence of minimal Surface Areas: 6, 10, 14, 16, 22, 22, 30, 24… which I then searched on OEIS, resulting with https://oeis.org/A075777 .

I then decided it would be a good exercise in rudimentary python to try to encode that algorithm, so here is my script:* *

*( caution: this script generates inaccurate results, it is a script of the inaccurate OEIS algorithm. My improved script is further down in this post)*

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
import math while 1==1: #input n = input("How many candies? n=") n = int(n) s1_0 = int(math.floor(n ** (1 / 3.0))) print("s1_0 = ", s1_0) s1 = s1_0 while n % s1 > 0: s1 = s1 - 1 print(s1) print("Side 1 = ",s1) s1quot = int(n/s1) # quotient of candies divided by first side s2_0 = int(math.floor(math.sqrt(n/s1))) print("s2_0 = ", s2_0) s2 = s2_0 while s1quot % s2 > 0: s2 = s2 - 1 print(s2) print("Side 2 = ",s2) s3 = int(n / (s1 * s2)) print("Side 3 = ",s3) SA = 2*(s1*s2 + s1*s3 + s2*s3) print("\n {",s1,", ",s2,", ",s3,"} with Surface Area =", SA) print("\n===== End =====\n") |

This algorithm is very similar to some that others were using in Dan’s comment thread. But here’s where it gets interesting. Unless I have an error in my code (entirely possible!) then I think we have broken this algorithm. Dan gives a few frequent algorithm-breaking-numbers here. And indeed, a few of these break the algorithm on OEIS:

Take n = 1332 using the algorithm described on OEIS:Cube root is ~11.002Floor is 11, but neither 11 nor 10 divide n.9 divides n. s1 = 9n / 9 = 148Square root (148) = ~12.166Floor is 12, but we need to subtract away 1 at a time until we find a divisor of 148: 4.s2 = 4Then s3 = 37And that gives a surface area of 1034.However, the minimal surface area is given by a solid of6*6*37.Surface Area is 960in that case.

*largest*divisor of n under the cube root. I’m in the process of notifying OEIS (I need an account!) unless anyone sees a mistake on my part.

*I improved the algorithm so that it loops through s1s under the cube root that divide n and s2s under the square root of n/s1. This is much slower, but should be accurate.*

**Update:**
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
def minSArectprism(n): s1_0 = int(math.ceil(n ** (1 / 3.0))) minSA=-1 s1 = s1_0 while s1>=1: while n % s1 > 0: s1 = s1 - 1 s1quot = int(n/s1) s2_0 = int(math.ceil(math.sqrt(n/s1))) s2 = s2_0 while s2>=1: while s1quot % s2 > 0: s2 = s2 - 1 s3 = int(n / (s1 * s2)) SA = 2*(s1*s2 + s1*s3 + s2*s3) if minSA==-1: minSA=SA else: if SA<minSA: minSA=SA s2 = s2 - 1 s1 = s1 - 1 return minSA |

Here is a file for the results of this up to 5000: minSA csv up to 5000

And here’s one up to 30000 with columns n, s1, s2, s3, minSA: min surfacearea SF upto 30000

Nice catch! Your algorithm can run 40% or so faster if you remove the ‘while’ loop in lines 11 and 21; it’s safe to pick the pair {s2, s3} closest to the square root of area.

Sweet thanks! Yes, now I see how lowering s2 through the divisors will only increase the surface area. That’s probably a nice little thing to explore with students too.