I had an answer before, but I looked into it a bit more and my answer was incorrect so I removed it. This link may be of interest: Circle Packing in a Square (wikipedia)
It was suggested by KennyTM that there may not be an optimal solution yet to this problem in general. Further digging into this has shown me that this is probably correct. Check out this page: Circle Packing - Best Known Packings. As you can see, solutions up to only 30 circles have been found and proven optimal. (Other higher numbers of circles have been proven optimal, but 31 hasn't)
Note that although problem defined on the wikipedia page and the other link is superficially different than the question asked here, the same fundamental question is being asked, which is "what is the most efficient way to pack circles in a square/rectangle container?".
...And it seems the answer is "we don't really know" :)
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:
Start with a cube of side 5, centred within the sphere (125 cubes).
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.
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.
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:
- For the two slices in the X-Y plane, slide rows parallel to the X axis.
- For the two slices in the Y-Z plane, slide rows parallel to the Y axis.
- 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.
Best Answer
You can read a lot about these questions on Wikipedia.
Concerning the random version, there are some links at Density of randomly packing a box. The accepted answer links to a paper that "focuses on spheres".