Orchard-Planting Problem

The orchard-planting problem (also known as the orchard problem or tree-planting problem) asks for the maximum number of straight lines containing exactly of distinct points in the plane. Equivalently, the points represent trees and the lines represent rows, with positive integers . The problem for is attributed to Sylvester (Croft et al. 1991, p. 159).

Here "orchard" refers to the arrangement of trees into rows. For visible points, orchard imagery instead refers to a fixed point lattice and unobstructed line segments between lattice points.

The following table gives values of or bounds on them reported by Friedman.

	3	4	5
OEIS	A003035	A006065	A008997
3	1	--	--
4	1	1	--
5	2	1	1
6	4	1	1
7	6	2	1
8	7	2	1
9	10	3	2
10	12	5	2
11	16	6	2
12	19	7	3
13		9	3
14		10	4
15		12
16	37	15
17		16
18		18
19
20
21
22
23
24
25

Interval entries in the table give lower and upper bounds (Friedman).

Sylvester showed that

(1)

where is the floor function (Ball and Coxeter 1987). Burr et al. (1974) have shown using cubic curves that

(2)

Known sporadic constructions for , 11, 16, and 19 have 6, 16, 37, and 52 three-point lines, respectively, compared with 5, 15, 35, and 51 from the right-hand side of the preceding bound (Pegg 2018). At least these four sporadic values are therefore known, while the existence of any others remains open.

Green and Tao (2013) proved that the preceding bound is exact for all sufficiently large . In other words, for all sufficiently large . For , the general upper bound is

(3)

where is the ceiling function.