Subject: Re: Visualize Prime Patterns
Date: 1 Feb 2000 06:21:19 -0800
From: Phil Carmody
To: primes-l@utm.EdU
Various people have asked for the formal proof that no element in the Nth layer of a
"Pascal's Tetrahedron" can have a value with a prime factor greater than N. I've reworked
it to use the (right,bottom,left) coordinates, as it appears the answer comes out far more
easily.
Assume all layers are 'point-up' ( /_\ )
Assume 3 points in a layer are
(r, b+1, l-1) --- (r-1, b+1, l)
\ /
\ x /
\ /
(r, b, l)
Induction hypothesis: the value V(r, b, l) = (r+b+l)!/r!b!l!
The new point, x, in the middle of the above triange, and in the layer below is (r, b+1,
l).
By the induction hypotheseis
V(r,b+1,l) = (r+b+l)!/r!b!l!
+ (r+b+l)!/(r-1)!(b+1)!l!
+ (r+b+l)!/r!(b+1)!(l-1!)
= (r+b+l)! ((b+1) + (r) + (l))/r!(b+1)!l!
= (r+b+1+l)!/r!(b+1)!l!
as expcted.
Note - the above assumes that (-1)! acts like a normal number with respect to
multiplication/division, (in particular that it cancels). This permits us to cope with the
boundary cases. More rigor should really be used (and the three borders can be handled in
one step without loss of generality).
The seed to the induction process is any (and therefore all) of the three elements in
layer 1. (once the rigor has been applied!)
So that's basically it. The gaps are left as an exercise to the readers :-)
So, not only is (r+b+l) the maximum posible prime factor of any element in a layer, but as
the value is
(r+b+l)!/r!b!l!
_all_ primes in (max(r,b,l) .. r+b+l] will be factors of the value. That's why there are
so many factors. In particular for the "centre" cells, where the max(r,b,l) is ceil(
r+b+l/3 ).
Have fun all,
Phil