A061168 -id:A061168 - cp's OEIS frontend

A306393 Number T(n,k) of defective (binary) heaps on n elements where k ancestor-successor pairs do not have the correct order; triangle T(n,k), n >= 0, 0 <= k <= A061168(n), read by rows.

1, 1, 1, 1, 2, 2, 2, 3, 6, 6, 6, 3, 8, 16, 24, 24, 24, 16, 8, 20, 60, 100, 120, 120, 120, 100, 60, 20, 80, 240, 480, 640, 720, 720, 720, 640, 480, 240, 80, 210, 840, 1890, 3150, 4200, 4830, 5040, 5040, 4830, 4200, 3150, 1890, 840, 210

Offset: 0

Alois P. Heinz, Feb 12 2019

T(n,k) is the number of permutations p of [n] having exactly k pairs (i,j) in {1,...,n} X {1,...,floor(log_2(i))} such that p(i) > p(floor(i/2^j)).

T(n,0) counts perfect (binary) heaps on n elements (A056971).

			T(4,0) = 3: 4231, 4312, 4321.
T(4,1) = 6: 3241, 3412, 3421, 4123, 4132, 4213.
T(4,2) = 6: 2341, 2413, 2431, 3124, 3142, 3214.
T(4,3) = 6: 1342, 1423, 1432, 2134, 2143, 2314.
T(4,4) = 3: 1234, 1243, 1324.
T(5,1) = 16: 43512, 43521, 45123, 45132, 45213, 45231, 45312, 45321, 52314, 52341, 52413, 52431, 53124, 53142, 53214, 53241.
(The examples use max-heaps.)
Triangle T(n,k) begins:
   1;
   1;
   1,   1;
   2,   2,   2;
   3,   6,   6,   6,   3;
   8,  16,  24,  24,  24,  16,   8;
  20,  60, 100, 120, 120, 120, 100,  60,  20;
  80, 240, 480, 640, 720, 720, 720, 640, 480, 240, 80;
  ...

Alois P. Heinz, Rows n = 0..100, flattened
Marko Riedel, math.stackexchange.com, Average number of inversions in a random binary heap on 2^n-1 elements.
Marko Riedel, Average number of inversions in a random binary heap on 2^n-1 elements (PDF).
Eric Weisstein's World of Mathematics, Heap,
Wikipedia, Binary heap.
Wikipedia, Permutation.

Columns k=0-10 give: A056971, A324062, A324063, A324064, A324065, A324066, A324067, A324068, A324069, A324070, A324071.
Row sums give A000142.
Central terms (also maxima) of rows give A324075.
Cf. A000523, A008302, A061168, A120385, A306343, A324074, A372640.
Average number of inversions of a full binary heap on 2^n-1 elements is A000337.

b:= proc(u, o) option remember; local n, g, l; n:= u+o;
      if n=0 then 1
    else g:= 2^ilog2(n); l:= min(g-1, n-g/2); expand(
         add(x^(n-j)*add(binomial(j-1, i)*binomial(n-j, l-i)*
         b(i, l-i)*b(j-1-i, n-l-j+i), i=0..min(j-1, l)), j=1..u)+
         add(x^(j-1)*add(binomial(j-1, i)*binomial(n-j, l-i)*
         b(l-i, i)*b(n-l-j+i, j-1-i), i=0..min(j-1, l)), j=1..o))
      fi
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):
seq(T(n), n=0..10);

b[u_, o_] := b[u, o] = Module[{n, g, l}, n = u + o;
     If[n == 0, 1, g = 2^Floor@Log[2, n]; l = Min[g - 1, n - g/2]; Expand[
     Sum[x^(n-j)*Sum[Binomial[j - 1, i]*Binomial[n - j, l - i]*
     b[i, l-i]*b[j-1-i, n-l-j+i], {i, 0, Min[j - 1, l]}], {j, 1, u}] +
     Sum[x^(j-1)*Sum[Binomial[j - 1, i]*Binomial[n - j, l - i]*
     b[l-i, i]*b[n-l-j+i, j-1-i], {i, 0, Min[j-1, l]}], {j, 1, o}]]]];
T[n_] := CoefficientList[b[n, 0], x];
T /@ Range[0, 10] // Flatten (* Jean-François Alcover, Feb 15 2021, after Alois P. Heinz *)

