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,2

Comments

Optimal binary search with equality.

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.

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)

Example

a_5 = 8 = 5 + a_1 + a_3; this is the smallest example where choosing the middle value is not optimal.

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 *)

Prog

(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<<m)-(n-1>>1) # Chai Wah Wu, Mar 29 2023

Crossrefs

See A097384 for the sequence with a pure binary search.

A003314 is the sequence with only 2-way comparisons.

Cf. A123753.

Sequence in context: A002240 A099798 A230108 * A072893 A349662 A371002

Adjacent sequences: A097380 A097381 A097382 * A097384 A097385 A097386

Keyword

easy,nonn

Author

Franklin T. Adams-Watters, Aug 11 2004

Status

approved