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)

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.002
Floor is 11, but neither 11 nor 10 divide n.
9 divides n.  s1 = 9
n / 9 = 148
Square root (148) = ~12.166
Floor is 12, but we need to subtract away 1 at a time until we find a divisor of 148: 4.
s2 = 4
Then s3 = 37
And that gives a surface area of 1034.
However, the minimal surface area is given by a solid of 6*6*37.  Surface Area is 960 in that case.
The algorithm also breaks for n=68 and n=74634.
We can see what the algorithm seems to be having trouble with is the first divisor taking too many prime factors along with it.  We do not necessarily want the 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.
Lots of good mathematical practices happening here!
Update: 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.

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