A006065 -id:A006065 - cp's OEIS frontend

A003035 Maximal number of 3-tree rows in n-tree orchard problem.

Original entry on oeis.org

0, 0, 1, 1, 2, 4, 6, 7, 10, 12, 16, 19, 22, 26

Offset: 1

N. J. A. Sloane

It is known that a(15) is 31 or 32, a(16)=37 and a(17) is 40, 41 or 42. - N. J. A. Sloane, Feb 11 2013

P. Brass et al., Research Problems in Discrete Geometry, Springer, 2005.
S. A. Burr, in The Mathematical Gardner, Ed. D. A. Klarner, p. 94, Wadsworth, 1981.
S. A. Burr, B. Grünbaum and N. J. A. Sloane, The Orchard Problem, Geometriae Dedicata, 2 (1974), 397-424.
Jean-Paul Delahaye, Des points qui s'alignent... ou pas, "Logique et calcul" column, "Pour la science", June 2021.
H. E. Dudeney, Amusements in Mathematics, Nelson, London, 1917, page 56.
Paul Erdos and George Purdy. Extremal problems in geometry, Chapter 17, pages 809-874 in R. L. Graham et al., eds., Handbook of Combinatorics, 2 vols., MIT Press, 1995. See Section 3.7.
M. Gardner, Time Travel and Other Mathematical Bewilderments. Freeman, NY, 1988, Chap. 22.
B. Grünbaum, Arrangements and Spreads. American Mathematical Society, Providence, RI, 1972, p. 22.
John Jackson, Rational Amusements for Winter Evenings, London, 1821.
F. Levi, Geometrische Konfigurationen, Hirzel, Leipzig, 1929.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

S. A. Burr, B. Grünbaum and N. J. A. Sloane, The Orchard Problem, Geometriae Dedicata, 2 (1974), 397-424.
Zhao Hui Du, Orchard Planting Problem [From _Zhao Hui Du_, Nov 20 2008] [Seems to concentrate on the 4 trees per line version. - _N. J. A. Sloane_, Oct 16 2010]
Noam D. Elkies, On some points-and-lines problems and configurations, arXiv:math/0612749 [math.MG], 2006; [Concerned with other versions of the problem].
Erich Friedman, Table of values and bounds for up to 25 trees
Z. Füredi and I. Palasti, Arrangements of lines with a large number of triangles, Proc. Amer. Math. Soc., 92(4):561-566, 1984.
B. Green, T. Tao, On sets defining few ordinary lines, arXiv:1208.4714. (Shows that a(n) = [n(n-3)/6]+1 for all sufficiently large n.)
R. Padmanabhan, Alok Shukla, Orchards in elliptic curves over finite fields, arXiv:2003.07172 [math.NT], 2020.
Ed Pegg, Jr., Cultivating New Solutions for the Orchard-Planting Problem
Ed Pegg, Jr., Illustration showing that a(15) >= 31 [Another version that uses all 31 triples from -7 to 7 which sum to 0 (mod 15). Coordinates are: {-7, {-1 - Sqrt[3], -1 + 2 Sqrt[3]}}, {-6, {2 (2 + Sqrt[3]), -5}}, {-5, {0, -3}}, {-4, {-2 (2 + Sqrt[3]), -1}}, {-3, {-2, 1}}, {-2, {2, -1}}, {-1, {2 (2 + Sqrt[3]), 1}}, {0, {0, 3}}, {1, {-2 (2 + Sqrt[3]), 5}}, {2, {1 + Sqrt[3], 1 - 2 Sqrt[3]}}, {3, {-2 (2 + Sqrt[3]), -1 - 2 Sqrt[3]}}, {4, {-2 - Sqrt[3], 1}}, {5, {0, 0}}, {6, {2 + Sqrt[3], -1}}, {7, {2 (2 + Sqrt[3]), 1 + 2 Sqrt[3]}}]
Ed Pegg, Jr., Illustration showing that a(15) >= 31 and a(16) >= 37
Ed Pegg, Jr., Illustration for a(16) = 37 [Based on a drawing in Burr-Grünbaum-Sloane (1974). The bottom left point is at -(sqrt(3), sqrt(5)). Note that 3 points and one line are at infinity.]
Ed Pegg, Jr., Illustrations of constructions for 9 through 28 trees.
G. B. Purdy and J. W. Smith, Lines, circles, planes and spheres, Discrete Comput. Geom., 44 (2010), 860-882. [Makes use of A003035 in a formula. - _N. J. A. Sloane_, Oct 19 2017]
N. J. A. Sloane, Illustration of initial terms (from Grünbaum-Burr-Sloane paper)
J. Solymosi and M. Stojakovic, Many collinear k-tuples with no k + 1 collinear points, Discrete & Computational Geometry, October 2013, Volume 50, Issue 3, pp 811-820; also arXiv 1107.0327, 2013.
Eric Weisstein's World of Mathematics, Orchard-Planting Problem.

Cf. A006065 (4 trees/row), A008997 (5 trees per row), A058212.

