A lattice of octahedra and tetrahedra (oct-tet lattice) is a useful paradigm for understanding
the structure of Pascal's pyramid, the 3-D analog of Pascal's triangle. Notation for levels and coordinates of
elements, a standard algorithm for generating the values of various elements, and a ratio method that is not dependent
on the calculation of previous levels are discussed. Figures show a bell curve in 3 dimensions, the association
of elements to primes and twin primes, and the values of elements mod(x) through patterns arranged in triangular
plots. It is conjectured that the largest factor of any element is less than the level index.
This 22K article contains illustrations and animations that are quite large.
These files can take a few minutes to download if you access the Internet with a modem or slow connection.
Pascal's Pyramid Or Pascal's Tetrahedron?
I. Introduction
In a 1966 Scientific American column, Martin Gardner mentions in passing that there are, ". . . endless variants
on the [Pascal's] triangle, and many ways to generalize it, such as building it in tetrahedral form to give the
coefficients of trinomial expansions."
One of the illustration of Pascal's triangle, included with that article shows the first 100 rows of the triangle
with odd and even numbers represented as dots. The pattern of dots representing odd and even numbers in the two
dimensional Pascal's triangle correspond to the octahedral and tetrahedral sections of an oct-tet lattice (see
figures 1 and 2). The octahedron faces of the lattice map to the even dots while the tetrahedron faces map to the
odd dots.
If we construct a three dimensional Pascal's triangle will the distribution of odd and even values for the elements
in the interior correspond to the octahedral and tetrahedral components of an oct-tet lattice?
A Galton board simulation, rolling marbles through a triangular maze, generates values that approximate the values
of coefficients of a binomial expansion. At each fork in the maze the marble has a 50-50 chance to go either way
until it falls into bins at the bottom of the maze in proportions that roughly approximate a bell-shaped curve.
The Galton Board can be simulated with a computer program that is a variation of the one used to generate the 3-D
analog of Pascal's triangle.
II. Precursors
Stephen Mueller published a paper in 1969 on Recursions Associated With
Pascal's Pyramid. In Mueller's definition, "Pascal's pyramid is the three-faced
pyramidal array of coefficients in the expansion of the trinomial, (a+b+c)j, such that the coefficients
of (a+b+c)j are systematically placed beneath those of (a+b+c)j-1, resulting in a Pascal
triangle on each of the three faces." Mueller labels the initial plane, containing one term, as level 0 (see
figure 3) which turns out to be a good choice of notation. Terms on higher levels are expressed as the product
of two binomial coefficients.
John Staib and his son Larry published The Pascal Pyramid in 1978. Like Mueller, the Staibs also used a stack of successively larger triangles to form a pyramid
(seefigure 3). They developed a coordinate notation for each point on each triangular level, a system for determining
which of the small triangles were centered above a point on the next level, that the sums of the trinomial coefficients
associated with the vertices of an upper triangle were equal to the trinomial coefficient found directly below
that triangle, that a trinomial expansion could be generalized from a binomial expansion and that a BASIC computer
program could be written to generate the coefficients of (x+y+z)n in the form of layers of a pyramid. In a 1938 book, Steinhaus gives a short example of a method of determining
winners in a three way election with a similar notation except that he breaks the triangle into hexagonal cells.
In 1986, Bollinger attempted to lay pyramid power to rest with, "It would seem that in spite
of the appeal of an array for multinomial coefficients similar to the triangle for binomials, one is better off
for most purposes using a convenient algorithm to generate the m-part compositions of n, from which the exponents
on the xi and the multinomial associated with a given term
are immediately available."
III. The Proper Paradigm
Two key concepts needed for a clearer understanding of the 3-D analog of Pascal's triangle are
missing from these earlier works.
Figure 4
First, the octahedron-tetrahedron lattice is a more accurate 3-D analog for the 2-D Pascal's
triangle. A triangular base pyramid is descriptive of outward shape but lacks any ability to illuminate the interconnectedness
of multiple subdivisions. The levels of the 3-D analog of Pascal's triangle are connected by an octahedron-tetrahedron
lattice. Some of the tetrahedra are oriented with a point up and some with a face up (see figure 4). Loeb states
it clearly:
"It is not possible to fill space with regular tetrahedra [or pyramids] only; four tetrahedra
and an octahedron are necessary to produce a tetrahedron having eight times the volume (twice the linear dimension)
of the original tetrahedron."
In order to fill space octahedra are used in combination with tetrahedra (see figure 1). Subdividing
the pyramid into these two components makes it a simple task to model the 3-D analog of Pascal's triangle.
Secondly, Pascal's pyramid (or tetrahedron) can be modeled with ordinary Cartesian coordinates.
A tetrahedron is point-for-point congruent to a cube-corner (see figure 5). If you visualize the X, Y, and Z axes
as the three legs of a collapsible photo tripod, the transformation from cube corner to oct-tet lattice is as like
changing the angle between legs from 60 to 90 degrees. As you raise the tripod the legs get longer but the angles
between them grow more acute.
IV. The Octahedron-Tetrahedron Lattice
Like Bollinger [6], Staib and Staib [4] state that, ". . .the three-dimensional nature of
the Pascal pyramid makes it awkward to use for hand calculating the trinomial coefficients." Staib and Staib
[4] and Mueller [3] both use illustrations of pyramids containing planes and levels with no interconnections between
levels. Drawing a tetrahedron, let alone a subdivided tetrahedral lattice can be hard. Without actual physical
models it can be daunting to visualize how tetrahedra in combination with octahedra might provide the needed paradigm
for interconnecting the pyramid's levels (see figure 3 and 4). Oct-tet lattices are also harder to picture in two-dimensioned
figures and illustrations because most of our drawing conventions are based on viewing cubic forms.
Looking for patterns among 2 or 3 thousand forty digit numbers is not easy work. "Computer
graphics is an excellent method by which patterns in Pascal's pyramid can be made obvious to both the mathematician
and interested layperson," according to Pickover and Khorasani . The figures in the following sections are
computer generated visualizations that highlight certain information while masking other things. To decide if a
50 digit number is odd or even we only need to examine one digit, the last one.
The oct-tet lattice provides not only a mental model but also a physical model of a 3-D analog
of Pascal's triangle. A group of small models made of toothpicks, soda straws, or cardboard can prove useful in
order to "think" about tetrahedra.
V. Basic Notation
The notation in figure 6 is suitable, it agrees closely with Staib and Staib's notation for coordinates
on any level while it uses Mueller's scheme for numbering the levels. The first level is set at zero. This is convenient
because the value of the second element in the first row at higher levels is equal to the level and the sum of
the coordinates for each point on a level is equal to the level index.
Any row in Pascal's triangle yields the coefficients of a binomial expansion. A plot of the coefficients
gives us the familiar, flat, two dimensional "bell" curve. This normal distribution can be modeled with
a Galton Board simulation or with a series of heads or tails coin tosses, each with a probability of 1/2.
The triangular levels of the 3-D analog yield the coefficients of trinomial expansions. A plot
of the coefficients gives us a three-dimensional "bell" curve (see figure 7 and 8). The 3-D version can
also be modeled. By constructing the edges of the octahedra and tetrahedra in an oct-tet lattice with hollow tubes
it would be possible to construct a working 3-D version of a Galton Board. Here we would have a series of decisions
with three possible outcomes, each with a 1/3 probability.
Figure 7.
A three dimensional bell curve. Level 74 of Pascal's Tetrahedron
The three edge rows of the 3-D "bell" curve (see figure 7) and the three flat faces
of the log plot (see figure 8 which shows log plots of values for 6 different levels) are 2-D "bell"
curves. The elements on three of the four faces of the tetrahedral 3-D analog are the same as the elements of the
2-D Pascal's triangle. Pascal's triangle is contained in the 3-D version.
Figure 8.
Log plot bell curve for 6 levels of Pascal's Tetrahedron
B. Factoring Elements
It appears that each element of a level factors into values that are less than the level number
(click for proof). A random example.
The value of the central element on level 1152 is a 547 digit number (click
to see figure 9). It has 227 factors, the largest being 1151. This 547 digit number has
factors that included 85% of the primes below it's level index of 1152 (click to see
figure 10).
It took 23 hours to come up with this central element's value and another 11 hours to factor
it, on a standard IBM PC. For example, Pomerance states, ". . . factoring is hard. It has been estimated conservatively
. . . that to factor certain composite n with 75 decimal digits, using the fastest factoring algorithm known on
an imaginary computer faster than any now in existence would take about 15 weeks. For certain numbers with 100
digits it could take a life time." The elements of the 3-D analog of Pascal's triangle are exceptions to Pomerance's
statement.
The numbers mentioned above are so large that few personal computer languages can handle them.
The True BASIC language along with two language
extension packages, the 3-Dimensional Graphics and the Mathematician's Toolkit, were used to compute the examples in this article.
The Hugelib library allows for arithmetic of arbitrary precision, up to 100,000 digits by packing numbers into
strings.
C. Odds and Evens
A number of interesting 2-D (and 3-D) patterns can be generated by representing the values
of the elements of a level with colored dots. These are similar to the patterns of odd and even distribution within
Pascal's triangle . In the 3-D analog the odds and evens are distributed into octahedral and tetrahedral components.
When we plot the distributions of other multiples for various levels we obtain other interesting patterns (see
figure 11).
True BASIC Program to generate Mod Plots of Pascal's Tetrahedron Element
Values
Figure 11
A screen shot of level 128 - modulus 2 showing odd and even numbers resembles a Sierpinski gasket
The mod(2) patterns for the slices of levels 7, 15, 31, 63, 127 . . . are the same at the patterns
for the three "exterior" faces of the tetrahedron (see figure 2). For a tetrahedron that is one level
less than a power of two, all four faces have the same pattern.
D. Plus or Minus One Primes
The values of the elements of this 3-D analog of Pascal's triangle factor into many small
primes, they are divisible by a high percentage of integers (level 75 element values). These same element values
plus or minus one have few divisors and few factors. Upon investigation we find that many of them are prime. Many
elements are one more or less than a prime number. Some are between twin primes (see figure 12).
Because computer languages for personal computers can handle about 15 significant digits you can calculate values
for elements up to about level 35 in a straight forward manner. Program and array size limitations in many popular
languages such as BASIC limit exploration of the 3-D analog of Pascal's triangle to the first 18 levels. Brute
force factoring methods also become unbearably time consuming at these levels.
Figure 12 a
A visualization of level 129 of Pascal's Tetrahedron. Elements are color coded.
A red dot is an element that is between twin primes
A green dot is an element that is one less than a prime number
A blue dot is an element that is a prime number plus 1
To explore above level 18 I switched from using brute force factoring as a prime test to using Fermat's
Little Theorem with a base of 2 as a composite test. This can be stated: if bn - b is a multiple of n, then n is a composite number. Above level 18 the composites I've identified are
composite, the primes are another story. Some might be pseudoprimes, some might be Charmichael numbers. It will
take more than a personal computer to be able to tell which is which.
There have been some estimates of the number of pseudoprimes. "The scarcity of pseudoprimes
to the base 2 among all the numbers smaller than 20 billion suggests that any number that passes the Fermat test
to base 2 is likely to be prime," according to Pomerance . Of course a good proportion of the values from
the 3-D analog of Pascal's triangle that I've looked at are above Pomerance's 20 billion limit. The central values
of level 74 are approximately 3.4x1034.
Exploration above level 18 would benefit from faster algorithms and computer systems that are more
powerful. Since any element, from one of the levels of the tetrahedral array, is easy to factor (all factors have
been less than the level index for every element factored to date). It might be possible to use Dixon's algorithm
which is based on a complete factorization of n-1, or other newer algorithms based on partial factorizations of
n-1 or n+1.
Figure 12c
The six elements of Pascal's Tetrahedron coded in blue at the very center of level 255 are 120 digits numbers.
I've broken that number into groups of ten digits for ease of inspection:
If you subtract one from this 120 digit number (change the final 5000 to 4999 you get a prime number). The ASCII
text file listing the elements of level 255 is over 300 pages long.
Figure 12d - Quicktime animation
Click below to view a 3,125 Kilobyte Quicktime animation (320 by 240) of primes on levels 1 to
150
similar to the 3-D illustration above. You might need to save this to disk and then open it with Quicktime. I'm
just learning this stuff.
The first line of code sets point(0,0,0) equal to 1 by definition. Next we assign a value of
1 to any point (on a vertex) that has 2 coordinates of zero.
If an element is not the initial point or a vertex point then we check to see if it's on the tetrahedral face.
If it is we sum the two values from the level above for any element that is on the edge of a level. The final ELSE statement assigns a value for all the points not
on an edge or vertex, setting them equal to the sum of the 3 elements from the level
above.
Let PT(0,0,0) = 1
FOR level = 1 TO top
FOR x = level TO 0 STEP -1
FOR y = (level - x) TO 0 STEP -1
FOR z = (level - (x+y)) TO 0 STEP -1
IF x = 0 AND y = 0 OR x = 0 AND z = 0
OR y = 0 AND z = 0 THEN
LET pt(x,y,z) = 1
ELSE IF x = 0
LET pt(x,y,z) = pt(x,y-1,z) + pt(z,y,z-1)
ELSE IF y = 0 THEN
LET pt(x,y,z) = pt(x-1,y,z) + pt(z,y,z-1)
ELSE IF x = 0 THEN
LET pt(x,y,z) = pt(x-1,y,z) + pt(z,y-1,z)
ELSE
LET pt(x,y,z)=pt(x-1,y,z)+pt(x,y-1,z)+pt(x,y,z-1)
NEXT z
NEXT y
NEXT z
NEXT level
F. An Alternate Algorithm
In order to explore above level 18 of the 3-D analog of Pascal's triangle on a PC it is necessary
to use a language that uses more than 64K of memory and can handle more than 16 digit integers. Since each level
is dependent on only one previous level it would also be possible to explore higher levels if we could find an
algorithm that made more sparing use of computer memory.
Alternating between two flat arrays rather than creating one large cubic array would be one solution.
The drawback is that it would involve lots of coordinate manipulation. On the other hand mapping an octahedron-tetrahedron
lattice onto the standard x,y,z cubic coordinate system is wasteful of computer memory because we can only store
5456 elements in the 27,000 storage locations in an array 30 by 30 by 30.
Another method of reaching higher levels in the 3-D analog of Pascal's triangle (also true of
Pascal's triangle) is based on the fact that each element of the tetrahedral array is related by a simple whole
number ratio to the 12 elements around it (see figure 13). The value of any element can be calculated from any
one of it's neighbors. We can start at any vertex element (which has a value of 1, by definition) on any level
and apply a ratio calculation, proceeding from element to element, each time incrementing the denominator and decrementing
the numerator of the interval ratio by 1. Using this system the need for array storage is cut drastically.
Figure 13
Each element of Pascal's Tet is related to every other element by a simple ratio. Also note the relationships
between ratios going across and up and down.
Even with shortcuts, the time needed to calculate the values of elements and run the Fermat test
quickly rises (figure 14 is not on WWW). Level 75 took 7 hours to compute on a personal computer with a 10 megahertz
80286 processor. For the first 75 levels the ratio of primes that are equal to the value of an element plus or
minus 1 appears to hold steady (figure 15 is not on WWW).
G. Some Other Properties
The value of any element is equal to the number of different paths from the apex of the tetrahedron
to that element. In Pascal's triangle this is the basis of "Taxicab" geometry.
The sum of the unique elements on any level equals 3 to the power of the level index. For instance
level 7 has eight unique elements; 1, 7, 21, 35, 42, 105, 140, and 210. These add up to 2187 or 3 to the seventh
power.
VII. Summary
The three dimensional analog of Pascal's triangle is of interest for the same reasons that Pascal's
triangle is of interest. It touches on number theory, the distribution of primes and twin primes, divisors, factors,
combinatorics, and geometry.
The patterns to be found in Pascal's triangle and it's 3-D analog seem endless.
References
Check the complete article in Computers and Graphics: An International Journal of Applications in Computer Graphics,
Volume 15, Number 2 1991 for more information. Pergamon Press ISSN 0097-8493
Footnotes
Gardner, Martin. (1966, December) The multiple charms of Pascal's triangle, Scientific American. pp. 128-132
Dewdney, A. K. (1985, April) Five easy pieces for a do loop and random-number generator [Computer Recreations].
Scientific American. p. 22.
Mueller, Stephen. (1969, Spring). Recursions associated with Pascal's pyramid. Pi Mu Epsilon Journal, (Vol 4,
#10). pp. 417-422.
Staib, John & Staib, Larry. (1978, September). The Pascal Pyramid. Mathematics Teacher. pp. 505-560.
Steinhaus, H. (1939). Mathematical snapshots. Leipzig: G. E. Stechert & Co. p. 30.
Bollinger, Richard C. (1986, May) A note on Pascal-t triangles, multinomial coefficients, and Pascal pyramids,
The Fibonacci Quarterly. pp. 140-144.
Loeb, Arthur L. (1975) "Contribution to Synergetics," in Synergetics, by R. Buckminster Fuller. MacMillan
(New York, 1975). p. 837.
Pickover, C and Khorasani, E. (1990) Infinite Triangular Arrays. Leonardo 23(3). In press.
Pomerance, Carl. (1981) Recent Developments in Primality Testing Math Intelligencer 3. pp. 97-105.
Pomerance, Carl. (1982, June) The Search for Prime Numbers, Scientific American. p. 141.
Dixon, J. D. (1981) Asymptotically fast factorization of Integers. Math. Comp. 36. pp. 255-260.
The elements Pascal's Tet are very divisible, but if we add or subtract one from an element's value we get some
very undivisible numbers, i.e., primes or at least something like primes.
Visualize Pascal's Tetrahedron as a stack of marbles. One marble for each element. A triangle of marbles for
each level of the tetrahedron. Code the marbles red, green and blue if the plus or minus one value is prime. If
not make it yellow. Levels 8, 9 & 10 in the 3-D illustration below exhibit some interesting patterns.
Download Windows 3.1/95/98 executable Programs and/or Mac/Windows Browser Plugin
PAS-TET.ZIP is a 765 Kilobyte downloadable archive file. Unzip it to your local harddisk and
you can explore Pascal's Pyramid (or is it Pascal's Tetrahedron) on your own machine. This zip
archive contains the following files:
File Name
What the file does or contains
RECIMAGE-C.EXE
Calculates the values of all the elements in one level of Pascal's Pyramid
Tests each element's plus-1 and minus-1 neighbor for primeness
Draws a triangular array of disks showing plus-1 and minus-1 primes
Saves a text file to the C:\LEVELS directory with the values of the elements of Pascal's Pyramid for the chosen
levels
Saves a small text file to the C:\LEVELS directory for each level with the letters P, B, M and N indicating
if that element of Pascal's Pyramid is next to a single prime number or between twin primes.
P if the element Plus 1 is prime
M if the element Minus 1 is prime
B if Both plus 1 and minus 1 are prime (twins) or
N if Neither is prime
PLAYIMAG.EXE
Quickly plays back the screen drawing of a triangular array of disks for any level of Pascal's
Pyramid. TheRECIMAGE program is very CPU intensive and can take hours to compute a single level of values and draw
the triangular array on the screen. Once those text files have been recorded with the RECIMAGE.EXE program, this
PLAYIMAG.EXE program will quickly redraw the screenshots that have been saved to disk.
README.TXT
Info from True BASIC and Microsoft on DLL files and WIN32 files in Windows 3.1
TB510.DLL
These three DLL files from True BASIC, Inc. need to be installed in your Windows/System directory
for the executable files to run
the 765 Kilobyte archive file with the programs and files listed in the table above
Get the True BASIC Webapp plugin wbreader.exe
(a 678 Kilobyte self unzipping file)
from the True BASIC website (available in Mac and Windows formats)
Run RECIMAGE.TRC in your web browser with the True BASIC Webapp plugin
Run PLAYIMAG.TRC in your web browser with the True
BASIC Webapp plugin
Illustrations and text adapted for the Internet by Jim Nugent using Visual Page,
Corel Draw, and Corel Paint.
Last updated on January 1, 2006
Jim Nugent
