A096351 -id:A096351 - cp's OEIS frontend

A268289 a(0)=0; thereafter a(n) = a(n-1) - A037861(n).

0, 1, 1, 3, 2, 3, 4, 7, 5, 5, 5, 7, 7, 9, 11, 15, 12, 11, 10, 11, 10, 11, 12, 15, 14, 15, 16, 19, 20, 23, 26, 31, 27, 25, 23, 23, 21, 21, 21, 23, 21, 21, 21, 23, 23, 25, 27, 31, 29, 29, 29, 31, 31, 33, 35, 39, 39, 41, 43, 47, 49

Offset: 0

Mark Moore, Jan 30 2016

The graph of this sequence is related to the Takagi (blancmange) curve: see Lagarias (2012), Section 9, especially Theorem 9.1. [Corrected by Laura Monroe, Oct 21 2020]
Theorem: a(n) is the cardinality of the set { 1<= m <= n, ((n-m) mod 2^floor(log_2(m)+1)) < 2^floor(log_2(m)) }. See links.
From Laura Monroe, Jun 11 2020: (Start)
Consider a full balanced binary tree with n unlabeled leaves such that for each internal node, the number of leaf descendants of the two children differs by at most 1. Call a tree with this even distribution of leaves "pairwise".
Apply labels to the internal nodes, where an internal node is labeled S if its two children have the same number of leaf descendants, and D if its two children have a different number of leaf descendants, and call this an SD-tree. (For a pairwise tree, this is equivalent to saying that a node is an S-node iff it has an even number of leaf descendants.)
a(n) is then the number of S-nodes on a pairwise SD-tree with n+1 leaves.
This is proved in Props. 17 and 18 of the Monroe et al. article in the links.
One example of such a tree is the summation tree generated by a pairwise summation on n+1 summands (see example below). Another example is the tree representing a neutral single-elimination tournament on n+1 teams, as in A096351.
(End)
From Laura Monroe, Oct 23 2020: (Start)
Subtracting a(n) from n gives a sequence of dilations of increasing length on the dyadic rational points of the Takagi function. The number of points in each dilation is 2^k and the scale of each dilation in both the x and y directions is 2^k, where k = floor(log_2(n+1)).
2^(a(n)) is the number of tree automorphisms on the pairwise (i.e., divide-and-conquer) tree with n+1 leaves.
(End)

			From _Laura Monroe_, Jun 11 2020: (Start)
For n=2, the pairwise summation on 2+1=3 summands takes the form ((a+b)+c). The corresponding summation tree and SD-tree look like:
       +            D
      / \          / \
     +   c        S   c
    / \          / \
   a   b        a   b
and exactly 1 internal node has an even number of leaf descendants, hence is an S-node.
For n=3, the pairwise summation on 3+1=4 summands takes the form ((a+b)+(c+d)). The corresponding summation tree and SD-tree look like:
       +            S
      / \          / \
     +   +        S   S
    /|   |\      /|   |\
   a b   c d    a b   c d
and exactly 3 internal nodes have an even number of leaf descendants, hence are S-nodes.
(End)

Laura Monroe, Table of n, a(n) for n = 0..16383 (first 10000 terms from N. J. A. Sloane)
Thomas Baruchel, Flattening Karatsuba's recursion tree into a single summation, arXiv:1902.08982 [math.NT], 2019. See (5) conjecture of theorem.
Thomas Baruchel, Properties of the cumulated deficient binary digit sum, arXiv:1908.02250 [math.NT], 2019. See 2.4 proof of theorem.
Thomas Baruchel, Flattening Karatsuba's Recursion Tree into a Single Summation, SN Computer Science (2020) Vol. 1, Article No. 48.
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.
Jeffrey C. Lagarias, The Takagi function and its properties, arXiv:1112.4205 [math.CA], 2011-2012.
Jeffrey C. Lagarias, The Takagi function and its properties, In Functions in number theory and their probabilistic aspects, 153--189, RIMS Kôkyûroku Bessatsu, B34, Res. Inst. Math. Sci. (RIMS), Kyoto, 2012. MR3014845.
Laura Monroe, A Few Identities of the Takagi Function on Dyadic Rationals, arXiv:2111.05996 [math.CO], 2021.
Laura Monroe, Takagi Function Identities on Dyadic Rationals, J. Int. Seq (2024) Vol. 27, Art. 24.2.7.
Laura Monroe and Vanessa Job, Computationally Inequivalent Summations and Their Parenthetic Forms, arXiv:2005.05387 [cs.DM], 2020. See Prop. 26, the alternate proof.

