login
a(n) is the smallest number whose greedy representation as a sum of terms of A126684 uses n terms.
1

%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