A268289 -id:A268289 - cp's OEIS frontend

A037861 (Number of 0's) - (number of 1's) in the base-2 representation of n.

1, -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

Offset: 0

Clark Kimberling

-Sum_{n>=1} a(n)/((2*n)*(2*n+1)) = the "alternating Euler constant" log(4/Pi) = 0.24156... - (see A094640 and Sondow 2005, 2010).

a(A072600(n)) < 0; a(A072601(n)) <= 0; a(A031443(n)) = 0; a(A072602(n)) >= 0; a(A072603(n)) > 0; a(A031444(n)) = 1; a(A031448(n)) = -1; abs(a(A089648(n))) <= 1. - Reinhard Zumkeller, Feb 07 2015

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Jonathan Sondow, Double integrals for Euler's constant and ln(4/Pi) and an analog of Hadjicostas's formula, arXiv:math/0211148 [math.CA], 2002-2004; Amer. Math. Monthly 112 (2005), 61-65.
Jonathan Sondow, New Vacca-Type Rational Series for Euler's Constant and Its "Alternating" Analog ln(4/Pi), arXiv:math/0508042 [math.NT], 2005; Additive Number Theory, Festschrift In Honor of the Sixtieth Birthday of Melvyn B. Nathanson (D. Chudnovsky and G. Chudnovsky, eds.), Springer, 2010, pp. 331-340.
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions, 2004.
Ralf Stephan, Table of generating functions (ps file).
Ralf Stephan, Table of generating functions (pdf file).
Index entries for sequences related to binary expansion of n

Cf. A031443 for n when a(n)=0, A053738 for n when a(n) odd, A053754 for n when a(n) even, A030300 for a(n+1) mod 2.
Cf. A066879, A094640, A110625, A145037.
Cf. A072600, A072601, A072602, A072603, A031444, A031448, A089648.
See A268289 for a recurrence based on this sequence.

a037861 n = a023416 n - a000120 n  -- Reinhard Zumkeller, Aug 01 2013

A037861:= proc(n) local L;
     L:= convert(n,base,2);
     numboccur(0,L) - numboccur(1,L)
end proc:
map(A037861, [$0..100]); # Robert Israel, Mar 08 2016

Table[Count[ IntegerDigits[n, 2], 0] - Count[IntegerDigits[n, 2], 1], {n, 0, 75}]

a(n) = if (n==0, 1, 1 + logint(n, 2) - 2*hammingweight(n)); \\ Michel Marcus, May 15 2020 and Jun 16 2020

def A037861(n):
    return 2*format(n,'b').count('0')-len(format(n,'b')) # Chai Wah Wu, Mar 07 2016

From Henry Bottomley, Oct 27 2000: (Start)
a(n) = A023416(n) - A000120(n) = A029837(n) - 2*A000120(n) = 2*A023416(n) - A029837(n).
a(2*n) = a(n) + 1; a(2*n + 1) = a(2*n) - 2 = a(n) - 1. (End)
G.f. satisfies A(x) = (1 + x)*A(x^2) - x*(2 + x)/(1 + x). - Franklin T. Adams-Watters, Dec 26 2006
a(n) = b(n) for n > 0 with b(0) = 0 and b(n) = b(floor(n/2)) + (-1)^(n mod 2). - Reinhard Zumkeller, Dec 31 2007
G.f.: 1 + (1/(1 - x))*Sum_{k>=0} x^(2^k)*(x^(2^k) - 1)/(1 + x^(2^k)). - Ilya Gutkovskiy, Apr 07 2018

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

Original entry on oeis.org

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

A296062 Base-2 logarithm of the number of different shapes of balanced binary trees with n nodes (A110316).

Original entry on oeis.org

0, 0, 1, 0, 2, 2, 2, 0, 3, 4, 5, 4, 5, 4, 3, 0, 4, 6, 8, 8, 10, 10, 10, 8, 10, 10, 10, 8, 8, 6, 4, 0, 5, 8, 11, 12, 15, 16, 17, 16, 19, 20, 21, 20, 21, 20, 19, 16, 19, 20, 21, 20, 21, 20, 19, 16, 17, 16, 15, 12, 11, 8, 5, 0, 6, 10, 14, 16, 20, 22, 24, 24, 28

Offset: 0

Katarzyna Matylla, Dec 04 2017

Since terms of A110316 are always powers of 2, it seems natural to have a sequence of the exponents too. Also, it conveys the same information as A110316 but is shorter and more readable.
Also, sum of absolute distances from (n+1) to the nearest multiple of 2^k for all 2^k < n+1. - Ivan Neretin, Jul 03 2018
Also, the minimum cost of connecting n+1 nodes when the cost of joining two connected components is the absolute difference of their sizes. In particular, connecting two equal sized components has zero cost. For example, in the case of n=4 there are 5 nodes. Connecting nodes 1 and 2 costs zero, connecting nodes 3 and 4 costs zero, then connecting {5} to {3,4} costs 1 and finally connecting {1,2} to {3,4,5} costs 1 giving a total cost of 2. Because this solution is optimal a(4) = 2. - Qingnian Su, Nov 03 2018
Also, the minimum Colless index of a rooted bifurcating tree with n leaves. - Francesc Rosselló, Apr 08 2019
Also, dilations of the Takagi function restricted to dyadic rationals in [0,1]. The number of points of a(n) 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)). See Allaart et. al (2012), Equation 4.7, attributed to Kruppel (2007). Also see Coronado et.al (2020), Corollary 4. - Laura Monroe, Oct 23 2020

Hsien-Kuei Hwang, S, Janson, T.-H. Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968, 2022.

Alois P. Heinz, Table of n, a(n) for n = 0..16383 (first 10001 terms from Robert Israel)
Pieter C. Allaart and Kiko Kawamura, The Takagi Function: a Survey, Real Analysis Exchange, pp. 1-54, Vol. 37, No. 1, 2011-12.
T. M. Coronado and F. Rosselló, The minimum value of the Colless index, arXiv:1903.11670 [q-bio.PE], 2019. - _Francesc Rosselló_, Apr 08 2019
T. M. Coronado et. al, On the minimum value of the Colless index and the bifurcating trees that achieve it, Journal of Mathematical Biology, pp. 1993-2054, Vol. 80, 2020.
M. Kruppel, On the extrema and the improper derivatives of Takagi’s continuous nowhere differentiable function, pp. 41-59, Rostock. Math. Kolloq.,Vol. 62, 2007.
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.
Wikipedia, Blancmange curve

Cf. A007814, A110316, A268289.

a:= proc(n) option remember; local r; `if`(n<2, 0,
      `if`(irem(n, 2, 'r')=0, 1+a(r)+a(r-1), a(r)*2))
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Dec 04 2017

Fold[Append[#1, If[EvenQ@ #2, #1[[#2/2 + 1]] + #1[[#2/2]] + 1, 2 #1[[(#2 - 1)/2 + 1]]]] &, {0, 0}, Range[2, 72]] (* Michael De Vlieger, Dec 04 2017 *)

seq(n)={my(v=vector(n)); for(m=2, #v, v[m]=vecmin(vector(m\2, i, v[i] + v[m-i] + m-2*i))); v} \\ Andrew Howroyd, Nov 04 2018

seq(n)={my(v=vector(n)); for(n=1, n-1, v[n+1]=if(n%2, 2*v[(n+1)/2], v[n/2] + v[n/2+1] + 1)); v} \\ Andrew Howroyd, Nov 04 2018

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

a(0) = a(1) = 0; a(2*n) = a(n) + a(n-1) + 1; a(2*n+1) = 2*a(n).
a(n) = A007814(A110316(n)).
2^a(n) = A110316(n).
G.f. g(x) satisfies g(x) = (1+x)^2*g(x^2) + x^2/(1-x^2). - Robert Israel, Dec 04 2017
a(n) = min_{i=1..floor((n+1)/2)} n + 1 - 2*i + a(i-1) + a(n-i). - Qingnian Su and Andrew Howroyd, Nov 04 2018
a(n) = Sum_{j=2..k} (m_1-m_j-2*(j-2))*2^m_j where m_1 > ... > m_k are the exponents in the binary expansion of n. - Francesc Rosselló, Apr 08 2019
From Laura Monroe, Oct 23 2020: (Start)
a(n+1) = (2^k)*tau(x/(2^k)), where tau is the Takagi function, and n = (2^k) + x with x < 2^k.
a(n) = n - A268289(n). (End)

A181132 a(0)=0; thereafter a(n) = total number of 0's in binary expansions of 1, ..., n.

Original entry on oeis.org

0, 0, 1, 1, 3, 4, 5, 5, 8, 10, 12, 13, 15, 16, 17, 17, 21, 24, 27, 29, 32, 34, 36, 37, 40, 42, 44, 45, 47, 48, 49, 49, 54, 58, 62, 65, 69, 72, 75, 77, 81, 84, 87, 89, 92, 94, 96, 97, 101, 104, 107, 109, 112, 114, 116, 117, 120, 122, 124, 125, 127, 128, 129, 129, 135, 140, 145

Offset: 0

Dylan Hamilton, Oct 05 2010

The graph of this sequence is a version of the Takagi curve: see Lagarias (2012), Section 9, especially Theorem 9.1. - N. J. A. Sloane, Mar 12 2016

Harvey P. Dale, Table of n, a(n) for n = 0..1000
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.

Cf. A000120, A023416, A000788, A059015, A268289.

[ n eq 1 select 0 else Self(n-1)+(#B-&+B) where B is Intseq(n, 2): n in [1..70] ]; // Klaus Brockhaus, Oct 08 2010

a:= proc(n) option remember; `if`(n=0, 0, a(n-1)+add(1-i, i=Bits[Split](n))) end:
seq(a(n), n=0..66);  # Alois P. Heinz, Nov 12 2024

Accumulate[Count[IntegerDigits[#,2],0]&/@Range[70]] (* Harvey P. Dale, May 16 2012 *)
Join[{0},Accumulate[DigitCount[Range[70],2,0]]] (* Harvey P. Dale, Jun 09 2016 *)

a(n)=my(m=logint(n,2)); 1 + (m+1)*(n+1) - 2^(m+1) + sum(j=1,m+1,my(t=floor(n/2^j + 1/2));(n>>j)*(2*n + 2 - (1 + (n>>j))<Charles R Greathouse IV, Dec 14 2015

def A181132(n): return 1+(n+1)*(m:=(n+1).bit_length())-(1<Chai Wah Wu, Mar 02 2023

def A181132(n): return 1+(n+1)*((t:=(n+1).bit_length())-n.bit_count())-(1<>j)-(r if n<<1>=m*(r:=k<<1|1) else 0)) for j in range(1,n.bit_length()+1))>>1)  # Chai Wah Wu, Nov 11 2024

microsoft word macro:
Sub concatcount() Dim base As Integer Dim digit As Integer Dim counter As Integer Dim standin As Integer Dim max As Integer Let base = 2 Let digit = 0 Let max = 100 Let counter = 0 For n = 1 To max Let standin = n Do While standin > 0 If standin Mod base = digit Then Let counter = counter + 1 Let standin = standin - (standin Mod base) If standin > 0 Then Let standin = standin / base Loop Selection.TypeText Text:=Str(counter) Next n End Sub

a(n) = A059015(n)-1. - Klaus Brockhaus, Oct 08 2010
From N. J. A. Sloane, Mar 10 2016: (Start)
a(0)=0; thereafter a(2n) = a(n)+a(n-1)+n, a(2n+1) = 2a(n)+n.
G.f.: (1/(1-x)^2) * Sum_{k >= 0} x^(2^(k+1))/(1+x^(2^k)). (End)

a(0)=0 added by N. J. A. Sloane, Mar 10 2016 (simplifies the recurrence, makes entry consistent with A059015 and other closely related sequences).

A269735 G.f.: Sum_{k >= 0} x^(2^k)*(1-x^(2^k))/(1+x^(2^k)).

Original entry on oeis.org

0, 1, -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

Offset: 0

N. J. A. Sloane, Mar 11 2016

sign

Second differences of A268289.

Antti Karttunen, Table of n, a(n) for n = 0..65537

Cf. A268289, A187038.

t7:=add(x^(2^k)*(1-x^(2^k))/(1+x^(2^k)),k=0..12);
t8:=series(t7,x,256);
# second Maple program:
b:= proc(n) option remember; `if`(n<0, 0,
      add(2*i-1, i=Bits[Split](n)))
    end:
a:= n-> b(n)-b(n-1):
seq(a(n), n=0..92);  # Alois P. Heinz, Jan 18 2022

Join[{0, 0}, Table[DigitCount[n, 2, 1] - DigitCount[n, 2, 0], {n, 1, 100}]] // Differences (* Jean-François Alcover, Jun 27 2022 *)

up_to = 1024;
A268289list(up_to) =  { my(v=vector(up_to), s = 1); v[1] = s; for(n=2, up_to, s += (2*hammingweight(n) - #binary(n)); v[n] = s); (v); };
v268289 = A268289list(up_to+1);
A268289(n) = if(!n,n,v268289[n]);
almost_firstdiffs_of_A268289(n) = if(!n,1,v268289[n+1]-v268289[n]);
A269735(n) = if(n<=1,n,almost_firstdiffs_of_A268289(n-1)-almost_firstdiffs_of_A268289(n-2)); \\ Antti Karttunen, Sep 30 2018

up_to_k = 16;
up_to = 1+(2^up_to_k);
x='x+O('x^(up_to+1));
v269735 = Vec(sum(k=0,up_to_k,x^(2^k)*(1-x^(2^k))/(1+x^(2^k))));
A269735(n) = if(!n,n,v269735[n]); \\ Antti Karttunen, Oct 01 2018

A301336 a(n) = total number of 1's minus total number of 0's in binary expansions of 0, ..., n.

Original entry on oeis.org

-1, 0, 0, 2, 1, 2, 3, 6, 4, 4, 4, 6, 6, 8, 10, 14, 11, 10, 9, 10, 9, 10, 11, 14, 13, 14, 15, 18, 19, 22, 25, 30, 26, 24, 22, 22, 20, 20, 20, 22, 20, 20, 20, 22, 22, 24, 26, 30, 28, 28, 28, 30, 30, 32, 34, 38, 38, 40, 42, 46, 48, 52, 56, 62, 57, 54, 51, 50, 47, 46, 45, 46, 43, 42, 41, 42

Offset: 0

Ilya Gutkovskiy, Mar 28 2018

			+---+-----+---+---+---+---+------------+
| n | bin.|1's|sum|0's|sum|    a(n)    |
+---+-----+---+---+---+---+------------+
| 0 |   0 | 0 | 0 | 1 | 1 | 0 - 1 =-1  |
| 1 |   1 | 1 | 1 | 0 | 1 | 1 - 1 = 0  |
| 2 |  10 | 1 | 2 | 1 | 2 | 2 - 2 = 0  |
| 3 |  11 | 2 | 4 | 0 | 2 | 4 - 2 = 2  |
| 4 | 100 | 1 | 5 | 2 | 4 | 5 - 4 = 1  |
| 5 | 101 | 2 | 7 | 1 | 5 | 7 - 5 = 2  |
| 6 | 110 | 2 | 9 | 1 | 6 | 9 - 6 = 3  |
+---+-----+---+---+---+---+------------+
bin. - n written in base 2;
1's - number of 1's in binary expansion of n;
0's - number of 0's in binary expansion of n;
sum - total number of 1's (or 0's) in binary expansions of 0, ..., n.

Index entries for sequences related to binary expansion of n

Cf. A000079, A000120, A000295, A000788, A001855, A023416, A037861, A059015, A083652, A145037, A268289, A301896.

a:= proc(n) option remember; `if`(n=0, -1,
      a(n-1)+add(2*i-1, i=Bits[Split](n)))
    end:
seq(a(n), n=0..75);  # Alois P. Heinz, Nov 11 2024

Accumulate[DigitCount[Range[0, 75], 2, 1] - DigitCount[Range[0, 75], 2, 0]]

def A301336(n):
    return sum(2*bin(i).count('1')-len(bin(i))+2 for i in range(n+1)) # Chai Wah Wu, Sep 03 2020

def A301336(n): return (n+1)*((n.bit_count()<<1)-(t:=(n+1).bit_length()))+(1<>j)-(r if n<<1>=m*(r:=k<<1|1) else 0)) for j in range(1,n.bit_length()+1))-2 # Chai Wah Wu, Nov 11 2024

G.f.: -1/(1 - x) + (1/(1 - x)^2)*Sum_{k>=0} x^(2^k)*(1 - x^(2^k))/(1 + x^(2^k)).
a(n) = A000788(n) - A059015(n).
a(n) = A268289(n) - 1.
a(A000079(n)) = A000295(n).

A308551 Start with an empty stack S; for n = 1, 2, 3, ..., interpret the binary representation of n from left to right as follows: in case of bit 1, push the number 1 on top of S, in case of bit 0, replace the two numbers on top of S with their sum; a(n) gives the number on top of S after processing n.

Original entry on oeis.org

1, 2, 1, 3, 1, 2, 1, 4, 1, 3, 1, 3, 1, 2, 1, 5, 1, 12, 1, 4, 1, 2, 1, 4, 1, 3, 1, 3, 1, 2, 1, 6, 1, 15, 1, 23, 1, 2, 1, 5, 1, 4, 1, 4, 1, 2, 1, 5, 1, 4, 1, 4, 1, 2, 1, 4, 1, 3, 1, 3, 1, 2, 1, 7, 1, 19, 1, 30, 1, 2, 1, 47, 1, 57, 1, 5, 1, 2, 1, 6, 1, 20, 1, 5

Offset: 1

Rémy Sigrist, Jun 07 2019

After processing n, S has A268289(n) elements, the sum of which is A000788(n).
Every positive integer appears infinitely many times in the sequence.
The sequence has the same shape when represented at different scales.

			The first terms, alongside the binary representation of n and the evolution of stack S, are:
  n  a(n)  bin(n)  S
  -  ----  ------  -------------------------------------------------
  1     1       1  () -> (1)
  2     2      10  (1) -> (1,1) -> (2)
  3     1      11  (2) -> (2,1) -> (2,1,1)
  4     3     100  (2,1,1) -> (2,1,1,1) -> (2,1,2) -> (2,3)
  5     1     101  (2,3) -> (2,3,1) -> (2,4) -> (2,4,1)
  6     2     110  (2,4,1) -> (2,4,1,1) -> (2,4,1,1,1) -> (2,4,1,2)

Rémy Sigrist, Table of n, a(n) for n = 1..8192
Sean A. Irvine, Java program (github)
Rémy Sigrist, PARI program
Wikipedia, Stack (abstract data type)

Cf. A000788, A020989, A268289.

Java
```
See Links section.
```
PARI
```
See Links section.
```

a(n) = 1 iff n is odd.
a(A020989(k)) = k + 1 for any k >= 0.
If n is in A014486, then a(n) = a(n-1) + A000120(n) = 1 + A000120(n). - Charlie Neder, Jun 07 2019

A096351 Number of meaningfully different ways to design a neutral single-elimination tournament with n teams.

Original entry on oeis.org

1, 1, 3, 3, 30, 90, 315, 315, 11340, 113400, 1247400, 3742200, 48648600, 170270100, 638512875, 638512875, 86837751000, 3126159036000, 118794043368000, 1187940433680000, 49893498214560000, 548828480360160000, 6311527524141840000

Offset: 1

Lowell Bruce Anderson (landerso(AT)ida.org), Jun 29 2004

nonn

The result for tournaments is well known (see the references). The recursive formula for general n is new.
From Laura Monroe, Jun 11 2020: (Start)
a(n) is the number of binary operations on n variables concatenated in a pairwise (or cascading) manner, where the operation is commutative, but not associative. This is proven in the Monroe et al. reference, Props. 13, 23, 24. The explicit formula given for general n is new.
One example of such an operation is given in the original sequence definition: the meaningfully different single-elimination tournaments on n teams, where the binary operation is the pairwise game.
Another example is floating-point addition: a(n) is the number of computationally equivalent pairwise summations on n floating-point numbers, using the IEEE 754 standard for floating-point arithmetic in very common use on digital systems in 2020. IEEE 754 guarantees pairwise commutativity of addition, but not associativity, and in fact can give different results for summations with the same summands having different groupings. (End)

			From _Laura Monroe_, Jun 11 2020: (Start)
For n=3, the a(3)=3 computationally inequivalent pairwise summations on the 3 summands a,b,c are: ((a+b)+c), ((a+c)+b) and ((b+c)+a).
For n=4, the a(4)=3 computationally inequivalent pairwise summations on 4 summands a,b,c,d are: ((a+b)+(c+d)), ((a+c)+(b+d)), and ((a+d)+(b+c)).
(End)

David, H. A. (1988). The Method of Paired Comparisons, 2nd Ed., New York: Oxford University Press. Page 123.

Michel Marcus, Table of n, a(n) for n = 1..400
Laura Monroe and Vanessa Job, Computationally Inequivalent Summations and Their Parenthetic Forms, arXiv:2005.05387[cs.DM], 2020.
T. V. Narayana, and F. Agyepong, Contributions to the Theory of Tournaments IV. A Comparison of Tournaments Through Probabilistic Completion, Cahiers BURO, Paris, 32 (1979), p. 21-34.
D. T. Searls, On the Probability of Winning With Different Tournament Procedures, Journal of the American Statistical Association, Vol. 58 Issue 304, 1963; 1064-1081.

Cf. A000142, A268289.

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

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

a(n) = 1 if n = 1. a(n) = ((n!/((n/2)!*(n/2)!))*(a(n/2))^2)/2 if n is even. a(n) = ((n!/((((n-1)/2)!*((n+1)/2)!)))*a((n+1)/2)*a((n-1)/2)) if n is odd and > 1.
If n = 2^k, then a(n) = n!/(2^(n-1)).
a(n) = n!/(2^A268289(n-1)). When the explicit form for A268289 is used, this is also an explicit form. - Laura Monroe, Jun 11 2020

a(23) from Laura Monroe, Jun 14 2020

A330261 Start with an empty stack S; for n = 1, 2, 3, ..., interpret the binary representation of n from left to right as follows: in case of bit 1, push the number 1 on top of S, in case of bit 0, replace the two numbers on top of S, say u on top of v, with u-v; a(n) gives the number on top of S after processing n.

Original entry on oeis.org

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

Offset: 1

Rémy Sigrist, Dec 07 2019

This sequence is a variant of A308551.
After processing n, S has A268289(n) elements.
Every integer appears infinitely many times in the sequence:
- the effect of the binary string b(0) = "110" is to leave 0 on top of S,
- the effect of the binary string b(1) = "1" is to leave 1 on top of S,
- the effect of the binary string b(-1) = "11100" is to leave -1 on top of S,
- let "|" denote the binary concatenation,
- for any k > 0:
   - the effect of b(k+1) = b(-1)|b(k)|"0" is to leave k+1 on top of S,
   - the effect of b(-k-1) = b(1)|b(-k)|"0" is to leave -k-1 on top of S,
- for any k, for any n > 0, if the binary representation of n ends with b(k), then a(n) = k, QED,
- see A330264 for the values in order of appearance.

			The first terms, alongside the binary representation of n and the evolution of stack S, are:
  n   a(n)  bin(n)  S
  --  ----  ------  ------------------------------------------------------------
   1     1       1  () -> (1)
   2     0      10  (1) -> (1,1) -> (0)
   3     1      11  (0) -> (0,1) -> (0,1,1)
   4    -1     100  (0,1,1) -> (0,1,1,1) -> (0,1,0) -> (0,-1)
   5     1     101  (0,-1) -> (0,-1,1) -> (0,2) -> (0,2,1)
   6     0     110  (0,2,1) -> (0,2,1,1) -> (0,2,1,1,1) -> (0,2,1,0)
   7     1     111  (0,2,1,0) -> (0,2,1,0,1) -> (0,2,1,0,1,1) -> (0,2,1,0,1,1,1)

Rémy Sigrist, Table of n, a(n) for n = 1..8192
Rémy Sigrist, Scatterplot of the first 2^20 terms
Rémy Sigrist, PARI program for A330261

Cf. A268289, A308551, A330261, A330264.

PARI
```
See Links section.
```

a(2*k-1) = 1 for any k > 0.

A330262 Start with an empty stack S; for n = 1, 2, 3, ..., interpret the binary representation of n from left to right as follows: in case of bit 1, push the number 1 on top of S, in case of bit 0, replace the two numbers on top of S, say u on top of v, with v-u; a(n) gives the number on top of S after processing n.

Original entry on oeis.org

1, 0, 1, 1, 1, 0, 1, 0, 1, -1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 2, 1, 0, 1, 0, 1, -1, 1, 1, 1, 0, 1, 0, 1, -1, 1, -1, 1, 0, 1, -1, 1, -2, 1, 0, 1, 0, 1, 1, 1, 0, 1, 2, 1, 0, 1, 0, 1, -1, 1, 1, 1, 0, 1, 1, 1, -1, 1, 0, 1, 0, 1, -3, 1, -3, 1, 1, 1, 0, 1, 2, 1, -2, 1

Offset: 1

Rémy Sigrist, Dec 07 2019

This sequence is a variant of A330261.
After processing n, S has A268289(n) elements.
Every integer appears infinitely many times in the sequence:
- the proof is similar to that found in A330261,
- see A330265 for the values in order of appearance.

			The first terms, alongside the binary representation of n and the evolution of stack S, are:
  n  a(n)  bin(n)  S
  -  ----  ------  ------------------------------------------------------------
  1     1       1  () -> (1)
  2     0      10  (1) -> (1,1) -> (0)
  3     1      11  (0) -> (0,1) -> (0,1,1)
  4     1     100  (0,1,1) -> (0,1,1,1) -> (0,1,0) -> (0,1)
  5     1     101  (0,1) -> (0,1,1) -> (0,0) -> (0,0,1)
  6     0     110  (0,0,1) -> (0,0,1,1) -> (0,0,1,1,1) -> (0,0,1,0)
  7     1     111  (0,0,1,0) -> (0,0,1,0,1) -> (0,0,1,0,1,1) -> (0,0,1,0,1,1,1)

Rémy Sigrist, Table of n, a(n) for n = 1..8192
Rémy Sigrist, Scatterplot of the first 2^20 terms
Rémy Sigrist, PARI program for A330262

Cf. A268289, A308551, A330261, A330265.

PARI
```
See Links section.
```

cp's OEIS Frontend

A037861 (Number of 0's) - (number of 1's) in the base-2 representation of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

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

A296062 Base-2 logarithm of the number of different shapes of balanced binary trees with n nodes (A110316).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Formula

A181132 a(0)=0; thereafter a(n) = total number of 0's in binary expansions of 1, ..., n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Python

Word

Formula

Extensions

A269735 G.f.: Sum_{k >= 0} x^(2^k)*(1-x^(2^k))/(1+x^(2^k)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

A301336 a(n) = total number of 1's minus total number of 0's in binary expansions of 0, ..., n.

Views

Author

Keywords