A296062 -id:A296062 - 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

A367076 Irregular triangle read by rows: T(n,k) (0 <= n, 0 <= k < 2^n). T(n,k) = -Sum_{i=0..k} A365968(n,i).

Original entry on oeis.org

0, 1, 0, 3, 4, 3, 0, 6, 10, 12, 12, 12, 10, 6, 0, 10, 18, 24, 28, 32, 34, 34, 32, 34, 34, 32, 28, 24, 18, 10, 0, 15, 28, 39, 48, 57, 64, 69, 72, 79, 84, 87, 88, 89, 88, 85, 80, 85, 88, 89, 88, 87, 84, 79, 72, 69, 64, 57, 48, 39, 28, 15, 0, 21, 40, 57, 72, 87

Offset: 0

John Tyler Rascoe, Nov 05 2023

			Triangle begins:
    k=0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
n=0:  0;
n=1:  1,  0;
n=2:  3,  4,  3,  0;
n=3:  6, 10, 12, 12, 12, 10,  6,  0;
n=4; 10, 18, 24, 28, 32, 34, 34, 32, 34, 34, 32, 28, 24, 18, 10,  0;

John Tyler Rascoe, Rows n = 0..12, flattened
Wikipedia, Blancmange curve.
Index entries for sequences related to binary expansion of n

Cf. A000217 (column k=0), A028552 (column k=1), A192021 (row sums).

Cf. A004074, A249071, A274575, A277914, A296062, A365968.

nmax=10; row[n_]:=Join[CoefficientList[Series[1/(1-x)*Sum[ i/(1+x^2^(i-1))*Product[1+x^2^j,{j,0,i-2}],{i,n}],{x,0,2^n-1}],x],{0}]; Array[row,6,0] (* Stefano Spezia, Dec 23 2023 *)

def row_gen(n):
    x = 0
    for k in range(2**n):
        b = bin(k)[2:].zfill(n)
        x += sum((-1)**(int(b[n-i])+1)*i for i in range(1,n+1))
        yield(-x)
def A367076_row_n(n): return(list(row_gen(n)))

T(n,k) = Sum_{i=0..n} abs(k + 1 - (2^i) * round((k+1)/2^i)) * i.

G.f. for n-th row: 1/(1-x) * Sum_{i=1..n} (i/(1+x^2^(i-1)) * Product_{j=0..i-2} 1 + x^2^j).

A307689 The number of rooted binary trees on n leaves with minimal Colless index.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 3, 4, 3, 3, 1, 1, 1, 4, 6, 10, 16, 21, 13, 11, 13, 21, 16, 10, 6, 4, 1, 1, 1, 5, 10, 20, 50, 82, 73, 66, 184, 411, 548, 351, 455, 326, 144, 67, 144, 326, 455, 351, 548, 411, 184, 66, 73, 82, 50, 20, 10, 5, 1, 1

Offset: 1

Mareike Fischer, Apr 22 2019

a(n) is the number of maximally balanced binary rooted trees with n leaves according to the Colless imbalance index. It is bounded above by sequence A299037.

			There are 13 trees with minimal Colless index and 23 leaves, i.e. a(23)=13.

Mareike Fischer, Table of n, a(n) for n = 1..512
Tomás M. Coronado and Francesc Rosselló, The minimum value of the Colless index arXiv:1903.11670 [q-bio.PE], 2019.
Mareike Fischer, Lina Herbst, and Kristina Wicke, Extremal properties of the Colless tree balance index for rooted binary trees, arXiv:1904.09771 [math.CO], 2019.
Tree Balance, Colless index

The sequence is bounded above by A299037.

The sequence of the number of trees with minimal Colless index is also linked to the values of the minimal Colless index as given by A296062.

