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

%I #21 Mar 29 2023 05:02:18

%S 0,1,1,2,3,4,6,8,10,13,17,22,28,37,47,59,75,96,120,153,194,242,309,

%T 391,487,619,784,976,1241,1570,1954,2485,3143,3911,4971,6288,7824,

%U 9945,12578,15650,19893,25159,31303,39787,50320,62608,79577,100642,125218,159157

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

%H F. K. Hwang, <a href="http://dx.doi.org/10.1137/0209026">Optimal merging of 3 elements with n elements</a>, SIAM J. Comput. 9 (1980), no. 2, 298--320. MR0568816 (82c:68022).

%H <a href="/index/Rec#order_10">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,1,-1,0,1,-1,0,2,-2).

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

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

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

%F From _Chai Wah Wu_, Mar 28 2023: (Start)

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

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

%o (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

%o (Python)

%o def A239100(n):

%o if n <= 8: return (0,1,1,2,3,4,6,8)[n-1]

%o r, b = divmod(n,3)

%o 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

%Y Cf. A200310, A200111.

%K nonn

%O 1,4

%A _N. J. A. Sloane_, Mar 24 2014

%E More terms from _Michel Marcus_, Mar 26 2014