Layer on which ball belongs in tetrahedron

Question

What is the most computationally efficient way to find the layer on which a ball (i) belongs when arranged in a tetrahedron or 3 dimensional triangle with a triangular base. The ball on the top layer is numbered one. The balls on the second layer are numbered 2 - 4. The fifth layer 4-10 and so on.

Answer 1

The numbers corresponding to complete tetrahedra are called (unsurprisingly) tetrahedral numbers, the $n$th tetrahedral number being given by

$$ T_n = \binom{n+2}{3} $$

If you have $m$ balls, therefore, you could do a quick-and-dirty estimate of the number of layers required to get to the $m$th ball by computing

$$ L_{est}(m) = \lfloor \sqrt[3]{6m} \rfloor $$

In most cases, I think this will work. For instance, anywhere between $21$ and $35$ balls require five layers, and sure enough, the floor of the cube root of any number between $126$ and $210$ is indeed $5$.

The answer will occasionally be higher. For instance, $57$ balls require a seventh layer, but the floor of the cube root of $342$ is $6$. This seems like a reasonably fast way to get close, though.

Answer 2

Background: The number of balls on layer $n$ is the $n$th triangle number $$ t_n = 1 + 2 + \cdots + n = \frac{n(n+1)}{2} = \binom{n+1}{2}, $$ and the total number of balls up to and including the $n$th layer is the $n$th tetrahedral number $$ T_n = t_1 + t_2 + \cdots + t_n = \frac{n(n+1)(n+2)}{6} = \binom{n+2}{3}. $$

You question: given positive integer $i$, find the unique positive integer $n$ such that $$ T_{n-1} < i \le T_n. $$ From the inequalities $$ \frac{(n-1)^3}{6} < T_{n-1} \quad\text{and}\quad T_n < \frac{(n+1)^3}{6} $$ we have $$ \begin{align} (n-1)^3 < 6i &< (n+1)^3 \\ n-1 < \sqrt[3]{6i} &< n+1, \end{align} $$ which by rounding will get you $n$ within one. Then just check $T_n$.

---

Example: Say $i = 1\,000\,000$. Then, $\sqrt[3]{6i} = 100\sqrt[3]{6} \approx 181$. (I rounded down.) Now, $$ T_{181} = 1\,004\,731 $$ and $$ T_{180} = 988\,260, $$ so the millionth ball is on the $181$st layer.