eXTReMe Tracker

Pascal's Pyramid Or Pascal's Tetrahedron?

By

Jim Nugent
3707 213th Place
Matteson, Illinois 60443

lastnamefirstinitial at ameritech.net

This is a copyrighted document.

The text, charts, graphs and illustrations are covered by various copyrights
©1990, 1991, 1996, 1997, 1999, 2006, & 2007

ABSTRACT

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

Figure 1 - Octahedrons and tetrahedrons filling space

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.

Figure 2 - Odd and even values for Pascal's triangle 

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.

Figure 3 - triangle shaped 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

Figure 4 - click here to go to larger oct-tet animation

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:

(Link to standalone Octahedron-Tetrahedron Animation (figure 4))

"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.

Figure 5 - Cubic and tetrahedral coordinates 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.

Figure 6 - Basic notation for Pascal's pyramid 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.

True BASIC Program to calculate Pascal's Tetrahedron Element Values.

VI. Some Interesting Properties

A. A Fully Rounded Bell Curve

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
Figure 7 - A 3 dimensional

 True BASIC Program to generate Bell Curve Plot 

True BASIC Program to generate Log Bell Curve Plot

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 

Figure 8 - Three dimensional bell curves - log value plot

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 

Figure 11 - Level 128, mod 2 - Pascal's Tetrahedron



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 

Figure 12a - Level 129, plus 1 and minus 1 primes - Pascal's Tetrahedron

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.

Figure 12b

Figure 12b - Level 150, plus 1 and minus 1 primes - Pascal's Tetrahedron

True BASIC Program to record images
like those on the right

True BASIC Program to playback images
like those on the right

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 - Level 129, plus 1 and minus 1 primes - Pascal's Tetrahedron

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:


1481381295 1722496842 2500487141
4311719641 9437870393 1200589484
8675243369 2295824399 2828691173
4768379843 4796671471 2573495000


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. 



Go to Apple to get Quicktime Viewer Plugin

E. The Oct-Tet Algorithm

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).

Figure 13 - Whole number ratios between the values of adjacent elements in Pascal's Pyramid

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.

Back to the Top
 

Visualizing Plus/Minus Primes on Multiple Levels

A Thought Experiment

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.

3-D view of levels 8, 9, & 10 of Pascal's Tetrahedron (pyramid)

Here are the numerical values that go with the various "marbles" Values for level 8, 9 & 10
Click here to view levels 32, 33, & 34this will take a minute since the GIF file is about 100K in size.
Click here to view levels 32, 33, & 34 - this is even higher resolution - about 300K in size.
 


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

  1. Calculates the values of all the elements in one level of Pascal's Pyramid 
  2. Tests each element's plus-1 and minus-1 neighbor for primeness 
  3. Draws a triangular array of disks showing plus-1 and minus-1 primes 
  4. Saves a text file to the C:\LEVELS directory with the values of the elements of Pascal's Pyramid for the chosen levels 
  5. 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 

XNMBA420.DLL

XNMTE420.DLL

Go to the top


 

Download PAS-TET.ZIP

the 765 Kilobyte archive file with the programs and files listed in the table above

 

Go to www.truebasic.com

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

nugentj@ameri-nospam-tech.net

Symantec software for web design - Made for Win95 and still running great under WinXPpro