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).
0, 2, 3, 6, 8, 11, 13, 17, 20, 24, 27, 31, 34, 38, 41, 46, 50, 55, 59, 64, 68, 73, 77, 82, 86, 91, 95, 100, 104, 109, 113, 119, 124, 130, 135, 141, 146, 152, 157, 163, 168, 174, 179, 185, 190, 196, 201, 207, 212, 218, 223, 229, 234, 240, 245, 251, 256, 262, 267, 273
Offset: 1
Examples
a_5 = 8 = 5 + a_1 + a_3; this is the smallest example where choosing the middle value is not optimal.
Links
- Robert Israel, Table of n, a(n) for n = 1..10000
- Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint 2016.
- Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
Crossrefs
Programs
-
Maple
f:= proc(n) option remember; n+min(seq(procname(k)+procname(n-1-k),k=1..n-1)) end proc: f(1):= 0: f(0):= 0: map(f, [$1..100]); # Robert Israel, Nov 30 2017 -
Mathematica
a[n_] := (n+1)(1+IntegerLength[n+1,2])-2^IntegerLength[n+1,2]-Quotient[3n+1,2]; Table[a[n], {n, 1, 60}] (* Peter Luschny, Dec 02 2017 *) -
Python
def A097383(n): s, i, z = -n//2, n, 1 while 0 <= i: s += i; i -= z; z += z return s print([A097383(n) for n in range(1, 61)]) # Peter Luschny, Nov 30 2017
-
Python
def A097383(n): return (n+1)*(m:=n.bit_length())-(1<
Formula
a(n) = min_{1<=k<=n-1} n + a(k) + a(n-1-k).
a(n) = A123753(n) - floor(3*(n+1)/2). - Peter Luschny, Nov 30 2017
From Robert Israel, Nov 30 2017: (Start)
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.
Empirical g.f.: (2*x^2+x^3)/(1-x-x^2+x^3) + Sum_{k>=2} x^{2^k}/(1-x)^2. (End)
Comments