A242284 Greedy residue sequence of triangular numbers 3, 6, 10, 15, ...

2, 2, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0

Offset

2,1

Comments

Suppose that s = (s(1), s(2), ... ) is a sequence of real numbers such that for every real number u, at most finitely many s(i) are < u, and suppose that x > min(s). We shall apply the greedy algorithm to x, using terms of s. Specifically, let i(1) be an index i such that s(i) = max{s(j) < x}, and put d(1) = x - s(i(1)). If d(1) < s(i) for all i, put r = x - s(i(1)). Otherwise, let i(2) be an index i such that s(i) = max{s(j) < x - s(i(1))}, and put d(2) = x - s(i(1)) - s(i(2)). If d(2) < s(i) for all i, put r = x - s(i(1)) - s(i(2)). Otherwise, let i(3) be an index i such that s(i) = max{s(j) < x - s(i(1)) - s(i(2))}, and put d(3) = x - s(i(1)) - s(i(2)) - s(i(3)). Continue until reaching k such that d(k) < s(i) for every i, and put r = x - s(i(1)) - ... - s(i(k)). Call r the s-greedy residue of x, and call s(i(1)) + ... + s(i(k)) the s-greedy sum for x. If r = 0, call x s-greedy summable. If s(1) = min(s) < s(2), then taking x = s(i) successively for i = 2, 3,... gives a residue r(i) for each i; call (r(i)) the greedy residue sequence for s. When s is understood from context, the prefix "s-" is omitted. For A242284, s = (1,3,6,10,15,...); s(n) = n(n + 1)/2.

Links

Clark Kimberling, Table of n, a(n) for n = 2..2000

Example

n .... n(n+1)/2 ... a(n)
1 ... 1 ... (undefined)
2 ... 3 ... 2 = 3 - 1
3 ... 6 ... 2 = 6 - 3 - 1
4 ... 10 .. 0 = 15 - 10 - 3 - 1
5 ... 15 .. 1 = 21 - 15 - 6
6 ... 21 .. 0 = 28 - 21 - 6 - 1
7 ... 28 .. 0 = 36 - 28 - 6 - 1
8 ... 36 .. 1 = 45 - 36 - 6 - 3

Mathematica

z = 200;  s = Table[n (n + 1)/2, {n, 1, z}]; t = Table[{s[[n]], #, Total[#] == s[[n]]} &[DeleteCases[-Differences[FoldList[If[#1 - #2 >= 0, #1 - #2, #1] &, s[[n]], Reverse[Select[s, # < s[[n]] &]]]], 0]], {n, z}]
r[n_] := s[[n]] - Total[t[[n]][[2]]];
tr = Table[r[n], {n, 2, z}]  (* A242284 *)
c = Table[Length[t[[n]][[2]]], {n, 2, z}] (* A242285 *)
f = 1 + Flatten[Position[tr, 0]]  (* A242286 *)
f (f + 1)/2  (* A242287 *) (* Peter J. C. Moses, May 06 2014 *)

Crossrefs

Cf. A242285, A242286, A242287, A241833, A242288, A000217.

Sequence in context: A116511 A248211 A049502 * A333624 A381088 A306595

Adjacent sequences: A242281 A242282 A242283 * A242285 A242286 A242287

Keyword

nonn,easy

Author

Clark Kimberling, May 10 2014

Status

approved