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,3

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)

References

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

Links

Table of n, a(n) for n=1..64.

David Applegate, Notes on A141000.

Ivan Moscovich, Grasshop Puzzle-Game.

Index entries for linear recurrences with constant coefficients, signature (1,1,-1).

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)

Example

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

Mathematica

{0, 1, 4, 9, 13, 16}~Join~LinearRecurrence[{1, 1, -1}, {20, 21, 24}, 58] (* Jean-François Alcover, Nov 20 2019 *)

Prog

(Tcl) # See the notes by D. Applegate above.

Crossrefs

Cf. A000980, A063865.

Sequence in context: A068949 A312876 A312877 * A312878 A312879 A140485

Adjacent sequences: A140997 A140998 A140999 * A141001 A141002 A141003

Keyword

nonn,nice,easy

Author

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

Status

approved