%I #31 Jul 18 2018 18:55:09
%S 1,3,13,55,225,907,3637,14559,58249,233011,932061,3728263,14913073,
%T 59652315,238609285,954437167,3817748697,15270994819,61083979309,
%U 244335917271,977343669121,3909374676523,15637498706133,62549994824575,250199979298345,1000799917193427
%N a(n) is the smallest number whose greedy representation as a sum of terms of A126684 uses n terms.
%C 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.
%H Colin Barker, <a href="/A302757/b302757.txt">Table of n, a(n) for n = 1..1000</a>
%H David Eppstein, <a href="https://arxiv.org/abs/1804.07396">Making Change in 2048</a>, arXiv:1804.07396 [cs.DM], 2018.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (6,-9,4).
%F a(n) = 4*a(n-1) + 2*n - 5.
%F From _Colin Barker_, Apr 13 2018: (Start)
%F G.f.: x*(1 - 3*x + 4*x^2) / ((1 - x)^2*(1 - 4*x)).
%F a(n) = (7 + 2^(1+2*n) - 6*n) / 9.
%F a(n) = 6*a(n-1) - 9*a(n-2) + 4*a(n-3) for n>3.
%F (End)
%t Fold[Append[#1, 4 Last[#1] + 2 #2 - 5] &, {1}, Range[2, 25]] (* _Michael De Vlieger_, Apr 12 2018 *)
%o (PARI) Vec(x*(1 - 3*x + 4*x^2) / ((1 - x)^2*(1 - 4*x)) + O(x^60)) \\ _Colin Barker_, Apr 13 2018
%Y Cf. A126684.
%K nonn,easy
%O 1,2
%A _David Eppstein_, Apr 12 2018