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

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

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, 298--320. MR0568816 (82c:68022).

Index entries for linear recurrences with constant coefficients, signature (1,0,1,-1,0,1,-1,0,2,-2).

Formula

For r >= 3, a(3r) = floor(43*2^(r-2)/7)-2,

a(3r+1) = floor(107*2^(r-3)/7)-2,

a(3r+2) = floor((17*2^r-6)/7)-1; initial terms are shown in sequence.

From Chai Wah Wu, Mar 28 2023: (Start)

a(n) = a(n-1) + a(n-3) - a(n-4) + a(n-6) - a(n-7) + 2*a(n-9) - 2*a(n-10) for n > 18.

G.f.: x*(2*x^17 - x^16 - x^15 + x^14 + x^13 - x^12 + 2*x^11 - x^10 + x^8 + x^6 + x^5 + x^3 + x)/((x - 1)*(2*x^3 - 1)*(x^6 + x^3 + 1)). (End)

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^(ndt-2)\7 - 2, if (nmt == 1, 107*2^(ndt-3)\7 - 2, (17*2^ndt-6)\7 - 1))); \\ Michel Marcus, Mar 26 2014
(Python)
def A239100(n):
    if n <= 8: return (0, 1, 1, 2, 3, 4, 6, 8)[n-1]
    r, b = divmod(n, 3)
    return ((107<<r-3)//7-2 if b==1 else ((17<<r)-6)//7-1) if b else (43<<r-2)//7-2 # Chai Wah Wu, Mar 28 2023

Crossrefs

Cf. A200310, A200111.

Sequence in context: A005434 A027589 A039851 * A337046 A341031 A243225

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