OFFSET
1,2
COMMENTS
A126684 is described as the fastest-growing sequence such that every nonnegative integer is the sum of two of its terms. However, if one uses a greedy algorithm to find a representation as a sum of its terms, the length of the representation will typically be more than two. This sequence gives the numbers whose greedy representations have record-setting lengths. For example, a(3) = 13 because (although 13 = 8 + 5, a representation as a sum of two terms of A126684) the greedy algorithm represents it as the three-term sum 13 = 10 + 2 + 1.
LINKS
Colin Barker, Table of n, a(n) for n = 1..1000
David Eppstein, Making Change in 2048, arXiv:1804.07396 [cs.DM], 2018.
Index entries for linear recurrences with constant coefficients, signature (6,-9,4).
FORMULA
a(n) = 4*a(n-1) + 2*n - 5.
From Colin Barker, Apr 13 2018: (Start)
G.f.: x*(1 - 3*x + 4*x^2) / ((1 - x)^2*(1 - 4*x)).
a(n) = (7 + 2^(1+2*n) - 6*n) / 9.
a(n) = 6*a(n-1) - 9*a(n-2) + 4*a(n-3) for n>3.
(End)
MATHEMATICA
Fold[Append[#1, 4 Last[#1] + 2 #2 - 5] &, {1}, Range[2, 25]] (* Michael De Vlieger, Apr 12 2018 *)
PROG
(PARI) Vec(x*(1 - 3*x + 4*x^2) / ((1 - x)^2*(1 - 4*x)) + O(x^60)) \\ Colin Barker, Apr 13 2018
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
David Eppstein, Apr 12 2018
STATUS
approved