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

A007814 Exponent of highest power of 2 dividing n, a.k.a. the binary carry sequence, the ruler sequence, or the 2-adic valuation of n.

Original entry on oeis.org

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

Offset: 1

John Tromp, Dec 11 1996

This sequence is an exception to my usual rule that when every other term of a sequence is 0 then those 0's should be omitted. In this case we would get A001511. - N. J. A. Sloane
To construct the sequence: start with 0,1, concatenate to get 0,1,0,1. Add + 1 to last term gives 0,1,0,2. Concatenate those 4 terms to get 0,1,0,2,0,1,0,2. Add + 1 to last term etc. - Benoit Cloitre, Mar 06 2003
The sequence is invariant under the following two transformations: increment every element by one (1, 2, 1, 3, 1, 2, 1, 4, ...), put a zero in front and between adjacent elements (0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, ...). The intermediate result is A001511. - Ralf Hinze (ralf(AT)informatik.uni-bonn.de), Aug 26 2003
Fixed point of the morphism 0->01, 1->02, 2->03, 3->04, ..., n->0(n+1), ..., starting from a(1) = 0. - Philippe Deléham, Mar 15 2004
Fixed point of the morphism 0->010, 1->2, 2->3, ..., n->(n+1), .... - Joerg Arndt, Apr 29 2014
a(n) is also the number of times to repeat a step on an even number in the hailstone sequence referenced in the Collatz conjecture. - Alex T. Flood (whiteangelsgrace(AT)gmail.com), Sep 22 2006
Let F(n) be the n-th Fermat number (A000215). Then F(a(r-1)) divides F(n)+2^k for r = k mod 2^n and r != 1. - T. D. Noe, Jul 12 2007
The following relation holds: 2^A007814(n)*(2*A025480(n-1)+1) = A001477(n) = n. (See functions hd, tl and cons in [Paul Tarau 2009].)
a(n) is the number of 0's at the end of n when n is written in base 2.
a(n+1) is the number of 1's at the end of n when n is written in base 2. - M. F. Hasler, Aug 25 2012
Shows which bit to flip when creating the binary reflected Gray code (bits are numbered from the right, offset is 0). That is, A003188(n) XOR A003188(n+1) == 2^A007814(n). - Russ Cox, Dec 04 2010
The sequence is squarefree (in the sense of not containing any subsequence of the form XX) [Allouche and Shallit]. Of course it contains individual terms that are squares (such as 4). - Comment expanded by N. J. A. Sloane, Jan 28 2019
a(n) is the number of zero coefficients in the n-th Stern polynomial, A125184. - T. D. Noe, Mar 01 2011
Lemma: For n < m with r = a(n) = a(m) there exists n < k < m with a(k) > r. Proof: We have n=b2^r and m=c2^r with b < c both odd; choose an even i between them; now a(i2^r) > r and n < i2^r < m. QED. Corollary: Every finite run of consecutive integers has a unique maximum 2-adic valuation. - Jason Kimberley, Sep 09 2011
a(n-2) is the 2-adic valuation of A000166(n) for n >= 2. - Joerg Arndt, Sep 06 2014
a(n) = number of 1's in the partition having Heinz number n. We define the Heinz number of a partition p = [p_1, p_2, ..., p_r] as Product_{j=1..r} p_j-th prime (concept used by Alois P. Heinz in A215366 as an "encoding" of a partition). For example, for the partition [1, 1, 2, 4, 10] we get 2*2*3*7*29 = 2436. Example: a(24)=3; indeed, the partition having Heinz number 24 = 2*2*2*3  is [1,1,1,2]. - Emeric Deutsch, Jun 04 2015
a(n+1) is the difference between the two largest parts in the integer partition having viabin number n (0 is assumed to be a part). Example: a(20) = 2. Indeed, we have 19 = 10011_2, leading to the Ferrers board of the partition [3,1,1]. For the definition of viabin number see the comment in A290253. - Emeric Deutsch, Aug 24 2017
Apart from being squarefree, as noted above, the sequence has the property that every consecutive subsequence contains at least one number an odd number of times. - Jon Richfield, Dec 20 2018
a(n+1) is the 2-adic valuation of Sum_{e=0..n} u^e = (1 + u + u^2 + ... + u^n), for any u of the form 4k+1 (A016813). - Antti Karttunen, Aug 15 2020
{a(n)} represents the "first black hat" strategy for the game of countably infinitely many hats, with a probability of success of 1/3; cf. the Numberphile link below. - Frederic Ruget, Jun 14 2021
a(n) is the least nonnegative integer k for which there does not exist i+j=n and a(i)=a(j)=k (cf. A322523). - Rémy Sigrist and Jianing Song, Aug 23 2022

			2^3 divides 24, so a(24)=3.
From _Omar E. Pol_, Jun 12 2009: (Start)
Triangle begins:
  0;
  1,0;
  2,0,1,0;
  3,0,1,0,2,0,1,0;
  4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0;
  5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0;
  6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,...
(End)

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 27.
K. Atanassov, On the 37th and the 38th Smarandache Problems, Notes on Number Theory and Discrete Mathematics, Sophia, Bulgaria, Vol. 5 (1999), No. 2, 83-85.
Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.

T. D. Noe, Table of n, a(n) for n = 1..10000
Joerg Arndt, Subset-lex: did we miss an order?, arXiv:1405.6503 [math.CO], 2014.
K. Atanassov, On Some of Smarandache's Problems
Alain Connes, Caterina Consani, and Henri Moscovici, Zeta zeros and prolate wave operators, arXiv:2310.18423 [math.NT], 2023.
Dario T. de Castro, P-adic Order of Positive Integers via Binomial Coefficients, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 22, Paper A61, 2022.
Mathieu Guay-Paquet and Jeffrey Shallit, Avoiding Squares and Overlaps Over the Natural Numbers, (2009) Discrete Math., 309 (2009), 6245-6254.
Mathieu Guay-Paquet and Jeffrey Shallit, Avoiding Squares and Overlaps Over the Natural Numbers, arXiv:0901.1397 [math.CO], 2009.
M. Hassani, Equations and inequalities involving v_p(n!), J. Inequ. Pure Appl. Math. 6 (2005) vol. 2, #29.
A. M. Hinz, S. Klavžar, U. Milutinović, and C. Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 61. Book's website
R. Hinze, Concrete stream calculus: An extended study, J. Funct. Progr. 20 (5-6) (2010) 463-535, doi, Section 3.2.3.
Clark Kimberling, Affinely recursive sets and orderings of languages, Discrete Math., 274 (2004), 147-160.
Francis Laclé, 2-adic parity explorations of the 3n+ 1 problem, hal-03201180v2 [cs.DM], 2021.
Shuo Li, Palindromic length sequence of the ruler sequence and of the period-doubling sequence, arXiv:2007.08317 [math.CO], 2020.
Nicolas Mallet, Trial for a proof of the Syracuse conjecture, arXiv preprint arXiv:1507.05039 [math.GM], 2015.
S. Mazzanti, Plain Bases for Classes of Primitive Recursive Functions, Mathematical Logic Quarterly, 48 (2002).
Matthew Andres Moreno, Luis Zaman, and Emily Dolson, Structured Downsampling for Fast, Memory-efficient Curation of Online Data Streams, arXiv:2409.06199 [cs.DS], 2024. See p. 5.
Sascha Mücke, Coding Nuggets Faster QUBO Brute-Force Solving, TU Dortmund Univ. (Germany 2023).
S. Northshield, An Analogue of Stern's Sequence for Z[sqrt(2)], Journal of Integer Sequences, 18 (2015), #15.11.6.
Numberphile, Hat Problems - Numberphile
Giovanni Pighizzini, Limited Automata: Properties, Complexity and Variants, International Conference on Descriptional Complexity of Formal Systems (DCFS 2019) Descriptional Complexity of Formal Systems, Lecture Notes in Computer Science (LNCS, Vol. 11612) Springer, Cham, 57-73.
Simon Plouffe, On the values of the functions ... [zeta and Gamma] ..., arXiv preprint arXiv:1310.7195 [math.NT], 2013.
A. Postnikov (MIT) and B. Sagan, What power of two divides a weighted Catalan number?, arXiv:math/0601339 [math.CO], 2006.
Lara Pudwell and Eric Rowland, Avoiding fractional powers over the natural numbers, arXiv:1510.02807 [math.CO] (2015). Also Electronic Journal of Combinatorics, Volume 25(2) (2018), #P2.27. See Section 2.
Ville Salo, Decidability and Universality of Quasiminimal Subshifts, arXiv preprint arXiv:1411.6644 [math.DS], 2014.
Vladimir Shevelev, Several results on sequences which are similar to the positive integers, arXiv:0904.2101 [math.NT], 2014.
F. Smarandache, Only Problems, Not Solutions!.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Paul Tarau, A Groupoid of Isomorphic Data Transformations. Calculemus 2009, 8th International Conference, MKM 2009, pp. 170-185, Springer, LNAI 5625.
P. M. B. Vitanyi, An optimal simulation of counter machines, SIAM J. Comput, 14:1(1985), 1-33.
Eric Weisstein's World of Mathematics, Binary, Binary Carry Sequence, and Double-Free Set.
Wikipedia, P-adic order.
Index entries for sequences that are fixed points of mappings
Index entries for sequences related to binary expansion of n

