A141000 Numbers k for which there is a solution to the Jumping Grasshopper game.

0, 1, 4, 9, 13, 16, 20, 21, 24, 25, 28, 29, 32, 33, 36, 37, 40, 41, 44, 45, 48, 49, 52, 53, 56, 57, 60, 61, 64, 65, 68, 69, 72, 73, 76, 77, 80, 81, 84, 85, 88, 89, 92, 93, 96, 97, 100, 101, 104, 105, 108, 109, 112, 113, 116, 117, 120, 121, 124, 125, 128, 129, 132, 133

Offset: 1

Author

Ivan Moscovich (i.moscovich2(AT)chello.nl), Jul 07 2008

Keywords

• nonn
• nice
• easy

Comments

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.)

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.

Further comments from David Applegate and N. J. A. Sloane, Jul 14 2008: (Start)

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.

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)

Examples

			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.)
		

References

• Ivan Moscovich, "MATH - Isn't It Beautiful!", 2009.

Links

• David Applegate, Notes on A141000.
• Ivan Moscovich, Grasshop Puzzle-Game.
• Index entries for linear recurrences with constant coefficients, signature (1,1,-1).

Crossrefs

Cf. A000980, A063865.

Programs

Mathematica

{0, 1, 4, 9, 13, 16}~Join~LinearRecurrence[{1, 1, -1}, {20, 21, 24}, 58] (* Jean-François Alcover, Nov 20 2019 *)
LinearRecurrence[{1,1,-1},{0,1,4,9,13,16,20,21,24},70] (* Harvey P. Dale, Mar 22 2025 *)

Tcl

# See the notes by D. Applegate above.

Formula

From Colin Barker, May 19 2013: (Start)

a(n) = (11 - (-1)^n + 4*n)/2 for n > 6.

a(n) = a(n-1) + a(n-2) - a(n-3) for n > 9.

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)