|
%I #46 Dec 10 2023 17:41:02
%S 0,1,4,9,13,16,20,21,24,25,28,29,32,33,36,37,40,41,44,45,48,49,52,53,
%T 56,57,60,61,64,65,68,69,72,73,76,77,80,81,84,85,88,89,92,93,96,97,
%U 100,101,104,105,108,109,112,113,116,117,120,121,124,125,128,129,132,133
%N Numbers k for which there is a solution to the Jumping Grasshopper game.
%C That is, numbers k such that there is a choice of signs s_1, s_2, ..., s_k (each +1 or -1) so that (i) 0 <= Sum_{i = 1..j } i*s_i <= k for all 1 <= j <= k-1 and (ii) Sum_{i = 1..k } i*s_i = k. (This forces s_1 = s_2 = s_k = +1.)
%C It has been shown by Dick Hess and Benji Fisher that a number k >= 20 is in the sequence iff k == 0 or 1 (mod 4). (For a proof see the Applegate link.) It is easy to see that k == 0 or 1 (mod 4) is a necessary condition.
%C Further comments from _David Applegate_ and _N. J. A. Sloane_, Jul 14 2008: (Start)
%C An obvious greedy algorithm (working backwards) does the following: For j = k, k-1, ..., 1, let target_j = k - Sum_{i = j+1..k} i * s_i and set s_j = +1 if target_j >= j and s_j = -1 otherwise. This works unless we hit one of five exceptions, in which we must set s_j = -1 instead of +1.
%C The five exceptions are when (j, target_j) is (5,5), (6,9), (7,14), (8,8), or (9,13). The algorithm also works for the more general case when the target total target_k is different from k, with the additional exception of (8,20). (End)
%D Ivan Moscovich, "MATH - Isn't It Beautiful!", 2009.
%H David Applegate, <a href="/A141000/a141000.txt">Notes on A141000</a>.
%H Ivan Moscovich, <a href="/A141000/a141000.pdf">Grasshop Puzzle-Game</a>.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,-1).
%F From _Colin Barker_, May 19 2013: (Start)
%F a(n) = (11 - (-1)^n + 4*n)/2 for n > 6.
%F a(n) = a(n-1) + a(n-2) - a(n-3) for n > 9.
%F G.f.: -x^2*(x^7+2*x^6+2*x^4-x^3-4*x^2-3*x-1) / ((x-1)^2*(x+1)). (End)
%e 4 is a member because we can take s_1 = s_2 = s_4 = +1, s_3 = -1. Note in particular that 1 + 2 -3 + 4 = 4. (See the illustration.)
%t {0, 1, 4, 9, 13, 16}~Join~LinearRecurrence[{1, 1, -1}, {20, 21, 24}, 58] (* _Jean-François Alcover_, Nov 20 2019 *)
%o (Tcl) # See the notes by D. Applegate above.
%Y Cf. A000980, A063865.
%K nonn,nice,easy
%O 1,3
%A Ivan Moscovich (i.moscovich2(AT)chello.nl), Jul 07 2008
|
