A373709 -id:A373709 - 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)

A119387 a(n) is the number of binary digits (1's and nonleading 0's) which remain unchanged in their positions when n and (n+1) are written in binary.

Original entry on oeis.org

0, 0, 1, 0, 2, 1, 2, 0, 3, 2, 3, 1, 3, 2, 3, 0, 4, 3, 4, 2, 4, 3, 4, 1, 4, 3, 4, 2, 4, 3, 4, 0, 5, 4, 5, 3, 5, 4, 5, 2, 5, 4, 5, 3, 5, 4, 5, 1, 5, 4, 5, 3, 5, 4, 5, 2, 5, 4, 5, 3, 5, 4, 5, 0, 6, 5, 6, 4, 6, 5, 6, 3, 6, 5, 6, 4, 6, 5, 6, 2, 6, 5, 6, 4, 6, 5, 6, 3, 6, 5, 6, 4, 6, 5, 6, 1, 6, 5, 6, 4, 6, 5, 6, 3, 6

Offset: 0

Leroy Quet, Jul 26 2006

The largest k for which A220645(n,k) > 0 is k = a(n). That is, a(n) is the largest power of 2 that divides binomial(n,i) for 0 <= i <= n. - T. D. Noe, Dec 18 2012

a(n) is the distance between the first and last 1's in the binary expansion of n+1; see examples and formulae. - David James Sycamore, Feb 21 2023

			9 in binary is 1001. 10 (decimal) is 1010 in binary. 2 binary digits remain unchanged (the leftmost two digits) between 1001 and 1010. So a(9) = 2.
From _David James Sycamore_, Feb 26 2023: (Start)
Number of bits surviving transition from n to n+1 = distance between first and last 1's in binary expansion of n+1 (no need to compare n and n+1). Examples:
n = 2^k - 1: distance between 1's in n+1 = 2^k is 0; a(n) = 0 (all bits change).
82 in binary is 1010010, and 83 is 1010011 distance between 1's in 83 = 6 = a(82).
Show visually for a(327) = 5:
 n   = 327 = 101000111
             ^^^^^      5 unchanged bits.
 n+1 = 328 = 101001000
             ^    ^     distance between 1's = 5. (End)

Paolo Xausa, Table of n, a(n) for n = 0..10000 (terms 0..1023 from T. D. Noe)
Lukas Spiegelhofer and Michael Wallner, Divisibility of binomial coefficients by powers of primes, arXiv:1604.07089 [math.NT], 2016. Mentions this sequence.
Index entries for sequences related to binary expansion of n

Cf. A048881, A086784.
Cf. A070940.
Cf. A000265.
Cf. A001511, A070939.
Cf. A373709 (partial sums).

#include 
#define NMAX 200
int sameD(int a, int b) { int resul=0 ; while(a>0 && b >0) { if( (a &1) == (b & 1)) resul++ ; a >>= 1 ; b >>= 1 ; } return resul ; }
int main(int argc, char*argv[])
{ for(int n=0;nR. J. Mathar, Jul 29 2006 */

int A119387(int n)
{
    int m=n+1;
    while (!(m&1)) m>>=1;
    int m_bits = 0;
    while (m>>=1) m_bits++;
    return m_bits;
}
/* Laura Monroe, Oct 18 2020 */

a119387 n = length $ takeWhile (< a070940 n) [1..n]
-- Reinhard Zumkeller, Apr 22 2013

a:= n-> ilog2(n+1)-padic[ordp](n+1, 2):
seq(a(n), n=0..128);  # Alois P. Heinz, Jun 28 2021

a = {0}; Table[b = IntegerDigits[n, 2]; If[Length[a] == Length[b], c = 1; While[a[[c]] == b[[c]], c++]; c--, c = 0]; a = b; c, {n, 101}] (* T. D. Noe, Dec 18 2012 *)
(* Second program, faster *)
Array[Last[#] - First[#] &@ Position[IntegerDigits[#, 2], 1][[All, 1]] &, 2^14] (* Michael De Vlieger, Feb 22 2023 *)
Table[BitLength[k] - 1 - IntegerExponent[k, 2], {k, 100}] (* Paolo Xausa, Oct 01 2024 *)

a(n) = n++; local(c); c=0; while(2^(c+1)Ralf Stephan, Oct 16 2013; corrected by Michel Marcus, Jun 28 2021 */

a(n) = my(x=Vecrev(binary(n)), y=Vecrev(binary(n+1))); sum(k=1, min(#x, #y), x[k] == y[k]); \\ Michel Marcus, Jun 27 2021

a(n) = exponent(n+1) - valuation(n+1, 2); \\ Antoine Mathys, Nov 20 2024

def A119387(n): return (n+1).bit_length()-(n+1&-n-1).bit_length() # Chai Wah Wu, Jul 07 2022

a(n) = A048881(n) + A086784(n+1). (A048881(n) is the number of 1's which remain unchanged between binary n and (n+1). A086784(n+1) is the number of nonleading 0's which remain unchanged between binary n and (n+1).)
a(A000225(n))=0. - R. J. Mathar, Jul 29 2006
a(n) = -valuation(H(n)*n,2) where H(n) is the n-th harmonic number. - Benoit Cloitre, Oct 13 2013
a(n) = A000523(n+1) - A007814(n+1) = floor(log(n+1)/log(2)) - valuation(n+1,2). - Benoit Cloitre, Oct 13 2013 [corrected by David James Sycamore, Feb 28 2023]
Recurrence: a(2n) = floor(log_2(n)) except a(0) = 0, a(2n+1) = a(n). - Ralf Stephan, Oct 16 2013, corrected by Peter J. Taylor, Mar 01 2020
a(n) = floor(log_2(A000265(n+1))). - Laura Monroe, Oct 18 2020
a(n) = A070939(n+1) - A001511(n+1). - David James Sycamore, Feb 24 2023

More terms from R. J. Mathar, Jul 29 2006

Edited by Charles R Greathouse IV, Aug 04 2010

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

A119387 a(n) is the number of binary digits (1's and nonleading 0's) which remain unchanged in their positions when n and (n+1) are written in binary.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

C

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

Extensions