Dhruv Matani - cp's OEIS frontend

User: Dhruv Matani

Dhruv Matani has authored 2 sequences.

A251743 Pairs of nodes in a complete binary tree that are at an absolute height difference of less than 2 from each other.

3, 13, 49, 185, 713, 2793, 11049, 43945, 175273, 700073, 2798249, 11188905, 44747433, 178973353, 715860649, 2863377065, 11453377193, 45813246633, 183252462249, 733008800425, 2932033104553, 11728128223913, 46912504507049, 187650001250985, 750599971449513, 3002399818689193, 12009599140539049

Offset: 1

Dhruv Matani, Dec 07 2014

nonn

			For a complete binary tree with 2 levels (root, level-1, level-2), the total number of node pairs is 7 choose 2 = 21, whereas the number of node pairs that are at levels which are at an absolute difference of less than 2 from each other are 13.

def nc2(n):
    return n * (n-1) // 2
def numAdjacentNodes(levels):
    ret = 0
    for level in range(1, levels+1):
        ret += ((1 << level) + nc2(1 << level))
    return ret
for height in range(1, 33):
    print(numAdjacentNodes(height), end=', ')

Conjectures from Colin Barker, Dec 09 2014: (Start)
a(n) = (3*2^n+2^(1+2*n)-5)/3.
a(n) = 6*a(n-1)-7*a(n-2)-6*a(n-3)+8*a(n-4).
G.f.: x*(8*x-3) / ((x-1)*(2*x-1)*(4*x-1)).
(End)

A182105 Number of elements merged by bottom-up merge sort.

Original entry on oeis.org

1, 1, 2, 1, 1, 2, 4, 1, 1, 2, 1, 1, 2, 4, 8, 1, 1, 2, 1, 1, 2, 4, 1, 1, 2, 1, 1, 2, 4, 8, 16, 1, 1, 2, 1, 1, 2, 4, 1, 1, 2, 1, 1, 2, 4, 8, 1, 1, 2, 1, 1, 2, 4, 1, 1, 2, 1, 1, 2, 4, 8, 16, 32, 1, 1, 2, 1, 1, 2, 4, 1, 1, 2, 1, 1, 2, 4, 8, 1, 1, 2, 1, 1, 2, 4, 1, 1, 2, 1, 1, 2, 4, 8, 16, 1, 1, 2, 1, 1, 2, 4, 1, 1, 2, 1, 1, 2, 4, 8

Offset: 1

Dhruv Matani, Apr 12 2012

Also triangle read by rows in which row j lists the first A001511(j) powers of 2, j >= 1, hence records give A000079. Right border gives A006519. Row sums give A038712. The equivalent sequence for partitions is A211009. See example. - Omar E. Pol, Sep 03 2013

It appears that A045412 gives the indices of the terms which are greater than 1. - Carl Joshua Quines, Apr 07 2017

			Using construction (b), the initial values n, u_n, v_n are:
  1, 1, 1
  2, 2, 1
  3, 2, 2
  4, 3, 1
  5, 4, 1
  6, 4, 2
  7, 4, 4
  8, 5, 1
  9, 6, 1
  10, 6, 2
  11, 7, 1
  12, 8, 1
  13, 8, 2
  14, 8, 4
  15, 8, 8
  16, 9, 1
  17, 10, 1
  18, 10, 2
  19, 11, 1
  20, 12, 1
  ...
From _Omar E. Pol_, Sep 03 2013: (Start)
Illustration of initial terms (first 2^5-1 terms):
Written as an irregular triangle: T(j,k) is also the length of the k-th column in the j-th region of the diagram, as shown below. Note that the j-th row of the diagram is equivalent to the j-th composition (in colexicographic order) of 5 (cf. A228525):
------------------------------------
.          Diagram      Triangle
------------------------------------
.  j / k: 1 2 3 4 5  /  1 2 3 4 5
------------------------------------
.         _ _ _ _ _
.  1     |_| | | | |    1;
.  2     |_ _| | | |    1,2;
.  3     |_|   | | |    1;
.  4     |_ _ _| | |    1,2,4;
.  5     |_| |   | |    1;
.  6     |_ _|   | |    1,2;
.  7     |_|     | |    1;
.  8     |_ _ _ _| |    1,2,4,8;
.  9     |_| | |   |    1;
. 10     |_ _| |   |    1,2;
. 11     |_|   |   |    1;
. 12     |_ _ _|   |    1,2,4;
. 13     |_| |     |    1;
. 14     |_ _|     |    1,2;
. 15     |_|       |    1;
. 16     |_ _ _ _ _|    1,2,4,8,16;
...
(End)

Donald E. Knuth, The Art of Computer Programming, Vol. 4, Pre-Fascicle 6A, Section 7.2.2.2, Eq. (97).
Donald E. Knuth, The Art of Computer Programming, Addison-Wesley (2015) Vol. 4, Fascicle 6, Satisfiability, p. 80, Eq. (130).

N. J. A. Sloane, Table of n, a(n) for n = 1..10000
Filip Bártek, Karel Chvalovský, and Martin Suda, Regularization in Spider-Style Strategy Discovery and Schedule Construction, arXiv:2403.12869 [cs.AI], 2024. See p. 5.
Michael Luby Alistair, Alistair Sinclair, and David Zuckerman, Optimal speedup of Las Vegas algorithms, Info. Processing Lett., 47 (1993), 173-180.
Laurent Orseau, Levi H. S. Lelis, Tor Lattimore, Théophane Weber, Single-Agent Policy Tree Search With Guarantees, arXiv:1811.10928 [cs.AI], 2018, also in Advances in Neural Information Processing Systems, 32nd Conference on Neural Information Processing Systems (NIPS 2018), Montréal, Canada.

Cf. A046699, A215020 (a version involving Fibonacci numbers).

A182105_list := proc(n) local L,m,k;
L := NULL;
for m from 1 to n do
for k from 0 to padic[ordp](m, 2) do
L := L,2^k od od;
L; end:
A182105_list(250);
# Peter Luschny, Aug 01 2012, based on Charles R Greathouse IV's PARI program.

Array[Prepend[2^Range@ IntegerExponent[#, 2], 1] &, 48] // Flatten (* Michael De Vlieger, Jan 22 2019 *)

for(n=1,50,for(k=0,valuation(n,2),print1(2^k", "))) \\ Charles R Greathouse IV, Apr 12 2012

The following two constructions are given by Knuth:
(a) a(1) = 1; thereafter a(n+1) = 2a(n) if a(n) has already occurred an even number of times, otherwise a(n+1) = 1.
(b) Set (u_1, v_1) = (1, 1), thereafter (u_{n+1}, v_{n+1}) = ( A ? B : C)
where
A = u_n & -u_n = v_n (where the AND refers to the binary expansions),
B = (u_n + 1, 1) (the result if A is true),
C = (u_n, 2v_n) (the result if A is false).
Then v_n = A182105, u_n = A046699 minus first term.
a(n) = 2^(A082850(n)-1). - Laurent Orseau, Jun 18 2019

Edited by N. J. A. Sloane, Aug 02 2012

cp's OEIS Frontend

User: Dhruv Matani

A251743 Pairs of nodes in a complete binary tree that are at an absolute height difference of less than 2 from each other.

Views

Author

Keywords

Examples

Programs

Python

Formula

A182105 Number of elements merged by bottom-up merge sort.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions