A097383 -id:A097383 - cp's OEIS frontend

A123753 Partial sums of A070941.

1, 3, 6, 9, 13, 17, 21, 25, 30, 35, 40, 45, 50, 55, 60, 65, 71, 77, 83, 89, 95, 101, 107, 113, 119, 125, 131, 137, 143, 149, 155, 161, 168, 175, 182, 189, 196, 203, 210, 217, 224, 231, 238, 245, 252, 259, 266, 273, 280, 287, 294, 301, 308, 315, 322, 329, 336, 343

Offset: 0

Reinhard Zumkeller, Oct 12 2006

nonn

Peter Luschny, Table of n, a(n) for n = 0..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.

Cf. A001855, A003314, A033156, A054248, A061168, A083652, A097383, A295508.

A123753 := proc(n) local i, J, z; i := n+1: J := i; i := i-1; z := 1;
while 0 <= i do J := J+i; i := i-z; z := z+z od; J end:
seq(A123753(n), n=0..57); # Peter Luschny, Nov 30 2017
# Alternatively:
a := n -> (n+1)*(1 + ilog2(2*n+3)) - 2^ilog2(2*n+3) + 1:
seq(a(n), n=0..57); # Peter Luschny, Dec 02 2017

a[n_] := (n + 1)(1 + IntegerLength[n + 1, 2]) - 2^IntegerLength[n + 1, 2] + 1;
Table[a[n], {n, 0, 57}] (* Peter Luschny, Dec 02 2017 *)

def A123753(n):
    s, i, z = n+1, n, 1
    while 0 <= i: s += i; i -= z; z += z
    return s
print([A123753(n) for n in range(0, 58)]) # Peter Luschny, Nov 30 2017

def A123753(n): return (n+1)*(1+(m:=n.bit_length()))-(1<Chai Wah Wu, Mar 29 2023

a(n) = A003314(n+1)+1. - Reinhard Zumkeller, Oct 12 2006

Let bil(n) = floor(log_2(n)) + 1 for n>0, bil(0) = 0 and b(n) = n + n*bil(n) - 2^bil(n) + 1 then a(n) = b(n+1). (This suggests that '0' be prepended to this sequence.) - Peter Luschny, Dec 02 2017

A097384 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), always choosing the mid-most value to compare to.

Original entry on oeis.org

0, 2, 3, 6, 9, 11, 13, 17, 21, 25, 29, 32, 35, 38, 41, 46, 51, 56, 61, 66, 71, 76, 81, 85, 89, 93, 97, 101, 105, 109, 113, 119, 125, 131, 137, 143, 149, 155, 161, 167, 173, 179, 185, 191, 197, 203, 209, 214, 219, 224, 229, 234, 239, 244, 249, 254, 259, 264, 269, 274

Offset: 1

Franklin T. Adams-Watters, Aug 11 2004

Pure binary search with equality.

			a_5 = 9 = 5 + a_2 + a_2; this is the smallest example where choosing the middle value is not optimal.

Hsien-Kuei Hwang, S Janson, TH 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; http://140.109.74.92/hk/wp-content/files/2016/12/aat-hhrr-1.pdf. Also 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

See A097383 for the sequence with an optimized binary search. A003314 is the sequence with only 2-way comparisons.

n + a_{floor((n-1)/2)} + a_{ceiling((n-1)/2)}.

A295513 a(n) = n*bil(n) - 2^bil(n) where bil(0) = 0 and bil(n) = floor(log_2(n)) + 1 for n>0.

Original entry on oeis.org

-1, -1, 0, 2, 4, 7, 10, 13, 16, 20, 24, 28, 32, 36, 40, 44, 48, 53, 58, 63, 68, 73, 78, 83, 88, 93, 98, 103, 108, 113, 118, 123, 128, 134, 140, 146, 152, 158, 164, 170, 176, 182, 188, 194, 200, 206, 212, 218, 224, 230, 236, 242, 248, 254, 260, 266, 272, 278

Offset: 0

Peter Luschny, Dec 02 2017

sign

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.

Cf. A001855, A003314, A033156, A054248, A061168, A083652, A097383, A123753, A295508.

A295513 := proc(n) local i, s, z; s := -1; i := n-1; z := 1;
while 0 <= i do s := s+i; i := i-z; z := z+z od; s end:
seq(A295513(n), n=0..57);

a[n_] := n IntegerLength[n, 2] - 2^IntegerLength[n, 2];
Table[a[n], {n, 0, 58}]

def A295513(n): return n*(m:=(n-1).bit_length())-(1<Chai Wah Wu, Mar 29 2023

A001855(n) = a(n) + 1.
A033156(n) = a(n) + 2n.
A003314(n) = a(n) + n.
A083652(n) = a(n+1) + 2.
A061168(n) = a(n+1) - n + 1.
A123753(n) = a(n+1) + n + 2.
A097383(n) = a(n+1) - div(n-1, 2).
A054248(n) = a(n) + n + rem(n, 2).

cp's OEIS Frontend

A123753 Partial sums of A070941.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Python

Python

Formula

A097384 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), always choosing the mid-most value to compare to.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Formula

A295513 a(n) = n*bil(n) - 2^bil(n) where bil(0) = 0 and bil(n) = floor(log_2(n)) + 1 for n>0.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula