login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


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.

License Agreements, Terms of Use, Privacy Policy. .

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