A360924 Smallest number of moves needed to win Integer Lunar Lander with starting position (0,n).

0, 2, 3, 4, 4, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17, 18, 18, 18

Offset: 0

Author

Allan C. Wechsler, Feb 25 2023

Keywords

• nonn

Comments

See A360923 for game rules.

Data provided by Tom Karzes.

It appears that a(n) = 1 + floor(sqrt(4*n-3)) for n>0 (which is essentially A000267 and A027434). - N. J. A. Sloane, Feb 25 2023 [This is proved by Casteigts, Raffinot, and Schoeters (2020) in the form a(n) = ceiling(2*sqrt(n)). - Pontus von Brömssen, Mar 01 2023]

Examples

			From (0,6), a 5-move solution is (-1,5), (-2,3), (-2,1), (-1,0), (0,0). There is no shorter solution, so a(6) = 5.
		

Links

• Tom Karzes, Table of n, a(n) for n = 0..484
• Arnaud Casteigts, Mathieu Raffinot, and Jason Schoeters, VectorTSP: A Traveling Salesperson Problem with Racetrack-like acceleration constraints, arXiv:2006.03666 [cs.DS], 2020. See Lemma 7.

Crossrefs

Top row of table A360923. Cf. A360925, A360926.

See also A000267 and A027434.