13 and 14 trees result from Zhao Hui Du, Nov 20 2008

Replaced my old picture with link to my write-up. - Ed Pegg Jr, Feb 02 2018

A008997 Orchard problem with 5 trees in a row (may not have all been proved optimal).

Original entry on oeis.org

0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4, 6, 6, 7, 9, 10, 11

Offset: 1

N. J. A. Sloane

Berloquin shows that a(21) >= 12.

S. A. Burr, B. Grünbaum and N. J. A. Sloane, The Orchard Problem, Geometriae Dedicata, 2 (1974), 397-424.
M. Gardner, Time Travel and Other Mathematical Bewilderments. Freeman, NY, 1988, Chap. 22.

P. Berloquin, a(21) >= 12 (from an article in Jeux & Strategies from 1983 - see Fig. 13)
S. A. Burr, B. Grünbaum and N. J. A. Sloane, The Orchard Problem, Geometriae Dedicata, 2 (1974), 397-424.
Erich Friedman, Table of values and bounds for up to 21 trees
Eric Weisstein's World of Mathematics, Orchard-Planting Problem

Cf. A003035, A006065.

A172992 Maximal number of 4-tree rows in n-tree orchard problem in which the tree coordinates are integers.

Original entry on oeis.org

0, 0, 0, 1, 1, 1, 2, 2, 3, 5, 6, 7, 9, 10, 12, 14, 15, 17, 20, 23, 24, 26, 28, 30, 32, 34, 36, 39, 41, 44, 46, 48, 50, 52, 54, 57, 59, 62, 64, 67, 69, 72, 75, 78, 80, 83, 86, 89, 91, 94, 97, 100, 103, 106, 109, 112, 116, 120, 123, 126

Offset: 1

Zhao Hui Du, Feb 07 2010