Cf. A011371 (partial sums), A094267 (first differences), A001511 (bisection), A346070 (mod 4).
Bisection of A050605 and |A088705|. Pairwise sums are A050603 and A136480. Difference of A285406 and A281264.
This is Guy Steele's sequence GS(1, 4) (see A135416). Cf. A053398(1,n). Column/row 1 of table A050602.
Cf. A007949 (3-adic), A235127 (4-adic), A112765 (5-adic), A122841 (6-adic), A214411 (7-adic), A244413 (8-adic), A122840 (10-adic).
Cf. A000079, A002487, A006519, A051064, A055457, A063787, A215366, A220466.
Cf. A086463 (Dgf at s=2).

a007814 n = if m == 0 then 1 + a007814 n' else 0
            where (n', m) = divMod n 2
-- Reinhard Zumkeller, Jul 05 2013, May 14 2011, Apr 08 2011

a007814 n | odd n = 0 | otherwise = 1 + a007814 (n `div` 2)
--  Walt Rorie-Baety, Mar 22 2013

[Valuation(n, 2): n in [1..120]]; // Bruno Berselli, Aug 05 2013

ord := proc(n) local i,j; if n=0 then return 0; fi; i:=0; j:=n; while j mod 2 <> 1 do i:=i+1; j:=j/2; od: i; end proc: seq(ord(n), n=1..111);
A007814 := n -> padic[ordp](n,2): seq(A007814(n), n=1..111); # Peter Luschny, Nov 26 2010

Table[IntegerExponent[n, 2], {n, 64}] (* Eric W. Weisstein *)
IntegerExponent[Range[64], 2] (* Eric W. Weisstein, Feb 01 2024 *)
p=2; Array[ If[ Mod[ #, p ]==0, Select[ FactorInteger[ # ], Function[ q, q[ [ 1 ] ]==p ], 1 ][ [ 1, 2 ] ], 0 ]&, 96 ]
DigitCount[BitXor[x, x - 1], 2, 1] - 1; a different version based on the same concept: Floor[Log[2, BitXor[x, x - 1]]] (* Jaume Simon Gispert (jaume(AT)nuem.com), Aug 29 2004 *)
Nest[Join[ #, ReplacePart[ #, Length[ # ] -> Last[ # ] + 1]] &, {0, 1}, 5] (* N. J. Gunther, May 23 2009 *)
Nest[ Flatten[# /. a_Integer -> {0, a + 1}] &, {0}, 7] (* Robert G. Wilson v, Jan 17 2011 *)

PARI
```
A007814(n)=valuation(n,2);
```

import math
def a(n): return int(math.log(n - (n & n - 1), 2)) # Indranil Ghosh, Apr 18 2017

def A007814(n): return (~n & n-1).bit_length() # Chai Wah Wu, Jul 01 2022

sapply(1:100,function(x) sum(gmp::factorize(x)==2)) # Christian N. K. Anderson, Jun 20 2013

(define (A007814 n) (let loop ((n n) (e 0)) (if (odd? n) e (loop (/ n 2) (+ 1 e))))) ;; Antti Karttunen, Oct 06 2017

a(n) = A001511(n) - 1.
a(2*n) = A050603(2*n) = A001511(n).
a(n) = A091090(n-1) + A036987(n-1) - 1.
a(n) = 0 if n is odd, otherwise 1 + a(n/2). - Reinhard Zumkeller, Aug 11 2001
Sum_{k=1..n} a(k) = n - A000120(n). - Benoit Cloitre, Oct 19 2002
G.f.: A(x) = Sum_{k>=1} x^(2^k)/(1-x^(2^k)). - Ralf Stephan, Apr 10 2002
G.f. A(x) satisfies A(x) = A(x^2) + x^2/(1-x^2). A(x) = B(x^2) = B(x) - x/(1-x), where B(x) is the g.f. for A001151. - Franklin T. Adams-Watters, Feb 09 2006
Totally additive with a(p) = 1 if p = 2, 0 otherwise.
Dirichlet g.f.: zeta(s)/(2^s-1). - Ralf Stephan, Jun 17 2007
Define 0 <= k <= 2^n - 1; binary: k = b(0) + 2*b(1) + 4*b(2) + ... + 2^(n-1)*b(n-1); where b(x) are 0 or 1 for 0 <= x <= n - 1; define c(x) = 1 - b(x) for 0 <= x <= n - 1; Then: a(k) = c(0) + c(0)*c(1) + c(0)*c(1)*c(2) + ... + c(0)*c(1)...c(n-1); a(k+1) = b(0) + b(0)*b(1) + b(0)*b(1)*b(2) + ... + b(0)*b(1)...b(n-1). - Arie Werksma (werksma(AT)tiscali.nl), May 10 2008
a(n) = floor(A002487(n - 1) / A002487(n)). - Reikku Kulon, Oct 05 2008
Sum_{k=1..n} (-1)^A000120(n-k)*a(k) = (-1)^(A000120(n)-1)*(A000120(n) - A000035(n)). - Vladimir Shevelev, Mar 17 2009
a(A001147(n) + A057077(n-1)) = a(2*n). - Vladimir Shevelev, Mar 21 2009
For n>=1, a(A004760(n+1)) = a(n). - Vladimir Shevelev, Apr 15 2009
2^(a(n)) = A006519(n). - Philippe Deléham, Apr 22 2009
a(n) = A063787(n) - A000120(n). - Gary W. Adamson, Jun 04 2009
a(C(n,k)) = A000120(k) + A000120(n-k) - A000120(n). - Vladimir Shevelev, Jul 19 2009
a(n!) = n - A000120(n). - Vladimir Shevelev, Jul 20 2009
v_{2}(n) = Sum_{r>=1} (r / 2^(r+1)) Sum_{k=0..2^(r+1)-1} e^(2(k*Pi*i(n+2^r))/(2^(r+1))). - A. Neves, Sep 28 2010, corrected Oct 04 2010
a(n) mod 2 = A096268(n-1). - Robert G. Wilson v, Jan 18 2012
a(A005408(n)) = 1; a(A016825(n)) = 3; A017113(a(n)) = 5; A051062(a(n)) = 7; a(n) = (A037227(n)-1)/2. - Reinhard Zumkeller, Jun 30 2012
a((2*n-1)*2^p) = p, p >= 0 and n >= 1. - Johannes W. Meijer, Feb 04 2013
a(n) = A067255(n,1). - Reinhard Zumkeller, Jun 11 2013
a(n) = log_2(n - (n AND n-1)). - Gary Detlefs, Jun 13 2014
a(n) = 1 + A000120(n-1) - A000120(n), where A000120 is the Hamming weight function. - Stanislav Sykora, Jul 14 2014
A053398(n,k) = a(A003986(n-1,k-1)+1); a(n) = A053398(n,1) = A053398(n,n) = A053398(2*n-1,n) = Min_{k=1..n} A053398(n,k). - Reinhard Zumkeller, Aug 04 2014
a((2*x-1)*2^n) = a((2*y-1)*2^n) for positive n, x and y. - Juri-Stepan Gerasimov, Aug 04 2016
a(n) = A285406(n) - A281264(n). - Ralf Steiner, Apr 18 2017
a(n) = A000005(n)/(A000005(2*n) - A000005(n)) - 1. - conjectured by Velin Yanev, Jun 30 2017, proved by Nicholas Stearns, Sep 11 2017
Equivalently to above formula, a(n) = A183063(n) / A001227(n), i.e., a(n) is the number of even divisors of n divided by number of odd divisors of n. - Franklin T. Adams-Watters, Oct 31 2018
a(n)*(n mod 4) = 2*floor(((n+1) mod 4)/3). - Gary Detlefs, Feb 16 2019
Asymptotic mean: lim_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 1. - Amiram Eldar, Jul 11 2020
a(n) = 2*Sum_{j=1..floor(log_2(n))} frac(binomial(n, 2^j)*2^(j-1)/n). - Dario T. de Castro, Jul 08 2022
a(n) = A070939(n) - A070939(A030101(n)). - Andrew T. Porter, Dec 16 2022
a(n) = floor((gcd(n, 2^n)^(n+1) mod (2^(n+1)-1)^2)/(2^(n+1)-1)) (see Lemma 3.4 from Mazzanti's 2002 article). - Lorenzo Sauras Altuzarra, Mar 10 2024
a(n) = 1 - A088705(n). - Chai Wah Wu, Sep 18 2024

Formula index adapted to the offset of A025480 by R. J. Mathar, Jul 20 2010

Edited by Ralf Stephan, Feb 08 2014

A005187 a(n) = a(floor(n/2)) + n; also denominators in expansion of 1/sqrt(1-x) are 2^a(n); also 2n - number of 1's in binary expansion of 2n.

Original entry on oeis.org

0, 1, 3, 4, 7, 8, 10, 11, 15, 16, 18, 19, 22, 23, 25, 26, 31, 32, 34, 35, 38, 39, 41, 42, 46, 47, 49, 50, 53, 54, 56, 57, 63, 64, 66, 67, 70, 71, 73, 74, 78, 79, 81, 82, 85, 86, 88, 89, 94, 95, 97, 98, 101, 102, 104, 105, 109, 110, 112, 113, 116, 117, 119, 120, 127, 128

Offset: 0

N. J. A. Sloane, May 20 1991; Allan Wilks, Dec 11 1999

Also exponent of the largest power of 2 dividing (2n)! (A010050) and (2n)!! (A000165).
Write n in binary: 1ab..yz, then a(n) = 1ab..yz + ... + 1ab + 1a + 1. - Ralf Stephan, Aug 27 2003
Also numbers having a partition into distinct Mersenne numbers > 0; A079559(a(n))=1; complement of A055938. - Reinhard Zumkeller, Mar 18 2009
Wikipedia's article on the "Whitney Immersion theorem" mentions that the a(n)-dimensional sphere arises in the Immersion Conjecture proved by Ralph Cohen in 1985. - Jonathan Vos Post, Jan 25 2010
For n > 0, denominators for consecutive pairs of integral numerator polynomials L(n+1,x) for the Legendre polynomials with o.g.f. 1 / sqrt(1-tx+x^2). - Tom Copeland, Feb 04 2016
a(n) is the total number of pointers in the first n elements of a perfect skip list. - Alois P. Heinz, Dec 14 2017
a(n) is the position of the n-th a (indexing from 0) in the fixed point of the morphism a -> aab, b -> b. - Jeffrey Shallit, Dec 24 2020
Numbers that can be expressed as the sum of distinct numbers of the form 2^k - 1 (lenient Mersenne numbers, A000225). This follows from the 2N - Hamming weight definition. A corollary is that these are the numbers with no 2 in their skew-binary representation (cf. A169683). - Allan C. Wechsler, Feb 25 2025

			G.f. = x + 3*x^2 + 4*x^3 + 7*x^4 + 8*x^5 + 10*x^6 + 11*x^7 + 15*x^8 + ...

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..20000 (first 1000 terms from T. D. Noe)
Jean-Paul Allouche, Jean Bétréma, and Jeffrey Shallit, Sur des points fixes de morphismes d'un monoïde libre, RAIRO-Theor. Inf. Appl. 23 (1989), 235-249.
Laurent Alonso, Edward M. Reingold, and René Schott, Determining the majority, Inform. Process. Lett. 47 (1993), no. 5, 253-255.
Laurent Alonso, Edward M. Reingold, and René Schott, The average-case complexity of determining the majority, SIAM J. Comput. 26 (1997), no. 1, 1-14.
Barry Brent, On the Constant Terms of Certain Laurent Series, Preprints (2023) 2023061164.
Sung-Hyuk Cha, On Integer Sequences Derived from Balanced k-ary Trees, Applied Mathematics in Electrical and Computer Engineering, 2012.
Sung-Hyuk Cha, On Complete and Size Balanced k-ary Tree Integer Sequences, International Journal of Applied Mathematics and Informatics, Issue 2, Volume 6, 2012, pp. 67-75. - From _N. J. A. Sloane_, Dec 24 2012
Ralph L. Cohen, The Immersion Conjecture for Differentiable Manifolds, The Annals of Mathematics, 1985: 237-328.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi 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, Svante Janson, and Tsung-Hsi 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.
Keith Johnson and Kira Scheibelhut, Rational Polynomials That Take Integer Values at the Fibonacci Numbers, American Mathematical Monthly 123.4 (2016): 338-346. See p. 340.
Tanya Khovanova, There are no coincidences, arXiv preprint 1410.2193 [math.CO], 2014.
Anunay Kulshrestha, On Hamming Distance between base-n representations of whole numbers, arXiv:1203.4547 [cs.DM], 2012.
Michael E. Saks and Michael Werman, On computing majority by comparisons, Combinatorica 11 (1991), no. 4, 383-387.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Wikipedia, Whitney Immersion Theorem.
Allan Wilks, Email to N. J. A. Sloane, Jul 7 1988.

Cf. A001790, A011371, A067080, A098844, A132027, A004128, A054899, A046161.
Cf. A001511 (first differences), A122247 (partial sums), A055938 (complement).
Cf. A004134, A010050, A000165.
Cf. A000120, A079559, A085354, A030308, A000225.

a005187 n = a005187_list !! n
a005187_list = 0 : zipWith (+) [1..] (map (a005187 . (`div` 2)) [1..])
-- Reinhard Zumkeller, Nov 07 2011, Oct 05 2011

[n + Valuation(Factorial(n), 2): n in [0..70]]; // Vincenzo Librandi, Jun 11 2019

A005187 := n -> 2*n - add(i, i=convert(n, base, 2)):
seq(A005187(n), n=0..65); # Peter Luschny, Apr 08 2014

a[0] = 0; a[n_] := a[n] = a[Floor[n/2]] + n; Table[ a[n], {n, 0, 50}] (* or *)
Table[IntegerExponent[(2n)!, 2], {n, 0, 65}] (* Robert G. Wilson v, Apr 19 2006 *)
Table[2n-DigitCount[2n,2,1],{n,0,70}] (* Harvey P. Dale, May 24 2014 *)

{a(n) = if( n<0, 0, valuation((2*n)!, 2))}; /* Michael Somos, Oct 24 2002 */

{a(n) = if( n<0, 0, sum(k=1, n, (2*n)\2^k))}; /* Michael Somos, Oct 24 2002 */

{a(n) = if( n<0, 0, 2*n - subst( Pol( binary( n ) ), x, 1) ) }; /* Michael Somos, Aug 28 2007 */

a(n)=my(s=n);while(n>>=1,s+=n);s \\ Charles R Greathouse IV, Apr 07 2012

a(n)=2*n-hammingweight(n) \\ Charles R Greathouse IV, Jan 07 2013

def A005187(n): return 2*n-bin(n).count('1') # Chai Wah Wu, Jun 03 2021

@CachedFunction
def A005187(n): return A005187(n//2) + n if n > 0 else 0
[A005187(n) for n in range(66)]  # Peter Luschny, Dec 13 2012

a(n) = A011371(2n+1) = A011371(n) + n, n >= 0.
A046161(n) = 2^a(n).
For m>0, let q = floor(log_2(m)); a(2m+1) = 2^q + 3m + Sum_{k>=1} floor((m-2^q)/2^k); a(2m) = a(2m+1) - 1. - Len Smiley
a(n) = Sum_{k >= 0} floor(n/2^k) = n + A011371(n). - Henry Bottomley, Jul 03 2001
G.f.: A(x) = Sum_{k>=0} x^(2^k)/((1-x)*(1-x^(2^k))). - Ralf Stephan, Dec 24 2002
a(n) = Sum_{k=1..n} A001511(k), sum of binary Hamming distances between consecutive integers up to n. - Gary W. Adamson, Jun 15 2003
Conjecture: a(n) = 2n + O(log(n)). - Benoit Cloitre, Oct 07 2003 [true as a(n) = 2*n - hamming_weight(2*n). Joerg Arndt, Jun 10 2019]
Sum_{n=2^k..2^(k+1)-1} a(n) = 3*4^k - (k+4)*2^(k-1) = A085354(k). - Philippe Deléham, Feb 19 2004
From Hieronymus Fischer, Aug 14 2007: (Start)
Recurrence: a(n) = n + a(floor(n/2)); a(2n) = 2n + a(n); a(n*2^m) = 2*n*(2^m-1) + a(n).
  a(2^m) = 2^(m+1) - 1, m >= 0.
Asymptotic behavior: a(n) = 2n + O(log(n)), a(n+1) - a(n) = O(log(n)); this follows from the inequalities below.
a(n) <= 2n-1; equality holds for powers of 2.
a(n) >= 2n-1-floor(log_2(n)); equality holds for n = 2^m-1, m > 0.
lim inf (2n - a(n)) = 1, for n-->oo.
lim sup (2n - log_2(n) - a(n)) = 0, for n-->oo.
lim sup (a(n+1) - a(n) - log_2(n)) = 1, for n-->oo. (End)
a(n) = 2n - A000120(n). - Paul Barry, Oct 26 2007
PURRS demo results: Bounds for a(n) = n + a(n/2) with initial conditions a(1) = 1: a(n) >= -2 + 2*n - log(n)*log(2)^(-1), a(n) <= 1 + 2*n for each n >= 1. - Alexander R. Povolotsky, Apr 06 2008
If n = 2^a_1 + 2^a_2 + ... + 2^a_k, then a(n) = n-k. This can be used to prove that 2^n maximally divides (2n!)/n!. - Jon Perry, Jul 16 2009
a(n) = Sum_{k>=0} A030308(n,k)*A000225(k+1). - Philippe Deléham, Oct 16 2011
a(n) = log_2(denominator(binomial(-1/2,n))). - Peter Luschny, Nov 25 2011
a(2n+1) = a(2n) + 1. - M. F. Hasler, Jan 24 2015
a(n) = A004134(n) - n. - Cyril Damamme, Aug 04 2015
G.f.: (1/(1 - x))*Sum_{k>=0} (2^(k+1) - 1)*x^(2^k)/(1 + x^(2^k)). - Ilya Gutkovskiy, Jul 23 2017

A047999 Sierpiński's [Sierpinski's] triangle (or gasket): triangle, read by rows, formed by reading Pascal's triangle (A007318) mod 2.

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1

Offset: 0

N. J. A. Sloane

Restored the alternative spelling of Sierpinski to facilitate searching for this triangle using regular-expression matching commands in ASCII. - N. J. A. Sloane, Jan 18 2016
Also triangle giving successive states of cellular automaton generated by "Rule 60" and "Rule 102". - Hans Havermann, May 26 2002
Also triangle formed by reading triangle of Eulerian numbers (A008292) mod 2. - Philippe Deléham, Oct 02 2003
Self-inverse when regarded as an infinite lower triangular matrix over GF(2).
Start with [1], repeatedly apply the map 0 -> [00/00], 1 -> [10/11] [Allouche and Berthe]
Also triangle formed by reading triangles A011117, A028338, A039757, A059438, A085881, A086646, A086872, A087903, A104219 mod 2. - Philippe Deléham, Jun 18 2005
J. H. Conway writes (in Math Forum): at least the first 31 rows give odd-sided constructible polygons (sides 1, 3, 5, 15, 17, ... see A001317). The 1's form a Sierpiński sieve. - M. Dauchez (mdzzdm(AT)yahoo.fr), Sep 19 2005
When regarded as an infinite lower triangular matrix, its inverse is a (-1,0,1)-matrix with zeros undisturbed and the nonzero entries in every column form the Prouhet-Thue-Morse sequence (1,-1,-1,1,-1,1,1,-1,...) A010060 (up to relabeling). - David Callan, Oct 27 2006
Triangle read by rows: antidiagonals of an array formed by successive iterates of running sums mod 2, beginning with (1, 1, 1, ...). - Gary W. Adamson, Jul 10 2008
T(n,k) = A057427(A143333(n,k)). - Reinhard Zumkeller, Oct 24 2010
The triangle sums, see A180662 for their definitions, link Sierpiński’s triangle A047999 with seven sequences, see the crossrefs. The Kn1y(n) and Kn2y(n), y >= 1, triangle sums lead to the Sierpiński-Stern triangle A191372. - Johannes W. Meijer, Jun 05 2011
Used to compute the total Steifel-Whitney cohomology class of the Real Projective space. This was an essential component of the proof that there are no product operations without zero divisors on R^n for n not equal to 1, 2, 4 or 8 (real numbers, complex numbers, quaternions, Cayley numbers), proved by Bott and Milnor. - Marcus Jaiclin, Feb 07 2012
T(n,k) = A134636(n,k) mod 2. - Reinhard Zumkeller, Nov 23 2012
T(n,k) = 1 - A219463(n,k), 0 <= k <= n. - Reinhard Zumkeller, Nov 30 2012
From Vladimir Shevelev, Dec 31 2013: (Start)
Also table of coefficients of polynomials s_n(x) of degree n which are defined by formula s_n(x) = Sum_{i=0..n} (binomial(n,i) mod 2)*x^k. These polynomials we naturally call Sierpiński's polynomials. They also are defined by the recursion: s_0(x)=1, s_(2*n+1)(x) = (x+1)*s_n(x^2), n>=0, and s_(2*n)(x) = s_n(x^2), n>=1.
Note that: s_n(1)  = A001316(n),
           s_n(2)  = A001317(n),
           s_n(3)  = A100307(n),
           s_n(4)  = A001317(2*n),
           s_n(5)  = A100308(n),
           s_n(6)  = A100309(n),
           s_n(7)  = A100310(n),
           s_n(8)  = A100311(n),
           s_n(9)  = A100307(2*n),
           s_n(10) = A006943(n),
           s_n(16) = A001317(4*n),
           s_n(25) = A100308(2*n), etc.
The equality s_n(10) = A006943(n) means that sequence A047999 is obtained from A006943 by the separation by commas of the digits of its terms. (End)
Comment from N. J. A. Sloane, Jan 18 2016: (Start)
Take a diamond-shaped region with edge length n from the top of the triangle, and rotate it by 45 degrees to get a square S_n. Here is S_6:
  [1, 1, 1, 1, 1, 1]
  [1, 0, 1, 0, 1, 0]
  [1, 1, 0, 0, 1, 1]
  [1, 0, 0, 0, 1, 0]
  [1, 1, 1, 1, 0, 0]
  [1, 0, 1, 0, 0, 0].
Then (i) S_n contains no square (parallel to the axes) with all four corners equal to 1 (cf. A227133); (ii) S_n can be constructed by using the greedy algorithm with the constraint that there is no square with that property; and (iii) S_n contains A064194(n) 1's. Thus A064194(n) is a lower bound on A227133(n). (End)
See A123098 for a multiplicative encoding of the rows, i.e., product of the primes selected by nonzero terms; e.g., 1 0 1 => 2^1 * 3^0 * 5^1. - M. F. Hasler, Sep 18 2016
From Valentin Bakoev, Jul 11 2020: (Start)
The Sierpinski's triangle with 2^n rows is a part of a lower triangular matrix M_n of dimension 2^n X 2^n. M_n is a block matrix defined recursively: M_1= [1, 0], [1, 1], and for n>1, M_n = [M_(n-1), O_(n-1)], [M_(n-1), M_(n-1)], where M_(n-1) is a block matrix of the same type, but of dimension 2^(n-1) X 2^(n-1), and O_(n-1) is the zero matrix of dimension 2^(n-1) X 2^(n-1). Here is how M_1, M_2 and M_3 look like:
1 0     1 0 0 0      1 0 0 0 0 0 0 0
1 1     1 1 0 0      1 1 0 0 0 0 0 0   - It is seen the self-similarity of the
        1 0 1 0      1 0 1 0 0 0 0 0     matrices M_1, M_2, ..., M_n, ...,
        1 1 1 1      1 1 1 1 0 0 0 0     analogously to the Sierpinski's fractal.
                     1 0 0 0 1 0 0 0
                     1 1 0 0 1 1 0 0
                     1 0 1 0 1 0 1 0
                     1 1 1 1 1 1 1 1
M_n can also be defined as M_n = M_1 X M_(n-1) where X denotes the Kronecker product. M_n is an important matrix in coding theory, cryptography, Boolean algebra, monotone Boolean functions, etc. It is a transformation matrix used in computing the algebraic normal form of Boolean functions. Some properties and links concerning M_n can be seen in LINKS. (End)
Sierpinski's gasket has fractal (Hausdorff) dimension log(A000217(2))/log(2) = log(3)/log(2) = 1.58496... (and cf. A020857). This gasket is the first of a family of gaskets formed by taking the Pascal triangle (A007318) mod j, j >= 2 (see CROSSREFS). For prime j, the dimension of the gasket is log(A000217(j))/log(j) = log(j(j + 1)/2)/log(j) (see Reiter and Bondarenko references). - Richard L. Ollerton, Dec 14 2021

			Triangle begins:
              1,
             1,1,
            1,0,1,
           1,1,1,1,
          1,0,0,0,1,
         1,1,0,0,1,1,
        1,0,1,0,1,0,1,
       1,1,1,1,1,1,1,1,
      1,0,0,0,0,0,0,0,1,
     1,1,0,0,0,0,0,0,1,1,
    1,0,1,0,0,0,0,0,1,0,1,
   1,1,1,1,0,0,0,0,1,1,1,1,
  1,0,0,0,1,0,0,0,1,0,0,0,1,
  ...

Boris A. Bondarenko, Generalized Pascal Triangles and Pyramids (in Russian), FAN, Tashkent, 1990, ISBN 5-648-00738-8.
Brand, Neal; Das, Sajal; Jacob, Tom. The number of nonzero entries in recursively defined tables modulo primes. Proceedings of the Twenty-first Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1990). Congr. Numer. 78 (1990), 47--59. MR1140469 (92h:05004).
John W. Milnor and James D. Stasheff, Characteristic Classes, Princeton University Press, 1974, pp. 43-49 (sequence appears on p. 46).
H.-O. Peitgen, H. Juergens and D. Saupe: Chaos and Fractals (Springer-Verlag 1992), p. 408.
Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
S. Wolfram, A New Kind of Science, Wolfram Media, 2002; Chapter 3.

N. J. A. Sloane, Table of n, a(n) for n = 0..10584 [First 144 rows, flattened; first 50 rows from T. D. Noe].
J.-P. Allouche and V. Berthe, Triangle de Pascal, complexité et automates, Bulletin of the Belgian Mathematical Society Simon Stevin 4.1 (1997): 1-24.
J.-P. Allouche, F. v. Haeseler, H.-O. Peitgen and G. Skordev, Linear cellular automata, finite automata and Pascal's triangle, Discrete Appl. Math. 66 (1996), 1-22.
David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.],
J. Baer, Explore patterns in Pascal's Triangle
Valentin Bakoev, Fast Bitwise Implementation of the Algebraic Normal Form Transform, Serdica J. of Computing 11 (2017), No 1, 45-57.
Valentin Bakoev, Properties and links concerning M_n
Thomas Baruchel, Flattening Karatsuba's Recursion Tree into a Single Summation, SN Computer Science (2020) Vol. 1, Article No. 48.
Thomas Baruchel, A non-symmetric divide-and-conquer recursive formula for the convolution of polynomials and power series, arXiv:1912.00452 [math.NT], 2019.
A. Bogomolny, Dot Patterns and Sierpinski Gasket
Boris A. Bondarenko, Generalized Pascal Triangles and Pyramids, English translation published by Fibonacci Association, Santa Clara Univ., Santa Clara, CA, 1993; see pp. 130-132.
Paul Bradley and Peter Rowley, Orbits on k-subsets of 2-transitive Simple Lie-type Groups, 2014.
E. Burlachenko, Fractal generalized Pascal matrices, arXiv:1612.00970 [math.NT], 2016. See p. 9.
S. Butkevich, Pascal Triangle Applet
David Callan, Sierpinski's triangle and the Prouhet-Thue-Morse word, arXiv:math/0610932 [math.CO], 2006.
B. Cherowitzo, Pascal's Triangle using Clock Arithmetic, Part I
B. Cherowitzo, Pascal's Triangle using Clock Arithmetic, Part II
C. Cobeli, A. Zaharescu, A game with divisors and absolute differences of exponents, arXiv:1411.1334 [math.NT], 2014; Journal of Difference Equations and Applications, Vol. 20, #11, 2014.
Ilya Gutkovskiy, Illustrations (triangle formed by reading Pascal's triangle mod m)
R. K. Guy, The strong law of small numbers. Amer. Math. Monthly 95 (1988), no. 8, 697-712.
Brady Haran, Chaos Game, Numberphile video, YouTube (April 27, 2017).
I. Kobayashi et al., Pascal's Triangle
Dr. Math, Regular polygon formulas [Broken link?]
Y. Moshe, The distribution of elements in automatic double sequences, Discr. Math., 297 (2005), 91-103.
National Curve Bank, Sierpinski Triangles
Hieu D. Nguyen, A Digital Binomial Theorem, arXiv:1412.3181 [math.NT], 2014.
S. Northshield, Sums across Pascal's triangle modulo 2, Congressus Numerantium, 200, pp. 35-52, 2010.
A. M. Reiter, Determining the dimension of fractals generated by Pascal's triangle, Fibonacci Quarterly, 31(2), 1993, pp. 112-120.
F. Richman, Javascript for computing Pascal's triangle modulo n. Go to this page, then under "Modern Algebra and Other Things", click "Pascal's triangle modulo n".
Vladimir Shevelev, On Stephan's conjectures concerning Pascal triangle modulo 2 and their polynomial generalization, J. of Algebra Number Theory: Advances and Appl., 7 (2012), no.1, 11-29. Also arXiv:1011.6083, 2010.
N. J. A. Sloane, Illustration of rows 0 to 32 (encoignure style)
N. J. A. Sloane, Illustration of rows 0 to 64 (encoignure style)
N. J. A. Sloane, Illustration of rows 0 to 128 (encoignure style)
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Eric Weisstein's World of Mathematics, Sierpiński Sieve, Rule 60, Rule 102
Index entries for sequences related to cellular automata
Index entries for triangles and arrays related to Pascal's triangle
Index entries for sequences generated by sieves

Sequences based on the triangles formed by reading Pascal's triangle mod m: (this sequence) (m = 2), A083093 (m = 3), A034931 (m = 4), A095140 (m = 5), A095141 (m = 6), A095142 (m = 7), A034930(m = 8), A095143 (m = 9), A008975 (m = 10), A095144 (m = 11), A095145 (m = 12), A275198 (m = 14), A034932 (m = 16).
Other versions: A090971, A038183.
Cf. A007318, A054431, A001317, A008292, A083093, A034931, A034930, A008975, A034932, A166360, A249133, A064194, A227133.
From Johannes W. Meijer, Jun 05 2011: (Start)
A106344 is a skew version of this triangle.
Triangle sums (see the comments): A001316 (Row1; Related to Row2), A002487 (Related to Kn11, Kn12, Kn13, Kn21, Kn22, Kn23), A007306 (Kn3, Kn4), A060632 (Fi1, Fi2), A120562 (Ca1, Ca2), A112970 (Gi1, Gi2), A127830 (Ze3, Ze4). (End)

import Data.Bits (xor)
a047999 :: Int -> Int -> Int
a047999 n k = a047999_tabl !! n !! k
a047999_row n = a047999_tabl !! n
a047999_tabl = iterate (\row -> zipWith xor ([0] ++ row) (row ++ [0])) [1]
-- Reinhard Zumkeller, Dec 11 2011, Oct 24 2010

A047999:= func< n,k | BitwiseAnd(n-k, k) eq 0 select 1 else 0 >;
[A047999(n,k): k in [0..n], n in [0..15]]; // G. C. Greubel, Dec 03 2024

# Maple code for first M rows (here M=10) - N. J. A. Sloane, Feb 03 2016
ST:=[1,1,1]; a:=1; b:=2; M:=10;
for n from 2 to M do ST:=[op(ST),1];
for i from a to b-1 do ST:=[op(ST), (ST[i+1]+ST[i+2]) mod 2 ]; od:
ST:=[op(ST),1];
a:=a+n; b:=a+n; od:
ST; # N. J. A. Sloane
# alternative
A047999 := proc(n,k)
    modp(binomial(n,k),2) ;
end proc:
seq(seq(A047999(n,k),k=0..n),n=0..12) ; # R. J. Mathar, May 06 2016

Mod[ Flatten[ NestList[ Prepend[ #, 0] + Append[ #, 0] &, {1}, 13]], 2] (* Robert G. Wilson v, May 26 2004 *)
rows = 14; ca = CellularAutomaton[60, {{1}, 0}, rows-1]; Flatten[ Table[ca[[k, 1 ;; k]], {k, 1, rows}]] (* Jean-François Alcover, May 24 2012 *)
Mod[#,2]&/@Flatten[Table[Binomial[n,k],{n,0,20},{k,0,n}]] (* Harvey P. Dale, Jun 26 2019 *)
A047999[n_,k_]:= Boole[BitAnd[n-k,k]==0];
Table[A047999[n,k], {n,0,15}, {k,0,n}]//Flatten (* G. C. Greubel, Sep 03 2025 *)

\\ Recurrence for Pascal's triangle mod p, here p = 2.
p = 2; s=13; T=matrix(s,s); T[1,1]=1;
for(n=2,s, T[n,1]=1; for(k=2,n, T[n,k] = (T[n-1,k-1] + T[n-1,k])%p ));
for(n=1,s,for(k=1,n,print1(T[n,k],", "))) \\ Gerald McGarvey, Oct 10 2009

A011371(n)=my(s);while(n>>=1,s+=n);s
T(n,k)=A011371(n)==A011371(k)+A011371(n-k) \\ Charles R Greathouse IV, Aug 09 2013

T(n,k)=bitand(n-k,k)==0 \\ Charles R Greathouse IV, Aug 11 2016

def A047999_T(n,k):
    return int(not ~n & k) # Chai Wah Wu, Feb 09 2016

Lucas's Theorem is that T(n,k) = 1 if and only if the 1's in the binary expansion of k are a subset of the 1's in the binary expansion of n; or equivalently, k AND NOT n is zero, where AND and NOT are bitwise operators. - Chai Wah Wu, Feb 09 2016 and N. J. A. Sloane, Feb 10 2016
Sum_{k>=0} T(n, k) = A001316(n) = 2^A000120(n).
T(n,k) = T(n-1,k-1) XOR T(n-1,k), 0 < k < n; T(n,0) = T(n,n) = 1. - Reinhard Zumkeller, Dec 13 2009
T(n,k) = (T(n-1,k-1) + T(n-1,k)) mod 2 = |T(n-1,k-1) - T(n-1,k)|, 0 < k < n; T(n,0) = T(n,n) = 1. - Rick L. Shepherd, Feb 23 2018
From Vladimir Shevelev, Dec 31 2013: (Start)
For polynomial {s_n(x)} we have
s_0(x)=1; for n>=1, s_n(x) = Product_{i=1..A000120(n)} (x^(2^k_i) + 1),
if the binary expansion of n is n = Sum_{i=1..A000120(n)} 2^k_i;
G.f. Sum_{n>=0} s_n(x)*z^n = Product_{k>=0} (1 + (x^(2^k)+1)*z^(2^k)) (0Let x>1, t>0 be real numbers. Then
Sum_{n>=0} 1/s_n(x)^t = Product_{k>=0} (1 + 1/(x^(2^k)+1)^t);
Sum_{n>=0} (-1)^A000120(n)/s_n(x)^t = Product_{k>=0} (1 - 1/(x^(2^k)+1)^t).
In particular, for t=1, x>1, we have
Sum_{n>=0} (-1)^A000120(n)/s_n(x) = 1 - 1/x. (End)
From Valentin Bakoev, Jul 11 2020: (Start)
(See my comment about the matrix M_n.) Denote by T(i,j) the number in the i-th row and j-th column of M_n (0 <= i, j < 2^n). When i>=j, T(i,j) is the j-th number in the i-th row of the Sierpinski's triangle. For given i and j, we denote by k the largest integer of the type k=2^m and kT(i,0) = T(i,i) = 1, or
T(i,j) = 0 if i < j, or
T(i,j) = T(i-k,j), if j < k, or
T(i,j) = T(i-k,j-k), if j >= k.
Thus, for given i and j, T(i,j) can be computed in O(log_2(i)) steps. (End)

Additional links from Lekraj Beedassy, Jan 22 2004

A179016 The infinite trunk of binary beanstalk: The only infinite sequence such that a(n-1) = a(n) - number of 1's in binary representation of a(n).

Original entry on oeis.org

0, 1, 3, 4, 7, 8, 11, 15, 16, 19, 23, 26, 31, 32, 35, 39, 42, 46, 49, 53, 57, 63, 64, 67, 71, 74, 78, 81, 85, 89, 94, 97, 101, 104, 109, 112, 116, 120, 127, 128, 131, 135, 138, 142, 145, 149, 153, 158, 161, 165, 168, 173, 176, 180, 184, 190, 193, 197, 200, 205, 209

Offset: 0

Carl R. White, Jun 24 2010

a(n) tells in what number we end in n steps, when we start climbing up the infinite trunk of the "binary beanstalk" from its root (zero). The name "beanstalk" is due to Antti Karttunen.

There are many finite sequences such as 0,1,2; 0,1,3,4,7,9; etc. obeying the same condition (see A218254) and as the length increases, so (necessarily) does the similarity to this infinite sequence.

Alois P. Heinz and Antti Karttunen, Table of n, a(n) for n = 0..16405 (first 1000 terms from Alois P. Heinz)
Paul Tek, Illustration of the first terms

Cf. A000120, A010062, A011371, A213710, A213711, A213717, A213730, A213731, A218600, A218616, A218789, A233271, A218602, A054429. First differences: A213712, complement: A213713.
A subsequence of A005187, i.e., a(n) = A005187(A213715(n)). For all n,
A071542(a(n)) = n, and furthermore A213708(n) <= a(n) <= A173601(n). (Cf. A218603, A218604).
Rows of A218254, when reversed, converge towards this sequence.
Cf. A276623, A219648, A219666, A255056, A276573, A276583, A276613 for analogous constructions, and also A259934.

TakeWhile[Reverse@ NestWhileList[# - DigitCount[#, 2, 1] &, 10^3, # > 0 &], # <= 209 &] (* Michael De Vlieger, Sep 12 2016 *)

a(0)=0, a(1)=1, and for n > 1, if n = A218600(A213711(n)) then a(n) = (2^A213711(n)) - 1, and in other cases, a(n) = a(n+1) - A213712(n+1). (This formula is based on Carl White's observation that this iterated/converging path must pass through each (2^n)-1. However, it would be very interesting to know whether the sequence admits more traditional recurrence(s), referring to previous, not to further terms in the sequence in their definition!) - Antti Karttunen, Oct 26 2012
a(n) = A218616(A218602(n)). - Antti Karttunen, Mar 04 2013
a(n) = A054429(A233271(A218602(n))). - Antti Karttunen, Dec 12 2013

Starting offset changed from 1 to 0 by Antti Karttunen, Nov 05 2012

A027868 Number of trailing zeros in n!; highest power of 5 dividing n!.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 18, 18, 18, 18, 18, 19

Offset: 0

Warut Roonguthai

Also the highest power of 10 dividing n! (different from A054899). - Hieronymus Fischer, Jun 18 2007
Alternatively, a(n) equals the expansion of the base-5 representation A007091(n) of n (i.e., where successive positions from right to left stand for 5^n or A000351(n)) under a scale of notation whose successive positions from right to left stand for (5^n - 1)/4 or A003463(n); for instance, n = 7392 has base-5 expression 2*5^5 + 1*5^4 + 4*5^3 + 0*5^2 + 3*5^1 + 2*5^0, so that a(7392) = 2*781 + 1*156 + 4*31 + 0*6 + 3*1 + 2*0 = 1845. - Lekraj Beedassy, Nov 03 2010
Partial sums of A112765. - Hieronymus Fischer, Jun 06 2012
Also the number of trailing zeros in A000165(n) = (2*n)!!. - Stefano Spezia, Aug 18 2024

			a(100)  = 24.
a(10^3) = 249.
a(10^4) = 2499.
a(10^5) = 24999.
a(10^6) = 249998.
a(10^7) = 2499999.
a(10^8) = 24999999.
a(10^9) = 249999998.
a(10^n) = 10^n/4 - 3 for 10 <= n <= 15 except for a(10^14) = 10^14/4 - 2. - _M. F. Hasler_, Dec 27 2019

M. Gardner, "Factorial Oddities." Ch. 4 in Mathematical Magic Show: More Puzzles, Games, Diversions, Illusions and Other Mathematical Sleight-of-Mind from Scientific American. New York: Vintage, 1978, pp. 50-65.

Hieronymus Fischer, Table of n, a(n) for n = 0..10000 (first 1000 terms from T. D. Noe)
David S. Hart, James E. Marengo, Darren A. Narayan, and David S. Ross, On the number of trailing zeros in n!, College Math. J., 39(2):139-145, 2008.
Enrique Pérez Herrero, Trailing Zeros in n!, Psychedelic Geometry Blogspot.
Soichi Ikeda and Kaneaki Matsuoka, On transcendental numbers generated by certain integer sequences, Siauliai Math. Semin., 8 (16) 2013, 63-69.
Shyam Sunder Gupta, Fascinating Factorials, Exploring the Beauty of Fascinating Numbers, Springer (2025) Ch. 16, 411-442.
Shu-Chung Liu and Jean C.-C. Yeh, Catalan numbers modulo 2^k, J. Int. Seq. 13 (2010), 10.5.4, eq (5).
Antonio M. Oller-Marcén, A new look at the trailing zeros of n!, arXiv:0906.4868v1 [math.NT], 2009.
Antonio M. Oller-Marcén and J. Maria Grau, On the Base-b Expansion of the Number of Trailing Zeros of b^k!, J. Int. Seq. 14 (2011) 11.6.8
Eric Weisstein's World of Mathematics, Factorial.
Index entries for sequences related to factorial numbers

See A000966 for the missing numbers. See A011371 and A054861 for analogs involving powers of 2 and 3.
Cf. A054899, A007953, A112765, A067080, A098844, A132027, A067080, A098844, A132029, A054999, A112765, A191610, A000351.
Cf. also A000142, A004154.
Cf. A000165, A008904.

a027868 n = sum $ takeWhile (> 0) $ map (n `div`) $ tail a000351_list
-- Reinhard Zumkeller, Oct 31 2012

[Valuation(Factorial(n), 5): n in [0..80]]; // Bruno Berselli, Oct 11 2021

0, seq(add(floor(n/5^i),i=1..floor(log[5](n))), n=1..100); # Robert Israel, Nov 13 2014

Table[t = 0; p = 5; While[s = Floor[n/p]; t = t + s; s > 0, p *= 5]; t, {n, 0, 100} ]
Table[ IntegerExponent[n!], {n, 0, 80}] (* Robert G. Wilson v *)
zOF[n_Integer?Positive]:=Module[{maxpow=0},While[5^maxpow<=n,maxpow++];Plus@@Table[Quotient[n,5^i],{i,maxpow-1}]]; Attributes[zOF]={Listable}; Join[{0},zOF[ Range[100]]] (* Harvey P. Dale, Apr 11 2022 *)

a(n)={my(s);while(n\=5,s+=n);s} \\ Charles R Greathouse IV, Nov 08 2012, edited by M. F. Hasler, Dec 27 2019

a(n)=valuation(n!,5) \\ Charles R Greathouse IV, Nov 08 2012

apply( A027868(n)=(n-sumdigits(n,5))\4, [0..99]) \\ M. F. Hasler, Dec 27 2019

from sympy import multiplicity
A027868, p5 = [0,0,0,0,0], 0
for n in range(5,10**3,5):
    p5 += multiplicity(5,n)
    A027868.extend([p5]*5) # Chai Wah Wu, Sep 05 2014

def A027868(n): return 0 if n<5 else n//5 + A027868(n//5) # David Radcliffe, Jun 26 2016

from sympy.ntheory.factor_ import digits
def A027868(n): return n-sum(digits(n,5)[1:])>>2 # Chai Wah Wu, Oct 18 2024

a(n) = Sum_{i>=1} floor(n/5^i).
a(n) = (n - A053824(n))/4.
From Hieronymus Fischer, Jun 25 2007 and Aug 13 2007, edited by M. F. Hasler, Dec 27 2019: (Start)
G.f.: g(x) = Sum_{k>0} x^(5^k)/(1-x^(5^k))/(1-x).
a(n) = Sum_{k=5..n} Sum_{j|k, j>=5} (floor(log_5(j)) - floor(log_5(j-1))).
G.f.: g(x) = L[b(k)](x)/(1-x) where L[b(k)](x) = Sum_{k>=0} b(k)*x^k/(1-x^k) is a Lambert series with b(k) = 1, if k>1 is a power of 5, else b(k) = 0.
G.f.: g(x) = Sum_{k>0} c(k)*x^k/(1-x), where c(k) = Sum_{j>1, j|k} floor(log_5(j)) - floor(log_5(j - 1)).
Recurrence:
a(n) = floor(n/5) + a(floor(n/5));
a(5*n) = n + a(n);
a(n*5^m) = n*(5^m-1)/4 + a(n).
a(k*5^m) = k*(5^m-1)/4, for 0 <= k < 5, m >= 0.
Asymptotic behavior:
a(n) = n/4 + O(log(n)),
a(n+1) - a(n) = O(log(n)), which follows from the inequalities below.
a(n) <= (n-1)/4; equality holds for powers of 5.
a(n) >= n/4 - 1 - floor(log_5(n)); equality holds for n = 5^m-1, m > 0.
lim inf (n/4 - a(n)) = 1/4, for n -> oo.
lim sup (n/4 - log_5(n) - a(n)) = 0, for n -> oo.
lim sup (a(n+1) - a(n) - log_5(n)) = 0, for n -> oo.
(End)
a(n) <= A027869(n). - Reinhard Zumkeller, Jan 27 2008
10^a(n) = A000142(n) / A004154(n). - Reinhard Zumkeller, Nov 24 2012
a(n) = Sum_{k=1..floor(n/2)} floor(log_5(n/k)). - Ammar Khatab, Feb 01 2025

Examples added by Hieronymus Fischer, Jun 06 2012

A054899 a(n) = Sum_{k>0} floor(n/10^k).

Original entry on oeis.org

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

Offset: 0

Henry Bottomley, May 23 2000

nonn

The old definition of this sequence was "Highest power of 10 dividing n!", but that is wrong (see A027868). For example, the highest power of 10 dividing 5!=120 is 1; however, a(5)=0. - Hieronymus Fischer, Jun 18 2007
Highest power of 10 dividing the quotient of multifactorials Product_{k>=1} M(10^k, 10^k*floor(n/10^k)) /( Product_{k>=1} M(10^(k-1), 10^(k-1) * floor(n/10^k)) ) where M(r,s) is the r-multifactorial (r>=1) of s which is defined by M(r,s) = s*M(r,s-r) for s > 0, M(r,s) = 1 for s <= 0. This is because that quotient of multifactorials evaluates to the product 10^floor(n/10)*10^floor(n/100)*... - Hieronymus Fischer, Jun 14 2007
Partial sums of A122840. - Hieronymus Fischer, Jun 06 2012
Called the "terminating nines function" by Kennedy et al. (1989). a(n) is the number of terminating nines which occur up to n but not including n. - Amiram Eldar, Sep 06 2024

			          a(11) = 1
         a(111) = 12.
        a(1111) = 123.
       a(11111) = 1234.
      a(111111) = 12345.
     a(1111111) = 123456.
    a(11111111) = 1234567.
   a(111111111) = 12345678.
  a(1111111111) = 123456789.

Hieronymus Fischer, Table of n, a(n) for n = 0..10000
Robert K. Kennedy, Curtis N. Cooper, Vladimir Drobot, and Fred Hickling, On the natural density of the range of the terminating nines function, International Journal of Mathematics and Mathematical Sciences, Vol. 12, No. 4 (1989), pp. 805-808.
Eric Weisstein's World of Mathematics, Multifactorial.

Cf. A011371 and A054861 for analogs involving powers of 2 and 3.
Different from the highest power of 10 dividing n! (see A027868 for reference).
Cf. A007953, A027868, A067080, A098844, A132027, A122840.

m:=10;
function a(n) // a = A054899, m = 10
  if n eq 0 then return 0;
  else return a(Floor(n/m)) + Floor(n/m);
  end if; end function;
[a(n): n in [0..103]]; // G. C. Greubel, Apr 28 2023

Table[t=0; p=10; While[s=Floor[n/p]; t=t+s; s>0, p*=10]; t, {n,0,100}]

a(n)=my(s);while(n\=10,s+=n);s \\ Charles R Greathouse IV, Jul 19 2011

m=10 # a = A054899
def a(n): return 0 if (n==0) else a(n//m) + (n//m)
[a(n) for n in range(104)] # G. C. Greubel, Apr 28 2023

a(n) = floor(n/10) + floor(n/100) + floor(n/1000) + ...
a(n) = (n - A007953(n))/9.
From Hieronymus Fischer, Jun 14 2007, Jun 25 2007, and Aug 13 2007: (Start)
a(n) = Sum_{k>0} floor(n/10^k).
a(n) = Sum_{k=10..n} Sum_{j|k, j>=10} ( floor(log_10(j)) -floor(log_10(j-1)) ).
G.f.: g(x) = ( Sum_{k>0} x^(10^k)/(1-x^(10^k)) )/(1-x).
G.f. expressed in terms of Lambert series:
g(x) = L[b(k)](x)/(1-x) where L[b(k)](x) = Sum_{k>=0} b(k)*x^k/(1-x^k) is a Lambert series with b(k)=1, if k>1 is a power of 10, else b(k)=0.
G.f.: g(x) = ( Sum_{k>0} c(k)*x^k )/(1-x), where c(k) = Sum_{j>1, j|k} (floor(log_10(j)) - floor(log_10(j-1)) ).
a(n) = Sum_{k=0..floor(log_10(n))} ds_10(floor(n/10^k))*10^k - n where ds_10(x) = digital sum of x in base 10.
a(n) = Sum_{k=0..floor(log_10(n))} A007953(floor(n/10^k))*10^k - n.
Recurrence:
a(n) = floor(n/10) + a(floor(n/10)).
a(10*n) = n + a(n).
a(n*10^m) = n*(10^m-1)/9 + a(n).
a(k*10^m) = k*(10^m-1)/9, for 0 <= k < 10, m >= 0.
Asymptotic behavior:
a(n) = n/9 + O(log(n)),
a(n+1) - a(n) = O(log(n)), which follows from the inequalities below.
a(n) <= (n - 1)/9; equality holds for powers of 10.
a(n) >= n/9 - 1 - floor(log_10(n)); equality holds for n=10^m-1, m>0.
lim inf (n/9 - a(n)) = 1/9, for n --> oo.
lim sup (n/9 - log_10(n) - a(n)) = 0, for n --> oo.
lim sup (a(n+1) - a(n) - log_10(n)) = 0, for n --> oo. (End)

An incorrect g.f. was deleted by N. J. A. Sloane, Sep 13 2009

Examples added by Hieronymus Fischer, Jun 06 2012

A054861 Greatest k such that 3^k divides n!.

Original entry on oeis.org

0, 0, 0, 1, 1, 1, 2, 2, 2, 4, 4, 4, 5, 5, 5, 6, 6, 6, 8, 8, 8, 9, 9, 9, 10, 10, 10, 13, 13, 13, 14, 14, 14, 15, 15, 15, 17, 17, 17, 18, 18, 18, 19, 19, 19, 21, 21, 21, 22, 22, 22, 23, 23, 23, 26, 26, 26, 27, 27, 27, 28, 28, 28, 30, 30, 30, 31, 31, 31, 32, 32, 32, 34, 34, 34, 35, 35

Offset: 0

Henry Bottomley, May 22 2000

Also the number of trailing zeros in the base-3 representation of n!. - Hieronymus Fischer, Jun 18 2007
Also the highest power of 6 dividing n!. - Hieronymus Fischer, Aug 14 2007
A column of A090622. - Alois P. Heinz, Oct 05 2012
The 'missing' values are listed in A096346. - Stanislav Sykora, Jul 16 2014

			a(100) = 48.
a(10^3) = 498.
a(10^4) = 4996.
a(10^5) = 49995.
a(10^6) = 499993.
a(10^7) = 4999994.
a(10^8) = 49999990.
a(10^9) = 499999993.

Hieronymus Fischer, Table of n, a(n) for n = 0..10000 (first 1000 terms from T. D. Noe)
S-C Liu and J. C.-C. Yeh, Catalan numbers modulo 2^k, J. Int. Seq. 13 (2010), 10.5.4, Eq. (5).
A. M. Oller-Marcen and J. Maria Grau, On the Base-b Expansion of the Number of Trailing Zeros of b^k!, J. Int. Seq. 14 (2011) 11.6.8

Cf. A011371 (for analog involving powers of 2). See also A027868.
Cf. A004128 (for a(3n)).
Cf. A000142, A007949, A053735, A054895, A054899, A067080, A096396, A098844, A132027.

[Valuation(Factorial(n), 3): n in [0..80]]; // Bruno Berselli, Aug 05 2013

A054861 := proc(n)
    (n - convert(convert(n, base, 3), `+`))/2 ;
end proc:
seq(A054861(n),n=0..1000) ; # Robert Israel, Jul 17 2014

(Plus@@Floor[#/3^Range[Length[IntegerDigits[#,3]]-1]]&)/@Range[0,100] (* Peter J. C. Moses, Apr 07 2012 *)
FoldList[Plus, 0, IntegerExponent[Range[100], 3]] (* T. D. Noe, Apr 10 2012 *)
Table[IntegerExponent[n!,3],{n,0,80}] (* Harvey P. Dale, Feb 05 2015 *)

a(n)=my(s);while(n\=3,s+=n);s \\ Charles R Greathouse IV, Jul 25 2011

a(n)=(n - vecsum(digits(n,3)))\2; \\ Gheorghe Coserea, Jan 01 2018

def A054861(n):
    A004128 = lambda n: A004128(n//3) + n if n > 0 else 0
    return A004128(n//3)
[A054861(i) for i in (0..76)]  # Peter Luschny, Nov 16 2012

a(n) = floor(n/3) + floor(n/9) + floor(n/27) + floor(n/81) + ... .
a(n) = (n - A053735(n))/2.
a(n+1) = Sum_{k=1..n} A007949(k). - Benoit Cloitre, Mar 24 2002
From Hieronymus Fischer, Jun 18, Jun 25 and Aug 14 2007: (Start)
G.f.: (1/(1-x))*Sum_{k>0} x^(3^k)/(1-x^(3^k)).
a(n) = Sum_{k=3..n} Sum_{j>=3, j|k} (floor(log_3(j)) - floor(log_3(j-1))).
G.f.: L[b(k)](x)/(1-x), where L[b(k)](x) = Sum_{k>=0} b(k)*x^k/(1-x^k) is a Lambert series with b(k) = 1, if k>1 is a power of 3, otherwise b(k)=0.
G.f.: (1/(1-x))*Sum_{k>0} c(k)*x^k, where c(k) = Sum_{j>1, j|k} (floor(log_3(j)) - floor(log_3(j-1))).
Recurrence:
a(n) = floor(n/3) + a(floor(n/3));
a(3*n) = n + a(n);
a(n*3^m) = n*(3^m-1)/2 + a(n).
a(k*3^m) = k*(3^m-1)/2, for 0 <= k < 3, m >= 0.
Asymptotic behavior:
a(n) = n/2 + O(log(n)),
a(n+1) - a(n) = O(log(n)); this follows from the inequalities below.
a(n) <= (n-1)/2; equality holds for powers of 3.
a(n) >= (n-2)/2 - floor(log_3(n)); equality holds for n = 3^m - 1, m > 0.
lim inf (n/2 - a(n)) = 1/2 for n->oo.
lim sup (n/2 - log_3(n) - a(n)) = 0 for n->oo.
lim sup (a(n+1) - a(n) - log_3(n)) = 0 for n->oo. (End)
a(n) = A007949(n!). - R. J. Mathar, Sep 03 2016
From R. J. Mathar, Jul 08 2021: (Start)
a(n) = A122841(n!).
Partial sums of A007949. (End)
a(n) = A007949(A000142(n)). - David A. Corneth, Nov 02 2023

Examples added by Hieronymus Fischer, Jun 06 2012

New name by David A. Corneth, Nov 02 2023

A013939 Partial sums of sequence A001221 (number of distinct primes dividing n).

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 14, 15, 17, 19, 20, 21, 23, 24, 26, 28, 30, 31, 33, 34, 36, 37, 39, 40, 43, 44, 45, 47, 49, 51, 53, 54, 56, 58, 60, 61, 64, 65, 67, 69, 71, 72, 74, 75, 77, 79, 81, 82, 84, 86, 88, 90, 92, 93, 96, 97, 99, 101, 102, 104, 107, 108, 110, 112

Offset: 1

N. J. A. Sloane, Henri Lifchitz

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Distinct Prime Factors

Cf. A005187, A006218, A011371, A013936.
Cf. A093614, A048865, A006218.
Cf. A027748, A000040, A082287.
Cf. A022559.
Cf. A077761.
Cf. A346617.
Cf. A001222, A048803.

a013939 n = a013939_list !! (n-1)
a013939_list = scanl1 (+) $ map a001221 [1..]
-- Reinhard Zumkeller, Feb 16 2012

[(&+[Floor(n/NthPrime(k)): k in [1..n]]): n in [1..70]]; // G. C. Greubel, Nov 24 2018

A013939 := proc(n) option remember;  `if`(n = 1, 0, a(n) + iquo(n+1, ithprime(n+1))) end:
seq(A013939(i), i = 1..69);  # Peter Luschny, Jul 16 2011

a[n_] := Sum[Floor[n/Prime[k]], {k, 1, n}]; Table[a[n], {n, 1, 69}] (* Jean-François Alcover, Jun 11 2012, from 2nd formula *)
Accumulate[PrimeNu[Range[120]]] (* Harvey P. Dale, Jun 05 2015 *)

t=0;vector(99,n,t+=omega(n)) \\ Charles R Greathouse IV, Jan 11 2012

a(n)=my(s);forprime(p=2,n,s+=n\p);s \\ Charles R Greathouse IV, Jan 11 2012

a(n) = sum(k=1, sqrtint(n), k * (primepi(n\k) - primepi(n\(k+1)))) + sum(k=1, n\(sqrtint(n)+1), if(isprime(k), n\k, 0)); \\ Daniel Suteu, Nov 24 2018

from sympy.ntheory import primefactors
print([sum(len(primefactors(k)) for k in range(1,n+1)) for n in range(1, 121)]) # Indranil Ghosh, Mar 19 2017

from sympy import primerange
def A013939(n): return sum(n//p for p in primerange(n+1)) # Chai Wah Wu, Oct 06 2024

[sum(floor(n/nth_prime(k)) for k in (1..n)) for n in (1..70)] # G. C. Greubel, Nov 24 2018

a(n) = Sum_{k <= n} omega(k).
a(n) = Sum_{k = 1..n} floor( n/prime(k) ).
a(n) = a(n-1) + A001221(n).
a(n) = A093614(n) - A048865(n); see also A006218.
A027748(a(A000040(n))+1) = A000040(n), A082287(a(n)+1) = n.
a(n) = Sum_{k=1..n} pi(floor(n/k)). - Vladeta Jovovic, Jun 18 2006
a(n) = n log log n + O(n). - Charles R Greathouse IV, Jan 11 2012
a(n) = n*(log log n + B) + o(n), where B = 0.261497... is the Mertens constant A077761. - Arkadiusz Wesolowski, Oct 18 2013
G.f.: (1/(1 - x))*Sum_{k>=1} x^prime(k)/(1 - x^prime(k)). - Ilya Gutkovskiy, Jan 02 2017
a(n) = Sum_{k=1..floor(sqrt(n))} k * (pi(floor(n/k)) - pi(floor(n/(k+1)))) + Sum_{p prime <= floor(n/(1+floor(sqrt(n))))} floor(n/p). - Daniel Suteu, Nov 24 2018
a(n) = Sum_{k>=1} k * A346617(n,k). - Alois P. Heinz, Aug 19 2021
a(n) = A001222(A048803(n+1)). - Flávio V. Fernandes, Jan 14 2025

More terms from Henry Bottomley, Jul 03 2001

Previous Showing 11-20 of 148 results. Next

cp's OEIS Frontend

A272666 a(n) = A011371(n) + 5*n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

A007814 Exponent of highest power of 2 dividing n, a.k.a. the binary carry sequence, the ruler sequence, or the 2-adic valuation of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Haskell

Magma

Maple

Mathematica

PARI

Python

Python

R

Scheme

Formula

Extensions

A005187 a(n) = a(floor(n/2)) + n; also denominators in expansion of 1/sqrt(1-x) are 2^a(n); also 2n - number of 1's in binary expansion of 2n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI