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

%I #24 Jul 18 2018 18:54:50

%S 1,5,23,185,1721,15545,277689,5586105,113081529,2289863865,

%T 46369706169,986739675321,26376728842425,711906436354233,

%U 19221208539173049,518972365315281081,22132599848083154505,944314039112845753929,40290722114409383329353

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

%H David Eppstein, <a href="https://arxiv.org/abs/1804.07396">Making Change in 2048</a>, arXiv:1804.07396 [cs.DM], 2018.

%F 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.

%e 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.

%t 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 *)

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

%K nonn

%O 1,2

%A _David Eppstein_, Dec 21 2017