Heron’s Rule and Integer-Area Triangles

Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 14

This note offers a follow-up to Eugene McDonnell’s Heron’s Rule & Integer-Area Triangles (VECTOR 12.3 pp133-142) and Roger Hui’s Linear Recurrences and Matrix Powers (VECTOR 12.4 pp113-115). It offers a simpler, fast solution to a problem they treat.

Mr. McDonnell’s exploration of a certain class of integer-area triangles leads him to the sequence 1, 2, 7, 26, 97, 362,… with recurrence relation A(n) = 4*A(n-1) - A(n-2). His J interpretation of the recurrence relation employs recursion and is intolerably slow. Subsequently he describes interesting applications of a generating function, Taylor’s series, and partial fraction decomposition, which result in rapid generation of terms of the sequence, with the added benefit of an edifying excursion with some less well known J primitives. Enlightening as that development is, it’s rather heavy machinery if the goal is to generate terms of the sequence speedily.

Mr. Hui interprets the recurrence relation as a matrix multiplication. In this interpretation generating terms of the sequence requires computing powers of a matrix, and Hui shows and compares three methods for accomplishing that task. This leads to very fast generation of terms of the sequence.

This sequence, and any which have linear recurrence relations, can be generated with an elementary approach which is transparent and quite fast. At any stage in generating this sequence we use the last two terms to generate the next term, append that to the sequence, and repeat this process. Generating the next term is simply taking an inner product of the vector _1 4 and the last two terms. Repetition of the process is accomplished by function iteration — power conjunction (^:) in J. The verb s implements this method.

   s=. 3 : 'y. , _1 4 +/ .* _2{. y.'

   s 1 2              NB. A few example runs
1 2 7

   s 1 2 7
1 2 7 26

   s^:8 [ 1 2         NB. The first 10 terms
1 2 7 26 97 362 1351 5042 18817 70226

   {: s^:28 [ 1 2     NB. The 30th term
1.92952e16

This term is computed in less than an eyeblink on a modest machine:

   6!:2 '{: s^:28 [ 1 2'
0.09

William R. Jones
Lafayette College