cp's OEIS Frontend

A227308 Given an equilateral triangular grid with side n consisting of n(n+1)/2 points, a(n) is the maximum number of points that can be painted so that, if any 3 of the painted ones are chosen, they do not form an equilateral triangle with sides parallel to the grid.

%I A227308 #31 Jul 07 2023 14:56:07
%S A227308 1,2,4,6,8,12,14,18,22,26,30,34,39,44,49
%N A227308 Given an equilateral triangular grid with side n consisting of n(n+1)/2 points, a(n) is the maximum number of points that can be painted so that, if any 3 of the painted ones are chosen, they do not form an equilateral triangle with sides parallel to the grid.
%C A227308 Numbers found by an exhaustive computational search for all solutions. This sequence is complementary to A227116: A227116(n) + A227308(n) = n(n+1)/2.
%C A227308 Up to n=12 there is always a symmetric maximal solution. For n=13 and n=15 symmetric solutions contain at most a(n)-1 painted points. - _Heinrich Ludwig_, Oct 26 2013
%H A227308 Heinrich Ludwig, <a href="/A227308/a227308_1.png">Illustration of a(2)..a(15)</a>
%H A227308 Giovanni Resta, <a href="/A227308/a227308.png">Illustration of a(3)-a(14)</a>
%e A227308 n = 11. At most a(11) = 30 points (X) of 66 can be painted, while 36 (.) must remain unpainted.
%e A227308                 .
%e A227308                X X
%e A227308               X . X
%e A227308              X . . X
%e A227308             X . . . X
%e A227308            X . . . . X
%e A227308           . X X . X X .
%e A227308          . X . X X . X .
%e A227308         . . X X . X X . .
%e A227308        X . . . . . . . . X
%e A227308       . X X X . . . X X X .
%e A227308 In this pattern there is no equilateral subtriangle with all vertices = X and sides parallel to the whole triangle.
%t A227308 ivar[r_, c_] := r*(r-1)/2 + c; a[n_] := Block[{m, qq, nv = n*(n+1)/2, ne}, qq = Union[ Flatten[Table[{ivar[r, c], ivar[r-j, c], ivar[r, c+j]}, {r, 2, n}, {c, r - 1}, {j, Min[r - 1, r - c]}], 2], Flatten[Table[{ivar[r, c], ivar[r + j, c], ivar[r, c - j]}, {r, 2, n}, {c, 2, r}, {j, Min[c - 1, n - r]}], 2]]; ne = Length@qq; m = Table[0, {ne}, {nv}]; Do[m[[i, qq[[i]]]] = 1, {i, ne}]; Total@ Quiet@ LinearProgramming[ Table[-1, {nv}], m, Table[{2, -1}, {ne}], Table[{0, 1}, {nv}], Integers]]; Array[a, 9] (* _Giovanni Resta_, Sep 19 2013 *)
%Y A227308 Cf. A227116 (the complementary problem), A152125, A227133, A002717.
%K A227308 nonn,hard,more
%O A227308 1,2
%A A227308 _Heinrich Ludwig_, Jul 06 2013
%E A227308 a(12), a(13) from _Heinrich Ludwig_, Sep 02 2013
%E A227308 a(14) from _Giovanni Resta_, Sep 19 2013
%E A227308 a(15) from _Heinrich Ludwig_, Oct 26 2013