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) >= 328. See Barnoff & Bright.

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.

Aaron Barnoff and Curtis Bright, North-East Lattice Paths Avoiding k Collinear Points via Satisfiability, arXiv:2511.23226 [math.CO], 2025. See pp. 2-3, 15.

Joseph L. Gerver and L. Thomas Ramsey, On certain sequences of lattice points, Pacific J. Math. (1979) Vol. 83, No. 2, 357-363.

Formula

A393935(n)-1 <= a(n) <= A380991(n-1) for n >= 2. - Pontus von Brömssen, May 05 2026

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

Cf. A380991, A393935 (a greedy version).

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