How to pack a sphere with cubes?

I read a little bit about packing spheres into cubes, but I imagine the problem changes drastically when trying to fill a sphere with unit cubes. For example, how many unit cubes could one fit into a sphere of radius five? Clearly the upper limit would be $\left \lfloor \frac{4}{3}\pi \cdot 5^3 \right \rfloor$, but I imagine there will be plenty more empty space than just a small fraction of a cube.

While there is no obvious reason in general to expect the optimal solution to be a simple, closely-packed formation, there are grounds for thinking that this is more likely in the case of radius 5 (diameter 10). Suppose we look for a formation of overlapping cuboids, each centred at the centre of the sphere, the whole formation being symmetric in three orthogonal directions (in other words, invariant under any series of right-angle rotations). The maximum possible length of a cuboid that fits within a sphere of diameter 10 is 9. Since this is an odd integer, we consider formations having a cube with its centre at the centre of the sphere (rather than those with 8 cubes sharing a vertex at the centre of the sphere). For symmetry as described, this requires cuboids with odd integer dimensions, at least two of the dimensions being equal.

Using Pythagoras’s Theorem to find the long diagonal of a cuboid, and since the sum of three odd squares is odd, no such cuboid can have a long diagonal of length 10. By trial and error, or using Brahmagupta’s Identity given that:

$$99 = 11 \times 9 = (3^2 + 2(1^2))3^2 = (3^2 + 2(1^2))(1^2 + 2(2^2))$$

there are, remarkably, three such cuboids with long diagonal $\sqrt{99}\approx9.9499$, namely:

$$9 \times 3 \times 3 \qquad 7 \times 5 \times 5 \qquad 1 \times 7 \times 7$$

This suggests a formation of nine overlapping cuboids, comprising three of each of the above sizes. One way to describe the formation and count its cubes is as follows:

1. Start with a cube of side 5, centred within the sphere (125 cubes).

2. On each of its faces, add a 5 x 5 block of cubes (plus 6 x 25 = 150 cubes). This gives the three 7 x 5 x 5 cuboids. The result can also be described as a cube of side 7, but with all cubes along its edges missing.

3. Add 1 cube at the middle of each of the above “missing edges” (plus 12 cubes). This gives the three 7 x 7 x 1 cuboids.

4. In the centre of each of the main 5 x 5 faces of the resulting solid, add a 3 x 3 block of cubes (plus 6 x 9 = 54 cubes). This gives the 9 x 3 x 3 cuboids.

The resulting formation contains 125 + 150 + 12 + 54 = 341 cubes.

Perhaps this is not optimal for a sphere of radius 5, but the fact that each vertex of each of the nine cuboids (72 points in all) is within $(10-\sqrt{99})/2\leq0.026$ of the surface of the sphere suggests that it may be hard to beat.

Update 16 March 2017 The above solution turns out not to be optimal. Note that it arranges the cubes, along each of three orthogonal axes which will be called X, Y and Z, into nine "slices", each of one cube thickness. The configuration of the second and eighth slices along each axis (six slices in all) is as below.

Two extra cubes can be added in each slice by sliding two rows of cubes a distance of half a cube length, producing the configuration below.

To make this possible on each of the six faces, care is needed to avoid a change in one slice blocking a change in a face at right angles to it. One way to achieve this is:

1. For the two slices in the X-Y plane, slide rows parallel to the X axis.
2. For the two slices in the Y-Z plane, slide rows parallel to the Y axis.
3. For the two slices in the X-Z plane, slide rows parallel to the Z axis.

In terms of overlapping cuboids, this gives three 7 x 6 x 3 cuboids, centred at the centre of the sphere, with long diagonals of length $\sqrt{94}<10$.

Altogether, this adds 6 x 2 = 12 cubes.

The first and ninth slices on each axis consist of a 3 x 3 block of cubes. In a similar way, a cube can be added to each block by sliding a central row of three cubes half a cube length. The resulting extra cuboids have dimensions 9 x 4 x 1, with long diagonal $\sqrt{98}<10$. This adds a further 6 cubes.

The formation resulting from these changes has 341 + 12 + 6 = 359 cubes.