A269735 -id:A269735 - cp's OEIS frontend

A145037 Number of 1's minus number of 0's in the binary representation of n.

0, 1, 0, 2, -1, 1, 1, 3, -2, 0, 0, 2, 0, 2, 2, 4, -3, -1, -1, 1, -1, 1, 1, 3, -1, 1, 1, 3, 1, 3, 3, 5, -4, -2, -2, 0, -2, 0, 0, 2, -2, 0, 0, 2, 0, 2, 2, 4, -2, 0, 0, 2, 0, 2, 2, 4, 0, 2, 2, 4, 2, 4, 4, 6, -5, -3, -3, -1, -3, -1, -1, 1, -3, -1, -1, 1, -1, 1, 1, 3, -3, -1, -1, 1, -1, 1, 1, 3, -1, 1, 1

Offset: 0

Reikku Kulon, Sep 30 2008

Column 2 of A144912 (which begins at n = 2).

Zeros in that column correspond to A031443.

			From _Michel Marcus_, Feb 12 2022: (Start)
Viewed as an irregular triangle:
   0;
   1;
   0,  2;
  -1,  1,  1, 3;
  -2,  0,  0, 2,  0, 2, 2, 4;
  -3, -1, -1, 1, -1, 1, 1, 3, -1, 1, 1, 3, 1, 3, 3, 5;
  ... (End)

Table of n, a(n) for n = 0..2^14

Cf. A037861 (negated), A031443 (indices of 0's), A144912, A000120.
Cf. A269735 (first differences), A268289 (partial sums).
Column k=1 of A360099.

a145037 0 = 0
a145037 n = a145037 n' + 2*m - 1 where (n', m) = divMod n 2
-- Reinhard Zumkeller, Jun 16 2011

a:= n-> add(2*i-1, i=Bits[Split](n)):
seq(a(n), n=0..90);  # Alois P. Heinz, Jan 18 2022

Join[{0}, Table[Count[#, 1] - Count[#, 0] &[IntegerDigits[n, 2]], {n, 1, 90}]] (* Robert P. P. McKone, Feb 12 2022 *)

A145037(n)=hammingweight(n)*2-logint(n<<1+!n,2) \\ M. F. Hasler, Mar 08 2018

result = [0]
for n in range (1, 2**14 + 1):
    result.append(bin(n)[2:].count("1") - bin(n)[2:].count("0"))
print(result[0:129]) # Karl-Heinz Hofmann, Jan 18 2022

def a(n): return (n.bit_count()<<1) - n.bit_length()
print([a(n) for n in range(1, 2**14+1)]) # Michael S. Branicky, May 14 2024
(C#)
int A145037(int n)  {
    int result = 0;
    while(n > 0)  {
        result += 2 * (n % 2) - 1;
        n /= 2;
    }
    return result;
} \\ Frank Hollstein, Dec 08 2022

a(n) = -A037861(n) for n >= 1.
a(n) = Sum_{i=1..k} (2*b[i] - 1) where b is the binary expansion of n and k is the number of bits in this binary expansion. - Michel Marcus, Jun 28 2021
From Aayush Soni Feb 12 2022: (Start)
Upper bound: a(n) <= floor(log_2(n+1)).
Lower bound: For n > 0, a(n) >= 1 - floor(log_2(n)).
If n is even, a(2^n) to a(2^(n+1)-1) inclusive are all odd and vice versa. (End)

Renamed (using a Mar 08 2018 comment from M. F. Hasler) and edited by Jon E. Schoenfield, Jun 29 2021

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

Original entry on oeis.org

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

A187038 Row sums of number triangle A187037.

Original entry on oeis.org

1, 2, 3, 2, 0, 2, 5, 2, 0, 2, 2, 2, 0, 2, 7, 2, 0, 2, 2, 2, 0, 2, 4, 2, 0, 2, 2, 2, 0, 2, 9, 2, 0, 2, 2, 2, 0, 2, 4, 2, 0, 2, 2, 2, 0, 2, 6, 2, 0, 2, 2, 2, 0, 2, 4, 2, 0, 2, 2, 2, 0, 2, 11, 2, 0, 2, 2, 2, 0, 2, 4, 2, 0, 2, 2, 2, 0, 2, 6, 2, 0, 2, 2, 2, 0, 2, 4, 2, 0, 2, 2, 2, 0, 2, 8, 2, 0, 2, 2, 2, 0, 2, 4, 2, 0, 2

Offset: 0

Paul Barry, Mar 08 2011

nonn

Apparently, apart from signs, same as A269735 (with a shift). If so, the g.f. for this sequence is obtained from that for A269735 by replacing x by -x. - N. J. A. Sloane, Mar 11 2016

For construction, see Barry, 2011. Although the paper doesn't treat especially this sequence, it outlines a general method for creating such sequences. - Antti Karttunen, Sep 30 2018

Antti Karttunen, Table of n, a(n) for n = 0..1025
P. Barry, Invariant number triangles, eigentriangles and Somos-4 sequences, arXiv:1107.5490 [math.CO], 2011.

Cf. A187034, A187036, A187037, A269735.

up_to = 128;
A187034aux(n,k) = if(k>n,0,if(n<=2*k, (-1)^(n-k), 0));
A187034downshifted_and_negated(n,k) = if(k==n,1,-A187034aux(n-1,k));
A187038list(up_to) = { my(m1=matrix(up_to,up_to,n,k,A187034downshifted_and_negated(n-1,k-1)), m2 = matsolve(m1,matid(up_to)), v = vector(up_to)); for(n=1,up_to,v[n] = vecsum(m2[n,])); (v); };
write_A187036_and_A187038list(up_to) = { my(m1=matrix(up_to,up_to,n,k,A187034downshifted_and_negated(n-1,k-1)), m2 = matsolve(m1,matid(up_to)), v187036 = (m2[,1]~), v187038 = vector(up_to,j,vecsum(m2[j,]))); for(n=1,up_to,write("b187036.txt", n-1, " ", v187036[n]); write("b187038.txt", n-1, " ", v187038[n])); }; \\ For computing both at the same time
v187038 = A187038list(1+up_to);
A187038(n) = v187038[1+n]; \\ Antti Karttunen, Sep 29 2018

More terms from Antti Karttunen, Sep 29 2018

cp's OEIS Frontend

A145037 Number of 1's minus number of 0's in the binary representation of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Python

Formula

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

A187038 Row sums of number triangle A187037.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Extensions