cp's OEIS Frontend

A271906 Size of the largest subset S of the points of an n X n square grid such that no three of the points of S form a right isosceles triangle.

%I A271906 #30 May 02 2016 10:10:50
%S A271906 1,2,4,6,9,11,14,17,20,23,26
%N A271906 Size of the largest subset S of the points of an n X n square grid such that no three of the points of S form a right isosceles triangle.
%C A271906 S must not contain 3 points A,B,C such that angle ABC = 90 degrees and |AB| = |BC|.
%C A271906 For example, this configuration is forbidden:
%C A271906    O B O O
%C A271906    O O O C
%C A271906    A O O O
%C A271906    O O O O
%C A271906 a(12) >= 29. - _Robert Israel_, Apr 22 2016
%C A271906 a(13) >= 32, a(14) >= 36, a(15) >= 38 (see pictures in Links). Note that a(14) >= 36 breaks the pattern of increasing by 3 at each step. - _Giovanni Resta_, Apr 23 2016
%H A271906 Giovanni Resta, <a href="/A271906/a271906.png">Illustration of a(3)-a(11)</a>
%H A271906 Giovanni Resta, <a href="/A271906/a271906_1.png">Illustration of lower bounds on a(12)-a(15)</a>
%e A271906 Illustration for a(3) = 4:
%e A271906    X X X
%e A271906    O O O
%e A271906    O X O
%e A271906 Illustration for a(8) = 17:
%e A271906    O X O O O O O X
%e A271906    X O O O O O O X
%e A271906    O O O X O O O X
%e A271906    O O X O O O O X
%e A271906    O O O O O O O X
%e A271906    O O O O O O O X
%e A271906    O O O O O O X O
%e A271906    X X X X X X O O
%t A271906 d[n_,a_,b_] := Block[{x1, y1, x2, y2}, x1 = Mod[a-1, n]; y1 = Floor[(a-1)/n];x2 = Mod[b-1, n]; y2 = Floor[(b-1)/n]; (x1-x2)^2 + (y1-y2)^2]; isorQ[n_,a_, b_,c_] := Block[{k = Sort[{d[n,a,b], d[n,b,c], d[n, a, c]}]}, k[[1]] == k[[2]] && 2 k[[1]] == k[[3]]]; sol[n_] := sol[n] = Block[{m, L={}, nv=n^2, ne}, Do[If[ isorQ[n, x, y, z], AppendTo[L, {x,y,z}]], {x, n^2}, {y, x-1}, {z, y-1}]; ne = Length@L; m = Table[0, {ne}, {nv}]; Do[m[[i, L[[i]]]] = 1, {i, ne}]; Quiet@ LinearProgramming[ Table[-1, {nv}], m, Table[{2, -1}, {ne}], Table[{0, 1}, {nv}], Integers]]; a[n_] := Total[sol[n]]; Do[Print@ MatrixForm@ Partition[ sol@n, n], {n,6}]; Array[a,6]
%Y A271906 Cf. A271907, A227133.
%K A271906 nonn,more
%O A271906 1,2
%A A271906 _Giovanni Resta_ and _N. J. A. Sloane_, Apr 22 2016