From Dmitry Kamenetsky, Feb 23 2012: (Start)
At the end of 2011 there was a 3-month programming competition (http://infinitesearchspace.dyndns.org/orchardplanting) for this problem for n in the range [11,60]. Later there was an unofficial contest (http://infinitesearchspace.dyndns.org/content/orchard-mini-contest) for finding optimal solutions that can be placed on the smallest possible grids.
The terms in this sequences are the best known solutions to date and they may not be optimal.
Any solution that can be represented with integer coordinates can also be represented with real-valued coordinates, hence A172992(n)<=A006065(n). It is believed (but not proved) that some real-valued solutions cannot be represented by integer-valued solutions. For example A172992(16)=14, but A006065(16)=15. (End)

			It is possible to place 10 points on an integer grid such that there are 5 straight lines with exactly 4 points lying on each line. Hence a(10) is 5. - _Dmitry Kamenetsky_, Feb 23 2012 (see the illustration by _Hugo Pfoertner_!)

Zhao Hui Du, More detailed results (no longer valid)
Infinite Search Space, Competition for the tree-planting problem, 2011.
Infinite Search Space, Orchard mini-contest, 2012.
Dmitry Kamenetsky, Best known solutions for n <= 29.
Hugo Pfoertner, Illustration of a(10) = 5.

A006065 is the same problem, but with real-valued tree coordinates.

More terms added by Dmitry Kamenetsky, Feb 23 2012

A273916 The Bingo-4 problem: minimal number of stones that must be placed on an infinite square grid to produce n groups of exactly 4 stones each. Groups consist of adjacent stones in a horizontal, vertical or diagonal line.

Original entry on oeis.org

0, 4, 7, 9, 11, 12, 12, 14, 15, 16, 16, 18, 19, 20, 22, 24

Offset: 0

Jiangshan Sun, Jason Y.S. Chiu, Hong-Chang Wang, Jun 03 2016

You are permitted to put 5 or more adjacent stones in a line, but cannot count them as a group.
Each pair of stones has at most one group that counts going through them. - David A. Corneth, Aug 01 2016
a(n) >= n and a(n+m) <= a(n) + a(m), e.g., a(16) <= a(10) + a(6) = 28. Placing stones in a 4 X k rectangular array shows that a(3k) <= 4(k+2). Fekete's subadditive lemma shows that 1 <= lim_{n->oo} a(n)/n <= 4/3 exists. - Chai Wah Wu, Jul 31 2016
Limit_{n->oo} a(n)/n = 1. See arXiv link. - Chai Wah Wu, Aug 25 2016

			From _M. F. Hasler_, Jul 30 2016: (Start)
One can get n=3 groups using a(3) = 9 stones (O) as follows:
   O O O O     The 3 groups are:
   . O O .     (1) the first line,
   . O . .     (2) the second column,
   O O . .     (3) the antidiagonal.
See the link for more examples. (End)

Hong-Chang Wang, Illustration of initial terms.
Chai Wah Wu, Minimal number of points on a grid forming patterns of blocks, arXiv:1608.07247 [math.CO], 2016.

See also the 4-trees-in-a-row orchard problem, A006065.

Edited by N. J. A. Sloane, Jul 29 2016

A337747 Maximal number of 4-point circles passing through n points on a plane.

Original entry on oeis.org

0, 0, 0, 1, 1, 3, 6, 12, 14, 22, 30, 45

Offset: 1

Dmitry Kamenetsky, Sep 17 2020

This is a variant of the orchard-planting problem that uses circles instead of straight lines.
The maximal number of 3-point circles passing through n points on a plane is binomial(n,3). Given an arrangement of n points in general position, any choice of three points defines a circle. - Peter Kagey, Oct 05 2020
Paul Panzer provides upper and lower bounds:
  a(n) <= floor(n*(n-1)*(n-2)/24).
  a(n) >= 2 + n*((n-2)*(n-2) + 4)/32 for n == 0 (mod 4) and n >= 8.
  a(n) >= 2 + (n-1)*((n-1)*(n-5) + 16)/32 for n == 1 (mod 4) and n >= 9.
  a(n) >= 2 + n*(n-2)*(n-2)/32 for n == 2 (mod 4) and n >= 10.
  a(n) >= 2 + (n-1)*((n-3)*(n-3) + 16)/32 for n == 3 (mod 4) and n >= 11.
It seems that a(n) = n*((n-2)*(n-2) + 4)/32 + 2*A008610(n/2-4) if n == 0 (mod 4) and n >= 8. - Zhao Hui Du, Dec 14 2022
The number of 4-point circles passing through n points (2*cos(t_k), sin(t_k)) where t_k = (2k-1)*Pi/n, k=1,2,...,n is A008610(n-4), so A337747(n) >= A008610(n-4), so A337747(n) ~ n^3/24 for sufficiently large n. - Zhao Hui Du, Dec 15 2022

			See examples in links.

Zhao Hui Du, Source code and running data to show there are at most 30 circles for 11 trees.
Zhao Hui Du, A group of solutions with 30 circles for 11 trees.
Zhao Hui Du, Geogebra dynamic graph for a group of solution to 12 trees 45 circles (4 trees per circle).
Zhao Hui Du, Best known solution for 14 trees (73 circles), removing point I from the solution to form a solution with 13 trees and 53 circles so that a(13) >= 53, a(14) >= 73.
Zhao Hui Du, Graph for 14 trees 73 circles (all black circles have same patterns as that in that in two co-center regular polygons (Paul Panzer's solution) while red circles are those extra circles).
Zhao Hui Du, Graph for 16 trees with 120 circles.
Zhao Hui Du, Geogebra graph for 16 trees with 120 circles (parameter d and m could be any real value and point PP could be moving too), removing any tree to form 15 trees with 90 circles so that a[15]>=90, a[16]>=120.
Zhao Hui Du, Chinese webpage to show that the number of 4 points circle through the n points in ellipse could be transformed to the number to pick 4 different numbers k1,k2,k3,k4 from 1 to n so that n|2+k1+k2+k3+k4, which is equal to A008610(n-4).
Dmitry Kamenetsky, Best known solutions for n <= 13.
Dmitry Kamenetsky, Orchard planting problem, Puzzling StackExchange, August 2020.
Dmitry Kamenetsky, General orchard planting problem, Puzzling StackExchange, September 2020.

Cf. A003035 (the original orchard problem), A006065.

a(11) from Zhao Hui Du, Nov 22 2022

a(12) from Zhao Hui Du, Dec 01 2022

A172993 Maximal number of 4-tree rows in n-tree orchard problem in which the coordinates of trees may be complex numbers.

Original entry on oeis.org

0, 0, 0, 1, 1, 1, 2, 2, 3, 5, 6, 9, 9, 11, 13, 15, 17, 18, 20, 23

Offset: 1

Zhao Hui Du, Feb 07 2010

			a(12)=9: Such as 12 trees in 9 rows: example for 12 trees with 9 rows: ABCD,AEFG,AHIJ,BEHK,BFIL,CEJL,CGIK,DFJK,DGHL. Let t^2+t+1=0, coordinate in projective plane: A[0:1:0], B[1:0:0], C[1:1+t:0], D[1:t:0], E(0,0), F(0,1), G(0,-t), H(1,0), I(1,1), J(1,t+1), K(1+t,0), L(-t,1).

Zhao Hui Du, Orchard planting problem with 4 trees per row

Cf. A006065.

a(12) corrected by Zhao Hui Du, Oct 30 2019

cp's OEIS Frontend

A003035 Maximal number of 3-tree rows in n-tree orchard problem.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A008997 Orchard problem with 5 trees in a row (may not have all been proved optimal).

Views

Author

Keywords

Comments

References

Links

Crossrefs

A172992 Maximal number of 4-tree rows in n-tree orchard problem in which the tree coordinates are integers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A273916 The Bingo-4 problem: minimal number of stones that must be placed on an infinite square grid to produce n groups of exactly 4 stones each. Groups consist of adjacent stones in a horizontal, vertical or diagonal line.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A337747 Maximal number of 4-point circles passing through n points on a plane.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A172993 Maximal number of 4-tree rows in n-tree orchard problem in which the coordinates of trees may be complex numbers.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions