

A141001


a(n) = number of different landings of a grasshopper after n hops.


2



1, 1, 1, 2, 3, 4, 7, 11, 16, 21, 26, 32, 38, 44, 51, 59, 67, 75, 84, 94, 104, 114, 125, 137, 149, 161, 174, 188, 202, 216, 231, 247, 263, 279, 296, 314, 332, 350, 369, 389, 409, 429, 450, 472, 494, 516, 539, 563, 587, 611, 636, 662, 688, 714, 741, 769, 797
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

Consider a grasshopper (cf. A141000) that starts at x=0 at time 0, then makes successive hops of sizes 1, 2, 3, ..., n, subject to the constraint that it must always land on a point x >= 0; sequence gives number of different places x where it can land after the nth jump.
Here, unlike A141000, there is no restriction on how large x can be (of course x <= n(n+1)/2).


LINKS

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (3,4,4,3,1).


FORMULA

a(n) = floor(n * (n+1) / 4  1) for n >= 9. The induction proof for A141000 shows that for n >= 21, you hit all numbers of the right parity except n(n+1)/22 and n(n+1)/24. The floor expression handles the various parity cases.  David Applegate.
G.f.: (1  2*x + 2*x^2  x^3 + x^5 + x^6  x^7 + 2*x^8  2*x^9  x^12 + x^13) / ((1  x)^3*(1 + x^2)).  Colin Barker, May 21 2013
From Colin Barker, Aug 06 2017: (Start)
a(n) = (1/8+i/8) * ((5+5*i) + (i)^(1+n) + i^n + (1i)*n + (1i)*n^2) for n>8 where i=sqrt(1).
a(n) = 3*a(n1)  4*a(n2) + 4*a(n3)  3*a(n4) + a(n5) for n>9.
(End)


EXAMPLE

For example, for n=3 the grasshopper can hit 0=1+23 or 6=1+2+3; for n=4 it can hit 2=1+2+34, 4=1+23+4, or 10=1+2+3+4.


PROG

(PARI) Vec((1  2*x + 2*x^2  x^3 + x^5 + x^6  x^7 + 2*x^8  2*x^9  x^12 + x^13) / ((1  x)^3*(1 + x^2)) + O(x^60)) \\ Colin Barker, Aug 06 2017


CROSSREFS

Cf. A141000, A141002.
Sequence in context: A238492 A140827 A125621 * A333260 A196382 A120415
Adjacent sequences: A140998 A140999 A141000 * A141002 A141003 A141004


KEYWORD

nonn,easy


AUTHOR

David Applegate and N. J. A. Sloane, Jul 21 2008


STATUS

approved



