A231255 a(n) is the smallest integer t such that every length-t walk from the origin (0,0) taking steps of either (0,1) or (1,0) is guaranteed to have n points that are collinear.

0, 1, 4, 9, 29, 97

Offset

1,3

Comments

By length-t we mean the number of steps, one less than the number of points.

It is known that a(7) >= 261.

Longest sequences avoiding n collinear points, encoded by 1 for (0,1) and 2 for (1,0):

n = 3: 121

n = 4: 11211211

n = 5: 1121112111211122212221222122

n = 6: 112111222212222122221211211112112122221222212222122221211211112111221222212222122221221112111221

Links

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

J. L. Gerver and L. T. Ramsey, On certain sequences of lattice points, Pacific J. Math. 83 (1979), 357-363.

Example

a(3) = 4 because two consecutive identical steps from (0,0) generate 3 collinear points, so the first three steps must be (0,1), (1,0), (0,1) or its complement. Then no matter what is chosen for the next step, three collinear points are generated.

Crossrefs

Sequence in context: A210969 A059345 A127768 * A241393 A186650 A091658

Adjacent sequences: A231252 A231253 A231254 * A231256 A231257 A231258

Keyword

nonn,more

Author

Jeffrey Shallit, Nov 06 2013

Status

approved