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)

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("\
 {",s1,", ",s2,", ",s3,"} with Surface Area =", SA)

print("\
===== End =====\
")

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.

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

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