cp's OEIS Frontend

A319158 Given an equilateral triangular grid with side n, containing n(n+1)/2 points, a(n) is the minimal number of points to be selected, such that any equilateral triangle of points will include at least one of the selection, if the triangle has the same orientation as the grid.

%I A319158 #29 Jan 10 2025 02:39:51
%S A319158 0,1,2,4,6,9,13,18,23,29,35,43,51
%N A319158 Given an equilateral triangular grid with side n, containing n(n+1)/2 points, a(n) is the minimal number of points to be selected, such that any equilateral triangle of points will include at least one of the selection, if the triangle has the same orientation as the grid.
%C A319158 This is the complementary problem to A157795: A157795(n-1) + a(n) = n(n+1)/2.
%C A319158 This is the same problem as A227116, except that here the triangles must have the same orientation as the grid. Here, the triangle's sides must be aligned with the sides of the grid, and the horizontal side of the triangle must be its base (assuming the grid has a horizontal base). A227116 is different in that it also includes upside-down triangles, rotated 180 degrees compared to the grid, since these have sides aligned with the grid (but different orientation).
%H A319158 Ed Wynn, <a href="https://arxiv.org/abs/1810.12975">A comparison of encodings for cardinality constraints in a SAT solver</a>, arXiv:1810.12975 [cs.LO], 2018.
%e A319158 For n=5, there is a unique solution for a(5)=6 (representing selected points by O):
%e A319158         O
%e A319158        . .
%e A319158       , O ,
%e A319158      . O O .
%e A319158     O . , . O
%e A319158 It can be seen that this is not a valid solution for A227116 because of the upside-down triangle of commas. One solution for A227116(5)=7 would be to select one of the commas as well.
%Y A319158 Cf. A157795, A227116, A319159.
%K A319158 nonn,hard,more
%O A319158 1,3
%A A319158 _Ed Wynn_, Sep 12 2018