1
$\begingroup$

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 third layer 5-10 and so on.

$\endgroup$
  • $\begingroup$ Welcome to SciComp! Is this a homework problem? $\endgroup$ – Geoff Oxberry Apr 8 '15 at 0:26
  • 2
    $\begingroup$ Are you talking about a set of spheres stacked in a close-packed (tetrahedral) arrangement? If so the question is very confusingly worded. Should "fifth layer" be "third layer"? Should "4-10" be "5-10"? $\endgroup$ – Doug Lipinski Apr 8 '15 at 3:18
  • 1
    $\begingroup$ oeis.org/A000292 -- highlight of the page is this sentence: a(n) is the number of gifts received from the lyricist's true love up to and including day n in the song "The Twelve Days of Christmas". $\endgroup$ – Federico Poloni Apr 8 '15 at 8:31
  • $\begingroup$ @GeoffOxberry no. I am trying to make a way of indexing the i'th combination of all combinations of something without making a list of all combinations. If i am able to find x,y,z (on a tetrahedron) of an index from 1 - max balls(each ball representing a combo) than I can construct the combination. $\endgroup$ – James Beezho Apr 8 '15 at 21:52
1
$\begingroup$

Rootfinding is probably the most computationally efficient way to find the layer in which a ball $i$ resides in a close-packed tetrahedral arrangement. Assume the balls are labeled consecutively such that balls increase as the layer number increases, so that layer 1 corresponding to the topmost ball (i.e., ball 1), layer 2 is beneath layer 1 (balls 2-4), layer 3 is beneath layer 2 (balls 5-10), and so on.

Since the number of objects in an $n$-layer tetrahedron is $T_{n} = n(n+1)(n+2)/6$, if $m$ satisfies $T_{n-1} < m \leq T_{n}$, ball $m$ is in layer $n$, with the convention that $T_{0} = 0$. This observation suggests the following procedure: solve $n(n+1)(n+2)/6 = m$ for $n$. Then $\lceil{n}\rceil$ (the ceiling of $n$) will be the layer number containing ball $m$.

In certain applications, you might instead want to store a sequence of tetrahedral numbers (according to the formula above) and then perform a table lookup instead of using rootfinding.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.