Finding Integer Triangles with Integer Area to Perimeter Ratios
Given a triangle with integer sides and area find all such triangles with integer area to perimeter ratios. Lets consider two methods: using the standard generating functions for Heronian triangles and a specialized method for any give ratio.
Finding All Triangles of the From A = rP and r is Arbitrary
This method is an extension of the usual parameterized form for finding Heronian triangle. To start, consider the following general set of equations by Carmichael [1]...
semiperimeter | (1) | |
perimeter | (2) | |
area | (3) | |
ratio | (4) | |
restrictions | (5) |
It is clear that in this case r is not always an integer, but that can be easily fixed by scaling all sides by a factor of 2 which scales the p by a factor of 2 and A by a factor of 4. While this producing a integer ratio for any valid n, m, and k it misses the various scalings of the triangles. That is, these equations produce exactly one base triangle per class (think family or type). We can make it find all target triangles by simply scaling our base triangle up or down. In fact, we can find all such triangles by applying a positive scaling to the "primitive" version of each generated triangle.
Finding Primitive Scalings for Each Heronian Class
Lets define a primitive target triangle as any triangle generated by the above equations such that it has the smallest area for its class. In short, for each triangle generated find a scaling such that when applied creates the smallest possible triangle with an integer ratio. Finding this primitive scaling is actually trivial once a, b, c, and r are found using the following equations.
sides | (6) | |
scale down factor | (7) | |
new sides | (8) | |
new ratio | (9) |
Method A, Finding All Triangles of the Form A = rP
for all m, n, k such that equation (5) is valid find 2a, 2b, 2c using equation (6) find 2r using equation (4) find scale_down using (7) primitive_triangle is a, b, c divided by scale_down primitive_ratio is 2r divided by scale_down for scale_up from 1 to MAX_SCALE triangle is primitive_triangle * scale_up |
for all m, n, k such that equation (5) is valid find 2a, 2b, 2c using equation (6) find 2r using equation (4) find scale_down using (7) primitive_triangle is a, b, c divided by scale_down primitive_ratio is 2r divided by scale_down for scale_up from 1 to MAX_SCALE triangle is primitive_triangle * scale_up
Finding All Triangles of the From A = rP and r is Predefined
While the above algorithm will find all triangles of interest, it is far to slow to final all triangles given a particular ratio. This section gives a brief overview of a method by Markov [2] which is much more suited to that version of the problem. First, the following equations are the foundation of the method...Heronian Formula | (10) | |
doubly-Pythagorean Form | (11) | |
substitute | (12) | |
new form | (13) | |
factor | (14) | |
restrictions | (15) | |
restrictions (u < v) | (16) | |
sides | (17) |
The key equation is (13) which reduces the problem to a special form of finding lattice points on an ellipse. This reducing, in turn, leads to an algorithm that has a runtime depending on the factorization of r. The following pseudo code should provide all triangles of the target form.
Method B, Finding All Triangles of the Form A = rP Given r
function find-triangles (r) answer = empty list for u in divisors of 2r for v in 1 to sqrt(3) * u and gcd(u, v) = 1 lhs = 4*m*m*(u*u+v*v) for d1 in divisors of lhs and d1 >= lhs/d1 d2 = lhs/d1 if u < v and d1*u < (2m(v*v-u*u)) then next d1 if d1+2mu = 0 mod v and d2+2mu = 0 mod v add triangle to answer using equation (17) |
function find-triangles (r) answer = empty list for u in divisors of 2r for v in 1 to sqrt(3) * u and gcd(u, v) = 1 lhs = 4*m*m*(u*u+v*v) for d1 in divisors of lhs and d1 >= lhs/d1 d2 = lhs/d1 if u < v and d1*u < (2m(v*v-u*u)) then next d1 if d1+2mu = 0 mod v and d2+2mu = 0 mod v add triangle to answer using equation (17)
References
[1] Carmichael, R. D. The Theory of Numbers and Diophantine Analysis. New York: Dover, 1952.
[2] Lubomir Markov, Heronian Triangles Whose Areas are Integer Multiples of Their Perimeters. Forum Geometricorum, 2007
May 7, 2010aewhiteCategory: General, Programming Read more
No Comments
Tags: Math
Comments are closed.