login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A141000 Numbers k for which there is a solution to the Jumping Grasshopper game. 6
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 (list; graph; refs; listen; history; text; internal format)
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.

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

AUTHOR

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 19 08:05 EDT 2021. Contains 347556 sequences. (Running on oeis4.)