A360925 -id:A360925 - cp's OEIS frontend

A360923 Table T(i,j), i >= 0, j >= 0, read by antidiagonals giving the smallest number of moves needed to win Integer Lunar Lander, starting from position (i,j). Game rules in comments.

0, 2, 1, 3, 3, 4, 4, 4, 5, 7, 4, 5, 6, 7, 9, 5, 5, 6, 8, 10, 12, 5, 6, 7, 8, 10, 12, 14, 6, 6, 7, 9, 10, 12, 14, 17, 6, 7, 8, 9, 11, 13, 15, 17, 19, 6, 7, 8, 9, 11, 13, 15, 17, 19, 21, 7, 7, 8, 10, 11, 13, 15, 17, 19, 22, 24, 7, 8, 9, 10, 12, 13, 15, 17, 20, 22, 24, 26

Offset: 0

Allan C. Wechsler, Feb 25 2023, using information about the original game from Eric Angelini, Hans Havermann, and M. F. Hasler, and data from Tom Karzes

A position in the game of Integer Lunar Lander consists of an ordered pair (i,j) of integers. There are always 3 legal moves, to (i+1,j+i+1), (i,j+i), and (i-1,j+i-1). The object of the game is to reach (0,0) in the minimum possible number of moves, T(i,j). The listed data was provided by Tom Karzes.
The ordered pair may be interpreted as the upward velocity and altitude of a vehicle; the object is to land the vehicle at zero velocity. In this version negative altitudes are permitted (that is, there is no crash detection, and the optimal trajectory is allowed to go underground without ill effects).
Are any of the numbers different if crashes are forbidden? It seems not, slowing to a soft landing always seems to produce a better solution than overshooting the surface and climbing back up. Of course from some initial positions like (-5,1) it is impossible not to crash. But it appears that if a soft landing is possible, then the optimal solution doesn't crash.
The game was invented in the early 1970's as a trivial version of a two-dimensional pencil-and-paper game that has been played at least since the first half of the 20th century.
Solution lengths for the corresponding game on triples would be interesting for (0,0,n) or (n,0,0).
Conjecture 1: For all i, j, T(i,j) differs from its eight neighbors by at most 3. The array of differences {T(i+1,j) - T(i,j)} might be worth studying, as well as the array {T(i,j) mod 2}. - N. J. A. Sloane, Feb 25 2023
Conjecture 2 (Start)
The zeroth row (0,j) is T(0,j) = 1+ floor(sqrt(4j-3)). j>0.
Let t_k = k(k+1)/2 be a triangular number.
Then the i-th row, {(i,j), j>=0}, is given by
  T(i,j) = T(0, j+t_{i-1}) + i for i>0.
In other words, to get the i-th row, shift the zeroth row to the left by i*(i-1)/2 places and add i to each term.
This would imply that the leading column, T(i,0), is equal to i+1+floor(sqrt(2*i^2-2*i-3)) for i >= 2.
(End) - N. J. A. Sloane, Feb 25 2023
Conjecture 1 seems to hold for all (i,j) except (1,0) and (2,1). - M. F. Hasler, Feb 27 2023

			For the starting position (2,3), a 6-move solution is (1,4), (0,4), (-1,3), (-2,1), (-1,0), (0,0). No shorter solution is possible, so T(2,3) = 6.
The upper left corner of the table i:
 0  2  3  4  4  5
 1  3  4  5  5
 4  5  6  6
 7  7  8
 9 10
12
The first few antidiagonals are
 0
 2 1
 3 3 4
 4 4 5 7
 4 5 6 7 9

Martin Gardner, "Sim, Chomp, and Race Track", "Mathematical Games", Scientific American, January, 1973. Reprinted in "Knotted Doughnuts and Other Mathematical Entertainments", W. H. Freeman, 1986, pp. 109-122.

Rémy Sigrist, Table of n, a(n) for n = 0..10010
Hans Havermann, Transcription of Gardner's account of the 2-D game.
Rémy Sigrist, C++ program
Rémy Sigrist, Scatterplot of (i, j) at an even number of moves from (0, 0) with abs(i), abs(j) <= 400
Rémy Sigrist, Scatterplot of (i, j) at up to 400 moves from (0, 0) (the color is function of the number of moves)
Wikipedia, Racetrack (game) (a 2D version), as of June 2022.

Cf. A360924, A360925, A360926.

M360923=Map(); T360923=0; S360923=[[0, 0]]; A360923(v, x)={iferr(mapget( M360923, [v,x]), E, while(!setsearch(S360923, [v,x]), foreach(S360923, vx, vx[1]>=0 && mapput(M360923, vx, T360923)); S360923 = Set(concat([[[u,vx[2]-vx[1]] | u<-[vx[1]-1..vx[1]+1], !mapisdefined(M360923, [u,vx[2]-vx[1]])] | vx <- S360923, vx[2]>=vx[1]])); T360923 += 1); T360923)} \\ M. F. Hasler, Feb 27 2023
T(i,j)=if(i,T(0,j+i*(i-1)\2)+i,j,sqrtint(4*j-3)+1) \\ Implementing Conjecture 2. - M. F. Hasler, Feb 27 2023

# From M. F. Hasler, Feb 27 2023: (Start)
def A360923(v, x, A={0:0, 1:{(0,0)}}):
    if (v,x) in A: return A[v,x]
    while (v,x) not in A[1]:
        A.update((vx,A[0]) for vx in A[1] if vx[0]>=0); A[0] += 1
        A[1] = {(u,x-v) for v,x in A[1] if x >= v
                for u in range(v-1,v+2) if (u,x-v) not in A}
    return A[0] # (End)

More terms from Rémy Sigrist, Feb 26 2023

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

Original entry on oeis.org

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

Allan C. Wechsler, Feb 25 2023

nonn

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]

			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.

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.

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

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

Original entry on oeis.org

0, 3, 6, 8, 11, 13, 16, 18, 20, 23, 25, 28, 30, 33, 35, 37, 40, 42, 45, 47, 49, 52, 54, 57, 59, 62, 64, 66, 69, 71, 74, 76, 78, 81, 83, 86, 88, 91, 93, 95, 98, 100, 103, 105, 107, 110, 112, 115, 117, 119, 122, 124, 127, 129, 132, 134, 136, 139, 141, 144, 146

Offset: 0

Allan C. Wechsler, Feb 25 2023

nonn

See A360923 for the rules of Integer Lunar Lander.
Data from Tom Karzes.
The conjectured formula for A360923 implies a formula for a(n). - N. J. A. Sloane, Feb 26 2023

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

Rémy Sigrist, Table of n, a(n) for n = 0..300
Rémy Sigrist, C++ program

Main diagonal of table A360923. Cf. A360924, A360925.

More terms from Rémy Sigrist, Feb 26 2023

cp's OEIS Frontend

A360923 Table T(i,j), i >= 0, j >= 0, read by antidiagonals giving the smallest number of moves needed to win Integer Lunar Lander, starting from position (i,j). Game rules in comments.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Python

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions