From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Lattice Problem (Triangles) Date: 8 Oct 1997 17:00:44 GMT In article <3435C701.7BF9@cruzio.com>, KD wrote: >How many triangles can be formed on an 8 x 8 lattice (like a geoboard) >such that the vertices of each triangle lie on lattice points? How many >triangles can be formed on an an n x n lattice? In article <61e5vk$q56$1@gannett.math.niu.edu>, Dave Rusin wrote: >More interesting is to ask for the number of _congruence classes_ of >triangles, or _similarity classes_ of triangles. or something. I don't >know the answer offhand, although for a general n I believe the >answers is on the order of n^4. See > http://www.math.niu.edu/known-math/95/integral.tris [URL updated 1999/01 -- djr] I should add that the number of congruence classes of triangles with vertices on an NxN grid is easy to compute for small N. Lemma: Every such triangle is congruent to one with a vertex at the origin Proof: Label the points "topmost", "bottommost", "leftmost", and "rightmost" as appropriate (multiple labels for ties). Three points, 4 awards, so at least one double winner. Translate that point to the appropriate corner. Rotate by quarter turns. QED Remark: We only use conjugacy under a _subgroup_ of the Euclidean group here. For each such triangle we compute the squares A,B,C of the side-lengths a,b,c; the numbers A, B, C are positive integers, and the triangle is degenerate ( (+-)a + (+-)b + (+-)c = 0 ) iff A^2+B^2+C^2=2(AB+BC+CA). (Proof: multiply four of those equations together). Thus we can perform a search for congruence classes using integer arithmetic: TriangleSet = { } For (i,j) in {0, 1, ..., N}^2 do For (k,l) in {0, 1, ..., N}^2 do let A=i^2+j^2, B=k^2+l^2, C=(i-k)^2+(j-l)^2 if A^2+B^2+C^2 <> 2(AB+BC+CA) then ( Sort S={A,B,C} ) if S is not in TriangleSet, insert it (in lex order) end if end do end do display cardinality of TriangleSet Here's what I get for the first few N: 1, 8, 29, 79, 172, 333, 587, 963, 1494, 2228, 3195, 4455 I looked for this sequence in Sloane's sequence server, but didn't find a match. (I suppose it will now be added to the Handbook). Is it possible to compute this number without enumerating the elements of TriangleSet? Maybe, but I did not pursue the details, as it seems fairly intricate. Clearly TriangleSet has at most (N+1)^4 elements. This is an over-count, as the two pairs of points {(i,j), (k,l)} and {(k,l}, (i,j)} give the same triangle, and the pair {(j,i), (l,k)} gives a congruent triangle. (If you want to track this carefully, you'll need to pay attention to triangles of the form {(i,j), (j,i)}. ) So we have an upper bound of (N+1)^4/4 or so. Also note that if {(i,j),(k,l)} is a triangle for which (in the proof of the lemma) there are two points each having two labels, then the pair {(i,j), (|i-k|,|j-l|)} denotes a congruent triangle. (Triangles with multiple ties will correspond to several pairs of points.) In this way one could probably compute precisely the number of equivalence classes of triangles, where two triangles are equivalent if they are in the same orbit under the action of the various subgroups of the Euclidean group. Candidates for which this might succeed include the group T of translations the subgroups S of the (dihedral) group of 8 symmetries of the square the group generated by T and any of these S But determining in advance the correct number of congruence classes is a bit trickier. This number is less than the number of equivalence classes under , since for example the triangle with vertices at (4,3) and (7,4) is congruent to the one with vertices at (5,0) and (8,1) but not by using symmetries in this restricted subgroup. Determination of such 'skew' congruences suggests some algebraic number theory, as I indicated in the previous post. I suspect this will reduce the number of equivalence classes by rather less than O(N^4). One could go further and look for equivalence classes under the still larger group which includes dilations, that is, look for similarity classes of triangles. One need only insert an extra step in the algorithm, dividing (A,B,C) by their greatest common factor before sorting and checking for inclusion. dave ============================================================================== From: sequences-reply@research.att.com To: rusin@math.niu.edu Date: Wed, 8 Oct 1997 10:56:18 -0400 (EDT) Subject: [none] Matches (up to a limit of 10) found for 1 8 29 79 172 333 587 : Even though there are 28,000 sequences in the table now, at least one of yours is not there! Please send it to me (njas@research.att.com) and I will (probably) add it! Include a brief description. Thanks! References (if any): o Dec '96: Take a look at my web page which does lookups "online"! Go to: http://www.research.att.com/~njas/sequences o The whole sequence table is also visible there. o For more sequences see "The Encyclopedia of Integer Sequences" by N. J. A. Sloane & S. Plouffe, Academic Press, ISBN 0-12-558630-2. o IF THE SEQUENCE YOU LOOKED UP WAS NOT IN THE TABLE, PLEASE SEND IT TO ME AT njas@research.att.com ! o There is a second sequence server (superseeker@research.att.com) that tries hard to find an explanation. Only 1 request per person per hour please. o Key: %I = ID line: Annnnnn = absolute catalogue number of sequence, Mnnnn = number in the Encyclopedia, %S, %T, %U = beginning of sequence, [%V,%W,%X = signed version] %N = name, %R = references, %Y = cross-references, %A = authority, %F = formula, %K = keywords, %H = URL address of source, %D = details of references, %p = Maple; %t = Mathematica; %o = other computer languages; %O = offset = [a,b]: a is subscript of first entry, b gives the position of the first entry >= 2. References to journals give volume, page, year. o If the word "lookup" does not appear you will be sent the help file. Sequentially yours, The On-Line Encyclopedia of Integer Sequences, N. J. A. Sloane, AT&T Research, Florham Park NJ 07932-0971 USA njas@research.att.com ============================================================================== [ I immediately sent this response: (I have updated the URL below, 1999/01) ] ============================================================================== I didn't see a match to the following sequence: 1, 8, 29, 79, ... This is the number of congruence classes of triangles which can be drawn using the lattice points in an NxN grid for vertices. If I've searched correctly the next few terms are 1, 8, 29, 79, 172, 333, 587, 963, 1494, 2228, 3195 I will store some information at this URL if you think this to be appropriate data for the handbook: http://www.math.niu.edu/~rusin/known-math/97/triangles.grid dave ============================================================================== Herewith some additional comments not posted. Last update 1997/10/10 ============================================================================== We can handle similarity as well as congruence with this Maple program: N:=3: # repeat from here ad nauseum TriangleSet:={}: SimSet:={}: for i from 0 to N do for j from 0 to N do for k from 0 to N do for l from 0 to N do A:=i^2+j^2:B:=k^2+l^2:C:=(i-k)^2+(j-l)^2: if A^2+B^2+C^2 <> 2*(A*B+B*C+C*A) then x:=sort([A,B,C]): TriangleSet:=TriangleSet union {x}: y:=gcd(A,B):y:=gcd(C,y): x:=[x[1]/y,x[2]/y,x[3]/y]: SimSet:=SimSet union {x}: fi:od:od:od:od: nops(TriangleSet); nops(SimSet); evalf("/""); N:=N+1; The output data are N 1 2 3 4 5 6 7 8 9 sim 1 6 20 55 119 229 402 667 1019 cong 1 8 29 79 172 333 587 963 1494 % 100 75 68.9 69.6 69.1 68.8 68.5 69.2 68.2 N 10 11 12 13 14 15 16 17 18 sim 1536 2216 3049 4168 5546 7203 9278 11755 14597 cong 2228 3195 4455 6050 8032 10481 13464 17014 21235 % 68.9 69.4 68.4 68.9 69.0 68.7 68.9 69.1 68.7 The number of similarity classes is a remarkably constant fraction of the number of congruence classes. (I suspect each of them can be given as quartic polynomials in N with an error which is perhaps O(N^2), say, so it's not surprising that a limit fraction exists, but I didn't expect the limit fraction to be attained so quickly.) ==============================================================================