The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 3
1, 2, 4, 6, 9, 11, 14, 17, 20, 23, 26 (list; graph; refs; listen; history; text; internal format)



S must not contain 3 points A,B,C such that angle ABC = 90 degrees and |AB| = |BC|.

For example, this configuration is forbidden:

   O B O O

   O O O C

   A O O O

   O O O O

a(12) >= 29. - Robert Israel, Apr 22 2016

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


Table of n, a(n) for n=1..11.

Giovanni Resta, Illustration of a(3)-a(11)

Giovanni Resta, Illustration of lower bounds on a(12)-a(15)


Illustration for a(3) = 4:

   X X X

   O O O

   O X O

Illustration for a(8) = 17:

   O X O O O O O X

   X O O O O O O X

   O O O X O O O X

   O O X O O O O X

   O O O O O O O X

   O O O O O O O X

   O O O O O O X O

   X X X X X X O O


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]


Cf. A271907, A227133.

Sequence in context: A274214 A276223 A288468 * A050502 A293956 A022760

Adjacent sequences:  A271903 A271904 A271905 * A271907 A271908 A271909




Giovanni Resta and N. J. A. Sloane, Apr 22 2016



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 30 21:33 EDT 2021. Contains 346365 sequences. (Running on oeis4.)