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

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,7

Comments

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)

Links

Table of n, a(n) for n=1..60.

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.

Example

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!)

Crossrefs

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

Sequence in context: A227191 A214045 A136432 * A006065 A218933 A266746

Adjacent sequences: A172989 A172990 A172991 * A172993 A172994 A172995

Keyword

hard,nonn

Author

Zhao Hui Du, Feb 07 2010

Extensions

More terms added by Dmitry Kamenetsky, Feb 23 2012

Status

approved