A296840 The smallest positive integer whose greedy representation as a sum of 3-smooth numbers (A003586) requires n terms.

1, 5, 23, 185, 1721, 15545, 277689, 5586105, 113081529, 2289863865, 46369706169, 986739675321, 26376728842425, 711906436354233, 19221208539173049, 518972365315281081, 22132599848083154505, 944314039112845753929, 40290722114409383329353

Offset: 1

Author

David Eppstein, Dec 21 2017

Keywords

• nonn

Examples

			For n = 4, 185 = 162 + 18 + 4 + 1 requires four terms in its greedy representation even though it has the shorter non-greedy representation 185 = 144 + 32 + 9.
		

Links

• David Eppstein, Making Change in 2048, arXiv:1804.07396 [cs.DM], 2018.

Crossrefs

Cf. A018899 (numbers requiring n terms in non-greedy representations as sums of A003586), A006892 and A066352 (sequences describing greedy representations as sums of squares and of primes respectively).

Programs

Mathematica

With[{nn = 19}, Block[{s = Sort@ Flatten@ Table[2^a * 3^b, {a, 0, Log[2, #]}, {b, 0, Log[3, #/2^a]}] &[10^Floor[8 nn/5]], t}, t = Transpose@ {Most@ s, Differences@ s}; Fold[Append[#1, Function[{a, n}, Last[a] + SelectFirst[t, Last[#] > Last@ a &][[1]]][#1, #2]] &, {1}, Range[2, nn]]]] (* Michael De Vlieger, Dec 22 2017 *)

Formula

a(n) is a(n-1) plus the smallest 3-smooth number s whose next successive 3-smooth number is greater than s + a(n-1). For instance, a(3) = 23 = 5 + 18, where a(2) = 5 is the predecessor of 23 in the sequence and where the first gap bigger than 5 among the 3-smooth numbers is the one from 18 to 24.