T(n,k) = T(n,A061168(n)-k) for n > 0.

Sum_{k=0..A061168(n)} k * T(n,k) = A324074(n).

A000523 a(n) = floor(log_2(n)).

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane

Or, n >= 0 appears 2^n times. - Jon Perry, Sep 21 2002
a(n) + 1 = number of bits in binary expansion of n.
Largest power of 2 dividing lcm(1..n): A007814(A003418(n)).
log_2(0) = -infinity.
Also Max_{k=1..n} Omega(k), where Omega(n) = A001222(n), number of prime factors with repetition; see A080613. - Reinhard Zumkeller, Feb 25 2003
From Paul Weisenhorn, Sep 29 2010, updated Aug 11 2020: (Start)
Arithmetic mean: m(1,(c+1)/c) = (2*c+1)/(2*c); harmonic mean: h(1,(c+1)/c) = 2*(c+1)/(2*c+1);
a(n) is the number of means to reach (n+1)/n from 2/1; with m for 0 and h for 1, the inverse binary expansion of n, without the leading 1, gives the sequence of means.
For example, n=20; inverse binary expansion without the leading 1: 0010 ---> m m h m or m(1, m(1, h(1, m(1, 2)))) = 21/20.
The 4 twofold means for n from 4 to 7:
m(1,m(1,2)) = m(1,3/2) = 5/4,
h(1,m(1,2)) = h(1,3/2) = 6/5,
m(1,h(1,2)) = m(1,4/3) = 7/6,
h(1,h(1,2)) = h(1,4/3) = 8/7. (End) [Edited by Petros Hadjicostas, Jul 23 2020]
As function of the absolute value, defines the minimal Euclidean function v on Z\{0}. A ring R is Euclidean if for some function v : R\{0}->N a division by nonzero b can be defined with remainder r satisfying either r=0 or v(r) < v(b). For the integers taking v(n)=|n| works, but v(n) = floor(log_2(|n|)) works as well; moreover it is the possibility with smallest possible values. For division by b>0 one can always choose |r| <= floor(b/2); this sequence satisfies a(1) = 0 and recursively a(n) = 1 + max(a(1), ..., a(floor(n/2))) for n > 1. - Marc A. A. van Leeuwen, Feb 16 2011
Maximum number of guesses required to find any k in a range of 1..n, with 'higher', 'lower' and 'correct' as answers. - Jon Perry, Nov 02 2013
Number of powers of 2 <= n. - Ralph-Joseph Tatt, Apr 23 2018
a(n) + 1 is the minimum number of pairwise disjoint subsets of an n-element set such that for each k from 1 to n there is a set with cardinality k which is the union of some of those subsets. - Wojciech Raszka, Apr 15 2019
Minimum height of an n-node binary tree. - Yuchun Ji, Mar 22 2021

			a(5)=2 because the binary expansion of 5 (=101) has three bits.

Rüdeger Baumann, Computer-Knobelei, LOG IN Heft 159 (2009), 74-77. - Paul Weisenhorn, Sep 29 2010
G. H. Hardy, Note on Dr. Vacca's series for gamma, Quart. J. Pure Appl. Math., Vol. 43 (1912), pp. 215-216.
Ernst Jacobsthal, Über die Eulersche konstante, Mathematisch-Naturwissenschaftliche Blätter, Vol. 3, No. 9 (1906), pp. 153-154.
Donald E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, p. 400.
Donald E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.1.3, Problem 41, p. 589. - From N. J. A. Sloane, Aug 03 2012

N. J. A. Sloane, Table of n, a(n) for n = 1..10000
Guo-Niu Han, Enumeration of Standard Puzzles, 2011. [Cached copy]
Guo-Niu Han, Enumeration of Standard Puzzles, arXiv:2006.14070 [math.CO], 2020.
G. H. Hardy, Note on Dr. Vacca's series for gamma, Quart. J. Pure Appl. Math. 43 (1912), 215-216. [Available only in the USA through the Hathi Trust.]
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions, 2004.
Ralf Stephan, Table of generating functions (ps file).
Ralf Stephan, Table of generating functions (pdf file).
G. Vacca, A new series for the Eulerian constant gamma=.577..., Quart. J. Pure Appl. Math., Vol. 41 (1910), pp. 363-368.

