A115419 -id:A115419 - cp's OEIS frontend

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

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

A042964 Numbers that are congruent to 2 or 3 mod 4.

Original entry on oeis.org

2, 3, 6, 7, 10, 11, 14, 15, 18, 19, 22, 23, 26, 27, 30, 31, 34, 35, 38, 39, 42, 43, 46, 47, 50, 51, 54, 55, 58, 59, 62, 63, 66, 67, 70, 71, 74, 75, 78, 79, 82, 83, 86, 87, 90, 91, 94, 95, 98, 99, 102, 103, 106, 107, 110, 111, 114, 115, 118, 119, 122, 123, 126, 127

Offset: 1

N. J. A. Sloane

Also numbers m such that binomial(m+2, m) mod 2 = 0. - Hieronymus Fischer, Oct 20 2007
Also numbers m such that floor(1+(m/2)) mod 2 = 0. - Hieronymus Fischer, Oct 20 2007
Partial sums of the sequence 2, 1, 3, 1, 3, 1, 3, 1, 3, 1, ... which has period 2. - Hieronymus Fischer, Oct 20 2007
In groups of four add and divide by two the odd and even numbers. - George E. Antoniou, Dec 12 2001
From Jeremy Gardiner, Jan 22 2006: (Start)
Comments on the "mystery calculator". There are 6 cards.
Card 0: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, ... (A005408 sequence).
Card 1: 2, 3, 6, 7, 10, 11, 14, 15, 18, 19, 22, 23, 26, 27, 30, 31, 34, 35, 38, 39, ... (this sequence).
Card 2: 4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23, 28, 29, 30, 31, 36, 37, 38, 39, ... (A047566).
Card 3: 8, 9, 10, 11, 12, 13, 14, 15, 24, 25, 26, 27, 28, 29, 30, 31, 40, 41, 42, ... (A115419).
Card 4: 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 48, 49, 50, ... (A115420).
Card 5: 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, ... (A115421).
The trick: You secretly select a number between 1 and 63 from one of the cards. You indicate to me the cards on which that number appears; I tell you the number you selected!
The solution: I add together the first term from each of the indicated cards. The total equals the selected number. The numbers in each sequence all have a "1" in the same position in their binary expansion. Example: You indicate cards 1, 3 and 5. Your selected number is 2 + 8 + 32 = 42.
Numbers having a 1 in position 1 of their binary expansion. One of the mystery calculator sequences: A005408, A042964, A047566, A115419, A115420, A115421. (End)
Complement of A042948. - Reinhard Zumkeller, Oct 03 2008
Also the 2nd Witt transform of A040000 [Moree]. - R. J. Mathar, Nov 08 2008
In general, sequences of numbers congruent to {a,a+i} mod k will have a closed form of (k-2*i)*(2*n-1+(-1)^n)/4+i*n+a, from offset 0. - Gary Detlefs, Oct 29 2013
Union of A004767 and A016825; Fixed points of A098180. - Wesley Ivan Hurt, Jan 14 2014, Oct 13 2015

David Lovler, Table of n, a(n) for n = 1..10000
Maths Magic, Mystery Calculator.
Pieter Moree, The formal series Witt transform, Discr. Math. no. 295 vol. 1-3 (2005) 143-160.
Index entries for linear recurrences with constant coefficients, signature (1,1,-1).

Cf. A000040, A133620, A133621, A133622, A133630, A133635.
Cf. A133872, A133882, A133890, A133900, A133910.
Card trick: A005408, A047566, A115419, A115420, A115421.
Cf. A004767, A016825 A040000, A042948, A047406, A098180.

[2*n+((-1)^(n-1)-1)/2 : n in [1..100]]; // Wesley Ivan Hurt, Oct 13 2015

[n: n in [1..150] | n mod 4 in [2, 3]]; // Vincenzo Librandi, Oct 13 2015

A042964:=n->2*n+((-1)^(n-1)-1)/2; seq(A042964(n), n=1..100); # Wesley Ivan Hurt, Jan 07 2014

Flatten[Table[4n + {2, 3}, {n, 0, 31}]] (* Alonso del Arte, Feb 07 2013 *)
Select[Range[200],MemberQ[{2,3},Mod[#,4]]&] (* or *) LinearRecurrence[ {1,1,-1},{2,3,6},90] (* Harvey P. Dale, Nov 28 2018 *)

PARI
```
a(n)=2*n+2-n%2
```

Vec((2+x+x^2)/((1-x)*(1-x^2)) + O(x^100)) \\ Altug Alkan, Oct 13 2015

a(n) = A047406(n)/2.
From Michael Somos, Jan 12 2000: (Start)
G.f.: x*(2+x+x^2)/((1-x)*(1-x^2)).
a(n) = a(n-1) + 2 + (-1)^n. (End)
a(n) = 2n if n is odd, otherwise n = 2n - 1. - Amarnath Murthy, Oct 16 2003
a(n) = (3 + (-1)^(n-1))/2 + 2*(n-1) = 2n + 2 - (n mod 2). - Hieronymus Fischer, Oct 20 2007
A133872(a(n)) = 0. - Reinhard Zumkeller, Oct 03 2008
a(n) = 4*n - a(n-1) - 3 (with a(1) = 2). - Vincenzo Librandi, Nov 17 2010
a(n) = 2*n + ((-1)^(n-1) - 1)/2. - Gary Detlefs, Oct 29 2013
Sum_{n>=1} (-1)^(n+1)/a(n) = Pi/8 - log(2)/4. - Amiram Eldar, Dec 05 2021
E.g.f.: 1 + ((4*x - 1)*exp(x) - exp(-x))/2. - David Lovler, Aug 08 2022

Edited by N. J. A. Sloane, Jun 30 2008 at the suggestion of R. J. Mathar

Corrected by Jaroslav Krizek, Dec 18 2009

A047566 Numbers that are congruent to {4, 5, 6, 7} mod 8.

Original entry on oeis.org

4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23, 28, 29, 30, 31, 36, 37, 38, 39, 44, 45, 46, 47, 52, 53, 54, 55, 60, 61, 62, 63, 68, 69, 70, 71, 76, 77, 78, 79, 84, 85, 86, 87, 92, 93, 94, 95, 100, 101, 102, 103, 108, 109

Offset: 1

N. J. A. Sloane

Numbers having a 1 in position 2 of their binary expansion. One of the mystery calculator sequences: A005408, A042964, A047566, A115419, A115420, A115421. - Jeremy Gardiner, Jan 22 2006

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
Maths Magic, Mystery Calculator.
Index entries for linear recurrences with constant coefficients, signature (1,0,0,1,-1).

Cf. A003628 (primes).

Mystery calculator sequences: A005408, A042964, A047566, A115419, A115420, A115421.

a047566 n = a047566_list !! (n-1)
a047566_list = [n | n <- [1..], mod n 8 > 3]
-- Reinhard Zumkeller, Dec 29 2012

A047566:= n-> n+3 + 4*iquo(n-1, 4):
seq(A047566(n), n=1..100);  # Alois P. Heinz, Aug 22 2011

Flatten[# + {4, 5, 6, 7}&/@(8Range[0, 14])] (* Harvey P. Dale, Feb 02 2011 *)

G.f.: x*(4+x+x^2+x^3+x^4) / ( (1+x)*(1+x^2)*(x-1)^2 ). - R. J. Mathar, Oct 08 2011
From Wesley Ivan Hurt, May 19 2016: (Start)
a(n) = a(n-1)+a(n-4)-a(n-5) for n>5.
a(n) = (4*n+1-(-1)^n-(-1)^((n+1)/2)-(-1)^(n/2)-(-1)^(-(n+1)/2)-(-1)^(-n/2))/2. (End)
E.g.f.: 1 + sin(x) - cos(x) + sinh(x) + 2*x*exp(x). - Ilya Gutkovskiy, May 20 2016
Sum_{n>=1} (-1)^(n+1)/a(n) = (2*sqrt(2)-1)*Pi/16 - 3*log(2)/8. - Amiram Eldar, Dec 26 2021

A368533 Numbers whose binary indices are all squarefree.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 16, 17, 18, 19, 20, 21, 22, 23, 32, 33, 34, 35, 36, 37, 38, 39, 48, 49, 50, 51, 52, 53, 54, 55, 64, 65, 66, 67, 68, 69, 70, 71, 80, 81, 82, 83, 84, 85, 86, 87, 96, 97, 98, 99, 100, 101, 102, 103, 112, 113, 114, 115, 116, 117, 118, 119, 512

Offset: 1

Gus Wiseman, Mar 23 2024

The complement first differs from A115419 in having 128.

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.

			The terms together with their binary expansions and binary indices begin:
    0:       0 ~ {}
    1:       1 ~ {1}
    2:      10 ~ {2}
    3:      11 ~ {1,2}
    4:     100 ~ {3}
    5:     101 ~ {1,3}
    6:     110 ~ {2,3}
    7:     111 ~ {1,2,3}
   16:   10000 ~ {5}
   17:   10001 ~ {1,5}
   18:   10010 ~ {2,5}
   19:   10011 ~ {1,2,5}
   20:   10100 ~ {3,5}
   21:   10101 ~ {1,3,5}
   22:   10110 ~ {2,3,5}
   23:   10111 ~ {1,2,3,5}
   32:  100000 ~ {6}
   33:  100001 ~ {1,6}
   34:  100010 ~ {2,6}
   35:  100011 ~ {1,2,6}
   36:  100100 ~ {3,6}
   37:  100101 ~ {1,3,6}
   38:  100110 ~ {2,3,6}

Set multipartitions: A049311, A050320, A089259, A116540.
For prime indices instead of binary indices we have A302478.
The case of prime binary indices is A326782.
The case of squarefree product is A371289.
For prime-power product we have A371290.
For nonprime binary indices we have A371443, composite A371444.
The semiprime case is A371453, squarefree case of A371454.
A005117 lists squarefree numbers.
A048793 lists binary indices, A000120 length, A272020 reverse, A029931 sum.
A070939 gives length of binary expansion.
A096111 gives product of binary indices.
Cf. A000040, A001222, A087086, A296119, A326031, A367905, A368109, A371450.

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
Select[Range[0,100],And@@SquareFreeQ/@bpe[#]&]

from math import isqrt
from sympy import mobius
def A368533(n):
    def f(x,n): return int(n+x-sum(mobius(k)*(x//k**2) for k in range(1, isqrt(x)+1)))
    def A005117(n):
        m, k = n, f(n,n)
        while m != k: m, k = k, f(k,n)
        return m
    return sum(1<<A005117(i)-1 for i, j in enumerate(bin(n-1)[:1:-1],1) if j=='1') # Chai Wah Wu, Oct 24 2024

A115420 Numbers having a 1 in position 4 of their binary expansion.

Original entry on oeis.org

16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127

Offset: 1

Jeremy Gardiner, Jan 22 2006

One of the mystery calculator sequences: A005408, A042964, A047566, A115419, A115420, A115421.

			a(1) = 16 = 10000 in binary.

Edd Mann, Mystery Calculator.

Cf. A005408, A042964, A047566, A115419, A115421.

a:= n-> n+15 + 16*iquo(n-1, 16):
seq(a(n), n=1..100);  # Alois P. Heinz, Aug 22 2011

def A115420(n): return ((n-1<<1)&-15|16)+(n-1&15) # Chai Wah Wu, Mar 28 2024

A115421 Numbers having a 1 in position 5 of their binary expansion.

Original entry on oeis.org

32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124

Offset: 1

Jeremy Gardiner, Jan 22 2006

One of the mystery calculator sequences: A005408, A042964, A047566, A115419, A115420, A115421.

			a(1) = 32 = 100000 in binary.

Robert Israel, Table of n, a(n) for n = 1..10000
Edd Mann, Mystery Calculator.

Cf. A005408, A042964, A047566, A115419, A115420.

a:= n-> n+31 + 32*iquo(n-1, 32):
seq(a(n), n=1..100);  # Alois P. Heinz, Aug 22 2011

Select[Range[256], BitAnd[#, 32] == 32 &] (* Alonso del Arte, Nov 14 2016 *)

def A115421(n): return ((n-1<<1)&-31|32)+(n-1&31) # Chai Wah Wu, Mar 28 2024

From Robert Israel, Nov 14 2016: (Start)
a(n + 32) = a(n) + 64.
O.g.f.: (31 + (1 - x^33)/(1 - x))*x/((1 - x)*(1 - x^32)). (End)

A224195 Ordered sequence of numbers of form (2^n - 1)*2^m + 1 where n >= 1, m >= 1.

Original entry on oeis.org

3, 5, 7, 9, 13, 15, 17, 25, 29, 31, 33, 49, 57, 61, 63, 65, 97, 113, 121, 125, 127, 129, 193, 225, 241, 249, 253, 255, 257, 385, 449, 481, 497, 505, 509, 511, 513, 769, 897, 961, 993, 1009, 1017, 1021, 1023, 1025, 1537, 1793, 1921, 1985, 2017, 2033, 2041, 2045, 2047

Offset: 1

Brad Clardy, Apr 01 2013

The table is constructed so that row labels are 2^n - 1, and column labels are 2^n. The body of the table is the row*col + 1. A MAGMA program is provided that generates the numbers in a table format. The sequence is read along the antidiagonals starting from the top left corner.
All of these numbers have the following property:
   let m be a member of A(n),
   if a sequence B(n) = all i such that i XOR (m - 1) = i - (m - 1), then
   the differences between successive members of B(n) is a repeating series
   of 1's with the last difference in the pattern m. The number of ones in
   the pattern is 2^j - 1, where j is the column index.
As an example consider A(4) which is 9,
   the sequence B(n) where i XOR 8 = i - 8 starts as:
   8, 9, 10, 11, 12, 13, 14, 15, 24... (A115419)
   with successive differences of:
   1, 1, 1, 1, 1, 1, 1, 9.
The main diagonal is the 6th cyclotomic polynomial evaluated at powers of two (A020515).
The formula for diagonals above the main diagonal
  2^(2*n+1) - 2^(n + (a+1)/2) + 1 n>=(a+1)/2 a=odd number above diagonal
  2^(2*n) - 2^(n  + (b/2)) + 1    n>=(b/2)+1 b=even number above diagonal
The formulas for diagonals below the main diagonal
  2^(2*n+1) - 2^(n + 1 -(a+1)/2) + 1 n>=(a+1)/2 a=odd number below diagonal
  2^(2*n) - 2^(n - (b/2)) + 1       n>=(b/2)+1 b=even number below diagonal
Primes of this sequence are in A152449.

			Using the lexicographic ordering of A057555 the sequence is:
A(n) = Table(i,j) with (i,j)=(1,1),(1,2),(2,1),(1,3),(2,2),(3,1)...
  +1  |    2    4     8    16    32     64    128    256     512    1024 ...
  ----|-----------------------------------------------------------------
  1   |    3    5     9    17    33     65    129    257     513    1025
  3   |    7   13    25    49    97    193    385    769    1537    3073
  7   |   15   29    57   113   225    449    897   1793    3585    7169
  15  |   31   61   121   241   481    961   1921   3841    7681   15361
  31  |   63  125   249   497   993   1985   3969   7937   15873   31745
  63  |  127  253   505  1009  2017   4033   8065  16129   32257   64513
  127 |  255  509  1017  2033  4065   8129  16257  32513   65025  130049
  255 |  511 1021  2041  4081  8161  16321  32641  65281  130561  261121
  511 | 1023 2045  4089  8177 16353  32705  65409 130817  261633  523265
  1023| 2047 4093  8185 16369 32737  65473 130945 261889  523777 1047553
  ...

Brad Clardy, Table of n, a(n) for n = 1..1000

Cf. A081118, A152449 (primes), A057555 (lexicographic ordering), A115419 (example).
Rows: A000051(i=1), A181565(2), A083686(3), A195744(4), A206371(5), A196657(6).
Cols: A000225(j=1), A036563(2), A048490(3), A176303 (7 offset of 8).
Diagonals: A020515 (main), A092440, A060867 (above), A134169 (below).

//program generates values in a table form
for i:=1 to 10 do
    m:=2^i - 1;
    m,[ m*2^n +1 : n in [1..10]];
end for;
//program generates sequence in lexicographic ordering of A057555, read
//along antidiagonals from top. Primes in the sequence are marked with *.
for i:=2 to 18 do
    for j:=1 to i-1 do
       m:=2^j -1;
       k:=m*2^(i-j) + 1;
       if IsPrime(k) then k,"*";
          else k;
       end if;;
    end for;
end for;

Table[(2^j-1)*2^(i-j+1) + 1, {i, 10}, {j, i}] (* Paolo Xausa, Apr 02 2024 *)

a(n) = (2^(A057555(2*n-1)) - 1)*2^(A057555(2*n)) + 1 for n>=1. [corrected by Jason Yuen, Feb 22 2025]

a(n) = A081118(n)+2; a(n)=(2^i-1)*2^j+1, where i=n-t*(t+1)/2, j=(t*t+3*t+4)/2-n, t=floor((-1+sqrt(8*n-7))/2). - Boris Putievskiy, Apr 04 2013

A214863 Numbers n such that n XOR 11 = n - 11.

Original entry on oeis.org

11, 15, 27, 31, 43, 47, 59, 63, 75, 79, 91, 95, 107, 111, 123, 127, 139, 143, 155, 159, 171, 175, 187, 191, 203, 207, 219, 223, 235, 239, 251, 255, 267, 271, 283, 287, 299, 303, 315, 319, 331, 335, 347, 351, 363

Offset: 1

Brad Clardy, Mar 09 2013

Links to sequences of the form n XOR m = n - m are found below with the value of m specified.

Index entries for linear recurrences with constant coefficients, signature (1,1,-1).

Cf. A005408 (m=1), A042964 (m=2), A131098 (m=3), A047566 (m=4), A047550 (m=5), A047589 (m=6), A004771 (m=7), A115419 (m=8), A214865 (m=9), A214864 (m=10), A133894 (m=12), A125169 (m=15).

Cf. also A016825, A168392.

XOR := func;
m:=11;
for n in [1 .. 500] do
      if (XOR(n, m) eq n-m) then n; end if;
end for;

Select[Range[400],BitXor[#,11]==#-11&] (* or *) LinearRecurrence[{1,1,-1},{11,15,27},50] (* Harvey P. Dale, Jun 05 2021 *)

a(n)= 1+8*n-2*(-1)^n.
a(n)=A016825(n) + A168392(n) +  for n>0.
G.f. x*(11+4*x+x^2) / ( (1+x)*(x-1)^2 ). - R. J. Mathar, Mar 10 2013

cp's OEIS Frontend

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

Fortran

Haskell

Haskell

Magma

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

PARI

PARI

Python

Python

Python

Python

SageMath

SageMath

Scala

Formula

A042964 Numbers that are congruent to 2 or 3 mod 4.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Magma

Maple

Mathematica

PARI

PARI

Formula

Extensions

A047566 Numbers that are congruent to {4, 5, 6, 7} mod 8.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

A368533 Numbers whose binary indices are all squarefree.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

A115420 Numbers having a 1 in position 4 of their binary expansion.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple