A358681 Largest area (doubled) of a triangle enclosed by a circle of radius n such that the center of the circle and the vertices of the triangle all have integer coordinates.

2, 8, 21, 36, 64, 90, 120, 157, 208, 256, 306, 360, 432, 504, 576, 650, 750, 832, 928, 1025, 1122, 1254, 1360, 1480, 1612, 1748, 1886, 2016, 2170, 2328, 2484, 2646, 2802, 3000, 3180, 3348, 3540, 3718, 3944, 4148, 4340, 4552, 4788, 5016, 5244, 5473, 5718, 5964

Offset: 1

Author

Gerhard Kirchner, Nov 26 2022

Keywords

• nonn

Comments

"Enclosing" means that all vertices are located on or inside the circle. (0,0) is the center of the circle. The area of a "grid triangle" with integer vertex coordinates is a multiple of 1/2. The vertices of any largest triangle are "close points", i.e., points (x,y) on or inside the circle such that at least two of the four points (x+-1,y+-1) are located outside (see link).

There are terms b(n) and c(n) with b(n) <= a(n) <= c(n), see formula section. For any n, a triangle with the doubled area b(n) exists. By checking b(n)=c(n), one obtains:

a( 1) = 2

a( 5) = 64

a( 17) = 750

a( 65) = 10976

a( 241) = 150898

a( 901) = 2109120

a( 3361) = 29348702

a( 12545) = 408877504

a( 46817) = 5694545250

a(174725) = 79316215616

a(652081) = 1104727025998

The sequence of indices is A120893.

Examples

			see link
		

Links

• Gerhard Kirchner, Examples and algorithm

Crossrefs

Cf. A358465, A120893.

Programs

Maxima

block(nmax: 50, a: makelist(0,i,1,nmax),
for n from 1 thru nmax do
  (p: floor(n/sqrt(2)), if 2*p*(p+1) > n^2-1 then d:0 else d:1,
   k0:n+1-d-p, z:2*k0-2+d,
   v: makelist([0,0],i,1,4*z), ma:0,
        /*Find close points with y>=0, x<=y:*/
   for k from 1 thru k0 do (j:k-1, v[k][2]:n-j, v[k][1]: floor(sqrt(j*(2*n-j)))),
          /*mirror x=y:*/
   for k from k0+d thru z+1 do(j:z+2-k, v[k][1]: v[j][2], v[k][2]: v[j][1]),
          /*rotation 90°:*/
   for k from z+2 thru 4*z do(j:k-z, v[k][1]: v[j][2], v[k][2]: -v[j][1]),
          /*All 4*z close points found, generate triangles:*/
   for k from 1 thru k0 do
    for j from k+2*z+1 thru k+3*z do
     for m from k+z thru k+2*z-1 do
      (ar:(v[j][1]-v[k][1])*(v[m][2]-v[k][2])-(v[j][2]-v[k][2])*(v[m][1]-v[k][1]),
       if ar>ma then ma:ar),  a[n]:ma), a);

Formula

Limits: b(n) <= a(n) <= c(n) with

c(n) = floor(n ^ 2 * sqrt(3) * 3 / 2).

With f(n,t) = (3*n + t) * floor(sqrt((3*n + t) * (n - t)) / 2):

b(n) = f(n,0) for even n

b(n) = max{f(n,-1),f(n,1)} for odd n.

a(n)/n^2 tends to sqrt(3) * 3 / 2.