## Tetrahedral Numbers

### September 13, 2011

Our first function calculates triangular numbers:

`(define (tri n)`

(let loop ((n n) (s 0))

(if (zero? n) s

(loop (- n 1) (+ s n)))))

Alternately, you may recognize Gauss’ formula for the sum of the first n integers:

`(define (tri n) (* n (+ n 1) 1/2))`

Then we can calculate tetrahedral numbers as the sum of triangular numbers:

`(define (tet n)`

(let loop ((n n) (s 0))

(if (zero? n) s

(loop (- n 1) (+ s (tri n))))))

We won’t show the derivation, but the recurrence has a closed form:

`(define (tet n) (* n (+ n 1) (+ n 2) 1/6))`

Then binary search can calculate the desired result:

`(define (prob-18 n)`

(let loop ((lo 1) (hi 2))

(if (< (tet hi) n)

(loop hi (* hi 2))

(let loop ((lo lo) (hi hi))

(let* ((mid (quotient (+ lo hi) 2))

(tet-mid (tet mid)))

(cond ((< tet-mid n) (loop mid hi))

((< n tet-mid) (loop lo mid))

(else mid)))))))

And the answer is:

`> (prob-18 169179692512835000)`

1005000

We’ll let the mathematicians in the group figure out how this works:

`> (floor (expt (* 6 169179692512835000) 1/3))`

1005000.0

You can run the program at http://programmingpraxis.codepad.org/6ZT1RVxa. If you’re interested in the math behind what we have done, see Sloane’s A000292.

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

}

}