A029837 -id:A029837 - cp's OEIS frontend

A217298 Triangle read by columns: T(n,k) = number of AVL trees of height n with k (leaf-) nodes, k>=1, A029837(k)<=n<A072649(k).

1, 1, 2, 1, 4, 6, 4, 1, 16, 32, 44, 60, 70, 56, 128, 28, 448, 8, 864, 1, 1552, 2720, 4288, 6312, 9004, 11992, 4096, 14372, 22528, 15400, 67584, 14630, 159744, 11968, 334080, 8104, 644992, 4376, 1195008, 1820, 2158912, 560, 3811904, 120, 6617184, 16, 11307904

Offset: 1

Alois P. Heinz, Mar 17 2013

			There are 2 AVL trees of height 2 with 3 (leaf-) nodes:
       o       o
      / \     / \
     o   N   N   o
    / \         / \
   N   N       N   N
Triangle begins:
  1
  . 1
  . . 2 1
  . . . . 4 6 4  1
  . . . . . . . 16 32 44 60 70  56  28   8    1
  . . . . . . .  .  .  .  .  . 128 448 864 1552 2720 ...

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 239, Eq 79, A_5.
D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 6.2.3 (7) and (8).

Alois P. Heinz, Columns k = 1..1500, flattened
Ralf Hinze, Functional Pearls: Purely functional 1-2 brother trees, Journal of Functional Programming, 19(6):633-644, 2009, DOI: 10.1017/S0956796809007333.
R. C. Richards, Shape distribution of height-balanced trees, Info. Proc. Lett., 17 (1983), 17-20.
Wikipedia, AVL tree
Index entries for sequences related to rooted trees

Triangle read by rows gives: A143897.
Row sums give: A029758.
Column sums give: A006265.
First elements of rows give: A174677.
First, last elements of columns give: A217299, A217300.
Row lengths give: 1+A008466(n).
Column heights give: A217710(k).
Cf. A029837, A072649.

A045716 a(n) is the binary order (A029837) of the n-th primorial number, A002110(n).

Original entry on oeis.org

1, 3, 5, 8, 12, 15, 19, 24, 28, 33, 38, 43, 49, 54, 60, 65, 71, 77, 83, 89, 96, 102, 108, 115, 121, 128, 135, 141, 148, 155, 162, 169, 176, 183, 190, 198, 205, 212, 220, 227, 235, 242, 250, 257, 265, 273, 280, 288, 296, 304, 312, 319, 327, 335, 343, 351, 359

Offset: 1

Labos Elemer

nonn

These orders determine the maximal numbers of unitary divisors valid for integers in given binary order ranges (see A046971).

			The sixth primorial number is 2*3*5*7*11*13 = 30030, which is in the interval [16385, 32768] = [2^14 + 1, 2^15], so its binary order is a(6)=15. [corrected by _Jon E. Schoenfield_, May 13 2018]

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A029837, A002110, A046971, A054850.

Table[Ceiling@ Log2[Times @@ Prime@ Range@ n], {n, 57}] (* Michael De Vlieger, Feb 05 2017 *)

a(n)=logint(prod(i=1,n,prime(i))-1,2)+1 \\ Charles R Greathouse IV, Feb 06 2017

a(n) = A054850(n)+1, n >= 2.

a(n) = A070939(A002110(n)) for n>1. - Jachym Barvinek, Mar 22 2018

A036382 Odd split numbers: have a nontrivial factorization n=ab with a and b coprime, so that L(a) + L(b) <= L(n), where L(x) = A029837(x) = ceiling(log_2(x)).

Original entry on oeis.org

21, 33, 35, 39, 65, 69, 75, 77, 87, 91, 93, 105, 129, 133, 135, 141, 143, 145, 147, 155, 159, 161, 165, 175, 177, 183, 189, 195, 203, 217, 259, 261, 265, 267, 273, 275, 279, 285, 287, 291, 295, 297, 299, 301, 303, 305, 309, 315, 319, 321, 325, 327, 329, 339

Offset: 1

Labos Elemer

nonn

All even numbers are split numbers, except that prime powers -- here powers of 2 -- are by definition excluded.

