cp's OEIS Frontend

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

%I A239100 #21 Mar 29 2023 05:02:18
%S A239100 0,1,1,2,3,4,6,8,10,13,17,22,28,37,47,59,75,96,120,153,194,242,309,
%T A239100 391,487,619,784,976,1241,1570,1954,2485,3143,3911,4971,6288,7824,
%U A239100 9945,12578,15650,19893,25159,31303,39787,50320,62608,79577,100642,125218,159157
%N A239100 Solution to the problem of finding the number of comparisons needed for optimal merging of 3 elements with n elements.
%H A239100 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 A239100 <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 A239100 For r >= 3, a(3r) = floor(43*2^(r-2)/7)-2,
%F A239100 a(3r+1) = floor(107*2^(r-3)/7)-2,
%F A239100 a(3r+2) = floor((17*2^r-6)/7)-1; initial terms are shown in sequence.
%F A239100 From _Chai Wah Wu_, Mar 28 2023: (Start)
%F A239100 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 A239100 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 A239100 (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 A239100 (Python)
%o A239100 def A239100(n):
%o A239100     if n <= 8: return (0,1,1,2,3,4,6,8)[n-1]
%o A239100     r, b = divmod(n,3)
%o A239100     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 A239100 Cf. A200310, A200111.
%K A239100 nonn
%O A239100 1,4
%A A239100 _N. J. A. Sloane_, Mar 24 2014
%E A239100 More terms from _Michel Marcus_, Mar 26 2014