(*QB[n] is just a support function -- the function that actually generates the sequence of the numbers of trees with minimal Colless index and n leaves is given by minCbasedonQB; see below*)
QB[n_] := Module[{k, n0, bin, l, m = {}, i, length, qb = {}, j},
  If[OddQ[n], k = 0,
   k = FactorInteger[n][[1]][[2]];
   ];
  n0 = n/(2^k);
  bin = IntegerDigits[n0, 2];
  length = Length[bin];
  For[i = Length[bin], i >= 1, i--,
   If[bin[[i]] != 0, PrependTo[m, length - i]];
   ];
  l = Length[m];
  If[l == 1, Return[{{n/2, n/2}}],
   AppendTo[
    qb, {2^k*(Sum[2^(m[[i]] - 1), {i, 1, l - 1}] + 1),
     2^k*(Sum[2^(m[[i]] - 1), {i, 1, l - 1}])}];
   For[j = 2, j <= l - 1, j++,
    If[m[[j]] > m[[j + 1]] + 1,
     AppendTo[
      qb, {2^k*(Sum[2^(m[[i]] - 1), {i, 1, j - 1}] + 2^m[[j]]),
       n - 2^k*(Sum[2^(m[[i]] - 1), {i, 1, j - 1}] + 2^m[[j]])}]];
    If[m[[j]] < m[[j - 1]] - 1,
     AppendTo[
      qb, {n - 2^k*Sum[2^(m[[i]] - 1), {i, 1, j - 1}],
       2^k*Sum[2^(m[[i]] - 1), {i, 1, j - 1}]}]];
    ];
   If[k >= 1, AppendTo[qb, {n/2, n/2}]];
   Return[qb];
   ];
  ]
minCbasedonQB[n_] := Module[{qb = QB[n], min = 0, i, na, nb},
  If[n == 1, Return[1],
   For[i = 1, i <= Length[qb], i++,
    na = qb[[i]][[1]]; nb = qb[[i]][[2]];
    If[na != nb, min = min + minCbasedonQB[na]*minCbasedonQB[nb],
     min = min + Binomial[minCbasedonQB[n/2] + 1, 2]];
    ];
   Return[min];
   ]
  ]

a(1)=1; a(n) = Sum_{(n_a,n_b): n_a+n_b=n, n_a > n_b, (n_a,n_b) in QB(n)}} ( a(n_a)* a(n_b)) +f(n), where f(n)=0 if n is odd} and f(n)= binomial(a(n/2)+1,2) if n is even; and where QB(n)={(n_a,n_b): n_a+n_b=n and such that there exists a tree T on n leaves with minimal Colless index and with leaf partitioning (n_a,n_b)} }.

A308430 Number of 0's minus number of 1's among the edge truncated binary representations of the first n prime numbers.

Original entry on oeis.org

0, 0, 1, 0, 0, 0, 3, 4, 3, 2, -1, 1, 3, 3, 1, 1, -1, -3, 0, 1, 4, 3, 4, 5, 8, 9, 8, 7, 6, 7, 2, 6, 10, 12, 14, 14, 14, 16, 16, 16, 16, 16, 12, 16, 18, 18, 18, 14, 14, 14, 14, 10, 10, 6, 13, 16, 19, 20, 23, 26, 27, 30, 31, 30, 31, 30, 31, 34, 33, 32, 35, 34, 31, 30, 27, 22, 25, 26, 29, 30, 31, 32, 29, 30, 27, 24, 27, 28, 27, 24, 23, 18, 15, 12, 9, 4, -1, 5, 9, 11

Offset: 1

Andrea Fornaciari, May 26 2019

By "edge truncated" we mean removing the first and last digit. For prime(3)=5 which has binary representation 101 edge truncating yields the string '0'. If there are 2 digits, then edge truncation yields the empty string ''. We count zero 1's and zero 0's in the empty string. The only cases of this are prime(1)=2 and prime(2)=3 which have binary representations 10 and 11.

Rémy Sigrist, Table of n, a(n) for n = 1..12251
Sean A. Irvine, Java program (github)
Jonas K. Sønsteby, Graph of 200 terms.
Jonas K. Sønsteby, Graph of 1000 terms.
Jonas K. Sønsteby, Graph of 5000 terms.
Jonas K. Sønsteby, Graph of 10000 terms.
Jonas K. Sønsteby, Graph of 100000 terms.