The gaps g(n) = a(n+1) - a(n) are growing up to some local maximum before suddenly dropping down to a very small value and starting a new cycle of growth. The local maxima, distinctly seen as kinks in the graph, are g(1) = 12, g(4) = 26, g(12) = 24, g(30) = 42, g(70) = 48, g(157) = 110, g(348) = 96, g(748) = 160, g(1603) = 192, g(3379) = 446, g(7076) = 384, ... They occur at indices slightly larger than twice the preceding one; every other is of size 6*2^k, k = 1,2,3,... while those in between don't seem to follow a simple pattern and are sometimes larger than the subsequent gap of size 6*2^k. - M. F. Hasler, Apr 15 2017

			s = 39 is a split number since s = 39 = 3*13, gcd(3,13)=1 and L(3) + L(13) = 2 + 4 = L(39).

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A029827, A029837, A036378-A036390.

Select[Range[1, 340, 2], Function[n, Total@ Boole@ Map[And[Total@ Ceiling@ Log2@ # <= Ceiling@ Log2@ n, CoprimeQ @@ #] &, Map[{#, n/#} &, Rest@ Take[#, Ceiling[Length[#]/2]]]] > 0 &@ Divisors@ n]] (* Michael De Vlieger, Mar 03 2017 *)

Name corrected by Michael De Vlieger, Mar 03 2017

A036451 Maximal value of d(x) (the number of divisors of x, A000005) if the binary order (see A029837) of x, the value g(x) = n.

Original entry on oeis.org

1, 2, 3, 4, 6, 8, 12, 16, 20, 24, 32, 40, 48, 64, 80, 96, 120, 144, 168, 200, 240, 288, 360, 432, 504, 600, 720, 864, 1008, 1152, 1344, 1600, 1920, 2304, 2688, 3072, 3584, 4096, 4800, 5760, 6720, 7680, 8640, 10080, 11520, 13824, 16128, 18432, 20736, 23040

Offset: 0

Labos Elemer

nonn

g(x) <= n can be replaced by g(x) = n.

			In the range of g(x) <= 5, the values of d(x) can be: 1, 2, 3, 4, 5, 6, 8 of which 8 is the maximal, so a(n) = a(g(x)) = 8.

Giovanni Resta, Table of n, a(n) for n = 0..250 (based on A002182 b-file)

Cf. A000005, A002182, A029837, A005179, A007416, A036470-A036472.

Max /@ Table[DivisorSigma[0, Floor[2^(n - 1) + k]], {n, 0, 22}, {k, Ceiling[2^(n - 1)]}] (* Michael De Vlieger, May 10 2017 *)

a(22)-a(32) from Alex Ratushnyak, Jun 06 2013

a(33)-a(49) from Giovanni Resta, Jun 06 2013

A036470 a(n) is the number of distinct possible values of d(k), the number of divisors of k, among numbers k whose binary order (A029837) does not exceed n.

Original entry on oeis.org

1, 2, 3, 4, 6, 7, 11, 12, 16, 17, 23, 26, 31, 37, 43, 48, 58, 64, 74, 82, 94, 106, 122, 133, 146, 165, 183, 202, 224, 244, 267, 294, 325, 355, 389, 416, 453, 500, 541, 584, 636, 680, 737, 795, 859, 922, 995, 1068, 1149, 1233, 1324, 1412, 1523, 1616, 1731, 1845

Offset: 0

Labos Elemer

nonn

			If 1 <= k <= 128, i.e., the binary order of k is g(k) <= 7, then d(k) takes 12 values {1,2,3,4,5,6,7,8,9,10,12,16}; thus a(7) = 12. The maximal value (16) appears as a(7) in A036451.

David A. Corneth, Table of n, a(n) for n = 0..63

Cf. A000005, A005179, A029837, A036471, A036493.

a(20)-a(21) corrected by David A. Corneth, May 12 2018

A036761 Number of refactorable integers (A033950) of binary order (A029837) n.

Original entry on oeis.org

1, 1, 0, 1, 2, 2, 4, 8, 13, 22, 39, 77, 137, 254, 459, 889, 1665, 3175, 6041, 11619, 22319, 42979, 83123, 160649, 311826, 605225, 1176998, 2291702, 4466923, 8716126, 17023771, 33279942, 65109458, 127484313, 249783733, 489738130, 960801221, 1886039740

Offset: 0

Labos Elemer

nonn

Since for any epsilon d(n) <= n^epsilon if n is large enough, a(n) does not grow very quickly.

			{1} has binary order 0, {2} has binary order 1, no term has binary order 2, {8} has binary order 3, {9,12} have binary order 4, {18,24} have binary order 5, ...
The 8 numbers, between 65 and 128 (with binary order 7) which are divided by d(x) (A000005) are 72,80,84,88,96,104,108,128, so a(7)=8.

Cf. A000005, A029837, A033950.

with(numtheory): A036761 := proc(n) local ct,k,lim: if(n=0)then return 1: else ct:=0: lim:=2^n: for k from 2^(n-1)+1 to lim do if(k mod tau(k) = 0)then ct:=ct+1: fi: od: return ct: fi: end: seq(A036761(n),n=0..10); # Nathaniel Johnston, May 04 2011

Table[Count[Range[2^(n - 1) + 1, 2^(n)], k_ /; Divisible[k, DivisorSigma[0, k]]] + Boole[n == 0], {n, 0, 22}] (* Michael De Vlieger, May 20 2017 *)

a(22)-a(37) from Donovan Johnson, Aug 29 2012

A228153 Triangle read by columns: T(n,k) = maximal external path length of AVL trees of height n with k (leaf-) nodes, k>=1, A029837(k)<=n<A072649(k).

Original entry on oeis.org

0, 2, 5, 8, 12, 16, 20, 24, 25, 30, 35, 40, 44, 49, 50, 54, 56, 59, 62, 64, 68, 73, 79, 85, 91, 97, 96, 102, 103, 107, 110, 113, 117, 119, 123, 125, 130, 131, 137, 136, 144, 142, 151, 148, 157, 154, 163, 160, 170, 177, 184, 180, 191, 188, 197, 196, 204, 204

Offset: 1

Herbert Eberle, Aug 13 2013

The external path length of a tree is the sum of the levels of its external nodes (i.e. leaves).

			In the (two) AVL trees of height 2 the 3 external nodes (leaves) have once depth 1 and twice depth 2:
       o       o
      / \     / \
     o   1   1   o
    / \         / \
   2   2       2   2
so that the sum of depths is 5 for both trees.
Triangle begins:
  0
  . 2
  . . 5 8
  . . . . 12 16 20 24
  . . . .  .  .  . 25 30 35 40 44 49 54 59 64
  . . . .  .  .  .  .  .  .  .  . 50 56 62 68 73 79 85 91 97 102 ...
  . . . .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 96 103 ...

D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 6.2.3 (7) and (8).

Alois P. Heinz, Columns k = 1..3000, flattened
R. C. Richards, Shape distribution of height-balanced trees, Info. Proc. Lett., 17 (1983), 17-20.
Wikipedia, AVL tree
Index entries for sequences related to rooted trees

Triangle read by rows gives: A228152.
Row maxima give: n*2^n = A036289(n).
Row minima give: A067331(n-1) for n>0 or A166106(n+2).
Row lengths give: 1+A008466(n).
Number of AVL trees read by rows gives: A143897.
The infimum of all external path lengths of binary trees with k (leaf-) nodes is: A003314(k) for k>0.
Column maxima give: A228155(k).
Column heights give: A217710(k).
Number of AVL trees read by columns gives: A217298.

maxNods = 100; Clear[T, A029837, A072649, A036289, A228155]; T[0, 1] = 0; A029837[1] = 0; A072649[1] = 1; A228155[1] = 0; For[k = 2, k <= maxNods, k++, A029837[k] = maxNods; A072649[k] = 0; A228155u = 0; For[kL = 1, kL <= Floor[k/2], kL++, For[hL = A029837[kL], hL <= A072649[kL] - 1, hL++, For[hR = Max[hL - 1, A029837[k - kL]], hR <= Min[hL + 1, A072649[k - kL] - 1], hR++, maxDepthSum = k + T[hL, kL] + T[hR, k - kL]; A228155u = Max[maxDepthSum, A228155u]; h = Max[hL, hR] + 1; If[ !IntegerQ[T[h, k]], T[h, k] = maxDepthSum, T[h, k] = Max[maxDepthSum, T[h, k]]]; A029837[k] = Min[h, A029837[k]]; If[ !IntegerQ[A036289[h]], A036289[h] = maxDepthSum, A036289[h] = Max[maxDepthSum, A036289[h]]]; A072649[k] = Max[h + 1, A072649[k]]; ]]]; A228155[k] = A228155u]; k =.; Table[ Select[ Table[T[n, k], {n, A029837[k], A072649[k] - 1}], IntegerQ], {k, 1, maxNods}] // Flatten (* Jean-François Alcover, Aug 19 2013, translated and adapted from Herbert Eberle's MuPAD program *)

maxNods:=100: // max number of leaves (= external nodes)
// Triangle T for all AVL trees with <= maxNods leaves:
delete T:
// table T indexed [h, k] (h=height, k=number of leaves):
T[0, 1]:=0:
// A029837 indexed [k], min height of tree with k leaves:
A029837:=array(1..maxNods): A029837[1]:=0:
// A072649 indexed [k], 1+max height of AVL tree with k leaves:
A072649:=array(1..maxNods): A072649[1]:=1:
// A036289 indexed [h], max depthsum of all height h AVL trees:
A036289:=array(1..maxNods):
// A228155 indexed [k], max depthsum of all AVL trees with k leaves:
A228155:=array(1..maxNods): A228155[1]:=0:
for k from 2 to maxNods do:
  A029837[k]:=maxNods: // try infinity for the min height
  A072649[k]:=0:
  A228155u:=0:
  // Put together 2 AVL trees:
  for kL from 1 to floor(k/2) do:
    // kL leaves in the left tree
    for hL from A029837[kL] to A072649[kL]-1 do:
      for hR from max(hL-1, A029837[k-kL])
               to min(hL+1, A072649[k-kL]-1) do:
        // k-kL leaves in the right subtree
        maxDepthSum:=T[hL, kL]+T[hR, k-kL]+k:
        A228155u:=max(maxDepthSum, A228155u):
        h:=max(hL, hR)+1:
        if type(T[h, k]) <> DOM_INT then // T[h, k] uninit
          T[h, k]:=maxDepthSum:
        else
          T[h, k]:=max(maxDepthSum, T[h, k]):
        end_if:
        A029837[k]:=min(h, A029837[k]):
        if type(A036289[h]) <> DOM_INT then
          A036289[h]:=maxDepthSum:
        else
          A036289[h]:=max(maxDepthSum, A036289[h]):
        end_if:
        A072649[k]:=max(h+1, A072649[k]):
      end_for: // hR
    end_for: // hL
  end_for: // kL
  A228155[k]:=A228155u:
end_for: // k

A036493 Largest number having binary order n (A029837) and of which the number of divisors is maximal in that range of g(k) = n.

Original entry on oeis.org

1, 2, 4, 8, 12, 30, 60, 120, 240, 504, 840, 1680, 3960, 7560, 15120, 32760, 65520, 131040, 262080, 498960, 997920, 1965600, 3603600, 7207200, 14414400, 32432400, 64864800, 122522400, 245044800, 514594080, 1029188160, 2095133040, 4227022800, 8454045600

Offset: 0

Labos Elemer

nonn

This sequence differs from A036451 only at n = 3, 5, 9, 12, and 15, which are the values of n for which there exists more than one k such that g(k) = n and d(k) has the maximum possible value.

a(n) is the largest term k in A067128 such that log_2(k) <= n. - Jon E. Schoenfield, May 13 2018

			For n = 9, k is in {257, 512}, max(d(k)) = 24 (see A036451); this holds for four different numbers (360, 420, 480, and 504); a(9) = 504 since it is the largest.

Cf. A000005, A029837, A005179, A007416, A036451, A036470, A036484.

{1}~Join~Table[Max@ MaximalBy[Range[2^(n - 1) + 1, 2^n], DivisorSigma[0, #] &], {n, 24}] (* Michael De Vlieger, Aug 01 2017 *)

a(22)-a(24) from Michael De Vlieger, Aug 01 2017

a(25)-a(33) from Jon E. Schoenfield, May 12 2018

A306297 Number T(n,k) of subsets of [n] with k binary carry-connected components; triangle T(n,k), n >= 0, 0 <= k <= A029837(n+1), read by rows.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 6, 1, 1, 7, 7, 1, 1, 19, 11, 1, 1, 47, 15, 1, 1, 111, 15, 1, 1, 112, 126, 16, 1, 1, 324, 166, 20, 1, 1, 776, 222, 24, 1, 1, 1736, 286, 24, 1, 1, 3708, 358, 28, 1, 1, 7740, 422, 28, 1, 1, 15868, 486, 28, 1, 1, 32252, 486, 28, 1, 1, 32253, 32738, 514, 29, 1

Offset: 0

Alois P. Heinz, Mar 31 2019

Two integers are binary carry-connected if their bitwise AND is not zero.

T(n,k) is defined for all n,k >= 0. The triangle contains only the positive terms. T(n,k) = 0 if k > A029837(n+1).

			T(4,0) = 1: {}.
T(4,1) = 7: 1, 2, 3, 13, 23, 123, 4.
T(4,2) = 7: 1|2, 1|4, 2|4, 3|4, 13|4, 23|4, 123|4.
T(4,3) = 1: 1|2|4.
(The connected components are shown as blocks of a set partition.)
Triangle T(n,k) begins:
  1;
  1,    1;
  1,    2,   1;
  1,    6,   1;
  1,    7,   7,  1;
  1,   19,  11,  1;
  1,   47,  15,  1;
  1,  111,  15,  1;
  1,  112, 126, 16, 1;
  1,  324, 166, 20, 1;
  1,  776, 222, 24, 1;
  1, 1736, 286, 24, 1;
  1, 3708, 358, 28, 1;
  ...

Alois P. Heinz, Rows n = 0..1023
Wikipedia, Bitwise operation
Wikipedia, Partition of a set

Columns k=0-1 give: A000007, -1 + A325105.
Row sums give A000079.
Number of terms in row n gives A070941.
Cf. A029837, A325105.

h:= proc(n, s) local i, m; m:= n;
      for i in s do m:= Bits[Or](m, i) od; {m}
    end:
g:= (n, s)-> (w-> `if`(w={}, s union {n}, s minus w union
              h(n, w)))(select(x-> Bits[And](n, x)>0, s)):
b:= proc(n, s) option remember; `if`(n=0, x^nops(s),
      b(n-1, s)+b(n-1, g(n, s)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, {})):
seq(T(n), n=0..23);

h[n_, s_List] := Module[{i, m = n}, For[i = 1, i <= Length[s], i++, m = BitOr[m, s[[i]]]]; m];
g[n_, s_List] := Function[w, If[w == {}, s ~Union~ {n}, s ~Complement~ w  ~Union~ {h[n, w]}]][Select[s, BitAnd[n, #] > 0&]];
b[n_, s_List] := b[n, s] = If[n == 0, x^Length[s], b[n - 1, s] + b[n - 1, g[n, s]]];
T[n_] := CoefficientList[b[n, {}], x];
T /@ Range[0, 23] // Flatten (* Jean-François Alcover, Apr 18 2021, after Alois P. Heinz *)

T(n,0) + T(n,1) = A325105(n).

T(n,A029837(n+1)) = 1.

A036385 Number of split numbers (A036382) with binary order (A029837) n, i.e., those in interval [ 2^(n-1), 2^n ].

Original entry on oeis.org

0, 0, 1, 3, 8, 18, 39, 81, 167, 342, 702, 1423, 2902, 5871, 11888, 24027, 48519, 97900, 197375, 397713, 800877, 1612007, 3243196, 6522366, 13112877, 26354391, 52951859, 106364992, 213608176, 428885665, 860959606

Offset: 1

Labos Elemer

			Out of the 128 numbers with the binary order 8, there are 81 split numbers (odd + even); so a(7)=81.

Cf. A029827, A029837, A036378-A036390.

a(20)-a(31) from Sean A. Irvine, Oct 29 2020

cp's OEIS Frontend

A217298 Triangle read by columns: T(n,k) = number of AVL trees of height n with k (leaf-) nodes, k>=1, A029837(k)<=n<A072649(k).

Views

Author

Keywords

Examples

References

Links

Crossrefs

A045716 a(n) is the binary order (A029837) of the n-th primorial number, A002110(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A036382 Odd split numbers: have a nontrivial factorization n=ab with a and b coprime, so that L(a) + L(b) <= L(n), where L(x) = A029837(x) = ceiling(log_2(x)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A036451 Maximal value of d(x) (the number of divisors of x, A000005) if the binary order (see A029837) of x, the value g(x) = n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A036470 a(n) is the number of distinct possible values of d(k), the number of divisors of k, among numbers k whose binary order (A029837) does not exceed n.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A036761 Number of refactorable integers (A033950) of binary order (A029837) n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Extensions

A228153 Triangle read by columns: T(n,k) = maximal external path length of AVL trees of height n with k (leaf-) nodes, k>=1, A029837(k)<=n<A072649(k).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

MuPAD

A036493 Largest number having binary order n (A029837) and of which the number of divisors is maximal in that range of g(k) = n.

Views

Author

Keywords

Comments

Examples