login
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).
4
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
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
KEYWORD
easy,nonn
AUTHOR
STATUS
approved