A061168 -id:A061168 - cp's OEIS frontend

A324075 Number of defective (binary) heaps on n elements having one half of their ancestor-successor pairs (rounded down) distorted.

1, 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 359520, 3590400, 39362400, 472919040, 6133670400, 85948262400, 1284106824000, 20434058444800, 345796766515200, 6188467544064000, 117398964114432000, 2341018467532800000, 49035684501872640000, 1074839883779211264000

Offset: 0

Alois P. Heinz, Feb 14 2019

nonn

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

Central terms (also maxima) of rows of A306393.

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

Cf. A000142, A000523, A061168, A306393.

h:= proc(n) option remember; `if`(n<1, 0, ilog2(n)+h(n-1)) end:
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-> coeff(b(n, 0), x, iquo(h(n), 2)):
seq(a(n), n=0..25);

h[n_] := h[n] = If[n < 1, 0, Length[IntegerDigits[n, 2]] - 1 + h[n - 1]];
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_] := Coefficient[b[n, 0], x, Quotient[h[n], 2]];
a /@ Range[0, 25] (* Jean-François Alcover, Apr 23 2021, after Alois P. Heinz *)

a(n) = A306393(floor(A061168(n)/2)).

a(n) <= (n-1)! for n >= 1 with equality only for n <= 9.

A123533 Primes in A001855.

Original entry on oeis.org

3, 5, 11, 17, 29, 37, 41, 59, 79, 89, 109, 349, 419, 433, 461, 503, 587, 601, 643, 727, 769, 809, 857, 881, 929, 937, 953, 977, 1009, 1033, 1049, 1097, 1129, 1153, 1193, 1201, 1217, 1249, 1289, 1297, 1321, 1361, 1409, 1433, 1481, 1489, 1553, 1601, 1609

Offset: 1

Jonathan Vos Post, Nov 10 2006

Paolo Xausa, Table of n, a(n) for n = 1..10000

Intersection of A000040 and A001855.

Cf. A001768, A029837, A003071, A000337, A030190, A030308, A061168.

A001855 := proc(n) local c ; c := ceil(log[2](n)) ; n*c-2^c+1 ; end: for n from 1 to 300 do srts := A001855(n) : if isprime(srts) then printf("%d, ",srts) ; fi ; od : # R. J. Mathar, Dec 16 2006

Select[Accumulate[BitLength[Range[0, 300]]], PrimeQ] (* Paolo Xausa, Jun 28 2024 *)

Corrected and extended by R. J. Mathar, Dec 16 2006

A123535 Recurrence from values at floor of a third and two-thirds.

Original entry on oeis.org

1, 4, 8, 16, 17, 26, 32, 33, 43, 58, 59, 61, 73, 74, 90, 101, 102, 105, 124, 125, 127, 145, 146, 158, 170, 171, 175, 210, 211, 213, 217, 218, 237, 241, 242, 255, 280, 281, 283, 289, 290, 326, 344, 345, 348, 364, 365, 367, 388, 389, 394, 399, 400, 414, 459, 460

Offset: 0

Jonathan Vos Post, Nov 11 2006

Roughly analogous to maximal number of comparisons for sorting n elements by binary insertion (A001855).

			a(0) = 1 by definition.
a(1) = a(floor(1/3)) + a(floor(2/3)) + 1 + 1 = a(0) + a(0) + 2 = 4.
a(2) = a(floor(2/3)) + a(floor(4/3)) + 2 + 1 = a(0) + a(1) + 3 = 8.
a(3) = a(floor(3/3)) + a(floor(6/3)) + 3 + 1 = a(1) + a(2) + 4 = 16.
a(4) = a(floor(4/3)) + a(floor(8/3)) + 4 + 1 = a(1) + a(2) + 5 = 17.
a(5) = a(floor(5/3)) + a(floor(10/3)) + 5 + 1 = a(1) + a(3) + 6 = 26.
a(6) = a(floor(6/3)) + a(floor(12/3)) + 6 + 1 = a(2) + a(4) + 7 = 32.

Paolo Xausa, Table of n, a(n) for n = 0..10000
Wikipedia, Akra-Bazzi method.

Cf. A001768, A001855, A029837, A003071, A000337, A030190, A030308, A061168.

A123535 := proc(n) options remember ; if n = 0 then RETURN(1) ; else RETURN(A123535(floor(n/3))+A123535(floor(2*n/3))+n+1) ; fi ; end: for n from 0 to 100 do printf("%d,",A123535(n)) ; od : # R. J. Mathar, Jan 13 2007

a[0] = 1; a[n_] := a[n] = a[Floor[n/3]] + a[Floor[2*n/3]] + n + 1;
Array[a, 100, 0] (* Paolo Xausa, Jun 27 2024 *)

a(0) = 1, for n>0: a(n) = a(floor(n/3)) + a(floor(2n/3)) + n + 1.

Corrected and extended by R. J. Mathar, Jan 13 2007

a(0)=1 prepended by Paolo Xausa, Jun 27 2024

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

A324075 Number of defective (binary) heaps on n elements having one half of their ancestor-successor pairs (rounded down) distorted.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A123533 Primes in A001855.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A123535 Recurrence from values at floor of a third and two-thirds.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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