

A239100


Solution to the problem of finding the number of comparisons needed for optimal merging of 3 elements with n elements.


2



0, 1, 1, 2, 3, 4, 6, 8, 10, 13, 17, 22, 28, 37, 47, 59, 75, 96, 120, 153, 194, 242, 309, 391, 487, 619, 784, 976, 1241, 1570, 1954, 2485, 3143, 3911, 4971, 6288, 7824, 9945, 12578, 15650, 19893, 25159, 31303, 39787, 50320, 62608, 79577, 100642, 125218, 159157
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,4


LINKS

Table of n, a(n) for n=1..50.
F. K. Hwang, Optimal merging of 3 elements with n elements, SIAM J. Comput. 9 (1980), no. 2, 298320. MR0568816 (82c:68022).


FORMULA

For r >= 3, a(3r) = floor(43*2^(r2)/7)2,
a(3r+1) = floor(107*2^(r3)/7)2,
a(3r+2) = floor((17*2^r6)/7)1; initial terms are shown in sequence.


PROG

(PARI) a(n) = if (n<9, v=[0, 1, 1, 2, 3, 4, 6, 8]; v[n], ndt = n\3; nmt = n%3; if (nmt==0, 43*2^(ndt2)\7  2, if (nmt == 1, 107*2^(ndt3)\7  2, (17*2^ndt6)\7  1))); \\ Michel Marcus, Mar 26 2014


CROSSREFS

Cf. A200310, A200111.
Sequence in context: A005434 A027589 A039851 * A243225 A220851 A028290
Adjacent sequences: A239097 A239098 A239099 * A239101 A239102 A239103


KEYWORD

nonn


AUTHOR

N. J. A. Sloane, Mar 24 2014


EXTENSIONS

More terms from Michel Marcus, Mar 26 2014


STATUS

approved



