A193838 Size k of smallest square of k X k lattice points from which n points with distinct mutual distances can be chosen.

1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 15, 16, 18

Offset: 1

Author

Hugo Pfoertner, Aug 06 2011

Keywords

• nonn
• hard
• more

Comments

Upper bounds for a(14) to a(26): 18, 21, 24, 26, 28, 29, 33, 36, 37, 40, 43, 46, 49. These have been obtained from the results of the Al Zimmermann competition. - Dmitry Kamenetsky, Apr 23 2021

Upper bounds for a(15) to a(18): 20, 22, 24, 27. - Fausto A. C. Cariboni, Jul 16 2022

Examples

			a(1) is the degenerate case of a single point, a(2)=2 is trivial.
a(3)=3: The points ((1,2),(3,1),(3,2)) have distinct mutual squared distances 1, 4, 5.
a(8)=9 is the first square for which k>n: ((1,1), (1,4), (2,2), (6,1), (7,6), (7,7), (9,2), (9,4)) have 7*8/2=28 mutual squared distances: 1, 2, 4, 5, 8, 9, 10, 13, 17, 18, 20, 25, 26, 29, 34, 37, 40, 41, 45, 49, 50, 53, 61, 64, 65, 68, 72, 73, and no configuration of 8 points fitting on an 8 X 8 square exists.
a(10)=11, only two subsets barring symmetry:
  {(0,0), (0,2), (0,3), (0,7), (1,10), (5,4), (6,0), (8,7), (9,8), (10, 10)},
  {(0,0), (0,6), (0,7), (1,2), (4,10), (7,8), (7,10), (9,2), (9,6), (10,5)}.
a(11)=13, one of the four subsets of the 12 X 13 grid, barring symmetry: {(0,0), (0,1), (0,9), (0,12), (2,0), (5,3), (6,12), (7,0), (8,4), (10,10), (11,11)}
a(12)=15 is satisfied by {(0,0), (1,0), (1,12), (3,0), (7,0), (7,14), (9,4), (12,11), (13,3), (13,8), (14,2), (14,13)}. - _Sean A. Irvine_, Jul 13 2020
a(13)=16 is satisfied by {(1,1), (2,2), (2,16), (4,14), (6,14), (7,16), (8,8), (11,2), (11,5), (13,15), (13,16), (16,1), (16,8)}. - _Bert Dobbelaere_, Sep 20 2020
		

References

• R. K. Guy, Unsolved Problems in Number Theory, Third Edition, Springer New York, 2004, F2, 367-368.
• Keith F. Lynch, Posting to Math Fun Mailing List, Apr 02 2016.

Links

• P. Erdős and R. K. Guy, Distinct distances between lattice points, Elemente der Mathematik 25 (1970), 121-123.
• Sean A. Irvine, Java program (github)
• Dmitry Kamenetsky, Best known solutions for n <= 13.
• Dmitry Kamenetsky, 7x7 Golomb Square, Puzzling StackExchange, April 2021.
• Matt Parker, Unique Distancing Puzzle.
• Samuel B. Reid, The unique solution that causes a(7) to be 7.
• Wolfram Demonstration Project, No Repeated Distances.
• A. Zimmermann, Al Zimmermann's Programming Contests: Point Packing. (Oct 10, 2009).

Crossrefs

Cf. A193839, A003022.

See A271490 for the inverse function.

Extensions

a(10)-a(11) corrected by Ehit Dinesh Agarwal, May 28 2020

a(12) from Sean A. Irvine, Jul 13 2020

a(13) from Bert Dobbelaere, Sep 20 2020

a(14) from Fausto A. C. Cariboni, Jul 16 2022