cp's OEIS Frontend

A000769 No-3-in-line problem: number of inequivalent ways of placing 2n points on an n X n grid so that no 3 are in a line.

%I A000769 M3252 N1313 #79 May 12 2025 12:00:47
%S A000769 0,1,1,4,5,11,22,57,51,156,158,566,499,1366,3978,5900,7094,19204
%N A000769 No-3-in-line problem: number of inequivalent ways of placing 2n points on an n X n grid so that no 3 are in a line.
%C A000769 This means no three points on any line, not just lines in the X or Y directions.
%C A000769 A000755 gives the total number of solutions (as opposed to the number of equivalence classes).
%C A000769 It is conjectured that a(n)=0 for all sufficiently large n.
%C A000769 Flammenkamp's web site reports that at least one solution is known for all n <= 46 and n=48, 50, 52.
%C A000769 From _R. K. Guy_, Oct 22 2004: (Start)
%C A000769 I got the no-three-in-line problem from Heilbronn over 50 years ago. See Section F4 in UPINT.
%C A000769 In Canad. Math. Bull. 11 (1968) 527-531, MR 39 #129, Guy & Kelly conjecture that, for large n, at most (c + eps)*n points can be selected, where 3*c^3 = 2*Pi^2, i.e., c ~ 1.87.
%C A000769 As recently as last March, Gabor Ellmann pointed out an error in our heuristic reasoning, which, when corrected, gives 3*c^2 = Pi^2, or c ~ 1.813799. (End)
%D A000769 M. A. Adena, D. A. Holton and P. A. Kelly, Some thoughts on the no-three-in-line problem, pp. 6-17 of Combinatorial Mathematics (Proceedings 2nd Australian Conf.), Lect. Notes Math. 403, 1974.
%D A000769 D. B. Anderson, Journal of Combinatorial Theory Series A, V.27/1979 pp. 365 - 366.
%D A000769 D. Craggs and R. Hughes-Jones, Journal of Combinatorial Theory Series A, V. 20/1976 pp. 363-364.
%D A000769 H. E. Dudeney, Amusements in Mathematics, Nelson, Edinburgh 1917, pp. 94, 222.
%D A000769 M. Gardner, Scientific American V236 / March 1977, pp. 139-140.
%D A000769 M. Gardner, Penrose Tiles to Trapdoor Ciphers. Freeman, NY, 1989, p. 69.
%D A000769 R. K. Guy, Unsolved combinatorial problems, pp. 121-127 of D. J. A. Welsh, editor, Combinatorial Mathematics and Its Applications. Academic Press, NY, 1971.
%D A000769 R. K. Guy, Unsolved Problems Number Theory, Section F4.
%D A000769 R. K. Guy and P. A. Kelly, The No-Three-Line Problem. Research Paper 33, Department of Mathematics, Univ. of Calgary, Calgary, Alberta, 1968. Condensed version in Canad. Math. Bull. Vol. 11, pp. 527-531, 1968.
%D A000769 R. R. Hall, T. H. Jackson, A. Sudberry and K. Wild, Journal of Combinatorial Theory Series A, V.18/1975 pp. 336-341.
%D A000769 H. Harborth, P. Oertel and T. Prellberg, Discrete Math. V73/1988 pp. 89-90.
%D A000769 T. Kløve, Journal of Combinatorial Theory Series A, V.24/1978 pp. 126-127.
%D A000769 T. Kløve, Journal of Combinatorial Theory Series A, V.26/1979 pp. 82-83.
%D A000769 K. F. Roth, Journal London Math. Society V.26 / 1951, p. 204.
%D A000769 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000769 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000769 Benjamin Chaffin, <a href="http://web.archive.org/web/20131027174807/http://wso.williams.edu/~bchaffin/no_three_in_line/index.htm">No-Three-In-Line Problem</a>.
%H A000769 Alec S. Cooper, Oleg Pikhurko, John R. Schmitt and Gregory S. Warrington, <a href="http://arxiv.org/abs/1206.5350">Martin Gardner's minimum no-3-in-a-line problem</a>, arXiv:1206.5350 [math.CO]. Also Amer. Math. Monthly, 121 (2014), 213-221.
%H A000769 Achim Flammenkamp, <a href="http://wwwhomes.uni-bielefeld.de/achim/no3in/readme.html">Progress in the no-three-in-line problem</a>.
%H A000769 Achim Flammenkamp, <a href="http://wwwhomes.uni-bielefeld.de/achim/no3in/table.txt">Solutions of the no-three-in-line problem</a>.
%H A000769 Achim Flammenkamp, <a href="https://doi.org/10.1016/0097-3165(92)90012-J">Progress in the no-three-in-line problem</a>, J. Combinat. Theory A 60 (1992), 305-311.
%H A000769 Achim Flammenkamp, <a href="https://doi.org/10.1006/jcta.1997.2829">Progress in the no-three-in-line problem. II</a>, J. Combin. Theory Ser. A 81 (1998), no. 1, 108-113.
%H A000769 R. K. Guy and P. A. Kelly, <a href="/A000755/a000755_1.pdf">The No-Three-Line Problem</a>, Research Paper 33, Department of Mathematics, Univ. of Calgary, Calgary, Alberta, 1968. [Annotated scanned copy]
%H A000769 R. K. Guy and P. A. Kelly, <a href="/A000755/a000755_2.pdf">The No-Three-Line Problem</a>, condensed version in Canad. Math. Bull. Vol. 11, pp. 527-531, 1968. [Annotated scanned copy]
%H A000769 R. K. Guy, P. A. Kelly, N. J. A. Sloane, <a href="/A000755/a000755.pdf">Correspondence, 1968-1971</a>.
%H A000769 S. V. Ullas Chandran, Sandi Klavžar, and James Tuite, <a href="https://arxiv.org/abs/2501.19385">The General Position Problem: A Survey</a>, arXiv:2501.19385 [math.CO], 2025. See p. 4.
%H A000769 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PointLattice.html">Point Lattice</a>.
%H A000769 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/No-Three-in-a-Line-Problem.html">No-Three-in-a-Line-Problem</a>.
%e A000769 a(3) = 1:
%e A000769   X X o
%e A000769   X o X
%e A000769   o X X
%Y A000769 Cf. A000755, A000938, A037185, A037186, A037187, A037188, A037189, A047840, A212807, A235453.
%Y A000769 See A272651 for the maximal number of no-3-in-line points on an n X n grid, and A277433 for minimal saturated.
%Y A000769 Cf. A194136 (triangular grid), A280537 (3D grid, no 4 in plane).
%K A000769 hard,nonn,nice,more
%O A000769 1,4
%A A000769 _N. J. A. Sloane_
%E A000769 a(17) and a(18) from _Benjamin Chaffin_, Apr 05 2006
%E A000769 Minor edits from _N. J. A. Sloane_, May 25 2010
%E A000769 Edited by _N. J. A. Sloane_, Mar 19 2013 at the suggestion of Dominique Bernardi