The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 (list; graph; refs; listen; history; text; internal format)
 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, 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, 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 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 A127758 A185599 Adjacent sequences:  A097380 A097381 A097382 * A097384 A097385 A097386 KEYWORD easy,nonn AUTHOR Franklin T. Adams-Watters, Aug 11 2004 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified October 17 21:17 EDT 2021. Contains 348065 sequences. (Running on oeis4.)