Building a Pile of Cubes

I was playing with some code challenges today and found one called "Building a Pile of Cubes."

My favourite code challenges are those which can be solved naively with a bunch of code, but have some clever shortcut which require applying a bit of mathematics, which is why I found this one to be enjoyable!

The general idea is that we are building a tower made of \(n\) cubes where we are given the total volume of the tower, \(V\). The base block of our tower should have a volume of \(n^3\), the next with a volume of \((n-1)^3\), and so forth until the top block which should have a volume of \(1^3\). We are tasked with finding \(n\) if it is possible to match the construction pattern with the total volume, \(V\).

As we know, by definition, a cube has equal length, width, and breadth, and we can compute the volume, \(v\), of a cube with side \(\ell\) by multiplying the length, width, and breadth,

\[ v = \ell \cdot \ell \cdot \ell\,. \]

There is a simple top-down coding solution that can be applied by starting with \(k = 1\), iteratively increasing \(k\) by \(1\), and retaining the total sum of each additional volume until the total volume has been reached. If the final sum equals the provided volume, then we have found the number of blocks.

function naive_cubepile(V)
    n = 1
    s = n
    while s < V
        n += 1
        s += n^3
    end
    return s == V ? n : nothing
end

However, there is a much more efficient way to solve this challenge.

Restating this mathematically, if \(V\) is the total volume of our pile and,

\[ V = \sum_{k = 1}^n k^3\,, \]

then the solution is \(n\).

By partial sum formulas, we can re-write \((2)\) as,

\[ V = \sum_{k = 1}^n k^3 = \frac{1}{4} n^2 ( n + 1 )^2\,,\]

therefore we are looking for solve for \(n\) given,

\[ V = \frac{1}{4} n^2 ( n + 1 )^2\,.\]

With some simple algebra, \((4)\) is re-written into quadratic form,

\[ n^2 + n - \sqrt{4V} = 0\,, \]

which is easily solved using the quadratic formula.

Our final function is therefore,

function cubepile(V)
    n = (sqrt(1 + 8 * sqrt(V)) - 1) / 2
    n == floor(n) ? Int(n) : nothing
end

@time cubepile(1071225)
>  0.000000 seconds
@time cubepile(4183059834009)
>  0.000000 seconds
@time cubepile(135440716410000)
>  0.000000 seconds

@time naive_cubepile(1071225)
>  0.000001 seconds
@time naive_cubepile(4183059834009)
>  0.000001 seconds
@time naive_cubepile(135440716410000)
>  0.000003 seconds