The OEIS is supported by the many generous donors to the OEIS Foundation.

 Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 59th year, we have over 358,000 sequences, and we’ve crossed 10,300 citations (which often say “discovered thanks to the OEIS”). Other ways to Give
 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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. (Formerly M3252 N1313) 15
 0, 1, 1, 4, 5, 11, 22, 57, 51, 156, 158, 566, 499, 1366, 3978, 5900, 7094, 19204 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,4 COMMENTS This means no three points on any line, not just lines in the X or Y directions. A000755 gives the total number of solutions (as opposed to the number of equivalence classes). It is conjectured that a(n)=0 for all sufficiently large n. Flammenkamp's web site reports that at least one solution is known for all n <= 46 and n=48, 50, 52. From R. K. Guy, Oct 22 2004: (Start) I got the no-three-in-line problem from Heilbronn over 50 years ago. See Section F4 in UPINT. 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 3c^3 = 2Pi^2 i.e. c ~ 1.87. As recently as last March, Gabor Ellmann pointed out an error in our heuristic reasoning, which, when corrected, gives 3c^2 = Pi^2, or c ~ 1.813799. (End) REFERENCES 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. B. Anderson, Journal of Combinatorial Theory Series A, V.27/1979 pp. 365 - 366. D. Craggs and R. Hughes-Jones, Journal of Combinatorial Theory Series A, V.20/1976 pp. 363 - 364 H. E. Dudeney, Amusements in Mathematics, Nelson, Edinburgh 1917, pp. 94, 222 A. Flammenkamp, Progress in the no-three-in-line problem, J. Combinat. Theory A 60 (1992), 305-311. A. Flammenkamp, Progress in the no-three-in-line problem. II. J. Combin. Theory Ser. A 81 (1998), no. 1, 108-113. M. Gardner, Scientific American V236 / March 1977, pp. 139 - 140 M. Gardner, Penrose Tiles to Trapdoor Ciphers. Freeman, NY, 1989, p. 69. R. K. Guy, Unsolved combinatorial problems, pp. 121-127 of D. J. A. Welsh, editor, Combinatorial Mathematics and Its Applications. Academic Press, NY, 1971. R. K. Guy, Unsolved Problems Number Theory, Section F4. 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. R. R. Hall, T. H. Jackson, A. Sudberry and K. Wild, Journal of Combinatorial Theory Series A, V.18/1975 pp. 336 - 341 H. Harborth, P. Oertel and T. Prellberg, Discrete Math. V73/1988 pp. 89-90 T. Kløve, Journal of Combinatorial Theory Series A, V.24/1978 pp. 126 - 127 T. Kløve, Journal of Combinatorial Theory Series A, V.26/1979 pp. 82 - 83 K. F. Roth, Journal London Math. Society V.26 / 1951, pp. 204 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence). N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence). LINKS Benjamin Chaffin, No-Three-In-Line Problem. Alec S. Cooper, Oleg Pikhurko, John R. Schmitt and Gregory S. Warrington, Martin Gardner's minimum no-3-in-a-line problem, arXiv:1206.5350 [math.CO]. Also Amer. Math. Monthly, 121 (2014), 213-221. A. Flammenkamp, Progress in the no-three-in-line problem A. Flammenkamp, Solutions of the no-three-in-line problem R. K. Guy and P. A. Kelly, The No-Three-Line Problem, Research Paper 33, Department of Mathematics, Univ. of Calgary, Calgary, Alberta, 1968. [Annotated scanned copy] R. K. Guy and P. A. Kelly, The No-Three-Line Problem, condensed version in Canad. Math. Bull. Vol. 11, pp. 527-531, 1968. [Annotated scanned copy] R. K. Guy, P. A. Kelly, N. J. A. Sloane, Correspondence, 1968-1971 Eric Weisstein's World of Mathematics, Point Lattice. Eric Weisstein's World of Mathematics, No-Three-in-a-Line-Problem EXAMPLE a(3)=1: X X o X o X o X X CROSSREFS Cf. A000755, A000938, A037185, A037186, A037187, A037188, A037189, A047840, A212807, A235453. See A272651 for the maximal number of no-3-in-line points on an n X n grid, and A277433 for minimal saturated. Cf. A194136 (triangular grid), A280537 (3D grid, no 4 in plane). Sequence in context: A036539 A279710 A303956 * A246495 A050831 A056799 Adjacent sequences: A000766 A000767 A000768 * A000770 A000771 A000772 KEYWORD hard,nonn,nice,more AUTHOR EXTENSIONS a(17) and a(18) from Benjamin Chaffin, Apr 05 2006 Minor edits from N. J. A. Sloane, May 25 2010 Edited by N. J. A. Sloane, Mar 19 2013 at the suggestion of Dominique Bernardi STATUS approved

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

Last modified December 6 21:00 EST 2022. Contains 358648 sequences. (Running on oeis4.)