5: We are given $n$ identical cubes, each of size $1 \times 1 \times 1$. We arrange all of these $n$ cubes to produce one or more congruent rectangular solids, and let $B(n)$ be the number of ways to do this. For example, if $n=12$, then one arrangement is twelve $1 \times 1 \times 1$ cubes, another is one $3 \times 2 \times 2$ solid, another is three $2 \times 2 \times 1$ solids, another is three $4 \times 1 \times 1$ solids, etc. We do not consider, say, $2 \times 2 \times 1$ and $1 \times 2 \times 2$ to be different; these solids are congruent. You may wish to verify, for example, that $B(12)=11$.
Find, with proof, the integer $m$ such that $10^{m}<B\left(2015^{100}\right)<10^{m+1}$.
Solution: The exact value of $B\left(2015^{100}\right)$ is $921,882,251,894,177$. Thus $m=14$.
Let us estimate $B(n)$. First we note that the actual primes do not matter, just the exponents. Since $2015=5 \cdot 13 \cdot 31$, we need to find $B\left(p^{100} q^{100} r^{100}\right)$, where $p, q, r$ are distinct primes.

Let's first try an easier case: $n=p^{3} q^{3} r^{3}$. For each divisor of $n$, there will be one or more different "formations" of congruent rectangular solids. For example, we could take the divisor $d=p^{2} q r$ and one possible formation would be $d$ solids, each with dimensions $p \times q \times q r^{2}$.

So each formation is a sort of 4-tuple, where the first coordinate is $d$, the number of solids, and the remaining three "coordinates" are the dimensions of the solid. In our example, the formation is the sort-of 4-tuple
$$
\left(p^{2} q r ;\left\{p, q, q r^{2}\right\}\right) .
$$

We call it a "sort-of" 4-tuple and use funny notation because the last three "coordinates" are an unordered trio, but the first coordinate-the number of solids-matters; it belongs in the first spot.

Making things even worse, each number $p^{a} q^{b} r^{c}$ in our pseudo-4-tuple corresponds to an ordered triple $(a, b, c)$ of exponents, where $0 \leq a, b, c \leq 3$. The example above is thus represented by
$$
((2,1,1) ;\{(1,0,0),(0,1,0),(0,1,2)\}) \text {. }
$$

It is confusing, however, to combine ordered and non-ordered reasoning, so let us suppose, temporarily, that the order of the three dimension triples $\mathrm{n}$ the psudo-4-tuple does matter. In fact, let's assume that the order matters for all 4 triples. Then our pseudo-4-tuple (of ordered triples) becomes a genuine ordered 4-tuple of ordered triples. Thus the following 4-tuples are considered to be different:
$$
\begin{array}{l}
((2,1,1) ;(1,0,0),(0,1,0),(0,1,2)), \\
((2,1,1) ;(0,1,0),(0,1,2),(1,0,0)), \\
((0,1,0) ;(2,1,1),(1,0,0),(0,1,2)) .
\end{array}
$$

Notice that the first two actually represent the same formation, but the last one is different.
This makes the counting much easier. For the divisor $d$ with exponents $(a, b, c)$, the possible dimensions are the three vectors
$$
\left(a_{1}, b_{1}, c_{1}\right),\left(a_{2}, b_{2}, c_{2}\right),\left(a_{3}, b_{3}, c_{3}\right),
$$
where
$$
\begin{aligned}
a+a_{1}+a_{2}+a_{3} & =3, \\
b+b_{1}+b_{2}+b_{3} & =3, \\
c+c_{1}+c_{2}+c_{3} & =3
\end{aligned}
$$

Each of these three equations represents a solution to a classic ball-and-urn counting problem with four distinguishable urns (since there are four terms) and three balls (since the sums are all equal to 3). For example, the number of ordered solutions to the first equation is the number of ordered 4-tuples $\left(a, a_{1}, a_{2}, a_{3}\right)$ with coordinates adding to 3, and there are $\binom{6}{3}$ such 4-tuples.
Since we can pick solution 4-tuples for each of the three equations independently, there are $\binom{6}{3}^{3}$ different ordered solutions (ordered 4-tuples of ordered triples). For example, one solution may be
$$
((2,1,1) ;(1,0,0),(0,1,0),(0,1,2)) \text {. }
$$

However, we are currently counting each of the 4 ! permutations of these as different. We want to order the count by the first triple (after all, this first triple indicates the number of blocks in the formation), but we do not want to count order among the other three triples.
Consequently, we just divide our current count by 3!, getting
$$
\frac{\binom{6}{3}^{3}}{6} .
$$

This is not an exact value (in fact, it is not even an integer), because it improperly accounts for solids where two or more of the dimensions are equal. For example, suppose that the number of solids is $p r q$ and the dimension of each of the the solids is $p r \times p r \times q^{2}$. Thus the first triple (for the number of solids) is $(1,1,1)$, and the three next triples (for the dimension) are $(1,0,1),(1,0,1)$, and $(0,2,0)$. These three triples do not have 6 different permutations, since two are equal; they have just 3 different permutations. Likewise, if the last three triples were the same (for example, if the dimensions of the solid was $p q \times p q \times p q$ then there is only one ordering of these three triples.

In the more general case, where $n=p^{t} q^{t} r^{t}$, our approximation would yield the formula $\binom{t+3}{3}^{3} / 6$, which slightly misses the exact value. We say "slightly," because the the formula is a degree-9 polynomial whose first term is $t^{9} / 1296$, but the number of formations for which there are two equal dimensions would be a polynomial of degree 6 and the number of formations for which there are three equal dimensions is a polynomial of degree $3 .{ }^{1}$

Thus for large values of $t$, the first term $t^{9} / 1296$ completely dominates. Plugging in $t=100$ yields $10^{18} / 1296$, which is approximately $10^{15}$.