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

Author

Zhao Hui Du, Feb 07 2010

Keywords

• hard
• nonn

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)

Examples

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

Links

• 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.

Crossrefs

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

Extensions

More terms added by Dmitry Kamenetsky, Feb 23 2012