Cf. A000193, A000195, A001222, A001620, A003462, A004233, A029837, A032924, A061168 (partial sums), A070939, A081604, A107680, A113473, A152487, A240857.

a000523 1 = 0
a000523 n = 1 + a000523 (div n 2)
a000523_list = 0 : f [0] where
   f xs = ys ++ f ys where ys = map (+ 1) (xs ++ xs)
-- Reinhard Zumkeller, Dec 31 2012, Feb 04 2012, Mar 18 2011

Magma
```
[Ilog2(n) : n in [1..130] ];
```

A000523 := proc(n)
    ilog2(n) ;
end proc: # R. J. Mathar, Nov 28 2016
seq(A000523(n), n=1..90);

Floor[Log[2,Range[110]]] (* Harvey P. Dale, Jul 16 2012 *)
a[ n_] := If[ n < 1, 0, BitLength[n] - 1]; (* Michael Somos, Jul 10 2018 *)

{a(n) = floor(log(n) / log(2))} \\ Likely to yield incorrect results for many if not almost all n. Better use most recent code.

{a(n) = if( n<1, 0, #binary(n) - 1)}; /* Michael Somos, May 28 2014 */

a(n)=logint(n,2) \\ Charles R Greathouse IV, Sep 01 2015

a(n)=exponent(n) \\ Charles R Greathouse IV, Nov 09 2017

def A000523(n):
    return len(bin(n))-3 # Chai Wah Wu, Jul 09 2020

def a(n): return n.bit_length() - 1
print([a(n) for n in range(1, 106)]) # Michael S. Branicky, Apr 18 2023

a(n) = A070939(n) - 1 for n >= 1.
a(n) = if n > 1, then a(floor(n / 2)) + 1; else 0. - Reinhard Zumkeller, Oct 29 2001
G.f.: (1/(1 - x)) * Sum_{k>=1} x^2^k. - Ralf Stephan, Apr 13 2002
a(n+1) = number of digits of n-th number with no 0 in ternary representation = A081604(A032924(n)); A107680(n) = A003462(a(n+1)). - Reinhard Zumkeller, May 20 2005
a(n) = A152487(n-1,0) = A152487(n,1). - Reinhard Zumkeller, Dec 06 2008
a(n) = k with 2^k <= n < 2^(k+1); a(n) = floor(log_2(n)). - Paul Weisenhorn, Sep 29 2010
a(n) = Max_{k=1..n} A240857(n,k). - Reinhard Zumkeller, Apr 14 2014
a(n) = A113473(n) - 1. - Filip Zaludek, Oct 29 2016
Sum_{n>=2} (-1)^n*a(n)/n = gamma = A001620 (Jacobsthal, 1906; Vacca, 1910). - Amiram Eldar, Jun 12 2021
a(n) = floor(Sum_{k=1..n-1} (n+1)^(n-2^k)) mod n. - Joseph M. Shunia, Jul 19 2024

Error in 4th term, pointed out by Joe Keane (jgk(AT)jgk.org), has been corrected.

More terms from Michael Somos, Aug 02 2002

A047778 Concatenation of the first n numbers in binary (converted to base 10).

Original entry on oeis.org

1, 6, 27, 220, 1765, 14126, 113015, 1808248, 28931977, 462911642, 7406586283, 118505380540, 1896086088653, 30337377418462, 485398038695407, 15532737238253040, 497047591624097297, 15905522931971113522, 508976733823075632723, 16287255482338420247156

Offset: 1

Aaron Gulliver (gulliver(AT)elec.canterbury.ac.nz)

The smallest prime in this sequence is 485398038695407. What is the full subsequence of primes? - N. J. A. Sloane, Oct 03 2015

There is only the one prime in the first 22400 terms, making a second prime > 10^91000. - Hans Havermann, Oct 07 2015

			a(4) = 1 10 11 100 [base 2] = 220 [base 10].

Joe B. Stephen, Table of n, a(n) for n = 1..400 (terms 1..250 from Reinhard Zumkeller)

Cf. A001855 (bit counts, offset by 1), A061168, A066716.

Concatenation of first n numbers in other bases: 2: this sequence, 3: A048435, 4: A048436, 5: A048437, 6: A048438, 7: A048439, 8: A048440, 9: A048441, 10: A007908, 11: A048442, 12: A048443, 13: A048444, 14: A048445, 15: A048446, 16: A048447.

a047778 = (foldl (\v d -> 2*v + d) 0) . concatMap (reverse . unfoldr
   (\x -> if x == 0 then Nothing else Just $ swap $ divMod x 2)) .
   enumFromTo 1
-- Reinhard Zumkeller, Feb 19 2012

conc:= (x,y) -> x*2^(1+ilog2(y))+y:
a[1]:= 1:
for n from 2 to 30 do a[n]:= conc(a[n-1],n) od:
seq(a[n],n=1..30); # Robert Israel, Oct 07 2015

If[STARTPOINT==1,n={},n=Flatten[IntegerDigits[Range[STARTPOINT-1],2]]]; Table[AppendTo[n,IntegerDigits[w,2]];n=Flatten[n];FromDigits[n,2],{w,STARTPOINT,ENDPOINT}] (* Dylan Hamilton, Aug 04 2010 *)
f[n_] := FromDigits[ Flatten@ IntegerDigits[ Range@n, 2], 2]; Array[f, 18] (* Robert G. Wilson v, Nov 07 2010 *)
Module[{n = 1}, NestList[#*2^BitLength[++n] + n &, 1, 25]] (* Paolo Xausa, Sep 30 2024 *)

cb(a,b)=a<<#binary(b) + b
a(n)=fold(cb, [1..n]) \\ Charles R Greathouse IV, Jun 21 2017

A047778_vec(N=20,s)=vector(N,k,s=s<M. F. Hasler, Oct 25 2019

def a(n): return int("".join([(bin(i))[2:] for i in range(1, n+1)]), 2)
print([a(n) for n in range(1, 19)]) # Michael S. Branicky, Jan 06 2021

from functools import reduce
def A047778(n): return reduce(lambda i,j:(i<Chai Wah Wu, Feb 26 2023

a(n) = a(n-1)*2^(1+floor(log_2(n))) + n. - Henry Bottomley, Jan 12 2001

a(n) = 4C / 2^frac(log_2(n)) * n^{n+1} / r(frac(log_2(n)))^n + O(1), where r(x) = 2^{x - 1 + 2^{1-x}}; frac is the fractional part function frac(x) = x - floor(x); and C is the binary Champernowne constant (A066716). (In fact, a(n) is the floor of this expression; the error term is between 1/2 and 1.) r(x) takes on values between e*log(2) and 2 for x in the range 0 to 1. It follows using Stirling's approximation that the radius of convergence for the e.g.f. is log 2. - Franklin T. Adams-Watters, Sep 07 2006

More terms from Patrick De Geest, May 15 1999

Name edited by Joe B. Stephen, Jul 22 2023

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

Original entry on oeis.org

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)

A123753 Partial sums of A070941.

Original entry on oeis.org

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

A208741 Triangular array read by rows. T(n,k) is the number of sets of exactly k distinct binary words with a total of n letters.

Original entry on oeis.org

2, 4, 1, 8, 8, 16, 22, 4, 32, 64, 20, 64, 156, 84, 6, 128, 384, 264, 40, 256, 888, 784, 189, 4, 512, 2048, 2152, 704, 50, 1024, 4592, 5664, 2384, 272, 1, 2048, 10240, 14368, 7328, 1232, 32, 4096, 22496, 35568, 21382, 4704, 248

Offset: 1

Geoffrey Critzer, Mar 08 2012

Equivalently, T(n,k) is the number of integer partitions of n into distinct parts with two types of 1's, four types of 2's, ... , 2^i types of i's,...; where k is the number of summands (of any type).
Row sums = A102866.
Row lengths increase by 1 at n=A061168(offset).

			T(3,2) = 8 because we have: {a,aa}, {a,ab}, {a,ba}, {a,bb}, {b,aa}, {b,ab}, {b,ba}, {b,bb}; 2 word languages with total length 3.
Triangle T(n,k) begins:
   2;
   4,     1;
   8,     8;
  16,    22,    4;
  32,    64,   20;
  64,   156,   84,   6;
  ...

Alois P. Heinz, Rows n = 0..300, flattened
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 64

Cf. A102866, A209406, A360634.

h:= proc(n, i) option remember; expand(`if`(n=0, 1, `if`(i<1, 0,
      add(h(n-i*j, i-1)*binomial(2^i, j)*x^j, j=0..n/i))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..degree(p)))(h(n$2)):
seq(T(n), n=1..15);  # Alois P. Heinz, Sep 24 2017

nn=12; p=Product[(1+y x^i)^(2^i), {i,1,nn}]; f[list_] := Select[list, #>0&]; Map[f, Drop[CoefficientList[Series[p[x,y], {x,0,nn}], {x,y}], 1]]//Flatten

O.g.f.: Product_{i>=1} (1 + y*x^i)^(2^i).

A296354 Official position where binary expansion of n starts in the list of binary numbers in the binary Champernowne sequence A076478.

Original entry on oeis.org

0, 1, 6, 8, 22, 25, 28, 31, 66, 70, 74, 78, 82, 86, 90, 94, 178, 183, 188, 193, 198, 203, 208, 213, 218, 223, 228, 233, 238, 243, 248, 253, 450, 456, 462, 468, 474, 480, 486, 492, 498, 504, 510, 516, 522, 528, 534, 540, 546, 552, 558, 564, 570, 576, 582, 588

Offset: 0

N. J. A. Sloane, Dec 14 2017

a(n) is the official position where the binary expansion of n appears. The binary expansion of n may also appear earlier, by accident, see A296355 and A296356.

			Here is the list A076478 broken up to show the successive binary numbers (the indexing starts at 0):
0,
1,
0,0,
0,1,
1,0,
1,1,
0,0,0,
0,0,1,
0,1,0,
0,1,1,
1,0,0,
1,0,1,
...
2 = 1,0 starts at position 6, so a(2) = 6.
4 = 1,0,0 starts at position 22, so a(4) = 22.

Rémy Sigrist, Table of n, a(n) for n = 0..16384

Cf. A029837, A036799, A061168, A076478, A296355, A296356.

a(n) = my (w=#binary(n)); return (2 + 2^w*(w-2) + w*n) \\ Rémy Sigrist, Dec 15 2017

a(n) = A036799(A029837(n + 1) - 1) + A029837(n + 1) * n. - Rémy Sigrist, Dec 15 2017

More terms from Rémy Sigrist, Dec 15 2017

A296355 True position where binary expansion of n starts in the list of binary numbers in the binary Champernowne sequence A076478.

Original entry on oeis.org

0, 1, 1, 5, 1, 6, 5, 20, 1, 17, 15, 6, 8, 5, 20, 63, 9, 1, 22, 17, 15, 55, 6, 25, 8, 21, 48, 5, 20, 27, 63, 174, 9, 111, 51, 1, 41, 22, 70, 17, 49, 15, 74, 55, 6, 154, 25, 78, 8, 65, 21, 59, 48, 73, 5, 28, 31, 20, 135, 27, 63, 89, 174, 445, 33, 9, 120, 111, 66

Offset: 0

N. J. A. Sloane, Dec 14 2017; corrected and extended Dec 17 2017

A296354(n) is the official position where the binary expansion of n appears in A076478, but the binary expansion of n may also appear earlier, by accident, and it is that starting position that is listed here.

In fact every number > 1 appears earlier - see A296356 for the proof.

			Here is the list A076478 broken up to show the successive binary numbers (the indexing starts at 0):
0,
1,
0,0,
0,1,
1,0,
1,1,
0,0,0,
0,0,1,
0,1,0,
0,1,1,
1,0,0,
1,0,1,
...
2 = 1,0 officially starts at position 6, so A076478(2) = 6, but 1,0 actually can be seen starting at position 1, so a(2) = 1.
4 = 1,0,0 officially starts at position 22, so A076478(4) = 22, but 1,0,0 actually can be seen starting at position 1, so a(4) = 1.

Rémy Sigrist, Table of n, a(n) for n = 0..16384
Rémy Sigrist, Perl program for A296355

Cf. A076478, A061168. A296354, A296356.

More terms from Rémy Sigrist, Dec 19 2017

A239091 Prefix overlap of dictionary consisting of binary expansions of 0 through n.

Original entry on oeis.org

0, 1, 2, 3, 5, 6, 8, 9, 12, 14, 17, 18, 21, 23, 26, 27, 31, 34, 38, 40, 44, 47, 51, 52, 56, 59, 63, 65, 69, 72, 76, 77, 82, 86, 91, 94, 99, 103, 108, 110, 115, 119, 124, 127, 132, 136, 141, 142, 147, 151, 156, 159, 164, 168, 173, 175, 180, 184, 189, 192, 197, 201, 206

Offset: 1

N. J. A. Sloane, Mar 22 2014

The prefix overlap of a dictionary is the sum of the prefix overlaps between successive words.

Partial sums of A238845.

			For n=5 the dictionary is
0
1
10
11
100
101
and the successive prefix overlaps are 0,1,1,1,2, whose sum is a(5)=5.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Rodica Simion and Herbert S. Wilf, The distribution of prefix overlap in consecutive dictionary entries, SIAM J. Algebraic Discrete Methods, 7(1986), no. 3, 470--475. MR0844051.

Cf. A000523, A011371, A061168, A238845, A239092.

a(n) = A061168(n+1) - A011371(n+1) + A000523(n+1). - Alan Michael Gómez Calderón, Jul 17 2025

A324074 Total number of distorted ancestor-successor pairs in all defective (binary) heaps on n elements.

Original entry on oeis.org

0, 0, 1, 6, 48, 360, 2880, 25200, 262080, 2903040, 34473600, 439084800, 5987520000, 87178291200, 1351263513600, 22230464256000, 397533007872000, 7469435990016000, 147254595231744000, 3041127510220800000, 65688354220769280000, 1481637322979573760000

Offset: 0

Alois P. Heinz, Feb 14 2019

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..100
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap

Cf. A000523, A061168, A306393.

b:= proc(u, o) option remember; local n, g, l; n:= u+o;
      if n=0 then 1
    else g:= 2^ilog2(n); l:= min(g-1, n-g/2); expand(
         add(x^(n-j)*add(binomial(j-1, i)*binomial(n-j, l-i)*
         b(i, l-i)*b(j-1-i, n-l-j+i), i=0..min(j-1, l)), j=1..u)+
         add(x^(j-1)*add(binomial(j-1, i)*binomial(n-j, l-i)*
         b(l-i, i)*b(n-l-j+i, j-1-i), i=0..min(j-1, l)), j=1..o))
      fi
    end:
a:= n-> (p-> add(coeff(p, x, i)*i, i=0..degree(p)))(b(n, 0)):
seq(a(n), n=0..25);

b[u_, o_] := b[u, o] = Module[{n, g, l}, n = u + o; If[n == 0, 1,
     g = 2^(Length[IntegerDigits[n, 2]]-1); l = Min[g-1, n-g/2]; Expand[
     Sum[x^(n - j)*Sum[Binomial[j - 1, i]*Binomial[n - j, l - i]*
     b[i, l-i]*b[j-1-i, n-l-j+i], {i, 0, Min[j - 1, l]}], {j, 1, u}] +
     Sum[x^(j - 1)*Sum[Binomial[j - 1, i]*Binomial[n - j, l - i]*
     b[l-i, i]*b[n-l-j+i, j-1-i], {i, 0, Min[j - 1, l]}], {j, 1,o}]]]];
a[n_] := With[{p=b[n, 0]}, CoefficientList[p, x].Range[0, Exponent[p, x]]];
a /@ Range[0, 25] (* Jean-François Alcover, Apr 23 2021, after Alois P. Heinz *)

a(n) = Sum_{k=0..A061168(n)} k * A306393(n,k).

cp's OEIS Frontend

A306393 Number T(n,k) of defective (binary) heaps on n elements where k ancestor-successor pairs do not have the correct order; triangle T(n,k), n >= 0, 0 <= k <= A061168(n), read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A000523 a(n) = floor(log_2(n)).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

Python

Python

Formula

Extensions

A047778 Concatenation of the first n numbers in binary (converted to base 10).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Python

Formula

Extensions

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

A123753 Partial sums of A070941.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica