A123753 -id:A123753 - cp's OEIS frontend

A001855 Sorting numbers: maximal number of comparisons for sorting n elements by binary insertion.

0, 1, 3, 5, 8, 11, 14, 17, 21, 25, 29, 33, 37, 41, 45, 49, 54, 59, 64, 69, 74, 79, 84, 89, 94, 99, 104, 109, 114, 119, 124, 129, 135, 141, 147, 153, 159, 165, 171, 177, 183, 189, 195, 201, 207, 213, 219, 225, 231, 237, 243, 249, 255, 261, 267, 273, 279, 285

Offset: 1

N. J. A. Sloane

Equals n-1 times the expected number of probes for a successful binary search in a size n-1 list.
Piecewise linear: breakpoints at powers of 2 with values given by A000337.
a(n) is the number of digits in the binary representation of all the numbers 1 to n-1. - Hieronymus Fischer, Dec 05 2006
It is also coincidentally the maximum number of comparisons for merge sort. - Li-yao Xia, Nov 18 2015

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, Sect 5.3.1, Eq. (3); Sect. 6.2.1 (4).
J. W. Moon, Topics on Tournaments. Holt, NY, 1968, p. 48.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Tianxing Tao, On optimal arrangement of 12 points, pp. 229-234 in Combinatorics, Computing and Complexity, ed. D. Du and G. Hu, Kluwer, 1989.

Paolo Xausa, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
Michael Albert, Michael Engen, Jay Pantone, and Vincent Vatter, Universal layered permutations, arXiv:1710.04240 [math.CO], (2017).
Michael Albert, Michael Engen, Jay Pantone, and Vincent Vatter, Universal Layered Permutations, Electronic Journal of Combinatorics. Volume 25(3), 2018, #P3.23.
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
Sung-Hyuk Cha, On Integer Sequences Derived from Balanced k-ary Trees, Applied Mathematics in Electrical and Computer Engineering, 2012.
Sung-Hyuk Cha, On Complete and Size Balanced k-ary Tree Integer Sequences, International Journal of Applied Mathematics and Informatics, Issue 2, Volume 6, 2012, pp. 67-75. - From _N. J. A. Sloane_, Dec 24 2012
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.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 36.
Tanya Khovanova, There are no coincidences, arXiv preprint 1410.2193 [math.CO], 2014.
D. Knuth, Letter to N. J. A. Sloane, date unknown
N. J. A. Sloane, "A Handbook of Integer Sequences" Fifty Years Later, arXiv:2301.03149 [math.NT], 2023, p. 5.
R. Stephan, Some divide-and-conquer sequences ...
R. Stephan, Table of generating functions
Eric Weisstein's World of Mathematics, Sorting.
Index entries for sequences related to sorting

Partial sums of A029837.

Cf. A003071, A000337, A030190, A030308, A061168, A123753, A373709.

import Data.List (transpose)
a001855 n = a001855_list !! n
a001855_list = 0 : zipWith (+) [1..] (zipWith (+) hs $ tail hs) where
   hs = concat $ transpose [a001855_list, a001855_list]
-- Reinhard Zumkeller, Jun 03 2013

a := proc(n) local k; k := ilog2(n) + 1; 1 + n*k - 2^k end; # N. J. A. Sloane, Dec 01 2007 [edited by Peter Luschny, Nov 30 2017]

a[n_?EvenQ] := a[n] = n + 2a[n/2] - 1; a[n_?OddQ] := a[n] = n + a[(n+1)/2] + a[(n-1)/2] - 1; a[1] = 0; a[2] = 1; Table[a[n], {n, 1, 58}] (* Jean-François Alcover, Nov 23 2011, after Pari *)
a[n_] := n IntegerLength[n, 2] - 2^IntegerLength[n, 2] + 1;
Table[a[n], {n, 1, 58}] (* Peter Luschny, Dec 02 2017 *)
Accumulate[BitLength[Range[0, 100]]] (* Paolo Xausa, Sep 30 2024 *)

PARI
```
a(n)=if(n<2,0,n-1+a(n\2)+a((n+1)\2))
```

a(n)=local(m);if(n<2,0,m=length(binary(n-1));n*m-2^m+1)

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

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

Let n = 2^(k-1) + g, 0 <= g <= 2^(k-1); then a(n) = 1 + n*k - 2^k. - N. J. A. Sloane, Dec 01 2007
a(n) = Sum_{k=1..n}ceiling(log_2 k) = n*ceiling(log_2 n) - 2^ceiling(log_2(n)) + 1.
a(n) = a(floor(n/2)) + a(ceiling(n/2)) + n - 1.
G.f.: x/(1-x)^2 * Sum_{k>=0} x^2^k. - Ralf Stephan, Apr 13 2002
a(1)=0, for n>1, a(n) = ceiling(n*a(n-1)/(n-1)+1). - Benoit Cloitre, Apr 26 2003
a(n) = n-1 + min { a(k)+a(n-k) : 1 <= k <= n-1 }, cf. A003314. - Vladeta Jovovic, Aug 15 2004
a(n) = A061168(n-1) + n - 1 for n>1. - Hieronymus Fischer, Dec 05 2006
a(n) = A123753(n-1) - n. - Peter Luschny, Nov 30 2017

Additional comments from M. D. McIlroy (mcilroy(AT)dartmouth.edu)

A070941 Length of binary representation of 2n+1.

Original entry on oeis.org

1, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8

Offset: 0

N. J. A. Sloane, May 18 2002

nonn

Sequence consists of A011782(n) n+1's. - Jon Perry, Apr 04 2004
For n > 0: a(n) = A003314(n+1) - A003314(n) = A123753(n) - A123753(n-1). - Reinhard Zumkeller, Oct 12 2006
For k >= 2, k appears 2^(k-2) times consecutively. - Bernard Schott, Jun 08 2019
Also length of binary representation of 2n. - Michel Marcus, Oct 28 2020

Index entries for sequences related to binary expansion of n

Bisection of A070939 and also of A070940.

Table[IntegerLength[n,2],{n,1,201,2}] (* Harvey P. Dale, May 17 2011 *)

PARI
```
a(n)=length(binary(2*n+1))
```

def A070941(n): return n.bit_length()+1 # Chai Wah Wu, Mar 29 2023

Let b(1)=1, b(n) = a(n-floor(n/2)) + 1, then a(n) = b(n+1). - Benoit Cloitre, Oct 23 2002
G.f.: 1/(1-x) * (1 + Sum_{k>=0} x^2^k). - Ralf Stephan, Apr 15 2002
a(n) = ceiling(log_2(n+1)) + 1 = A029837(n+1) + 1. - Ralf Stephan, Apr 15 2002
a(n) = ceiling(average of previous entries) + 1. - Jon Perry, Apr 04 2004

A083652 Sum of lengths of binary expansions of 0 through n.

Original entry on oeis.org

1, 2, 4, 6, 9, 12, 15, 18, 22, 26, 30, 34, 38, 42, 46, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100, 105, 110, 115, 120, 125, 130, 136, 142, 148, 154, 160, 166, 172, 178, 184, 190, 196, 202, 208, 214, 220, 226, 232, 238, 244, 250, 256, 262, 268, 274, 280, 286, 292

Offset: 0

Reinhard Zumkeller, May 01 2003

a(n) = A001855(n) + 1 for n > 0;
a(0) = A070939(0)=1, n > 0: a(n) = a(n-1) + A070939(n).
A030190(a(k))=1; A030530(a(k)) = k + 1.
Partial sums of A070939. - Hieronymus Fischer, Jun 12 2012
Young writes "If n = 2^i + k [...] the maximum is (i+1)(2^i+k)-2^{i+1}+2." - Michael Somos, Sep 25 2012

			G.f. = 1 + 2*x + 4*x^2 + 6*x^3 + 9*x^4 + 12*x^5 + 15*x^6 + 18*x^7 + 22*x^8 + ...

Reinhard Zumkeller, 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; DOI: 10.1145/3127585.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 36.
Alfred Young, The Maximum Order of an Irreducible Covariant of a System of Binary Forms, Proc. Roy. Soc. 72 (1903), 399-400 = The Collected Papers of Alfred Young, 1977, 136-137.
Index entries for sequences related to binary expansion of n

Cf. A000120, A007088, A023416, A059015, A070939 (base 2), A123753.

A296349 is an essentially identical sequence.

a083652 n = a083652_list !! n
a083652_list = scanl1 (+) a070939_list
-- Reinhard Zumkeller, Jul 05 2012

Accumulate[Length/@(IntegerDigits[#,2]&/@Range[0,60])] (* Harvey P. Dale, May 28 2013 *)
a[n_] := (n + 1) IntegerLength[n + 1, 2] - 2^IntegerLength[n + 1, 2] + 2;Table[a[n], {n, 0, 58}] (* Peter Luschny, Dec 02 2017 *)

{a(n) = my(i); if( n<0, 0, n++; i = length(binary(n)); n*i - 2^i + 2)}; /* Michael Somos, Sep 25 2012 */

a(n)=my(i=#binary(n++));n*i-2^i+2 \\ equivalent to the above

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

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

a(n) = 2 + (n+1)*ceiling(log_2(n+1)) - 2^ceiling(log_2(n+1)).
G.f.: g(x) = 1/(1-x) + (1/(1-x)^2)*Sum_{j>=0} x^2^j. - Hieronymus Fischer, Jun 12 2012; corrected by Ilya Gutkovskiy, Jan 08 2017
a(n) = A123753(n) - n. - Peter Luschny, Nov 30 2017

A061168 Partial sums of floor(log_2(k)) (= A000523(k)).

Original entry on oeis.org

0, 1, 2, 4, 6, 8, 10, 13, 16, 19, 22, 25, 28, 31, 34, 38, 42, 46, 50, 54, 58, 62, 66, 70, 74, 78, 82, 86, 90, 94, 98, 103, 108, 113, 118, 123, 128, 133, 138, 143, 148, 153, 158, 163, 168, 173, 178, 183, 188, 193, 198, 203, 208, 213, 218, 223, 228, 233, 238, 243, 248

Offset: 1

Antti Karttunen, Apr 19 2001

Given a term b>0 of the sequence and its left hand neighbor c, the corresponding unique sequence index n with property a(n)=b can be determined by n(b)=e+(b-d*(e+1)+2*(e-1))/d, where d=b-c and e=2^d. - Hieronymus Fischer, Dec 05 2006
a(n) gives index of start of binary expansion of n in the binary Champernowne sequence A076478. - N. J. A. Sloane, Dec 14 2017
a(n) is the number of pairs in ancestor relationship (= transitive closure of the parent relationship) in all (binary) heaps on n elements. - Alois P. Heinz, Feb 13 2019

D. E. Knuth, Fundamental Algorithms, Addison-Wesley, 1973, Section 1.2.4, ex. 42(b).

Alois P. Heinz, Table of n, a(n) for n = 1..10000 (first 1000 terms from Harry J. Smith)
Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197, ex. 27.
Sung-Hyuk Cha, On Integer Sequences Derived from Balanced k-ary Trees, Applied Mathematics in Electrical and Computer Engineering, 2012.
Sung-Hyuk Cha, On Complete and Size Balanced k-ary Tree Integer Sequences, International Journal of Applied Mathematics and Informatics, Issue 2, Volume 6, 2012, pp. 67-75.
Alan M. Cleary, Joseph Winjum, Jordan Dood, Hiroki Shibata, and Shunsuke Inenaga, Bit Packed Encodings for Grammar-Compressed Strings Supporting Fast Random Access, Leibniz Int'l Proc. Informatics (LIPIcs) 23rd Int'l Symp. on Experim. Algor. (SEA 2025) Art. No. 12, 12:1-12:17. See p. 12:8.
Martin Griffiths, More sums involving the floor function, Math. Gaz., 86 (2002), 285-287.
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.
Tamás Lengyel, On the 2-Adic Valuation of Differences of Harmonic Numbers, Integers (2024) Vol. 24, A27. See p. 8.
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap

Cf. A000523, A001855, A123753, A076478.

import Data.List (transpose)
a061168 n = a061168_list !! n
a061168_list = zipWith (+) [0..] (zipWith (+) hs $ tail hs) where
   hs = concat $ transpose [a001855_list, a001855_list]
-- Reinhard Zumkeller, Jun 03 2013

seq(add(floor(log[2](k)),k=1..j),j=1..100);
# second Maple program:
a:= proc(n) option remember; `if`(n<1, 0, ilog2(n)+a(n-1)) end:
seq(a(n), n=1..80);   # Alois P. Heinz, Feb 12 2019

Accumulate[Floor[Log[2,Range[110]]]] (* Harvey P. Dale, Jul 16 2012 *)
a[n_] := (n+1) IntegerLength[n+1, 2] - 2^IntegerLength[n+1, 2] - n + 1;
Table[a[n], {n, 1, 61}] (* Peter Luschny, Dec 02 2017 *)

a(n)=if(n<1,0,if(n%2==0,a(n/2)+a(n/2-1)+n-1,2*a((n-1)/2)+n-1)) /* _Ralf Stephan */

a(n)=local(k); if(n<1,0,k=length(binary(n))-1; (n+1)*k-2*(2^k-1))

{ for (n=1, 1000, k=length(binary(n))-1; write("b061168.txt", n, " ", (n + 1)*k - 2*(2^k - 1)) ) } \\ Harry J. Smith, Jul 18 2009

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

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

a(n) = A001855(n+1) - n.
a(n) = Sum_{k=1..n} floor(log_2(k)) = (n+1)*floor(log_2(n)) - 2*(2^floor(log_2(n)) - 1). - Diego Torres (torresvillarroel(AT)hotmail.com), Oct 29 2002
G.f.: 1/(1-x)^2 * Sum(k>=1, x^2^k). - Ralf Stephan, Apr 13 2002
a(n) = A123753(n) - 2*n - 1. - Peter Luschny, Nov 30 2017

A003314 Binary entropy function: a(1)=0; for n > 1, a(n) = n + min { a(k)+a(n-k) : 1 <= k <= n-1 }.

Original entry on oeis.org

0, 2, 5, 8, 12, 16, 20, 24, 29, 34, 39, 44, 49, 54, 59, 64, 70, 76, 82, 88, 94, 100, 106, 112, 118, 124, 130, 136, 142, 148, 154, 160, 167, 174, 181, 188, 195, 202, 209, 216, 223, 230, 237, 244, 251, 258, 265, 272, 279, 286, 293, 300, 307, 314, 321, 328, 335

Offset: 1

N. J. A. Sloane

Morris gives many other interesting properties of this function.

a(n) is a convex function of n. (See the Morris reference.)

			a(6) = 6 + min {1+12, 2+8, 5+5} = 6 + 10 = 16.

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, Sect 5.4.9, Eq. (19). p. 374.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Indranil Ghosh, Table of n, a(n) for n = 1..32768 (terms 1..1000 from T. D. Noe)
Mareike Fischer, Extremal values of the Sackin balance index for rooted binary trees, arXiv:1801.10418 [q-bio.PE], 2018.
Mareike Fischer, Extremal Values of the Sackin Tree Balance Index, Ann. Comb. (2021) Vol. 25, 515-541, Remark 4.
D. Chistikov, S. Iván, A. Lubiw, and J. Shallit, Fractional coverings, greedy coverings, and rectifier networks, arXiv preprint arXiv:1509.07588 [cs.CC], 2015-2016.
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.
D. Knuth, Letter to N. J. A. Sloane, date unknown
R. Morris, Some theorems on sorting, SIAM J. Appl. Math., 17 (1969), 1-6.

Cf. A054248, A070941, A123753.

a003314 n = a003314_list !! (n-1)
a003314_list = 0 : f [0] [2..] where
   f vs (w:ws) = y : f (y:vs) ws where
     y = w + minimum (zipWith (+) vs $ reverse vs)
-- Reinhard Zumkeller, Aug 13 2013

A003314 := proc(n) local i,j; option remember; if n<=2 then n elif n=3 then 5 else j := 10^10; for i from 1 to n-1 do if A003314(i)+A003314(n-i) < j then j := A003314(i)+A003314(n-i); fi; od; n+j; fi; end;

a[1] = 0; a[n_] := If[OddQ[n], n + a[(n-1)/2 + 1] + a[(n-1)/2], 2*(n/2 + a[n/2])];
Table[a[n], {n, 1, 57}] (* Jean-François Alcover, Oct 15 2012 *)
a[n_] := n + n IntegerLength[n, 2] - 2^IntegerLength[n, 2];
Table[a[n], {n, 1, 57}] (* Peter Luschny, Dec 02 2017 *)

PARI
```
a(n)=if(n<2,0,n+a(n\2)+a((n+1)\2))
```

a(n)=local(m);if(n<2,0,m=length(binary(n-1));n*m-2^m+n)

def A003314(n):
    return n*int(math.log(4*n,2))-2**int(math.log(2*n,2)) # Indranil Ghosh, Feb 03 2017

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

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

a(1) = 0; a(n) = n + a([n/2]) + a(n-[n/2]). (See the Morris reference.)
a(n) = A001855(n)+n-1. - Michael Somos Feb 07 2004
a(n) = n + a(floor(n/2)) + a(ceiling(n/2)) = n*floor(log_2(4n))-2^floor(log_2(2n)) = A033156(n) - n = n*A070941(n) - A062383(n). - Henry Bottomley, Jul 03 2002
a(1) = 0 and for n>1: a(n) = a(n-1) + A070941(2*n-1). Also a(n) = A123753(n-1) - 1. - Reinhard Zumkeller, Oct 12 2006
a(n) = A123753(n-1) - 1. - Peter Luschny, Nov 30 2017

A033156 a(1) = 1; for m >= 2, a(n) = a(n-1) + floor(a(n-1)/(n-1)) + 2.

Original entry on oeis.org

1, 4, 8, 12, 17, 22, 27, 32, 38, 44, 50, 56, 62, 68, 74, 80, 87, 94, 101, 108, 115, 122, 129, 136, 143, 150, 157, 164, 171, 178, 185, 192, 200, 208, 216, 224, 232, 240, 248, 256, 264, 272, 280, 288, 296, 304, 312, 320, 328, 336, 344, 352, 360, 368, 376, 384, 392, 400, 408

Offset: 1

N. J. A. Sloane, Jun 05 2002

nonn

Harvey P. Dale, Table of n, a(n) for n = 1..1000
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.
Haomin Li, Computing a Basis for an Integer Lattice, Master's Thesis, Univ. of Waterloo (Ontario, Canada 2022).
M. A. Nyblom, Some curious sequences involving floor and ceiling functions, Am. Math. Monthly 109 (#6, 200), 559-564, Th. 3.1.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions

Cf. A123753.

A033156 := proc(n) option remember; if n=1 then 1 else A033156(n-1)+floor(A033156(n-1)/(n-1))+2; fi; end;

a[n_] := n (2 + IntegerLength[n, 2]) - 2^IntegerLength[n, 2];
Table[a[n], {n, 1, 59}] (* Peter Luschny, Dec 02 2017 *)
nxt[{n_,a_}]:={n+1,a+Floor[a/n]+2}; NestList[nxt,{1,1},60][[All,2]] (* Harvey P. Dale, Nov 03 2020 *)

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

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

a(n) = n*(floor(log_2 n) + 3) - 2^((floor (log_2 n)) + 1).
a(n) = n + a(floor(n/2)) + a(ceiling(n/2)) = n + min{a(k) + a(n-k):0 < k < n} = n + A003314(n). - Henry Bottomley, Jul 03 2002
A001855(n) + 2n-1. a(n) = b(n)+1 with b(0)=0, b(2n) = b(n) + b(n-1) + 2n + 2, b(2n+1) = 2b(n) + 2n + 3. - Ralf Stephan, Oct 24 2003
a(n) = A123753(n-1) + n - 1. - Peter Luschny, Nov 30 2017

A054248 Binary entropy: a(n) = n + min { a(k)+a(n-k) : 1 <= k <= n-1 }.

Original entry on oeis.org

1, 2, 6, 8, 13, 16, 21, 24, 30, 34, 40, 44, 50, 54, 60, 64, 71, 76, 83, 88, 95, 100, 107, 112, 119, 124, 131, 136, 143, 148, 155, 160, 168, 174, 182, 188, 196, 202, 210, 216, 224, 230, 238, 244, 252, 258, 266, 272, 280, 286, 294, 300, 308, 314, 322, 328, 336

Offset: 1

N. J. A. Sloane, May 04 2000

nonn

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, p. 374.

Alois P. Heinz, 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.

Cf. A003314, A123753.

A054248 := proc(n) local i,j; option remember; if n<=2 then n else j := 10^10; for i from 1 to n-1 do if A054248(i)+A054248(n-i) < j then j := A054248(i)+A054248(n-i); fi; od; n+j; fi; end;
# second Maple program:
a:= proc(n) option remember; `if`(n<3, n,
      n + min(seq(a(k)+a(n-k), k=1..n/2)))
    end:
seq(a(n), n=1..80);  # Alois P. Heinz, Aug 29 2015

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

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

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

a(n) = A123753(n-1) - (n-1) mod 2. - Peter Luschny, Nov 30 2017

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

Original entry on oeis.org

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

Franklin T. Adams-Watters, Aug 11 2004

Optimal binary search with equality.

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

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.

See A097384 for the sequence with a pure binary search.
A003314 is the sequence with only 2-way comparisons.
Cf. A123753.

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

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

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

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

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)

A295508 Triangle read by rows, related to binary partitions of n.

Original entry on oeis.org

0, 1, 0, 2, 1, 0, 3, 2, 1, 4, 3, 2, 0, 5, 4, 3, 1, 6, 5, 4, 2, 7, 6, 5, 3, 8, 7, 6, 4, 0, 9, 8, 7, 5, 1, 10, 9, 8, 6, 2, 11, 10, 9, 7, 3, 12, 11, 10, 8, 4, 13, 12, 11, 9, 5, 14, 13, 12, 10, 6, 15, 14, 13, 11, 7, 16, 15, 14, 12, 8, 0, 17, 16, 15, 13, 9, 1

Offset: 0

Peter Luschny, Nov 30 2017

			0;
1,   0;
2,   1,  0;
3,   2,  1;
4,   3,  2,  0;
5,   4,  3,  1;
6,   5,  4,  2;
7,   6,  5,  3;
8,   7,  6,  4, 0;
9,   8,  7,  5, 1;
10,  9,  8,  6, 2;
11, 10,  9,  7, 3;
12, 11, 10,  8, 4;
13, 12, 11,  9, 5;
14, 13, 12, 10, 6;
15, 14, 13, 11, 7;

Cf. A123753.

A295508_row := proc(n) local i, s, z; s := n; i := n-1; z := 1;
while 0 <= i do s := s,i; i := i-z; z := z+z od; s end:
seq(A295508_row(n), n=0..17);
# Alternatively after formula:
T := (n, k) -> `if`(k=0, n, n - 2^(k-1)):
L := n -> nops(convert(n, base, 2)) - 0^n:
T_row := n -> seq(T(n,k), k=0..L(n)):
seq(T_row(n), n=0..17);

Let L(n) = (length of binary representation of n) - 0^n then
T(n, k) = n if k=0 else n - 2^(k-1) for n >= 0 and 0 <= k <= L(n).
Sum_{k=0..L(n)} T(n,k) = A123753(n-1) for n>=1.

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

A001855 Sorting numbers: maximal number of comparisons for sorting n elements by binary insertion.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Python

Formula

Extensions

A070941 Length of binary representation of 2n+1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A083652 Sum of lengths of binary expansions of 0 through n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Python

Python

Formula

A061168 Partial sums of floor(log_2(k)) (= A000523(k)).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Formula

A003314 Binary entropy function: a(1)=0; for n > 1, a(n) = n + min { a(k)+a(n-k) : 1 <= k <= n-1 }.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI