A080791 -id:A080791 - cp's OEIS frontend

A233271 a(0)=0; thereafter a(n+1) = a(n) + 1 + number of 0's in binary representation of a(n), counted with A080791.

0, 1, 2, 4, 7, 8, 12, 15, 16, 21, 24, 28, 31, 32, 38, 42, 46, 49, 53, 56, 60, 63, 64, 71, 75, 79, 82, 87, 90, 94, 97, 102, 106, 110, 113, 117, 120, 124, 127, 128, 136, 143, 147, 152, 158, 162, 168, 174, 178, 183, 186, 190, 193, 199, 203, 207, 210, 215, 218, 222

Offset: 0

Antti Karttunen, Dec 12 2013

These are iterates of A233272: a(0)=0, and for n>0, a(n) = A233272(a(n-1)). The difference from A216431 stems from the fact that it uses A023416 to count the 0-bits in the binary expansion of n, while this sequence uses A080791, which results a slightly different start for the iteration, and a much better alignment with sequences related to "infinite trunk of binary beanstalk", A179016.

Apart from term a(2)=2, it seems that each term a(n) >= A179016(n). Please see their ratio plotted with Plot2, and also their differences: A233270.

Antti Karttunen, Table of n, a(n) for n = 0..8727
A. Karttunen Ratio A233271/A179016 plotted with OEIS Plot2-script

Differs from A216431 only in that here 1 has been inserted into position a(1), between 0 and 2.

Cf. A080791, A010062, A233272, A179016, A233270, A218616, A054429, A213710, A218600.

a[0] = 0; a[n_] := a[n] = If[n == 1, 1, # + 1 + Last@ DigitCount[#, 2] &@ a[n - 1]]; Table[a@ n, {n, 0, 59}] (* or *)
Insert[NestList[# + 1 + DigitCount[#, 2, 0] &, 0, nn], 1, 2] (* Michael De Vlieger, Mar 07 2016, the latter after Harvey P. Dale at A216431 *)

a(0)=0, and for n>0, a(n) = A233272(a(n-1)).
a(0)=0, and for n>0, a(n) = a(n-1) + 1 + A080791(a(n-1)).
a(n) = A054429(A218616(n)) = A054429(A179016(A218602(n))) [This sequence can be mapped to the infinite trunk of "binary beanstalk" with involutions A054429 & A218602].
For all n, a(A213710(n)) = 2^n = A000079(n).
For n>=3, a(A218600(n)) = A000225(n).

A233272 a(n) = n + 1 + number of nonleading zeros in binary representation of n (A080791).

Original entry on oeis.org

1, 2, 4, 4, 7, 7, 8, 8, 12, 12, 13, 13, 15, 15, 16, 16, 21, 21, 22, 22, 24, 24, 25, 25, 28, 28, 29, 29, 31, 31, 32, 32, 38, 38, 39, 39, 41, 41, 42, 42, 45, 45, 46, 46, 48, 48, 49, 49, 53, 53, 54, 54, 56, 56, 57, 57, 60, 60, 61, 61, 63, 63, 64, 64, 71, 71, 72

Offset: 0

Antti Karttunen, Dec 12 2013

From Antti Karttunen, Jan 30 2022: (Start)
Write n in binary: 1ab..xyz, then a(n) = (1+1ab..xy) + (1+1ab..x) + ... + (1+1ab) + (1+1a) + (1+1) + (1+0) + 1. This method was found by LODA miner, see the assembly program at C. Krause link.
Proof: Compare to a similar formula given for A011371, with a(n) = a(floor(n/2)) + floor(n/2) to the new formula for this sequence which is a(n) = 1 + a(floor(n/2)) + floor(n/2), for n > 0 and a(0) = 1. It is easy to see that the difference between these, a(n) - A011371(n) = 1+A070939(n), for n > 0. As A011371(n) = n minus (number of 1's in binary expansion of n), then a(n) = 1 + (number of digits in binary expansion of n) + (n minus number of 1's in binary expansion of n) = 1 + n + (number of nonleading 0's in binary expansion of n), which indeed is the definition of this sequence.
(End)

Antti Karttunen, Table of n, a(n) for n = 0..8192
Christian Krause, et al, A mined LODA assembly source for this sequence
Index entries for sequences related to binary expansion of n

Bisection: A233273 (A120511 + 1). Iterates: A233271, A216431.

Cf. A000120, A005187, A011371, A054429, A070939, A080791, A092391.

DigitCount[#, 2, 0] + # + 1 & [Range[0, 100]] (* Paolo Xausa, Mar 01 2024 *)

A233272(n) = { my(s=1); while(n, n>>=1; s+=(1+n)); (s); }; \\ (After a LODA-assembly program found by a miner) - Antti Karttunen, Jan 30 2022

(define (A233272 n) (+ 1 n (A080791 n)))
;; Alternatively:
(define (A233272 n) (if (zero? n) 1 (+ n (A000120 (A054429 n)))))

a(n) = n + A080791(n) + 1.
For all n>=1, a(n) = n + A000120(A054429(n)).
a(0) = 1; for n > 1, a(n) = 1 + floor(n/2) + a(floor(n/2)). - (Found by LODA miner, see comments) - Antti Karttunen, Jan 30 2022

A285716 a(n) = A080791(A245611(n)).

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Apr 25 2017

nonn

Antti Karttunen, Table of n, a(n) for n = 1..8192

One less than A091304 after the initial term.
Cf. A000120, A080791, A244153, A245611, A278223, A285712, A285714, A285715.
Cf. A006254 (gives the positions of zeros after initial a(1)=0.)

a[n_] := PrimeOmega[2*n - 1] - 1; a[1] = 0; Array[a, 100] (* Amiram Eldar, Jul 23 2023 *)

;; First implementation uses memoization-macro definec:
(definec (A285716 n) (if (<= n 2) 0 (+ (if (= 2 (modulo n 3)) 1 0) (A285716 (A285712 n)))))
(define (A285716 n) (A080791 (A245611 n)))

a(1) = 0, a(2) = 1, for n > 2, a(n) = a(A285712(n)) + [n == 2 mod 3]. (Where [] is Iverson bracket, giving here 1 only if n is of the form 3k+2, and 0 otherwise.)
a(n) = A080791(A245611(n)).
For all n >= 2,  a(n) = A091304(n)-1 = A000120(A244153(n))-1. - Antti Karttunen, May 31 2017

A267109 a(n) = A080791(A267111(n)).

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Jan 16 2016

nonn

Antti Karttunen, Table of n, a(n) for n = 1..8192

Cf. A004001, A070939, A080791, A088359, A265332, A267108, A267110, A267111.

a(1) = 0; for n > 1, if A265332(n) = 1 [when n is one of the terms of A088359], a(n) =  a(A004001(n)-1), otherwise 1 + a(n) = a(n-A004001(n)).
a(n) = A080791(A267111(n)).
Other identities. For all n >= 1:
a(n) = A070939(n) - A267108(n).

A265336 Number of nonleading 0-bits in bijective base-3 reversal of n: a(n) = A080791(A263273(n)).

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Dec 18 2015

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

Cf. A080791, A263273, A265337, A265339, A265340.

a(n) = A080791(A263273(n)).
a(0) = 0, a(2n) = 1 + a(A265339(n)), a(2n+1) = a(A265339(n)).
a(n) = A265340(n) - A265337(n).

A342102 Lexicographically latest sequence of distinct nonnegative integers such that for any n >= 0, {A000120(n), A080791(n)} = {A000120(a(n)), A080791(a(n))}.

Original entry on oeis.org

0, 1, 2, 3, 6, 5, 4, 7, 14, 12, 10, 13, 9, 11, 8, 15, 30, 28, 26, 25, 24, 22, 21, 29, 20, 19, 18, 27, 17, 23, 16, 31, 62, 60, 58, 56, 57, 52, 50, 54, 53, 49, 44, 51, 42, 48, 46, 61, 45, 41, 38, 43, 37, 40, 39, 59, 35, 36, 34, 55, 33, 47, 32, 63, 126, 124, 122

Offset: 0

Rémy Sigrist, Feb 28 2021

This sequence is a self-inverse permutation of the nonnegative integers.

			The first terms, in decimal and in binary, alongside {A000120(n), A080791(n)}, are:
  n   a(n)  bin(n)  bin(a(n))  {A000120(n), A080791(n)}
  --  ----  ------  ---------  ------------------------
   0     0       0          0  {0}
   1     1       1          1  {0, 1}
   2     2      10         10  {1}
   3     3      11         11  {0, 2}
   4     6     100        110  {1, 2}
   5     5     101        101  {1, 2}
   6     4     110        100  {1, 2}
   7     7     111        111  {0, 3}
   8    14    1000       1110  {1, 3}
   9    12    1001       1100  {2}
  10    10    1010       1010  {2}
  11    13    1011       1101  {1, 3}
  12     9    1100       1001  {2}
  13    11    1101       1011  {1, 3}
  14     8    1110       1000  {1, 3}
  15    15    1111       1111  {0, 4}

Rémy Sigrist, Table of n, a(n) for n = 0..8191
Rémy Sigrist, Colored scatterplot of the first 2^20 terms (where the color is function of min(A000120(n), A080791(n)))
Rémy Sigrist, PARI program for A342102
Index entries for sequences related to binary expansion of n
Index entries for sequences that are permutations of the natural numbers

See A342115, A342116 and A342117 for similar sequences.

Cf. A000120, A080791, A331274, A337242.

PARI
```
\\ See Links section.
```

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

a(n) < 2^k for any n < 2^k.

A089263 First differences of A080791.

Original entry on oeis.org

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

Offset: 0

Ralf Stephan, Oct 30 2003

Number of trailing zeros in the binary representation of n, minus one if n is not a power of two.

a(0) = 0 by convention. - Antti Karttunen, Sep 27 2018

Antti Karttunen, Table of n, a(n) for n = 0..65537
Index entries for sequences related to binary expansion of n

Cf. A080791, A088705.

a(n)=if(!n,n,(valuation(n, 2)+(2^valuation(n, 2)==n)-1)); \\ Check for n=0 added by Antti Karttunen, Sep 27 2018

a(n)=if(n<1,0,if(n%2==0,a(n/2)+1,-1+(((n-1)/2)==0)))

a(0)=0, a(2n) = a(n) + 1, a(2n+1) = -1 + [n==0].
a(n) = A007814(n) + A036987(n-1) - 1.
G.f.: sum(k>=0, t^2/(1+t), t=x^2^k).
a(n) = A080791(n+1) - A080791(n). - Antti Karttunen, Sep 27 2018

Definition corrected (A023416 replaced with A080791) by Antti Karttunen, Sep 27 2018

A000120 1's-counting sequence: number of 1's in binary expansion of n (or the binary weight of n).

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

The binary weight of n is also called Hamming weight of n. [The term "Hamming weight" was named after the American mathematician Richard Wesley Hamming (1915-1998). - Amiram Eldar, Jun 16 2021]
a(n) is also the largest integer such that 2^a(n) divides binomial(2n, n) = A000984(n). - Benoit Cloitre, Mar 27 2002
To construct the sequence, start with 0 and use the rule: If k >= 0 and a(0), a(1), ..., a(2^k-1) are the first 2^k terms, then the next 2^k terms are a(0) + 1, a(1) + 1, ..., a(2^k-1) + 1. - Benoit Cloitre, Jan 30 2003
An example of a fractal sequence. That is, if you omit every other number in the sequence, you get the original sequence. And of course this can be repeated. So if you form the sequence a(0 * 2^n), a(1 * 2^n), a(2 * 2^n), a(3 * 2^n), ... (for any integer n > 0), you get the original sequence. - Christopher.Hills(AT)sepura.co.uk, May 14 2003
The n-th row of Pascal's triangle has 2^k distinct odd binomial coefficients where k = a(n) - 1. - Lekraj Beedassy, May 15 2003
Fixed point of the morphism 0 -> 01, 1 -> 12, 2 -> 23, 3 -> 34, 4 -> 45, etc., starting from a(0) = 0. - Robert G. Wilson v, Jan 24 2006
a(n) is the number of times n appears among the mystery calculator sequences: A005408, A042964, A047566, A115419, A115420, A115421. - Jeremy Gardiner, Jan 25 2006
a(n) is the number of solutions of the Diophantine equation 2^m*k + 2^(m-1) + i = n, where m >= 1, k >= 0, 0 <= i < 2^(m-1); a(5) = 2 because only (m, k, i) = (1, 2, 0) [2^1*2 + 2^0 + 0 = 5] and (m, k, i) = (3, 0, 1) [2^3*0 + 2^2 + 1 = 5] are solutions. - Hieronymus Fischer, Jan 31 2006
The first appearance of k, k >= 0, is at a(2^k-1). - Robert G. Wilson v, Jul 27 2006
Sequence is given by T^(infinity)(0) where T is the operator transforming any word w = w(1)w(2)...w(m) into T(w) = w(1)(w(1)+1)w(2)(w(2)+1)...w(m)(w(m)+1). I.e., T(0) = 01, T(01) = 0112, T(0112) = 01121223. - Benoit Cloitre, Mar 04 2009
For n >= 2, the minimal k for which a(k(2^n-1)) is not multiple of n is 2^n + 3. - Vladimir Shevelev, Jun 05 2009
Triangle inequality: a(k+m) <= a(k) + a(m). Equality holds if and only if C(k+m, m) is odd. - Vladimir Shevelev, Jul 19 2009
a(k*m) <= a(k) * a(m). - Robert Israel, Sep 03 2023
The number of occurrences of value k in the first 2^n terms of the sequence is equal to binomial(n, k), and also equal to the sum of the first n - k + 1 terms of column k in the array A071919. Example with k = 2, n = 7: there are 21 = binomial(7,2) = 1 + 2 + 3 + 4 + 5 + 6 2's in a(0) to a(2^7-1). - Brent Spillner (spillner(AT)acm.org), Sep 01 2010, simplified by R. J. Mathar, Jan 13 2017
Let m be the number of parts in the listing of the compositions of n as lists of parts in lexicographic order, a(k) = n - length(composition(k)) for all k < 2^n and all n (see example); A007895 gives the equivalent for compositions into odd parts. - Joerg Arndt, Nov 09 2012
From Daniel Forgues, Mar 13 2015: (Start)
Just tally up row k (binary weight equal k) from 0 to 2^n - 1 to get the binomial coefficient C(n,k). (See A007318.)
     0   1       3               7                              15
  0: O | . | .   . | .   .   .   . | .   .   .   .   .   .   .   . |
  1:   | O | O   . | O   .   .   . | O   .   .   .   .   .   .   . |
  2:   |   |     O |     O   O   . |     O   O   .   O   .   .   . |
  3:   |   |       |             O |             O       O   O   . |
  4:   |   |       |               |                             O |
Due to its fractal nature, the sequence is quite interesting to listen to.
(End)
The binary weight of n is a particular case of the digit sum (base b) of n. - Daniel Forgues, Mar 13 2015
The mean of the first n terms is 1 less than the mean of [a(n+1),...,a(2n)], which is also the mean of [a(n+2),...,a(2n+1)]. - Christian Perfect, Apr 02 2015
a(n) is also the largest part of the integer partition having viabin number n. The viabin number of an integer partition is defined in the following way. Consider the southeast border of the Ferrers board of the integer partition and consider the binary number obtained by replacing each east step with 1 and each north step, except the last one, with 0. The corresponding decimal form is, by definition, the viabin number of the given integer partition. "Viabin" is coined from "via binary". For example, consider the integer partition [2, 2, 2, 1]. The southeast border of its Ferrers board yields 10100, leading to the viabin number 20. - Emeric Deutsch, Jul 20 2017
a(n) is also known as the population count of the binary representation of n. - Chai Wah Wu, May 19 2020

			Using the formula a(n) = a(floor(n / floor_pow4(n))) + a(n mod floor_pow4(n)):
  a(4) = a(1) + a(0) = 1,
  a(8) = a(2) + a(0) = 1,
  a(13) = a(3) + a(1) = 2 + 1 = 3,
  a(23) = a(1) + a(7) = 1 + a(1) + a(3) = 1 + 1 + 2 = 4.
_Gary W. Adamson_ points out (Jun 03 2009) that this can be written as a triangle:
  0,
  1,
  1,2,
  1,2,2,3,
  1,2,2,3,2,3,3,4,
  1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
  1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
  1,2,2,3,2,3,...
where the rows converge to A063787.
From _Joerg Arndt_, Nov 09 2012: (Start)
Connection to the compositions of n as lists of parts (see comment):
[ #]:   a(n)  composition
[ 0]:   [0]   1 1 1 1 1
[ 1]:   [1]   1 1 1 2
[ 2]:   [1]   1 1 2 1
[ 3]:   [2]   1 1 3
[ 4]:   [1]   1 2 1 1
[ 5]:   [2]   1 2 2
[ 6]:   [2]   1 3 1
[ 7]:   [3]   1 4
[ 8]:   [1]   2 1 1 1
[ 9]:   [2]   2 1 2
[10]:   [2]   2 2 1
[11]:   [3]   2 3
[12]:   [2]   3 1 1
[13]:   [3]   3 2
[14]:   [3]   4 1
[15]:   [4]   5
(End)

Jean-Paul Allouche and Jeffrey Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 119.
Donald E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.1.3, Problem 41, p. 589. - N. J. A. Sloane, Aug 03 2012
Manfred R. Schroeder, Fractals, Chaos, Power Laws. W.H. Freeman, 1991, p. 383.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n = 0..10000
Franklin T. Adams-Watters, and Frank Ruskey, Generating Functions for the Digital Sum and Other Digit Counting Sequences, JIS, Vol. 12 (2009), Article 09.5.6.
J.-P. Allouche, On an Inequality in a 1970 Paper of R. L. Graham, INTEGERS 21A (2021), #A2.
Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Sci., Vol. 98 (1992), pp. 163-197. (PS file on author's web page.)
Jean-Paul Allouche, Jeffrey Shallit and Jonathan Sondow, Summation of Series Defined by Counting Blocks of Digits, arXiv:math/0512399 [math.NT], 2005-2006.
Jean-Paul Allouche, Jeffrey Shallit and Jonathan Sondow, Summation of series defined by counting blocks of digits, J. Number Theory, Vol. 123 (2007), pp. 133-143.
Richard Bellman and Harold N. Shapiro, On a problem in additive number theory, Annals Math., Vol. 49, No. 2 (1948), pp. 333-340. - _N. J. A. Sloane_, Mar 12 2009
C. Cobeli and A. Zaharescu, A game with divisors and absolute differences of exponents, Journal of Difference Equations and Applications, Vol. 20, #11 (2014) pp. 1489-1501, DOI: 10.1080/10236198.2014.940337. Also available as arXiv:1411.1334 [math.NT], 2014. See delta_n.
Jean Coquet, Power sums of digital sums, J. Number Theory, Vol. 22, No. 2 (1986), pp. 161-176.
F. M. Dekking, The Thue-Morse Sequence in Base 3/2, J. Int. Seq., Vol. 26 (2023), Article 23.2.3.
Karl Dilcher and Larry Ericksen, Hyperbinary expansions and Stern polynomials, Elec. J. Combin, Vol. 22 (2015), #P2.24.
Josef Eschgfäller and Andrea Scarpante, Dichotomic random number generators, arXiv:1603.08500 [math.CO], 2016.
Emmanuel Ferrand, Deformations of the Taylor Formula, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.7.
Steven R. Finch, Pascal Sebah and Zai-Qiao Bai, Odd Entries in Pascal's Trinomial Triangle, arXiv:0802.2654 [math.NT], 2008.
Philippe Flajolet, Peter Grabner, Peter Kirschenhofer, Helmut Prodinger and Robert F. Tichy, Mellin Transforms And Asymptotics: Digital Sums, Theoret. Computer Sci., Vol. 123, No. 2 (1994), pp. 291-314.
Michael Gilleland, Some Self-Similar Integer Sequences.
P. J. Grabner, P. Kirschenhofer, H. Prodinger and R. F. Tichy, On the moments of the sum-of-digits function, Applications of Fibonacci numbers, Vol. 5 (St. Andrews, 1992), Kluwer Acad. Publ., Dordrecht, 1993, 263-271.
Ronald L. Graham, On primitive graphs and optimal vertex assignments, Internat. Conf. Combin. Math. (New York, 1970), Annals of the NY Academy of Sciences, Vol. 175, 1970, pp. 170-186.
Khodabakhsh Hessami Pilehrood and Tatiana Hessami Pilehrood, Vacca-Type Series for Values of the Generalized Euler Constant Function and its Derivative, J. Integer Sequences, Vol. 13 (2010), Article 10.7.3.
Nick Hobson, Python program for this sequence.
Kathy Q. Ji and Herbert S. Wilf, Extreme Palindromes, arXiv:math/0611465 [math.CO], 2006.
Guy Louchard and Helmut Prodinger, The Largest Missing Value in a Composition of an Integer and Some Allouche-Shallit-Type Identities, J. Int. Seq., Vol. 16 (2013), Article 13.2.2.
J.-L. Mauclaire and Leo Murata, On q-additive functions, I, Proc. Japan Acad. Ser. A Math. Sci., Vol. 59, No. 6 (1983), pp. 274-276.
J.-L. Mauclaire and Leo Murata, On q-additive functions, II, Proc. Japan Acad. Ser. A Math. Sci., Vol. 59, No. 9 (1983), pp. 441-444.
M. D. McIlroy, The number of 1's in binary integers: bounds and extremal properties, SIAM J. Comput., Vol. 3 (1974), pp. 255-261.
Kerry Mitchell, Spirolateral-Type Images from Integer Sequences, 2013.
Sam Northshield, Stern's Diatomic Sequence 0,1,1,2,1,3,2,3,1,4,..., Amer. Math. Month., Vol. 117, No. 7 (2010), pp. 581-598.
Theophanes E. Raptis, Finite Information Numbers through the Inductive Combinatorial Hierarchy, arXiv:1805.06301 [physics.gen-ph], 2018.
Carlo Sanna, On Arithmetic Progressions of Integers with a Distinct Sum of Digits, Journal of Integer Sequences, Vol. 15 (2012), Article 12.8.1. - _N. J. A. Sloane_, Dec 29 2012
Nanci Smith, Problem B-82, Fib. Quart., Vol. 4, No. 4 (1966), pp. 374-375.
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, D. and G. Chudnovsky, eds., Springer, 2010, pp. 331-340.
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions, 2004.
Ralf Stephan, Table of generating functions.
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
Kenneth B. Stolarsky, Power and exponential sums of digital sums related to binomial coefficient parity, SIAM J. Appl. Math., Vol. 32 (1977), pp. 717-730. See B(n). - _N. J. A. Sloane_, Apr 05 2014
J. R. Trollope, An explicit expression for binary digital sums, Math. Mag., Vol. 41, No. 1 (1968), pp. 21-25.
Robert Walker, Self Similar Sloth Canon Number Sequences.
Eric Weisstein's World of Mathematics, Binary, Digit Count, Stolarsky-Harborth Constant, Digit Sum.
Wikipedia, Hamming weight.
Wolfram Research, Numbers in Pascal's triangle.
Index entries for "core" sequences
Index entries for sequences related to binary expansion of n
Index entries for Colombian or self numbers and related sequences
Index entries for sequences that are fixed points of mappings

The basic sequences concerning the binary expansion of n are this one, A000788, A000069, A001969, A023416, A059015, A007088.
Partial sums see A000788. For run lengths see A131534. See also A001792, A010062.
Number of 0's in n: A023416 and A080791.
a(n) = n - A011371(n).
Sum of digits of n written in bases 2-16: this sequence, A053735, A053737, A053824, A053827, A053828, A053829, A053830, A007953, A053831, A053832, A053833, A053834, A053835, A053836.
Cf. A001620, A344716, A007814, A063787.
This is Guy Steele's sequence GS(3, 4) (see A135416).
Cf. A055640, A055641, A102669-A102685, A117804, A122840, A122841, A160093, A160094, A196563, A196564 (for base 10).
Cf. A230952 (boustrophedon transform).
Cf. A070939 (length of binary representation of n).

Fortran
```
c See link in A139351
```

import Data.Bits (Bits, popCount)
a000120 :: (Integral t, Bits t) => t -> Int
a000120 = popCount
a000120_list = 0 : c [1] where c (x:xs) = x : c (xs ++ [x,x+1])
-- Reinhard Zumkeller, Aug 26 2013, Feb 19 2012, Jun 16 2011, Mar 07 2011

a000120 = concat r
    where r = [0] : (map.map) (+1) (scanl1 (++) r)
-- Luke Palmer, Feb 16 2014

[Multiplicity(Intseq(n, 2), 1): n in [0..104]]; // Marius A. Burtea, Jan 22 2020

[&+Intseq(n, 2):n in [0..104]]; // Marius A. Burtea, Jan 22 2020

A000120 := proc(n) local w,m,i; w := 0; m := n; while m > 0 do i := m mod 2; w := w+i; m := (m-i)/2; od; w; end: wt := A000120;
A000120 := n -> add(i, i=convert(n,base,2)): # Peter Luschny, Feb 03 2011
with(Bits): p:=n->ilog2(n-And(n,n-1)): seq(p(binomial(2*n,n)),n=0..200) # Gary Detlefs, Jan 27 2019

Table[DigitCount[n, 2, 1], {n, 0, 105}]
Nest[Flatten[# /. # -> {#, # + 1}] &, {0}, 7] (* Robert G. Wilson v, Sep 27 2011 *)
Table[Plus @@ IntegerDigits[n, 2], {n, 0, 104}]
Nest[Join[#, # + 1] &, {0}, 7] (* IWABUCHI Yu(u)ki, Jul 19 2012 *)
Log[2, Nest[Join[#, 2#] &, {1}, 14]] (* gives 2^14 term, Carlos Alves, Mar 30 2014 *)

{a(n) = if( n<0, 0, 2*n - valuation((2*n)!, 2))};

{a(n) = if( n<0, 0, subst(Pol(binary(n)), x ,1))};

{a(n) = if( n<1, 0, a(n\2) + n%2)}; /* Michael Somos, Mar 06 2004 */

a(n)=my(v=binary(n));sum(i=1,#v,v[i]) \\ Charles R Greathouse IV, Jun 24 2011

a(n)=norml2(binary(n)) \\ better use {A000120=hammingweight}. - M. F. Hasler, Oct 09 2012, edited Feb 27 2020

a(n)=hammingweight(n) \\ Michel Marcus, Oct 19 2013
(Common Lisp) (defun floor-to-power (n pow) (declare (fixnum pow)) (expt pow (floor (log n pow)))) (defun enabled-bits (n) (if (< n 4) (n-th n (list 0 1 1 2)) (+ (enabled-bits (floor (/ n (floor-to-power n 4)))) (enabled-bits (mod n (floor-to-power n 4)))))) ; Stephen K. Touset (stephen(AT)touset.org), Apr 04 2007

def A000120(n): return bin(n).count('1') # Chai Wah Wu, Sep 03 2014

import numpy as np
A000120 = np.array([0], dtype="uint8")
for bitrange in range(25): A000120 = np.append(A000120, np.add(A000120, 1))
print([A000120[n] for n in range(0, 105)]) # Karl-Heinz Hofmann, Nov 07 2022

def A000120(n): return n.bit_count() # Requires Python 3.10 or higher. - Pontus von Brömssen, Nov 08 2022

Python
```
# Also see links.
```

def A000120(n):
    if n <= 1: return Integer(n)
    return A000120(n//2) + n%2
[A000120(n) for n in range(105)]  # Peter Luschny, Nov 19 2012

def A000120(n) : return sum(n.digits(2)) # Eric M. Schmidt, Apr 26 2013

(0 to 127).map(Integer.bitCount()) // _Alonso del Arte, Mar 05 2019

a(0) = 0, a(2*n) = a(n), a(2*n+1) = a(n) + 1.
a(0) = 0, a(2^i) = 1; otherwise if n = 2^i + j with 0 < j < 2^i, a(n) = a(j) + 1.
G.f.: Product_{k >= 0} (1 + y*x^(2^k)) = Sum_{n >= 0} y^a(n)*x^n. - N. J. A. Sloane, Jun 04 2009
a(n) = a(n-1) + 1 - A007814(n) = log_2(A001316(n)) = 2n - A005187(n) = A070939(n) - A023416(n). - Henry Bottomley, Apr 04 2001; corrected by Ralf Stephan, Apr 15 2002
a(n) = log_2(A000984(n)/A001790(n)). - Benoit Cloitre, Oct 02 2002
For n > 0, a(n) = n - Sum_{k=1..n} A007814(k). - Benoit Cloitre, Oct 19 2002
a(n) = n - Sum_{k>=1} floor(n/2^k) = n - A011371(n). - Benoit Cloitre, Dec 19 2002
G.f.: (1/(1-x)) * Sum_{k>=0} x^(2^k)/(1+x^(2^k)). - Ralf Stephan, Apr 19 2003
a(0) = 0, a(n) = a(n - 2^floor(log_2(n))) + 1. Examples: a(6) = a(6 - 2^2) + 1 = a(2) + 1 = a(2 - 2^1) + 1 + 1 = a(0) + 2 = 2; a(101) = a(101 - 2^6) + 1 = a(37) + 1 = a(37 - 2^5) + 2 = a(5 - 2^2) + 3 = a(1 - 2^0) + 4 = a(0) + 4 = 4; a(6275) = a(6275 - 2^12) + 1 = a(2179 - 2^11) + 2 = a(131 - 2^7) + 3 = a(3 - 2^1) + 4 = a(1 - 2^0) + 5 = 5; a(4129) = a(4129 - 2^12) + 1 = a(33 - 2^5) + 2 = a(1 - 2^0) + 3 = 3. - Hieronymus Fischer, Jan 22 2006
A fixed point of the mapping 0 -> 01, 1 -> 12, 2 -> 23, 3 -> 34, 4 -> 45, ... With f(i) = floor(n/2^i), a(n) is the number of odd numbers in the sequence f(0), f(1), f(2), f(3), f(4), f(5), ... - Philippe Deléham, Jan 04 2004
When read mod 2 gives the Morse-Thue sequence A010060.
Let floor_pow4(n) denote n rounded down to the next power of four, floor_pow4(n) = 4 ^ floor(log4 n). Then a(0) = 0, a(1) = 1, a(2) = 1, a(3) = 2, a(n) = a(floor(n / floor_pow4(n))) + a(n % floor_pow4(n)). - Stephen K. Touset (stephen(AT)touset.org), Apr 04 2007
a(n) = n - Sum_{k=2..n} Sum_{j|n, j >= 2} (floor(log_2(j)) - floor(log_2(j-1))). - Hieronymus Fischer, Jun 18 2007
a(n) = A138530(n, 2) for n > 1. - Reinhard Zumkeller, Mar 26 2008
a(A077436(n)) = A159918(A077436(n)); a(A000290(n)) = A159918(n). - Reinhard Zumkeller, Apr 25 2009
a(n) = A063787(n) - A007814(n). - Gary W. Adamson, Jun 04 2009
a(n) = A007814(C(2n, n)) = 1 + A007814(C(2n-1, n)). - Vladimir Shevelev, Jul 20 2009
For odd m >= 1, a((4^m-1)/3) = a((2^m+1)/3) + (m-1)/2 (mod 2). - Vladimir Shevelev, Sep 03 2010
a(n) - a(n-1) = { 1 - a(n-1) if and only if A007814(n) = a(n-1), 1 if and only if A007814(n) = 0, -1 for all other A007814(n) }. - Brent Spillner (spillner(AT)acm.org), Sep 01 2010
a(A001317(n)) = 2^a(n). - Vladimir Shevelev, Oct 25 2010
a(n) = A139351(n) + A139352(n) = Sum_k {A030308(n, k)}. - Philippe Deléham, Oct 14 2011
From Hieronymus Fischer, Jun 10 2012: (Start)
a(n) = Sum_{j = 1..m+1} (floor(n/2^j + 1/2) - floor(n/2^j)), where m = floor(log_2(n)).
General formulas for the number of digits >= d in the base p representation of n, where 1 <= d < p: a(n) = Sum_{j = 1..m+1} (floor(n/p^j + (p-d)/p) - floor(n/p^j)), where m=floor(log_p(n)); g.f.: g(x) = (1/(1-x))*Sum_{j>=0} (x^(d*p^j) - x^(p*p^j))/(1-x^(p*p^j)). (End)
a(n) = A213629(n, 1) for n > 0. - Reinhard Zumkeller, Jul 04 2012
a(n) = A240857(n,n). - Reinhard Zumkeller, Apr 14 2014
a(n) = log_2(C(2*n,n) - (C(2*n,n) AND C(2*n,n)-1)). - Gary Detlefs, Jul 10 2014
Sum_{n >= 1} a(n)/2n(2n+1) = (gamma + log(4/Pi))/2 = A344716, where gamma is Euler's constant A001620; see Sondow 2005, 2010 and Allouche, Shallit, Sondow 2007. - Jonathan Sondow, Mar 21 2015
For any integer base b >= 2, the sum of digits s_b(n) of expansion base b of n is the solution of this recurrence relation: s_b(n) = 0 if n = 0 and s_b(n) = s_b(floor(n/b)) + (n mod b). Thus, a(n) satisfies: a(n) = 0 if n = 0 and a(n) = a(floor(n/2)) + (n mod 2). This easily yields a(n) = Sum_{i = 0..floor(log_2(n))} (floor(n/2^i) mod 2). From that one can compute a(n) = n - Sum_{i = 1..floor(log_2(n))} floor(n/2^i). - Marek A. Suchenek, Mar 31 2016
Sum_{k>=1} a(k)/2^k = 2 * Sum_{k >= 0} 1/(2^(2^k)+1) = 2 * A051158. - Amiram Eldar, May 15 2020
Sum_{k>=1} a(k)/(k*(k+1)) = A016627 = log(4). - Bernard Schott, Sep 16 2020
a(m*(2^n-1)) >= n. Equality holds when 2^n-1 >= A000265(m), but also in some other cases, e.g., a(11*(2^2-1)) = 2 and a(19*(2^3-1)) = 3. - Pontus von Brömssen, Dec 13 2020
G.f.: A(x) satisfies A(x) = (1+x)*A(x^2) + x/(1-x^2). - Akshat Kumar, Nov 04 2023

A156552 Unary-encoded compressed factorization of natural numbers.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 8, 7, 6, 9, 16, 11, 32, 17, 10, 15, 64, 13, 128, 19, 18, 33, 256, 23, 12, 65, 14, 35, 512, 21, 1024, 31, 34, 129, 20, 27, 2048, 257, 66, 39, 4096, 37, 8192, 67, 22, 513, 16384, 47, 24, 25, 130, 131, 32768, 29, 36, 71, 258, 1025, 65536, 43, 131072, 2049, 38, 63, 68, 69, 262144

Offset: 1

Leonid Broukhis, Feb 09 2009

The primes become the powers of 2 (2 -> 1, 3 -> 2, 5 -> 4, 7 -> 8); the composite numbers are formed by taking the values for the factors in the increasing order, multiplying them by the consecutive powers of 2, and summing. See the Example section.
From Antti Karttunen, Jun 27 2014: (Start)
The odd bisection (containing even terms) halved gives A244153.
The even bisection (containing odd terms), when one is subtracted from each and halved, gives this sequence back.
(End)
Question: Are there any other solutions that would satisfy the recurrence r(1) = 0; and for n > 1, r(n) = Sum_{d|n, d>1} 2^A033265(r(d)), apart from simple variants 2^k * A156552(n)? See also A297112, A297113. - Antti Karttunen, Dec 30 2017

			For 84 = 2*2*3*7 -> 1*1 + 1*2 + 2*4 + 8*8 =  75.
For 105 = 3*5*7 -> 2*1 + 4*2 + 8*4 = 42.
For 137 = p_33 -> 2^32 = 4294967296.
For 420 = 2*2*3*5*7 -> 1*1 + 1*2 + 2*4 + 4*8 + 8*16 = 171.
For 147 = 3*7*7 = p_2 * p_4 * p_4 -> 2*1 + 8*2 + 8*4 = 50.

David A. Corneth, Table of n, a(n) for n = 1..10000 (first 1024 terms from Antti Karttunen)
Hans Havermann, Factorization of the first 10000 terms, in format [[primes], [exponents]]
A puzzle by Sergey Orlov (in Russian)
Index entries for sequences related to binary expansion of n
Index entries for sequences that are permutations of the natural numbers
Index entries for sequences computed from indices in prime factorization

One less than A005941.
Inverse permutation: A005940 with starting offset 0 instead of 1.
Cf. A000079, A000120, A001222, A052126, A054429, A061395, A064216, A064989, A003188, A243071, A243065-A243066, A244153, A243354, A112798, A125106, A056239, A161511.
Cf. also A297106, A297112 (Möbius transform), A297113, A153013, A290308, A300827, A323243, A323244, A323247, A324201, A324812 (n for which a(n) is a square), A324813, A324822, A324823, A324398, A324713, A324815, A324819, A324865, A324866, A324867.
Other related permutations: A253551, A253792, A253564, A253791, A277195, A297163, A297164, A297165, A297166, A302023, A305418, A322863, A322864.

Table[Floor@ Total@ Flatten@ MapIndexed[#1 2^(#2 - 1) &, Flatten[ Table[2^(PrimePi@ #1 - 1), {#2}] & @@@ FactorInteger@ n]], {n, 67}] (* Michael De Vlieger, Sep 08 2016 *)

a(n) = {my(f = factor(n), p2 = 1, res = 0); for(i = 1, #f~, p = 1 << (primepi(f[i, 1]) - 1); res += (p * p2 * (2^(f[i, 2]) - 1)); p2 <<= f[i, 2]); res}; \\ David A. Corneth, Mar 08 2019

A064989(n) = {my(f); f = factor(n); if((n>1 && f[1,1]==2), f[1,2] = 0); for (i=1, #f~, f[i,1] = precprime(f[i,1]-1)); factorback(f)};
A156552(n) = if(1==n, 0, if(!(n%2), 1+(2*A156552(n/2)), 2*A156552(A064989(n)))); \\ (based on the given recurrence) - Antti Karttunen, Mar 08 2019

# Program corrected per instructions from Leonid Broukhis. - Antti Karttunen, Jun 26 2014
# However, it gives correct answers only up to n=136, before corruption by a wrap-around effect.
# Note that the correct answer for n=137 is A156552(137) = 4294967296.
$max = $ARGV[0];
$pow = 0;
foreach $i (2..$max) {
@a = split(/ /, `factor $i`);
shift @a;
$shift = 0;
$cur = 0;
while ($n = int shift @a) {
$prime{$n} = 1 << $pow++ if !defined($prime{$n});
$cur |= $prime{$n} << $shift++;
}
print "$cur, ";
}
print "\n";
(Scheme, with memoization-macro definec from Antti Karttunen's IntSeq-library, two different implementations)
(definec (A156552 n) (cond ((= n 1) 0) (else (+ (A000079 (+ -2 (A001222 n) (A061395 n))) (A156552 (A052126 n))))))
(definec (A156552 n) (cond ((= 1 n) (- n 1)) ((even? n) (+ 1 (* 2 (A156552 (/ n 2))))) (else (* 2 (A156552 (A064989 n))))))
;; Antti Karttunen, Jun 26 2014

from sympy import primepi, factorint
def A156552(n): return sum((1<Chai Wah Wu, Mar 10 2023

From Antti Karttunen, Jun 26 2014: (Start)
a(1) = 0, a(n) = A000079(A001222(n)+A061395(n)-2) + a(A052126(n)).
a(1) = 0, a(2n) = 1+2*a(n), a(2n+1) = 2*a(A064989(2n+1)). [Compare to the entanglement recurrence A243071].
For n >= 0, a(2n+1) = 2*A244153(n+1). [Follows from the latter clause of the above formula.]
a(n) = A005941(n) - 1.
As a composition of related permutations:
a(n) = A003188(A243354(n)).
a(n) = A054429(A243071(n)).
For all n >= 1, A005940(1+a(n)) = n and for all n >= 0, a(A005940(n+1)) = n. [The offset-0 version of A005940 works as an inverse for this permutation.]
This permutations also maps between the partition-lists A112798 and A125106:
A056239(n) = A161511(a(n)). [The sums of parts of each partition (the total sizes).]
A003963(n) = A243499(a(n)). [And also the products of those parts.]
(End)
From Antti Karttunen, Oct 09 2016: (Start)
A161511(a(n)) = A056239(n).
A029837(1+a(n)) = A252464(n). [Binary width of terms.]
A080791(a(n)) = A252735(n). [Number of nonleading 0-bits.]
A000120(a(n)) = A001222(n). [Binary weight.]
For all n >= 2, A001511(a(n)) = A055396(n).
For all n >= 2, A000120(a(n))-1 = A252736(n). [Binary weight minus one.]
A252750(a(n)) = A252748(n).
a(A250246(n)) = A252754(n).
a(A005117(n)) = A277010(n). [Maps squarefree numbers to a permutation of A003714, fibbinary numbers.]
A085357(a(n)) = A008966(n). [Ditto for their characteristic functions.]
For all n >= 0:
a(A276076(n)) = A277012(n).
a(A276086(n)) = A277022(n).
a(A260443(n)) = A277020(n).
(End)
From Antti Karttunen, Dec 30 2017: (Start)
For n > 1, a(n) = Sum_{d|n, d>1} 2^A033265(a(d)). [See comments.]
More linking formulas:
A106737(a(n)) = A000005(n).
A290077(a(n)) = A000010(n).
A069010(a(n)) = A001221(n).
A136277(a(n)) = A181591(n).
A132971(a(n)) = A008683(n).
A106400(a(n)) = A008836(n).
A268411(a(n)) = A092248(n).
A037011(a(n)) = A010052(n) [conjectured, depends on the exact definition of A037011].
A278161(a(n)) = A046951(n).
A001316(a(n)) = A061142(n).
A277561(a(n)) = A034444(n).
A286575(a(n)) = A037445(n).
A246029(a(n)) = A181819(n).
A278159(a(n)) = A124859(n).
A246660(a(n)) = A112624(n).
A246596(a(n)) = A069739(n).
A295896(a(n)) = A053866(n).
A295875(a(n)) = A295297(n).
A284569(a(n)) = A072411(n).
A286574(a(n)) = A064547(n).
A048735(a(n)) = A292380(n).
A292272(a(n)) = A292382(n).
A244154(a(n)) = A048673(n), a(A064216(n)) = A244153(n).
A279344(a(n)) = A279339(n), a(A279338(n)) = A279343(n).
a(A277324(n)) = A277189(n).
A037800(a(n)) = A297155(n).
For n > 1, A033265(a(n)) = 1+A297113(n).
(End)
From Antti Karttunen, Mar 08 2019: (Start)
a(n) = A048675(n) + A323905(n).
a(A324201(n)) = A000396(n), provided there are no odd perfect numbers.
The following sequences are derived from or related to the base-2 expansion of a(n):
A000265(a(n)) = A322993(n).
A002487(a(n)) = A323902(n).
A005187(a(n)) = A323247(n).
A324288(a(n)) = A324116(n).
A323505(a(n)) = A323508(n).
A079559(a(n)) = A323512(n).
A085405(a(n)) = A323239(n).
The following sequences are obtained by applying to a(n) a function that depends on the prime factorization of its argument, which goes "against the grain" because a(n) is the binary code of the factorization of n, which in these cases is then factored again:
A000203(a(n)) = A323243(n).
A033879(a(n)) = A323244(n) = 2*a(n) - A323243(n),
A294898(a(n)) = A323248(n).
A000005(a(n)) = A324105(n).
A000010(a(n)) = A324104(n).
A083254(a(n)) = A324103(n).
A001227(a(n)) = A324117(n).
A000593(a(n)) = A324118(n).
A001221(a(n)) = A324119(n).
A009194(a(n)) = A324396(n).
A318458(a(n)) = A324398(n).
A192895(a(n)) = A324100(n).
A106315(a(n)) = A324051(n).
A010052(a(n)) = A324822(n).
A053866(a(n)) = A324823(n).
A001065(a(n)) = A324865(n) = A323243(n) - a(n),
A318456(a(n)) = A324866(n) = A324865(n) OR a(n),
A318457(a(n)) = A324867(n) = A324865(n) XOR a(n),
A318458(a(n)) = A324398(n) = A324865(n) AND a(n),
A318466(a(n)) = A324819(n) = A323243(n) OR 2*a(n),
A318467(a(n)) = A324713(n) = A323243(n) XOR 2*a(n),
A318468(a(n)) = A324815(n) = A323243(n) AND 2*a(n).
(End)

More terms from Antti Karttunen, Jun 28 2014

A023416 Number of 0's in binary expansion of n.

Original entry on oeis.org

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

Offset: 0

David W. Wilson

Another version (A080791) has a(0) = 0.

N. J. A. Sloane, Table of n, a(n) for n = 0..10000
Franklin T. Adams-Watters and Frank Ruskey, Generating Functions for the Digital Sum and Other Digit Counting Sequences, JIS 12 (2009) 09.5.6.
Jean-Paul Allouche and Jeffrey O. Shallit, Infinite products associated with counting blocks in binary strings, J. London Math. Soc.39 (1989) 193-204.
Jean-Paul Allouche and Jeffrey Shallit, Sums of digits and the Hurwitz zeta function, in: K. Nagasaka and E. Fouvry (eds.), Analytic Number Theory, Lecture Notes in Mathematics, Vol. 1434, Springer, Berlin, Heidelberg, 1990, pp. 19-30.
Alex S. A. Alochukwu, Audace A. V. Dossou-Olory, Fadekemi J. Osaye, Valisoa R. M. Rakotonarivo, Shashank Ravichandran, Sarah J. Selkirk, Hua Wang, and Hays Whitlatch, Characterization of Trees with Maximum Security, arXiv:2411.19188 [math.CO], 2024. See p. 12.
Khodabakhsh Hessami Pilehrood and Tatiana Hessami Pilehrood, Vacca-Type Series for Values of the Generalized Euler Constant Function and its Derivative, J. Integer Sequences, 13 (2010), Article 10.7.3.
Vladimir Shevelev, The number of permutations with prescribed up-down structure as a function of two variables, INTEGERS, Vol. 12 (2012), #A1. - From _N. J. A. Sloane_, Feb 07 2013
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions, 2004.
Ralf Stephan, Table of generating functions.
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
Index entries for sequences related to binary expansion of n

The basic sequences concerning the binary expansion of n are A000120, A000788, A000069, A001969, A023416, A059015, A070939, A083652. Partial sums see A059015.
With initial zero and shifted right, same as A080791.
Cf. A055641 (for base 10), A188859.

a023416 0 = 1
a023416 1 = 0
a023416 n = a023416 n' + 1 - m where (n', m) = divMod n 2
a023416_list = 1 : c [0] where c (z:zs) = z : c (zs ++ [z+1,z])
-- Reinhard Zumkeller, Feb 19 2012, Jun 16 2011, Mar 07 2011

A023416 := proc(n)
    if n = 0 then
        1;
    else
        add(1-e,e=convert(n,base,2)) ;
    end if;
end proc: # R. J. Mathar, Jul 21 2012

Table[ Count[ IntegerDigits[n, 2], 0], {n, 0, 100} ]
DigitCount[Range[0,110],2,0] (* Harvey P. Dale, Jan 10 2013 *)

a(n)=if(n==0,1,n=binary(n); sum(i=1, #n, !n[i])) \\ Charles R Greathouse IV, Jun 10 2011

a(n)=if(n==0,1,#binary(n)-hammingweight(n)) \\ Charles R Greathouse IV, Nov 20 2012

a(n) = if(n == 0, 1, 1+logint(n,2) - hammingweight(n))  \\ Gheorghe Coserea, Sep 01 2015

def A023416(n): return n.bit_length()-n.bit_count() if n else 1 # Chai Wah Wu, Mar 13 2023

a(n) = 1, if n = 0; 0, if n = 1; a(n/2)+1 if n even; a((n-1)/2) if n odd.
a(n) = 1 - (n mod 2) + a(floor(n/2)). - Marc LeBrun, Jul 12 2001
G.f.: 1 + 1/(1-x) * Sum_{k>=0} x^(2^(k+1))/(1+x^2^k). - Ralf Stephan, Apr 15 2002
a(n) = A070939(n) - A000120(n).
a(n) = A008687(n+1) - 1.
a(n) = A000120(A035327(n)).
From Hieronymus Fischer, Jun 12 2012: (Start)
a(n) = m + 1 + Sum_{j=1..m+1} (floor(n/2^j) - floor(n/2^j + 1/2)), where m=floor(log_2(n)).
General formulas for the number of digits <= d in the base p representation n, where 0 <= d < p.
a(n) = m + 1 + Sum_{j=1..m+1} (floor(n/p^j) - floor(n/p^j + (p-d-1)/p)), where m=floor(log_p(n)).
G.f.: 1 + (1/(1-x))*Sum_{j>=0} ((1-x^(d*p^j))*x^p^j + (1-x^p^j)*x^p^(j+1)/(1-x^p^(j+1))). (End)
Product_{n>=1} ((2*n)/(2*n+1))^((-1)^a(n)) = sqrt(2)/2 (A010503) (see Allouche & Shallit link). - Michel Marcus, Aug 31 2014
Sum_{n>=1} a(n)/(n*(n+1)) = 2 - 2*log(2) (A188859) (Allouche and Shallit, 1990). - Amiram Eldar, Jun 01 2021

cp's OEIS Frontend

A233271 a(0)=0; thereafter a(n+1) = a(n) + 1 + number of 0's in binary representation of a(n), counted with A080791.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A233272 a(n) = n + 1 + number of nonleading zeros in binary representation of n (A080791).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Scheme

Formula

A285716 a(n) = A080791(A245611(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Scheme

Formula

A267109 a(n) = A080791(A267111(n)).

Views

Author

Keywords

Links

Crossrefs

Formula

A265336 Number of nonleading 0-bits in bijective base-3 reversal of n: a(n) = A080791(A263273(n)).

Views

Author

Keywords

Links

Crossrefs

Formula

A342102 Lexicographically latest sequence of distinct nonnegative integers such that for any n >= 0, {A000120(n), A080791(n)} = {A000120(a(n)), A080791(a(n))}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A089263 First differences of A080791.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

PARI

Formula

Extensions

A000120 1's-counting sequence: number of 1's in binary expansion of n (or the binary weight of n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs