Conference rusure::math

    The exact number may be a difficult question in additive number theory...

    The (a,b,c) lengths will be integer lattice points lying on the
    plane a+b+c = n and satisfying the further inequalities

	a,b,c > 0   positive lengths lie in equilateral triangle in plane
        c < a+b	    triangle inequality

	a <= b
	a <= c
	b <= c	    make the triangle unique up to symmetry

    It shouldn't be hard to have an asymptotic estimate of the number of
    triangles, since the limiting density of lattice points in the
    plane a+b+c = n should be easy to estimate, (I don't know the number
    offhand) and the bounds could be used to compute the area of the subset
    we're interested in.

    - Jim

    I tried a simple minded program and it seems that
    log(k)/log(n) ~= 1.4 or so; this doesn't make sense, since the density
    of lattice points in a plane x+y+z = n is proprortional to n^2
    (the constant is about .5771).  If the points were equidistributed
    then only 1/6 of them would be our triangles on account of the
    inequalities and symmetry.

    The density of lattice points in the plane must not be uniform.

    I may try plotting the pattern and see if it looks interesting.

    fwiw, for n = 20000 I saw 8333333 unique triangles.

    - Jim

    Is it really that difficult? I calculate that for
    
    	n = 12*m		k = 3*m^2
    
    	n = 12*m+6		k = 3*m*(m+1)+1
    
    and the other 5/6 should be similar. On the other hand I could be wrong
    as I'm rushing to do this before my ALL-IN-1 link completes.
    
    dick

    Yes, my face should be red for making it overly complex...

    The cases could be tabulated as:

	    n		    k
	----------	------------------
	 12*m		  3*m^2
	 12*m + 1	  3*m^2 + 2*m
         12*m + 2	  3*m^2 + m
	 12*m + 3	  3*m^2 + 3*m + 1
	 12*m + 4	  3*m+2 + 2*m
	 12*m + 5	  3*m+2 + 4*m + 1
	 12*m + 6	  3*m+2 + 3*m + 1
	 12*m + 7	  3*m+2 + 5*m + 2
	 12*m + 8	  3*m+2 + 4*m + 1
	 12*m + 9	  3*m+2 + 6*m + 3
	 12*m + 10	  3*m^2 + 5*m + 2
	 12*m + 11	  3*m^2 + 7*m + 4

    - Jim

Q: How many triangles are there with each side a positive integer, and 
perimeter n, where n is a positive integer?


A:
If n = 12q + r,
N(n) = 3q� + yq + z

where y & z come from:
r |	0   1   2   3   4   5   6   7   8   9  10  11
y |     0   2   1   3   2   4   3   5   4   6   5   7
z |	0   0   0   1   0   1   1   2   1   3   2   4


Y: Suppose that the sides are a >= b >= c > 0, where b+c > a.

	a can run from ceil(n/3) to ceil(n/2)-1
	given a, b can run from ceil((n-a)/2) to a
	c is determined uniquely by a & b above

Check:
	b =< a by definition
	b >= ceil((n-a)/2) => 2b >= n-a => b >= c
	a =< ceil(n/2)-1 => 2a < n => a < b+c
	n > 2a => n > a+b => c > 0

Now, given a, the number of possible b is 1+a-ceil((n-a)/2).   Is this
always non-negative?   The smallest that this could be is when a = ceil(n/3).
Suppose that n = 12q+r.

the lower bound on the number of b is then:
1 + s - t
where s = ceil(r/3) & t = ceil((r-s)/2)

r = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11
s = 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4
t = 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4
u = 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6
v = 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1
so 1+s-t never becomes negative.

The number of possible a is ceil(n/2)-ceil(n/3) = 2q+u-s
where u = ceil(r/2).   This only becomes zero where q=0, and r=0,1,2or4.

Thus the number of possible triangles is:
N(n) =	sum(a = ceil(n/3) to ceil(n/2)-1) 1+a-ceil((n-a)/2)
=	sum(a = 4q+s to 6q+u-1) 1+a-6q-ceil((r-a)/2)
=	sum(a = 4q+s to 6q+u-1) 1+3a/2-u-6q+k
where k = -a/2+u-ceil((r-a)/2)
r mod 2: 0, 1, 0, 1
a mod 2: 0, 0, 1, 1
k:       0, 0,-�, �
      
To return to the sum of 
N(n) = sum(a = 4q+s to 6q+u-1) 1+3a/2-u-6q+k
     = 3(6q+u-1)(6q+u)/4 - 3(4q+s)(4q+s-1)/4 +(1-u-6q)(2q+u-s)
	+ sum(a = 4q+s to 6q+u-1) k

N(n) = 27q� + 9(u-1/2)q + 3(u-1)u/4
      -12q� - 3(2s-1)q - 3s(s-1)/4
      -12q� + (2-8u+6s)q +(1-u)(u-s)
	+ sum(a = 4q+s to 6q+u-1) k

N(n) = 3q� + (u+1/2)q 
	+ 3(u-1)u/4 -3s(s-1)/4 -(u-1)(u-s)
	+ sum(a = 4q+s to 6q+u-1) k

The last term is proportional to (v-�), and also, q+w, the number of odd a,
thus becomes (q+w)(v-�).   I don't bother to work out w, because...

N(n) = 3q� + (u+v)q 
	+ 3(u-1)u/4 -3s(s-1)/4 -(u-1)(u-s) + w(v-�)
The best way to compute the term independent of q is to take q=0, ie n < 12,
and count the number of possible triangles.

-------------------------------------------------------------------------------

If n = 12q + r,
N(n) = 3q� + yq + z

where y & z come from:
r |	0   1   2   3   4   5   6   7   8   9  10  11
y |     0   2   1   3   2   4   3   5   4   6   5   7
z |	0   0   0   1   0   1   1   2   1   3   2   4

Check by computing the possible triangles with perimeter up to 35, and it
works perfectly:

r |	0   1   2   3   4   5   6   7   8   9  10  11
q:+--------------------------------------------------
0 |	0   0   0   1   0   1   1   2   1   3   2   4
1 |     3   5   4   7   5   8   7  10   8  12  10  14
2 |    12  16  14  19  16  21  19  24  21  27  24  30

Regards,
Andrew.

    Here is an even simpler expression for the number

	n even:	floor((n^2+21)/48)
	n odd:  floor((n^2+6*n+21)/48)

    Actually, the problem would have been simpler if you hadn't required that
    congruent triangles be considered equivalent :-)

    - Jim