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

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

Offset: 1

Author

David Eppstein, Apr 12 2018

Keywords

• nonn
• easy

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).

Crossrefs

Cf. A126684.

Programs

Mathematica

Fold[Append[#1, 4 Last[#1] + 2 #2 - 5] &, {1}, Range[2, 25]] (* Michael De Vlieger, Apr 12 2018 *)

PARI

Vec(x*(1 - 3*x + 4*x^2) / ((1 - x)^2*(1 - 4*x)) + O(x^60)) \\ Colin Barker, Apr 13 2018

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)