Tetrahedral Numbers
September 13, 2011
Before I started writing my own programming exercises, I enjoyed solving other programming exercises available on the internet, many of them mathematical in nature. Today’s exercise comes from http://open-cs.net/problems.php?id=18 and concerns triangular and tetrahedral numbers.
A triangular number tells the number of ways that balls can be stacked in a triangle. The first triangular number is 1, the second is 3 (a row of 1 plus a row of 2), the third triangular number is 6 (the first two rows plus a row of 3), the fourth triangular number is 10 (adding a row of 4), the fifth triangular number is 15 (think of the 15 balls on a pool table), and so on.
A tetrahedral number is the three-dimensional equivalent of a triangular number; think of cannonballs stacked in a three-sided pyramid. The top layer has one ball, the second layer has 3 balls (the second triangular number) so the second tetrahedral number is 1 + 3 = 4, the third layer has 6 balls giving a total of 10 balls in the tetrahedron, and so on.
Your task is to find the base of the tetrahedron that contains 169179692512835000 balls. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
import Data.List
tria = tail $ scanl (+) 0 [1..]
tetra = 1:zipWith (+) tetra (tail tria)
main = do
let (Just n) = findIndex (==169179692512835000) tetra
putStrLn $ show n
My Haskell solution (see http://bonsaicode.wordpress.com/2011/09/13/programming-praxis-tetrahedral-numbers/ for a version with comments):
[…] today’s Programming Praxis, our goal is to find the base of the three-sided pyramid that has […]
For my Python solution, I wrote a linear search as well as a binary one:
def tetra(n):
return n * (n + 1) * (n + 2) / 6
def prob18_linear(target):
n = 1
while tetra(n) < target:
n += 1
return n
def bin_search(target, func):
lo, hi = 1, 10
while func(hi) < t:
hi *= 10
mid = (lo + hi) / 2
fmid = func(mid)
while fmid != target:
if fmid < target:
lo, mid = mid, (mid + hi) / 2
else:
hi, mid = mid, (lo + mid) / 2
fmid = func(mid)
return mid
def prob18_log(t):
return bin_search(t, tetra)
Sorry for the formatting error, I forgot a second quotation mark. Trying again:
Python 3 added accumulate() to the itertools library, which makes implementing
a linear search a snap.
Inspired by Graham’s binary search, I tried to find a way to use ‘bisect’
from the standard library. The Tetrahedrals class fakes being a list of
tetrahedral numbers by calculating the numbers on the fly based on the index
passed to __getitem__(). This is enough to get bisect() to work when using the
lo and hi parameters.
In Ruby …
We use a lambda to create a tetrahedral function we can pass around specifically to the linear (very slow in this case) and binary (much faster).
;; With binary search. Quite naive.
Optimised/more clean version:
@Mike: very elegant. I was looking for a way to let bisect do the search for me, but didn’t think beyond having a very large list.
all brute force solutions?
here’s one using newton’s method:
and since the theme seems to be keeping it as concise as possible, good luck reading this one
(x^3+3*x^2+2*x)/6 = 169179692512835000; one real root: 1005000
Constant time. Thanks for playing.
quick and dirty solution:
n<-500 #initial length of vector
#b<-20958500
b<-169179692512835000 #number of balls in tetrahedron of interest
for (y in 1:20) {
tri<-1
for (a in 2:n) {
tri<-c(tri,max(tri)+a)
}
dtri<-1
for (a in 2:n) {
dtri<-c(dtri,max(dtri)+tri[a])
}
c<-1
for (a in 1:n) {
if (dtri[a]==b) {
print(a)
c<-a
}
}
if (c==1) {
n<-n*10
}
else {
break
}
}