Cf. A004676, A095375, A014499, A177718, A296062.

s=0; forprime (p=2, 541, print1 (s += #binary(p\2)+1-2*hammingweight(p\2) ", ")) \\ Rémy Sigrist, Jul 13 2019

import gmpy2
def dec2bin(x):
    return str(bin(x))[2:]
def digitBalance(string):
    s = 0
    for char in string:
        if int(char) > 0:
            s -= 1
        else:
            s += 1
    return s
N = 100 # number of terms
seq = [0]
prime = 2
for i in range(N-1):
    prime = gmpy2.next_prime(prime)
    binary = dec2bin(prime)
    truncated = binary[1:-1]
    term = seq[-1] + digitBalance(truncated)
    seq.append(term)
print(seq) # Jonas K. Sønsteby, May 27 2019

def A308430list(b):
    L = []; s = 0
    for p in prime_range(2, b):
        q = (p//2).digits(2)
        s += 1 + len(q) - 2*sum(q)
        L.append(s)
    return L
print(A308430list(542)) # Peter Luschny, Jul 13 2019

a(n) = a(n-1) + bitlength(prime(n)2) - 2 * popcount(prime(n)_2) + 2, n > 1. - _Sean A. Irvine, May 27 2019

a(n) = Sum_{k=2..n} (A035100(k) - 2*A014499(k) + 2) = Sum_{k=2..n} (A070939(A000040(k)) - 2*A000120(A000040(k)) + 2). - Daniel Suteu, Jul 13 2019

A343754 a(n) = 0, and for any n > 0, a(n+1) = a(n) - A065363(n) + 1.

Original entry on oeis.org

0, 0, 1, 1, 0, 2, 3, 3, 4, 4, 3, 3, 2, 0, 3, 5, 6, 8, 9, 9, 10, 10, 9, 11, 12, 12, 13, 13, 12, 12, 11, 9, 10, 10, 9, 9, 8, 6, 5, 3, 0, 4, 7, 9, 12, 14, 15, 17, 18, 18, 21, 23, 24, 26, 27, 27, 28, 28, 27, 29, 30, 30, 31, 31, 30, 30, 29, 27, 30, 32, 33, 35, 36

Offset: 0

Rémy Sigrist, Apr 27 2021

This sequence has connections with A296062 and the Takagi (or blancmange) curve:
- for any real number x,
- let s(x) = min(frac(x), 1-frac(x)) (this is the building block of the Takagi curve),
- let t(x) = min(1/3, s(x)),
- let f(x) = Sum_{k >= 0} t(x * 3^k) / 3^k,
- the scatterplot of the sequence in the range A003462(k)..A003462(k+1)
  approaches the curve x -> f(x)*3^k for x in the range 0..1.

Rémy Sigrist, Table of n, a(n) for n = 0..9841
Rémy Sigrist, Scatterplot of the sequence for n = 0..A003462(11)
Rémy Sigrist, Representation of f in the range 0..1
Rémy Sigrist, Successive approximations of f
Wikipedia, Blancmange curve

Cf. A005823, A065363, A174574, A296062.

s=0; for (n=1, 73, print1 (s", "); m=n; while (m>1, s-=d=centerlift(Mod(m, 3)); m=(m-d)\3))

a(n) = n - A174574(n).
a(n) >= 0 with equality iff n belongs to A003462.
a(n) <= n/2 with equality iff n belongs to A005823.

cp's OEIS Frontend

A325942 Positions of records in A296062.

Views

Author

Keywords

Links

Crossrefs

A325944 Least k such that A296062(k) = n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

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

A367076 Irregular triangle read by rows: T(n,k) (0 <= n, 0 <= k < 2^n). T(n,k) = -Sum_{i=0..k} A365968(n,i).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A307689 The number of rooted binary trees on n leaves with minimal Colless index.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A308430 Number of 0's minus number of 1's among the edge truncated binary representations of the first n prime numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Python

Sage

Formula

A343754 a(n) = 0, and for any n > 0, a(n+1) = a(n) - A065363(n) + 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI