

A141000


Numbers n 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 n such that there is a choice of signs s_1, s_2, ..., s_n (each +1 or 1) so that (i) 0 <= Sum_{i = 1..j } i*s_i <= n for all 1 <= j <= n1 and (ii) Sum_{i = 1..n } i*s_i = n. (This forces s_1 = s_2 = s_n = +1.)
It has been shown by Dick Hess and Benji Fisher that a number n >= 20 is in the sequence iff n == 0 or 1 mod 4. (For a proof see the Applegate link.) It is easy to see that n == 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 = n, n1, ..., 1, let target_j = n  Sum_{i = j+1..n} 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_n is different from n, with the additional exception of (8,20). (End)


REFERENCES

Ivan Moscovich, "MATH  Isn't It Beautiful !", 2009 (to appear)


LINKS

Table of n, a(n) for n=1..64.
D. Applegate, Notes on A141000
Ivan Moscovich, Grasshop PuzzleGame


FORMULA

Conjecture: a(n) = (11(1)^n+4*n)/2 for n>6. a(n) = a(n1)+a(n2)a(n3) for n>9. G.f.: x^2*(x^7+2*x^6+2*x^4x^34*x^23*x1) / ((x1)^2*(x+1)).  Colin Barker, May 19 2013


EXAMPLE

4 is a member because we can take s_1 = s_2 = s_4 = +1, s_3 = 1. Note in particular that 1+23+4 = 4. (See illustration.)


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



