cp's OEIS Frontend

A268239 Given an n X n X n grid of points, a(n) is the maximum number of points that can be painted red so that, if any 8 of the red points are chosen, they do not form a cube with sides parallel to the grid.

%I A268239 #24 Sep 28 2018 18:54:07
%S A268239 0,1,7,25,56,109,187,295,440
%N A268239 Given an n X n X n grid of points, a(n) is the maximum number of points that can be painted red so that, if any 8 of the red points are chosen, they do not form a cube with sides parallel to the grid.
%C A268239 Using a greedy coloring gives a(4) >= 49.
%H A268239 Giovanni Resta, <a href="/A268239/a268239.png">Illustration of a(3)-a(6)</a>
%e A268239 For n=3, we may color 25 of the 27 points red (X) without any of 25 red points forming a cube. Color the three slices as follows:
%e A268239 XXX XXX XXX
%e A268239 XXX X.X XXX
%e A268239 XXX XXX xx.
%t A268239 a[n_] := Block[{m, qq, nv = n^3, ne}, qq = Flatten[1 + Table[n^2*z + n*x + y + s*Plus @@@ Tuples[{{0, 1}, {0, n}, {0, n^2}}], {x, 0, n-2}, {y, 0, n-2}, {z, 0, n-2}, {s, Min[n-x, n-y, n-z] - 1}], 3]; ne = Length@ qq; m = Table[0, {ne}, {nv}]; Do[m[[i, qq[[i]]]] = 1, {i, ne}]; Total@ Quiet@ LinearProgramming[ Table[-1, {nv}], m, Table[{7, -1}, {ne}], Table[{0, 1}, {nv}], Integers]]; Table[ a[n], {n, 0, 6}] (* _Giovanni Resta_, Feb 06 2016 *)
%Y A268239 This is a three-dimensional analog of A227133.
%K A268239 nonn,more
%O A268239 0,3
%A A268239 _Benoit Cloitre_ and _N. J. A. Sloane_, Feb 05 2016
%E A268239 a(4)-a(6) from _Giovanni Resta_, Feb 06 2016
%E A268239 a(7)-a(8) from _Paul Tabatabai_ using integer programming, Sep 27 2018