

A302757


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


1



1, 3, 13, 55, 225, 907, 3637, 14559, 58249, 233011, 932061, 3728263, 14913073, 59652315, 238609285, 954437167, 3817748697, 15270994819, 61083979309, 244335917271, 977343669121, 3909374676523, 15637498706133, 62549994824575, 250199979298345, 1000799917193427
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

A126684 is described as the fastestgrowing 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 recordsetting 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 threeterm 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(n1) + 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(n1)  9*a(n2) + 4*a(n3) 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

Cf. A126684.
Sequence in context: A308349 A140320 A037583 * A093834 A296045 A286191
Adjacent sequences: A302754 A302755 A302756 * A302758 A302759 A302760


KEYWORD

nonn,easy


AUTHOR

David Eppstein, Apr 12 2018


STATUS

approved