Partial sums of A145037.

Cf. A000120, A000788, A023416, A037861, A096351, A181132, A269735, A233271, A296062.

int a(int n)   {
    int m=n+1;
    int result=0;
    int i=0;
    while (n) {
        int ith_bit_set = m&(1<>= 1;
    }
   return result;
}
/* Laura Monroe, Jun 17 2020 */

function A268289List(len)
    A = zeros(Int, len)
    for n in 1:len-1
        a, b, c = n, n & 1, 1
        while (a >>= 1) != 0
            b += a & 1
            c += 1
        end
        A[n+1] = A[n] + <<(b, 1) - c
    end
    A
end; println(A268289List(61)) # Peter Luschny, Jun 22 2020

a000120 := proc(n) add(i, i=convert(n, base, 2)) end:
a023416 := proc(n) if n = 0 then 1; else add(1-e, e=convert(n, base, 2)) ; end if; end proc:
a268289:=proc(n) option remember; global a000120, a023416;
if n=0 then 0 else a268289(n-1)+a000120(n)-a023416(n); fi; end;
[seq(a268289(n),n=0..132)];
# N. J. A. Sloane, Mar 07 2016
# second Maple program:
a:= proc(n) option remember; `if`(n<0, 0,
      a(n-1)+add(2*i-1, i=Bits[Split](n)))
    end:
seq(a(n), n=0..60);  # Alois P. Heinz, Jan 18 2022

Join[{0}, Table[DigitCount[n, 2, 1] - DigitCount[n, 2, 0], {n, 1, 100}] // Accumulate] (* Jean-François Alcover, Oct 24 2016 *)

a(n) = if (n==0, 0, if (n%2, 2*a((n-1)/2)+1, a(n/2) + a(n/2-1))); \\ Michel Marcus, Jun 16 2020

a(n) = my(v=binary(n+1),s=-1); for(i=1,#v, v[i]=if(v[i],s++,s--;1)); fromdigits(v,2); \\ Kevin Ryde, Jun 16 2020

def A268289(n): return (sum(i.bit_count() for i in range(1,n+1))<<1)-1-(n+1)*(m:=(n+1).bit_length())+(1<Chai Wah Wu, Mar 01 2023

def A268289(n): return sum((n+1)%m if (n+1)&(m:=1<Chai Wah Wu, Nov 11 2024

From N. J. A. Sloane, Mar 11 2016: (Start)
a(0)=0; for n > 0, a(n) = a(n-1) + A000120(n) - A023416(n) = A000788(n) - A181132(n).
a(0)=0; thereafter a(2*n) = a(n) + a(n-1), a(2*n+1) = 2*a(n) + 1.
G.f.: (1/(1-x)^2) * Sum_{k >= 0} x^(2^k)*(1-x^(2^k))/(1+x^(2^k)).
a(2^k-1) = 2^k-1, a(3*2^k-1) = 2^(k+1)-1, a(5*2^k-1) = 3*2^k-1, etc.
(End)
From Laura Monroe, Jun 11 2020: (Start)
a(n-1) = Sum_{i=0..floor(log_2(n))} (((floor(n/(2^i))+1) mod 2)*(2^i)+(-1)^((floor(n/(2^i))+1) mod 2)*(n mod (2^i))), for n>=1.
This is an explicit formula for this sequence, and is O(log(n)). This formula is proven in Prop. 18, in the Monroe et al. reference in the links. (End)
From Laura Monroe, Oct 23 2020: (Start)
a(n) = n - A296062(n).
a(n+1) = (n+1) - (2^k)*tau(x/(2^k)), where tau is the Takagi function and n+1 = (2^k)+x with x < 2^k. (End)

Simplified definition following a suggestion from Michel Marcus. Corrected start, added more terms. - N. J. A. Sloane, Mar 07 2016

A335833 Triangle read by rows. T(n,k) is the number of full binary trees with n leaves and with k internal nodes whose left and right children have the same number of leaf descendants, where n > 0 and 0 <= k < n.

Original entry on oeis.org

1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 2, 2, 1, 0, 0, 1, 4, 3, 3, 0, 0, 0, 1, 6, 7, 6, 3, 0, 1, 0, 1, 9, 14, 13, 8, 1, 1, 0, 0, 1, 12, 27, 28, 23, 8, 3, 1, 0, 0, 1, 16, 49, 58, 54, 25, 8, 3, 0, 0, 0, 1, 20, 82, 119, 125, 82, 34, 15, 2, 1, 0

Offset: 1

Laura Monroe, Jun 25 2020

Consider a full binary tree with n unlabeled leaves, such that for every internal node, the number of leaf descendants of the left child is greater than or equal to the number of leaf descendants of the right child. Two such trees are considered isomorphic if one may be obtained from the other by some series of transpositions of left and right children. Label an internal nodes S if its two children have the same number of leaf descendants, and D if its two children have a different number of leaf descendants, and call this an SD-tree. T(n,k) is then the number of distinct trees having n > 0 leaves and 0 <= k < n S-nodes, read by rows (Monroe et al., proposition 38).
Binary operations that are commutative and non-associative map to this type of tree. One example of this kind of operation is floating-point summation on n summands on a machine adhering to IEEE 754 arithmetic standards. Another example is a single-elimination tournament on n teams (A096351), which always has A268289(n-1) S-nodes.
Column 1 gives A000012 (Monroe et al., proposition 11 and remark 42).
Column 2 gives A002620 (Monroe et al., proposition 18).
Row sums give A000992 (Monroe et al., proposition 36 and remark 42).
T(n,n-1) is 1 if n = 2^k and is 0 otherwise. This is true because there are exactly n-1 internal nodes on a binary tree with n leaves, and the only way for all of these to be S-nodes is if the tree is the unique perfect tree with 2^k leaves.
T(n,1) is the first non-0 entry in row n, when n>1. T(n,A011371(n)) is the last non-0 entry in row n. (Monroe et al., propositions 27 and 34)
The number of unique leaf-labeled full binary trees of isomorphic parenthetic form with exactly k >= 1 S-nodes is n!/(2^k) (Monroe et al., corollary 4). There are then T(n,k)*n!/(2^k) not necessarily isomorphic unique leaf-labeled full binary trees having exactly k nodes. For example, serial summation, where the parenthesization is in summand order, as in (...(((a+b)+c)+d)+...), always has exactly 1 S-node, so there are n!/2 possible serial summations (Monroe et al., lemmas 8 and 9, corollary 10, and proposition 11).
The comments above that suggest that this sequence enumerates binary trees up to transpositions of left and right children appear to be incorrect. This sequence rather enumerates those trees as specified in the opening paragraph: for every internal node, the number of leaf descendants of the left child is greater than or equal to the number of leaf descendants of the right child. This is the difference between A000992 which is the row sums of this sequence and A001190. The two diverge for n >= 8. The remark that commutative binary operations map to this type of tree is, therefore, also incorrect. - Andrew Howroyd, Mar 25 2023

			The table for T(n,k) begins:
  n\k 0   1   2   3    4    5    6    7    8   9  10  11  12  13  14  15
   1  1
   2  0   1
   3  0   1   0
   4  0   1   0   1
   5  0   1   1   1    0
   6  0   1   2   2    1    0
   7  0   1   4   3    3    0    0
   8  0   1   6   7    6    3    0    1
   9  0   1   9  14   13    8    1    1    0
  10  0   1  12  27   28   23    8    3    1   0
  11  0   1  16  49   58   54   25    8    3   0   0
  12  0   1  20  82  119  125   82   34   15   2   1   0
  13  0   1  25 132  237  270  213   99   42   8   3   0   0
  14  0   1  30 199  449  578  542  322  151  51  11   3   0   0
  15  0   1  36 294  821 1190 1255  867  440 173  39  15   0   0   0
  16  0   1  42 414 1419 2394 2841 2338 1388 656 215  79  18   7   0   1
  ...
The complete set of non-isomorphic 4-leaf SD-trees is:
        D            S
       / \          / \
      D   *        S   S
     / \          /|   |\
    S   *        * *   * *
   / \
  *   *
T(6,2) = 2 gives the first example of a set of parameters n and k that has more than one non-isomorphic SD-tree. The complete set of non-isomorphic 6-leaf 2-S-node SD-trees is:
          D                 D
         / \               / \
        D   S             D   *
       / \  |\           / \
      D   * * *         D   S
     / \               / \  |\
    S   *             S   * * *
   / \               / \
  *   *             *   *
From _Andrew Howroyd_, Apr 12 2023: (Start)
When n = 8 there are two trees, illustrated below, which are isomorphic (up to exchange of left and right children), but are counted separately by this sequence:
             S                     S
           /   \                 /   \
          D     S              S      D
        / |     | \          / |      | \
       D  *     S  S        S  S      D  *
     /  \      /|  |\      /|  |\     | \
    S    *    * *  * *    * *  * *    S  *
   / \                               / \
  *   *                             *   *
(End)

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 rows).
Laura Monroe, A Class of Trees Having Near-Best Balance, arXiv:2108.11496 [cs.DM], 2021.
Laura Monroe and Vanessa Job, Computationally Inequivalent Summations and Their Parenthetic Forms, arXiv:2005.05387 [cs.DM], 2020.

Cf. A000012, A000992, A002620, A011371, A096351, A268289.

using Memoize
@memoize function T(n, k)
    k > n-1 && return 0
    (n==1) && (k==0) && return 1
    t, h = 0, n>>1
    for j in 1:h-1, i in 0:k
            t += T(j, i)*T(n-j, k-i)
    end
    if n&1 > 0
        for i in 0:k
            t += T(h, i)*T(h+1, k-i)
        end
    else
        for i in 0:k
            t += T(h, i)*T(h, k-i-1)
        end
    end
    t
end
for n in 1:16
    [T(n,k) for k in 0:n-1] |> println
end # Peter Luschny, Jun 26 2020

T(n)={my(v=vector(n)); v[1] = 1; for(n=2, n, v[n] = (polcoef(Ser(v[1..n])^2, n-2) + if(n%2==0, (2*y-1)*v[n/2]^2))/2); vector(#v, n, Vecrev(v[n], n))}
{ my(A=T(12)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Mar 25 2023

T(n,k) = 0, if k >= n. T(n,k) = 1, if n = 1 and k = 0.
T(n,k) = Sum_{j=1..floor((n-1)/2)} Sum_{i=0..k} T(j,i)*T(n-j,k-i), if n is odd and > 1.
T(n,k) = Sum_{j=1..floor((n-1)/2)} Sum_{i=0..k} T(j,i)*T(n-j,k-i) + Sum_{i=0..k-1} T(n/2,i)*T(n/2,k-1-i), if n is even.

cp's OEIS Frontend

A268289 a(0)=0; thereafter a(n) = a(n-1) - A037861(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Julia

Maple

Mathematica

PARI

PARI

Python

Python

Formula

Extensions

A335833 Triangle read by rows. T(n,k) is the number of full binary trees with n leaves and with k internal nodes whose left and right children have the same number of leaf descendants, where n > 0 and 0 <= k < n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Julia

PARI

Formula