Triangle Perimeters

Date: 12/15/98 at 21:36:24
From: Eric Olmsted
Subject: Triangle perimeter computation

How many triangles with integer sides have a given perimeter?

I am trying to use the law of inequality, but I am having problems 
applying this law to the question. Do you have any suggestions?

Date: 12/17/98 at 10:28:59
From: Doctor Rob
Subject: Re: Triangle perimeter computation

Thanks for writing to Ask Dr. Math!

This problem turns out to be quite complicated, but possible.

Let the sides be a, b, and c, such that:

   0 < a <= b <= c

Then:

   p = a + b + c

By the Triangle Inequality:

   c < a + b

(The other two inequalities are automatically true.)

Now you have to figure out how to put these together. For starters:

   p = a + b + c <= 3*c
   p/3 <= c < a + b
   p/3 <= p - a - b < a + b
   p/3 + a + b <= p < 2a + 2b
   p/2 < a + b <= 2*p/3
   p/2 - a < b <= 2*p/3 - a
   (p+1)/2 - a <= b <= 2*p/3 - a

Furthermore,

   0 < a <= b <= p - a - b
   0 < a <= b <= (p-a)/2

Putting these together, we get:

   max(a,[(p+1)/2]-a) <= b <= min([2*p/3]-a,[(p-a)/2])

where [x] is the greatest integer less than or equal to x. Further
we see that:

   3*a <= a + b + c = p
   1 <= a <= p/3
   1 <= a <= [p/3]

Now a <= [(p+1)/2] - a if and only if a <= [(p+1)/2]/2 if and only
if a <= [(p+1)/4]. Furthermore, [2*p/3] - a <= [(p-a)/2] if and
only if a >= p - 2*[(p+2)/3] (this is not obvious, but true). That
means that we should break up the range of a into three parts:

1:  1 <= a <= [(p+1)/4]
        [(p+1)/2]-a <= b <= [(p-a)/2]

2:  [(p+1)/4] + 1 <= a <= p - 2*[(p+2)/3]
        a <= b <= [(p-a)/2]

3:  p - 2*[(p+2)/3] + 1 <= a <= [p/3]
        a <= b <= [2*p/3]-a

The third part is empty (there are no values of a satisfying the
conditions) unless (p+2)/3 is an integer, in which case it contains the 
single value a = (p-1)/3, and then b = (p-1)/3, too.

Then the number of possibilities for the pairs (a,b) is:

          [p/3] min([2*p/3]-a,[(p-a)/2])
   N(p) =  SUM            SUM            1
           a=1    b=max(a,[(p+1)/2]-a)

which can be evaluated by splitting the outer sum into three parts
according to the above scheme, and summing each part separately.
I leave the details of this to you.

Since the denominators inside [.] are 2, 3, and 4, whose LCM is 12,
12 cases can be considered separately, each corresponding to a 
remainder obtained when dividing p by 12.  For example, when p leaves 
remainder 0 on division by 12, the number N(p) = p^2/48, and when the 
remainder is 1, N(p) = (p^2+6*p-7)/48, and so on.  In all cases, the 
highest degree term is p^2/48.

The numbers look like this, starting with p = 0 and reading left to
right:

     0    0    0    1    0    1    1    2    1    3    2    4
     3    5    4    7    5    8    7   10    8   12   10   14
    12   16   14   19   16   21   19   24   21   27   24   30
    27   33   30   37   33   40   37   44   40   48   44   52
    48   56   52   61   56   65   61   70   65   75   70   80
    75   85   80   91   85   96   91  102   96  108  102  114
   108  120  114  127  120  133  127  140  133  147  140  154
   147  161  154  169  161  176  169  184  176  192  184  200
   192  208  200  217  208  ...

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/