cp's OEIS Frontend

A097383 Minimum total number of comparisons to find each of the values 1 through n using a binary search with 3-way comparisons (less than, equal and greater than).

%I A097383 #35 Mar 30 2023 02:00:29
%S A097383 0,2,3,6,8,11,13,17,20,24,27,31,34,38,41,46,50,55,59,64,68,73,77,82,
%T A097383 86,91,95,100,104,109,113,119,124,130,135,141,146,152,157,163,168,174,
%U A097383 179,185,190,196,201,207,212,218,223,229,234,240,245,251,256,262,267,273
%N A097383 Minimum total number of comparisons to find each of the values 1 through n using a binary search with 3-way comparisons (less than, equal and greater than).
%C A097383 Optimal binary search with equality.
%H A097383 Robert Israel, <a href="/A097383/b097383.txt">Table of n, a(n) for n = 1..10000</a>
%H A097383 Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, <a href="http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf">Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications</a>, Preprint 2016.
%H A097383 Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, <a href="https://doi.org/10.1145/3127585">Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications</a>, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
%F A097383 a(n) = min_{1<=k<=n-1} n + a(k) + a(n-1-k).
%F A097383 a(n) = A123753(n) - floor(3*(n+1)/2). - _Peter Luschny_, Nov 30 2017
%F A097383 From _Robert Israel_, Nov 30 2017: (Start)
%F A097383 Empirical: a(n+3)-a(n+2)-a(n+1)+a(n) = 1 if n = 2^k-3 or 2^k-2 for some k, 0 otherwise.
%F A097383 Empirical g.f.: (2*x^2+x^3)/(1-x-x^2+x^3) + Sum_{k>=2} x^{2^k}/(1-x)^2. (End)
%e A097383 a_5 = 8 = 5 + a_1 + a_3; this is the smallest example where choosing the middle value is not optimal.
%p A097383 f:= proc(n) option remember;
%p A097383      n+min(seq(procname(k)+procname(n-1-k),k=1..n-1))
%p A097383 end proc:
%p A097383 f(1):= 0: f(0):= 0:
%p A097383 map(f, [$1..100]); # _Robert Israel_, Nov 30 2017
%t A097383 a[n_] := (n+1)(1+IntegerLength[n+1,2])-2^IntegerLength[n+1,2]-Quotient[3n+1,2];
%t A097383 Table[a[n], {n, 1, 60}] (* _Peter Luschny_, Dec 02 2017 *)
%o A097383 (Python)
%o A097383 def A097383(n):
%o A097383     s, i, z = -n//2, n, 1
%o A097383     while 0 <= i: s += i; i -= z; z += z
%o A097383     return s
%o A097383 print([A097383(n) for n in range(1, 61)]) # _Peter Luschny_, Nov 30 2017
%o A097383 (Python)
%o A097383 def A097383(n): return (n+1)*(m:=n.bit_length())-(1<<m)-(n-1>>1) # _Chai Wah Wu_, Mar 29 2023
%Y A097383 See A097384 for the sequence with a pure binary search.
%Y A097383 A003314 is the sequence with only 2-way comparisons.
%Y A097383 Cf. A123753.
%K A097383 easy,nonn
%O A097383 1,2
%A A097383 _Franklin T. Adams-Watters_, Aug 11 2004