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.

%I A360923 #83 Jul 09 2025 05:00:11
%S A360923 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,
%T A360923 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,
%U A360923 10,11,13,15,17,19,22,24,7,8,9,10,12,13,15,17,20,22,24,26
%N 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.
%C A360923 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_.
%C A360923 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).
%C A360923 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.
%C A360923 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.
%C A360923 Solution lengths for the corresponding game on triples would be interesting for (0,0,n) or (n,0,0).
%C A360923 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
%C A360923 Conjecture 2 (Start)
%C A360923 The zeroth row (0,j) is T(0,j) = 1+ floor(sqrt(4j-3)). j>0.
%C A360923 Let t_k = k(k+1)/2 be a triangular number.
%C A360923 Then the i-th row, {(i,j), j>=0}, is given by
%C A360923   T(i,j) = T(0, j+t_{i-1}) + i for i>0.
%C A360923 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.
%C A360923 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.
%C A360923 (End) - _N. J. A. Sloane_, Feb 25 2023
%C A360923 Conjecture 1 seems to hold for all (i,j) except (1,0) and (2,1). - _M. F. Hasler_, Feb 27 2023
%D A360923 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.
%H A360923 Rémy Sigrist, <a href="/A360923/b360923.txt">Table of n, a(n) for n = 0..10010</a>
%H A360923 Hans Havermann, <a href="http://chesswanks.com/txt/RaceTrack.html">Transcription of Gardner's account of the 2-D game</a>.
%H A360923 Rémy Sigrist, <a href="/A360923/a360923.txt">C++ program</a>
%H A360923 Rémy Sigrist, <a href="/A360923/a360923.png">Scatterplot of (i, j) at an even number of moves from (0, 0) with abs(i), abs(j) <= 400</a>
%H A360923 Rémy Sigrist, <a href="/A360923/a360923_1.png">Scatterplot of (i, j) at up to 400 moves from (0, 0)</a> (the color is function of the number of moves)
%H A360923 Wikipedia, <a href="https://en.wikipedia.org/wiki/Racetrack_(game)">Racetrack (game)</a> (a 2D version), as of June 2022.
%e A360923 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.
%e A360923 The upper left corner of the table i:
%e A360923  0  2  3  4  4  5
%e A360923  1  3  4  5  5
%e A360923  4  5  6  6
%e A360923  7  7  8
%e A360923  9 10
%e A360923 12
%e A360923 The first few antidiagonals are
%e A360923  0
%e A360923  2 1
%e A360923  3 3 4
%e A360923  4 4 5 7
%e A360923  4 5 6 7 9
%o A360923 (C++) See Links section.
%o A360923 (PARI) 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
%o A360923 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
%o A360923 (Python) # From _M. F. Hasler_, Feb 27 2023: (Start)
%o A360923 def A360923(v, x, A={0:0, 1:{(0,0)}}):
%o A360923     if (v,x) in A: return A[v,x]
%o A360923     while (v,x) not in A[1]:
%o A360923         A.update((vx,A[0]) for vx in A[1] if vx[0]>=0); A[0] += 1
%o A360923         A[1] = {(u,x-v) for v,x in A[1] if x >= v
%o A360923                 for u in range(v-1,v+2) if (u,x-v) not in A}
%o A360923     return A[0] # (End)
%Y A360923 Cf. A360924, A360925, A360926.
%K A360923 nonn,tabl,nice
%O A360923 0,2
%A A360923 _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_
%E A360923 More terms from _Rémy Sigrist_, Feb 26 2023