login
Minimum number of points of the square lattice falling strictly inside an equilateral triangle of side n.
2

%I #29 Jul 15 2020 04:33:43

%S 0,0,0,2,4,8,12,17,23,30,37

%N Minimum number of points of the square lattice falling strictly inside an equilateral triangle of side n.

%C Due to the symmetry and periodicity of the square lattice it is sufficient to explore possible equilateral triangles with center belonging to the triangular region with vertices (0,0), (1/2, 0), and (1/2, 1/2), and for every center the orientations between 0 and 2*Pi/3 radians must be explored. A simple strategy to obtain this sequence is to explore many triangles with centers and orientations in the previously described regions and count the points falling strictly inside the triangles, then picking the minimum number obtained. In the given Mathematica program the explored triangles are generated by regularly moving its center with constant increment in both main orthogonal directions, and for every center different orientations are generated with constant angular step increment.

%C Is there any criterion to determine how small should be the pitch and the angular increment in order to catch an equilateral triangle with the smallest possible number of points for a given side length n?

%C The different regions for the centers producing constant minimum numbers of lattice points inside equilateral triangles of side length n seem to become very complex and irregular as n increases (see density plots in Links).

%H Andres Cicuttin, <a href="/A292060/a292060.pdf">Plots of regions for centers of equilateral triangles of several side lengths n enclosing constant minimum number of lattice points</a>

%F a(n) ~ (1/4)*sqrt(3)*n^2.

%t (* This gives a polar function of a "k" sides polygon with side length "sidelength" and vertical rightmost side *)

%t PolarPolygonSide[sidelength_, theta_, k_] := ((sidelength/2)/Tan[Pi/k])/Cos[Mod[theta - Pi/k , 2 Pi/k] - Pi/k];

%t (* uncomment next to generate and plot different polygons *)

%t (* Manipulate[PolarPlot[PolarPolygonSide[sidelength, theta + phase, sides], {theta, 0, 2 Pi}, PlotRange -> sidelength, GridLines -> {Range[-sidelength, sidelength] + di, Range[-sidelength, sidelength] + dj}], {sidelength, 1, 10, 1}, {sides, 3, 30, 1}, {phase, 0, 2 Pi/3, 2 Pi/300}, {dj, 0, 1/2, 0.01}, {di, 0, 1/2, 0.01}] *)

%t (* This function gives 1 if the point of coordinates (x,y) is strictly inside a polygon given by PolarPolygonSide[sidelength, theta, sides] rotated by "phase", and 0 otherwise *)

%t TruePointInsidePhase[x_, y_, sidelength_, phase_, sides_] :=

%t Module[{theta},

%t theta = ArcTan[x, y] + phase;

%t If[x^2 + y^2 == 0, 1,

%t If[x^2 + y^2 - (PolarPolygonSide[sidelength, theta, sides]^2) <

%t 0, 1, 0]] // Return];

%t sides = 3; (* number of sides of the polygon *)

%t (* The following step increments seem to be small enough for sidelengths up to 10 *)

%t dstep = 0.01; (* scanning step on x and y *)

%t phasestep = 2 Pi/3000; (* orientation angular increment step *)

%t seq = {};

%t Do[

%t npoints = {}; k = 0;

%t Do[Do[Do[

%t Do[Do[

%t k =

%t k + TruePointInsidePhase[i + di, j + dj, sidelength, phase,

%t sides]

%t , {i, -sidelength - 1, sidelength + 1, 1}], {j, -sidelength -

%t 1, sidelength + 1, 1}];

%t AppendTo[npoints, k];

%t k = 0;

%t , {dj, 0, 1/2, dstep}], {di, 0, 1/2, dstep}], {phase, 0, 2 Pi/3,

%t phasestep}] // Quiet;

%t temp = npoints // Min;

%t AppendTo[seq, temp];

%t , {sidelength, 0, 10, 1}]

%t seq

%Y Cf. A291259, A292896.

%K nonn,hard,more

%O 0,4

%A _Andres Cicuttin_, Sep 08 2017