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

A053735 Sum of digits of (n written in base 3).

Original entry on oeis.org

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

Offset: 0

Henry Bottomley, Mar 28 2000

Also the fixed point of the morphism 0->{0,1,2}, 1->{1,2,3}, 2->{2,3,4}, etc. - Robert G. Wilson v, Jul 27 2006

			a(20) = 2 + 0 + 2 = 4 because 20 is written as 202 base 3.
From _Omar E. Pol_, Feb 20 2010: (Start)
This can be written as a triangle with row lengths A025192 (see the example in the entry A000120):
0,
1,2,
1,2,3,2,3,4,
1,2,3,2,3,4,3,4,5,2,3,4,3,4,5,4,5,6,
1,2,3,2,3,4,3,4,5,2,3,4,3,4,5,4,5,6,3,4,5,4,5,6,5,6,7,2,3,4,3,4,5,4,5,6,3,...
where the k-th row contains a(3^k+i) for 0<=i<2*3^k and converges to A173523 as k->infinity. (End) [Changed conjectures to statements in this entry. - _Franklin T. Adams-Watters_, Jul 02 2015]
G.f. = x + 2*x^2 + x^3 + 2*x^4 + 3*x^5 + 2*x^6 + 3*x^7 + 4*x^8 + x^9 + 2*x^10 + ...

T. D. Noe, Table of n, a(n) for n = 0..10000
F. T. Adams-Watters and F. Ruskey, Generating Functions for the Digital Sum and Other Digit Counting Sequences, JIS, Vol. 12 (2009), Article 09.5.6.
F. M. Dekking, The Thue-Morse Sequence in Base 3/2, J. Int. Seq., Vol. 26 (2023), Article 23.2.3.
Michael Gilleland, Some Self-Similar Integer Sequences.
A. V. Kitaev and A. Vartanian, Algebroid Solutions of the Degenerate Third Painlevé Equation for Vanishing Formal Monodromy Parameter, arXiv:2304.05671 [math.CA], 2023. See pp. 11, 13.
Jan-Christoph Puchta and Jürgen Spilker, Altes und Neues zur Quersumme, Math. Semesterber, Vol. 49 (2002), pp. 209-226; preprint.
Jeffrey O. Shallit, Problem 6450, Advanced Problems, The American Mathematical Monthly, Vol. 91, No. 1 (1984), pp. 59-60; Two series, solution to Problem 6450, ibid., Vol. 92, No. 7 (1985), pp. 513-514.
Vladimir Shevelev, Compact integers and factorials, Acta Arith., Vol. 126, No. 3 (2007), pp. 195-236 (cf. p.205).
Robert Walker, Self Similar Sloth Canon Number Sequences.
Eric Weisstein's World of Mathematics, Digit Sum.

Cf. A065363, A007089, A173523. See A134451 for iterations.
Cf. A003137, A138530.
Sum of digits of n written in bases 2-16: A000120, this sequence, A053737, A053824, A053827, A053828, A053829, A053830, A007953, A053831, A053832, A053833, A053834, A053835, A053836.
Related base-3 sequences: A006047, A230641, A230642, A230643, A230853, A230854, A230855, A230856, A230639, A230640, A010063 (trajectory of 1), A286585, A286632, A289813, A289814.

a053735 = sum . a030341_row
-- Reinhard Zumkeller, Feb 21 2013, Feb 19 2012

m=1; for u=0:104; sol(m)=sum(dec2base(u,3)-'0'); m=m+1;end
sol; % Marius A. Burtea, Jan 17 2019

[&+Intseq(n,3):n in [0..104]]; // Marius A. Burtea, Jan 17 2019

seq(convert(convert(n,base,3),`+`),n=0..100); # Robert Israel, Jul 02 2015

Table[Plus @@ IntegerDigits[n, 3], {n, 0, 100}] (* or *)
Nest[Join[#, # + 1, # + 2] &, {0}, 6] (* Robert G. Wilson v, Jul 27 2006 and modified Jul 27 2014 *)

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

A053735(n)=sumdigits(n,3) \\ Requires version >= 2.7. Use sum(i=1,#n=digits(n,3),n[i]) in older versions. - M. F. Hasler, Mar 15 2016

(define (A053735 n) (let loop ((n n) (s 0)) (if (zero? n) s (let ((d (mod n 3))) (loop (/ (- n d) 3) (+ s d)))))) ;; For R6RS standard. Use modulo instead of mod in older Schemes like MIT/GNU Scheme. - Antti Karttunen, Jun 03 2017

From Benoit Cloitre, Dec 19 2002: (Start)
a(0) = 0, a(3n) = a(n), a(3n + 1) = a(n) + 1, a(3n + 2) = a(n) + 2.
a(n) = n - 2*Sum_{k>0} floor(n/3^k) = n - 2*A054861(n). (End)
a(n) = A062756(n) + 2*A081603(n). - Reinhard Zumkeller, Mar 23 2003
G.f.: (Sum_{k >= 0} (x^(3^k) + 2*x^(2*3^k))/(1 + x^(3^k) + x^(2*3^k)))/(1 - x). - Michael Somos, Mar 06 2004, corrected by Franklin T. Adams-Watters, Nov 03 2005
In general, the sum of digits of (n written in base b) has generating function (Sum_{k>=0} (Sum_{0 <= i < b} i*x^(i*b^k))/(Sum_{i=0..b-1} x^(i*b^k)))/(1-x). - Franklin T. Adams-Watters, Nov 03 2005
First differences of A094345. - Vladeta Jovovic, Nov 08 2005
a(A062318(n)) = n and a(m) < n for m < A062318(n). - Reinhard Zumkeller, Feb 26 2008
a(n) = A138530(n,3) for n > 2. - Reinhard Zumkeller, Mar 26 2008
a(n) <= 2*log_3(n+1). - Vladimir Shevelev, Jun 01 2011
a(n) = Sum_{k>=0} A030341(n, k). - Philippe Deléham, Oct 21 2011
G.f. satisfies G(x) = (x+2*x^2)/(1-x^3) + (1+x+x^2)*G(x^3), and has a natural boundary at |x|=1. - Robert Israel, Jul 02 2015
a(n) = A056239(A006047(n)). - Antti Karttunen, Jun 03 2017
a(n) = A000120(A289813(n)) + 2*A000120(A289814(n)). - Antti Karttunen, Jul 20 2017
a(0) = 0; a(n) = a(n - 3^floor(log_3(n))) + 1. - Ilya Gutkovskiy, Aug 23 2019
Sum_{n>=1} a(n)/(n*(n+1)) = 3*log(3)/2 (Shallit, 1984). - Amiram Eldar, Jun 03 2021

A194959 Fractalization of (1 + floor(n/2)).

Original entry on oeis.org

1, 1, 2, 1, 3, 2, 1, 3, 4, 2, 1, 3, 5, 4, 2, 1, 3, 5, 6, 4, 2, 1, 3, 5, 7, 6, 4, 2, 1, 3, 5, 7, 8, 6, 4, 2, 1, 3, 5, 7, 9, 8, 6, 4, 2, 1, 3, 5, 7, 9, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 12, 10, 8, 6, 4, 2, 1, 3, 5, 7, 9, 11, 13, 12, 10, 8, 6, 4, 2, 1, 3, 5

Offset: 1

Clark Kimberling, Sep 06 2011

Suppose that p(1), p(2), p(3), ... is an integer sequence satisfying 1 <= p(n) <= n for n >= 1. Define g(1)=(1) and for n > 1, form g(n) from g(n-1) by inserting n so that its position in the resulting n-tuple is p(n). The sequence f obtained by concatenating g(1), g(2), g(3), ... is clearly a fractal sequence, here introduced as the fractalization of p. The interspersion associated with f is here introduced as the interspersion fractally induced by p, denoted by I(p); thus, the k-th term in the n-th row of I(p) is the position of the k-th n in f. Regarded as a sequence, I(p) is a permutation of the positive integers; its inverse permutation is denoted by Q(p).
...
Example: Let p=(1,2,2,3,3,4,4,5,5,6,6,7,7,...)=A008619. Then g(1)=(1), g(2)=(1,2), g(3)=(1,3,2), so that
f=(1,1,2,1,3,2,1,3,4,2,1,3,5,4,2,1,3,5,6,4,2,1,...)=A194959; and I(p)=A057027, Q(p)=A064578.
The interspersion I(P) has the following northwest corner, easily read from f:
  1  2  4  7 11 16 22
  3  6 10 15 21 28 36
  5  8 12 17 23 30 38
  9 14 20 27 35 44 54
  ...
Following is a chart of selected p, f, I(p), and Q(p):
   p         f        I(p)      Q(p)
A000027   A002260   A000027   A000027
A008619   A194959   A057027   A064578
A194960   A194961   A194962   A194963
A053824   A194965   A194966   A194967
A053737   A194973   A194974   A194975
A019446   A194968   A194969   A194970
A049474   A194976   A194977   A194978
A194979   A194980   A194981   A194982
A194964   A194983   A194984   A194985
A194986   A194987   A194988   A194989
Count odd numbers up to n, then even numbers down from n. - Franklin T. Adams-Watters, Jan 21 2012
This sequence defines the square array A(n,k), n > 0 and k > 0, read by antidiagonals and the triangle T(n,k) = A(n+1-k,k) for 1 <= k <= n read by rows (see Formula and Example). - Werner Schulte, May 27 2018

			The sequence p=A008619 begins with 1,2,2,3,3,4,4,5,5,..., so that g(1)=(1). To form g(2), write g(1) and append 2 so that in g(2) this 2 has position p(2)=2: g(2)=(1,2). Then form g(3) by inserting 3 at position p(3)=2: g(3)=(1,3,2), and so on. The fractal sequence A194959 is formed as the concatenation g(1)g(2)g(3)g(4)g(5)...=(1,1,2,1,3,2,1,3,4,2,1,3,5,4,2,...).
From _Werner Schulte_, May 27 2018: (Start)
This sequence seen as a square array read by antidiagonals:
  n\k: 1  2  3  4  5   6   7   8   9  10  11  12 ...
  ===================================================
   1   1  2  2  2  2   2   2   2   2   2   2   2 ... (see A040000)
   2   1  3  4  4  4   4   4   4   4   4   4   4 ... (see A113311)
   3   1  3  5  6  6   6   6   6   6   6   6   6 ...
   4   1  3  5  7  8   8   8   8   8   8   8   8 ...
   5   1  3  5  7  9  10  10  10  10  10  10  10 ...
   6   1  3  5  7  9  11  12  12  12  12  12  12 ...
   7   1  3  5  7  9  11  13  14  14  14  14  14 ...
   8   1  3  5  7  9  11  13  15  16  16  16  16 ...
   9   1  3  5  7  9  11  13  15  17  18  18  18 ...
  10   1  3  5  7  9  11  13  15  17  19  20  20 ...
  etc.
This sequence seen as a triangle read by rows:
  n\k:  1  2  3  4  5   6   7   8   9  10  11  12  ...
  ======================================================
   1    1
   2    1  2
   3    1  3  2
   4    1  3  4  2
   5    1  3  5  4  2
   6    1  3  5  6  4   2
   7    1  3  5  7  6   4   2
   8    1  3  5  7  8   6   4   2
   9    1  3  5  7  9   8   6   4   2
  10    1  3  5  7  9  10   8   6   4   2
  11    1  3  5  7  9  11  10   8   6   4   2
  12    1  3  5  7  9  11  12  10   8   6   4   2
  etc.
(End)

Clark Kimberling, "Fractal sequences and interspersions," Ars Combinatoria 45 (1997) 157-168.

Paul Lévy, Sur quelques classes de permutations, Compositio Mathematica, Volume 8, 1951, pages 1-48. P_n = g(n).
Eric Weisstein's World of Mathematics, Fractal sequence
Eric Weisstein's World of Mathematics, Interspersion
Wikipedia, Fractal sequence

Cf. A000142, A000217, A005408, A005843, A008619, A057027, A064578, A209229, A210535, A219977; A000012 (col 1), A157532 (col 2), A040000 (row 1), A113311 (row 2); A194029 (introduces the natural fractal sequence and natural interspersion of a sequence - different from those introduced at A194959).

Cf. A003558 (g permutation order), A102417 (index), A330081 (on bits), A057058 (inverse).

r = 2; p[n_] := 1 + Floor[n/r]
Table[p[n], {n, 1, 90}]  (* A008619 *)
g[1] = {1}; g[n_] := Insert[g[n - 1], n, p[n]]
f[1] = g[1]; f[n_] := Join[f[n - 1], g[n]]
f[20] (* A194959 *)
row[n_] := Position[f[30], n];
u = TableForm[Table[row[n], {n, 1, 5}]]
v[n_, k_] := Part[row[n], k];
w = Flatten[Table[v[k, n - k + 1], {n, 1, 13},
{k, 1, n}]]  (* A057027 *)
q[n_] := Position[w, n]; Flatten[
Table[q[n], {n, 1, 80}]]  (* A064578 *)
Flatten[FoldList[Insert[#1, #2, Floor[#2/2] + 1] &, {}, Range[10]]] (* Birkas Gyorgy, Jun 30 2012 *)

T(n,k) = min(k<<1-1,(n-k+1)<<1); \\ Kevin Ryde, Oct 09 2020

From Werner Schulte, May 27 2018 and Jul 10 2018: (Start)
Seen as a triangle: It seems that the triangle T(n,k) for 1 <= k <= n (see Example) is the mirror image of A210535.
Seen as a square array A(n,k) and as a triangle T(n,k):
A(n,k) = 2*k-1 for 1 <= k <= n, and A(n,k) = 2*n for 1 <= n < k.
A(n+1,k+1) = A(n,k+1) + A(n,k) - A(n-1,k) for k > 0 and n > 1.
A(n,k) = A(k,n) - 1 for n > k >= 1.
P(n,x) = Sum_{k>0} A(n,k)*x^(k-1) = (1-x^n)*(1-x^2)/(1-x)^3 for n >= 1.
Q(y,k) = Sum_{n>0} A(n,k)*y^(n-1) = 1/(1-y) for k = 1 and Q(y,k) = Q(y,1) + P(k-1,y) for k > 1.
G.f.: Sum_{n>0, k>0} A(n,k)*x^(k-1)*y^(n-1) = (1+x)/((1-x)*(1-y)*(1-x*y)).
Sum_{k=1..n} A(n+1-k,k) = Sum_{k=1..n} T(n,k) = A000217(n) for n > 0.
Sum_{k=1..n} (-1)^(k-1) * A(n+1-k,k) = Sum_{k=1..n} (-1)^(k-1) * T(n,k) = A219977(n-1) for n > 0.
Product_{k=1..n} A(n+1-k,k) = Product_{k=1..n} T(n,k) = A000142(n) for n > 0.
A(n+m,n) = A005408(n-1) for n > 0 and some fixed m >= 0.
A(n,n+m) = A005843(n) for n > 0 and some fixed m > 0.
Let A_m be the upper left part of the square array A(n,k) with m rows and m columns. Then det(A_m) = 1 for some fixed m > 0.
The P(n,x) satisfy the recurrence equation P(n+1,x) = P(n,x) + x^n*P(1,x) for n > 0 and initial value P(1,x) = (1+x)/(1-x).
Let B(n,k) be multiplicative with B(n,p^e) = A(n,e+1) for e >= 0 and some fixed n > 0. That yields the Dirichlet g.f.: Sum_{k>0} B(n,k)/k^s = (zeta(s))^3/(zeta(2*s)*zeta(n*s)).
Sum_{k=1..n} A(k,n+1-k)*A209229(k) = 2*n-1. (conjectured)
(End)
From Kevin Ryde, Oct 09 2020: (Start)
T(n,k) = 2*k-1 if 2*k-1 <= n, or 2*(n+1-k) if 2*k-1 > n. [Lévy, chapter 1 section 1 equations (a),(b)]
Fixed points T(n,k)=k for k=1 and k = (2/3)*(n+1) when an integer. [Lévy, chapter 1 section 2 equation (3)]
(End)

Name corrected by Franklin T. Adams-Watters, Jan 21 2012

A008611 a(n) = a(n-3) + 1, with a(0)=a(2)=1, a(1)=0.

Original entry on oeis.org

1, 0, 1, 2, 1, 2, 3, 2, 3, 4, 3, 4, 5, 4, 5, 6, 5, 6, 7, 6, 7, 8, 7, 8, 9, 8, 9, 10, 9, 10, 11, 10, 11, 12, 11, 12, 13, 12, 13, 14, 13, 14, 15, 14, 15, 16, 15, 16, 17, 16, 17, 18, 17, 18, 19, 18, 19, 20, 19, 20, 21, 20, 21, 22, 21, 22, 23, 22, 23, 24, 23, 24, 25, 24, 25, 26, 25, 26, 27, 26, 27, 28

Offset: 0

N. J. A. Sloane, Mar 15 1996

Molien series of 2-dimensional representation of cyclic group of order 3 over GF(2).
One step back, two steps forward.
The crossing number of the graph C(n, {1,3}), n >= 8, is [n/3] + n mod 3, which gives this sequence starting at the first 4. [Yang Yuansheng et al.]
A Chebyshev transform of A078008. The g.f. is the image of (1-x)/(1-x-2*x^2) (g.f. of A078008) under the Chebyshev transform A(x)-> (1/(1+x^2))*A(x/(1+x^2)). - Paul Barry, Oct 15 2004
A047878 is an essentially identical sequence. - Anton Chupin, Oct 24 2009
Rhyme scheme of Dante Alighieri's "Divine Comedy." - David Gaita, Feb 11 2011
A194960 results from deleting the first four terms of A008611. Note that deleting the first term or first four terms of A008611 leaves a concatenation of segments (n, n+1, n+2); for related concatenations, see
  A008619, (n,n+1) after deletion of first term;
  A053737, (n,n+1,n+2,n+3) beginning with n=0;
  A053824, (n to n+4) beginning with n=0. - Clark Kimberling, Sep 07 2011
It appears that a(n) is the number of roots of x^(n+1) + x + 1 inside the unit circle. - Michel Lagneau, Nov 02 2012
Also apparently for n >= 2: a(n) is the largest remainder r that results from dividing n+2 by 1..n+2 more than once, i.e., a(n) = max(i, A072528(n+2,i)>1). - Ralf Stephan, Oct 21 2013
Number of n-element subsets of [n+1] whose sum is a multiple of 3. a(4) = 1: {1,2,4,5}. - Alois P. Heinz, Feb 06 2017
It appears that a(n) is the number of roots of the Fibonacci polynomial F(n+2,x) strictly inside the unit circle of the complex plane. - Michel Lagneau, Apr 07 2017
For the proof of the preceding conjecture see my comments under A008615 and A049310. Chebyshev S(n,x) = i^n*F(n+1,-i*x), with i = sqrt(-1). - Wolfdieter Lang, May 06 2017
The sequence is the interleaving of three sequences: the positive integers (A000027), the nonnegative integers (A001477), and the positive integers, in that order. - Guenther Schrack, Nov 07 2020
a(n) is the number of multiples of 3 between n and 2n. - Christian Barrientos, Dec 20 2021
a(n) is the least number of football games a team has to play to be able to get n-1 points, where a win is 3 points, a draw is 1 point, and a loss is 0 points. - Sigurd Kittilsen, Dec 01 2022

			G.f. = 1 + x^2 + 2*x^3 + x^4 + 2*x^5 + 3*x^6 + 2*x^7 + 3*x^8 + 4*x^9 + ...

D. J. Benson, Polynomial Invariants of Finite Groups, Cambridge, 1993, p. 103.

Vincenzo Librandi, Table of n, a(n) for n = 0..10000
Cristian Cobeli, Aaditya Raghavan, and Alexandru Zaharescu, On the central ball in a translation invariant involutive field, arXiv:2408.01864 [math.NT], 2024. See p. 7.
Frederik Glitzner and David Manlove, Perspectives on Unsolvability in Roommates Markets, arXiv:2505.06717 [cs.GT], 2025. See p. 13.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 447.
Gerard P. Michon, Counting Polyhedra.
Yang Yuansheng et al., The crossing number of C(n; {1,3}), Discr. Math. 289 (2004), 107-118.
Index entries for linear recurrences with constant coefficients, signature (1,0,1,-1).
Index entries for Molien series.

Cf. A000027, A001477, A008619, A047878, A049310, A049347, A053737, A053824, A058207, A058788, A072528, A078008, A194960, A257075, A330396.

a008611 n = n' + mod r 2 where (n', r) = divMod (n + 1) 3
a008611_list = f [1,0,1] where f xs = xs ++ f (map (+ 1) xs)
-- Reinhard Zumkeller, Nov 25 2013

[(n-1)-2*Floor((n-1)/3): n in [0..90]]; // Vincenzo Librandi, Aug 21 2011

with(numtheory): for n from 1 to 70 do:it:=0:
y:=[fsolve(x^n+x+1, x, complex)] : for m from 1 to nops(y) do : if abs(y[m])< 1 then it:=it+1:else fi:od: printf(`%d, `,it):od:
A008611:=n->(n-1)-2*floor((n-1)/3); seq(A008611(n), n=0..50); # Wesley Ivan Hurt, May 18 2014

With[{nn=30},Riffle[Riffle[Range[nn],Range[0,nn-1]],Range[nn],3]] (* or *) RecurrenceTable[{a[0]==a[2]==1,a[1]==0,a[n]==a[n-3]+1},a,{n,90}] (* Harvey P. Dale, Nov 06 2011 *)
LinearRecurrence[{1, 0, 1, -1}, {1, 0, 1, 2}, 100] (* Vladimir Joseph Stephan Orlovsky, Feb 23 2012 *)
a[ n_] := Quotient[n - 1, 3] + Mod[n + 2, 3]; (* Michael Somos, Jan 23 2014 *)

{a(n) = (n-1) \ 3 + (n+2) % 3}; /* Michael Somos, Jan 23 2014 */

a(n) = a(n-3) + 1.
a(n) = (n-1) - 2*floor((n-1)/3).
G.f.: (1 + x^2 + x^4)/(1 - x^3)^2.
After the initial term, has form {n, n+1, n+2} for n=0, 1, 2, ...
From Paul Barry, Mar 18 2004: (Start)
a(n) = Sum_{k=0..n} (-1)^floor(2*(k-2)/3);
a(n) = 4*sqrt(3)*cos(2*Pi*n/3 + Pi/6)/9 + (n+1)/3. (End)
From Paul Barry, Oct 15 2004: (Start)
G.f.: (1 - x + x^2)/((1 + x + x^2)*(x-1)^2);
a(n) = Sum_{k=0..floor(n/2)} binomial(n-k, k)*A078008(n-2k)*(-1)^k. (End)
a(n) = -a(-2-n) for all n in Z.
Euler transform of length 6 sequence [0, 1, 2, 0, 0, -1]. - Michael Somos, Jan 23 2014
a(n) = ((n-1) mod 3) + floor((n-1)/3). - Wesley Ivan Hurt, May 18 2014
PSUM transform of A257075. - Michael Somos, Apr 15 2015
a(n) = A194960(n-3), n >= 0, with extended A194960. See the a(n) formula two lines above. - Wolfdieter Lang, May 06 2017
From Guenther Schrack, Nov 07 2020: (Start)
a(n) = (3*n + 3 + 2*(w^(2*n)*(1 - w) + w^n*(2 + w)))/9, where w = (-1 + sqrt(-3))/2, a primitive third root of unity;
a(n) = (n + 1 + 2*A049347(n))/3;
a(n) = (2*n - A330396(n-1))/3. (End)
E.g.f.: (3*exp(x)*(1 + x) + exp(-x/2)*(6*cos(sqrt(3)*x/2) - 2*sqrt(3)*sin(sqrt(3)*x/2)))/9. - Stefano Spezia, May 06 2022
Sum_{n>=2} (-1)^n/a(n) = 3*log(2) - 1. - Amiram Eldar, Sep 10 2023

A053824 Sum of digits of (n written in base 5).

Original entry on oeis.org

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

Offset: 0

Henry Bottomley, Mar 28 2000

Also the fixed point of the morphism 0->{0,1,2,3,4}, 1->{1,2,3,4,5}, 2->{2,3,4,5,6}, etc. - Robert G. Wilson v, Jul 27 2006

			a(20) = 4 + 0 = 4 because 20 is written as 40 in base 5.
From _Omar E. Pol_, Feb 21 2010: (Start)
It appears that this can be written as a triangle:
  0,
  1,2,3,4,
  1,2,3,4,5,2,3,4,5,6,3,4,5,6,7,4,5,6,7,8,
  1,2,3,4,5,2,3,4,5,6,3,4,5,6,7,4,5,6,7,8,5,6,7,8,9,2,3,4,5,6,3,4,5,6,7,4,5,...
See the conjecture in the entry A000120. (End)

Tanar Ulric, Table of n, a(n) for n = 0..10000 (terms 0..3125=5^5 from Reinhard Zumkeller).
Jeffrey O. Shallit, Problem 6450, Advanced Problems, The American Mathematical Monthly, Vol. 91, No. 1 (1984), pp. 59-60; Two series, solution to Problem 6450, ibid., Vol. 92, No. 7 (1985), pp. 513-514.
Robert Walker, Self Similar Sloth Canon Number Sequences.
Eric Weisstein's World of Mathematics, Digit Sum.

Cf. A231668, A231669, A231670, A231671, A138530.
Sum of digits of n written in bases 2-16: A000120, A053735, A053737, this sequence, A053827, A053828, A053829, A053830, A007953, A053831, A053832, A053833, A053834, A053835, A053836.
Cf. A173525. - Omar E. Pol, Feb 21 2010
Cf. A173670 (last nonzero decimal digit of (10^n)!). - Washington Bomfim, Jan 01 2011

a053824 0 = 0
a053824 x = a053824 x' + d  where (x', d) = divMod x 5
-- Reinhard Zumkeller, Jan 31 2014

[&+Intseq(n, 5):n in [0..100]]; // Marius A. Burtea, Aug 24 2019

Table[Plus @@ IntegerDigits[n, 5], {n, 0, 100}] (* or *)
Nest[Flatten[ #1 /. a_Integer -> Table[a + i, {i, 0, 4}]] &, {0}, 4] (* Robert G. Wilson v, Jul 27 2006 *)
f[n_] := n - 4 Sum[Floor[n/5^k], {k, n}]; Array[f, 103, 0]

PARI
```
a(n)=if(n<1,0,if(n%5,a(n-1)+1,a(n/5)))
```

a(n) = sumdigits(n, 5); \\ Michel Marcus, Aug 24 2019

From Benoit Cloitre, Dec 19 2002: (Start)
a(0) = 0, a(5n+i) = a(n) + i for 0 <= i <= 4;
a(n) = n - 4*Sum_{k>=1} floor(n/5^k) = n - 4*A027868(n). (End)
a(n) = A138530(n,5) for n > 4. - Reinhard Zumkeller, Mar 26 2008
If i >= 2, a(2^i) mod 4 = 0. - Washington Bomfim, Jan 01 2011
a(n) = Sum_{k>=0} A031235(n,k). - Philippe Deléham, Oct 21 2011
a(0) = 0; a(n) = a(n - 5^floor(log_5(n))) + 1. - Ilya Gutkovskiy, Aug 23 2019
Sum_{n>=1} a(n)/(n*(n+1)) = 5*log(5)/4 (Shallit, 1984). - Amiram Eldar, Jun 03 2021

A053830 Sum of digits of (n written in base 9).

Original entry on oeis.org

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

Offset: 0

Henry Bottomley, Mar 28 2000

Also the fixed point of the morphism 0->{0,1,2,3,4,5,6,7,8}, 1->{1,2,3,4,5,6,7,8,9}, 2->{2,3,4,5,6,7,8,9,10}, etc. - Robert G. Wilson v, Jul 27 2006

			a(20) = 2+2 = 4 because 20 is written as 22 base 9.
From _Omar E. Pol_, Feb 23 2010: (Start)
It appears that this can be written as a triangle (see the conjecture in the entry A000120):
0;
1,2,3,4,5,6,7,8;
1,2,3,4,5,6,7,8,9,2,3,4,5,6,7,8,9,10,3,4,5,6,7,8,9,10,11,4,5,6,7,8,9,10,11,...
where the rows converge to A173529. (End)

Indranil Ghosh, Table of n, a(n) for n = 0..59049
Jeffrey O. Shallit, Problem 6450, Advanced Problems, The American Mathematical Monthly, Vol. 91, No. 1 (1984), pp. 59-60; Two series, solution to Problem 6450, ibid., Vol. 92, No. 7 (1985), pp. 513-514.
Robert Walker, Self Similar Sloth Canon Number Sequences.
Eric Weisstein's World of Mathematics, Digit Sum.

Cf. A000120, A007953, A053735, A053737, A053824, A053828, A231684, A231685, A231686, A231687.

Cf. A173529. - Omar E. Pol, Feb 23 2010

[&+Intseq(n, 9):n in [0..100]]; // Marius A. Burtea, Aug 24 2019

Table[Plus @@ IntegerDigits[n, 9], {n, 0, 100}] (* or *)
Nest[ Flatten[ #1 /. a_Integer -> Table[a + i, {i, 0, 8}]] &, {0}, 3] (* Robert G. Wilson v, Jul 27 2006 *)

PARI
```
a(n)=if(n<1,0,if(n%9,a(n-1)+1,a(n/9)))
```

From Benoit Cloitre, Dec 19 2002: (Start)
a(0) = 0, a(9n+i) = a(n) + i for 0 <= i <= 8;
a(n) = n - 8*Sum_{k>=1} floor(n/9^k) = n - 8*A054898(n). (End)
a(n) = A138530(n,9) for n > 8. - Reinhard Zumkeller, Mar 26 2008
a(n) = Sum_{k>=0} A031087(n,k). - Philippe Deléham, Oct 21 2011
a(0) = 0; a(n) = a(n - 9^floor(log_9(n))) + 1. - Ilya Gutkovskiy, Aug 24 2019
Sum_{n>=1} a(n)/(n*(n+1)) = 9*log(9)/8 (Shallit, 1984). - Amiram Eldar, Jun 03 2021

A053827 Sum of digits of (n written in base 6).

Original entry on oeis.org

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

Offset: 0

Henry Bottomley, Mar 28 2000

Also the fixed point of the morphism 0->{0,1,2,3,4,5}, 1->{1,2,3,4,5,6}, 2->{2,3,4,5,6,7}, etc. - Robert G. Wilson v, Jul 27 2006

Sum of six consecutive terms is (15,21,27,33,39,45; 21,27,33,39,45,51; 27,33,39,45,51,57; and so on). - Vincenzo Librandi, Aug 02 2010

			a(20)=3+2=5 because 20 is written as 32 base 6.
From _Omar E. Pol_, Feb 21 2010: (Start)
It appears that this can be written as a triangle :
  0,
  1,2,3,4,5,
  1,2,3,4,5,6,2,3,4,5,6,7,3,4,5,6,7,8,4,5,6,7,8,9,5,6,7,8,9,10,
  1,2,3,4,5,6,2,3,4,5,6,7,3,4,5,6,7,8,4,5,6,7,8,9,5,6,7,8,9,10,6,7,8,9,10,11,2...
where the rows converge to A173526.
See the conjecture in the entry A000120. (End)

Indranil Ghosh, Table of n, a(n) for n = 0..10000
Jeffrey O. Shallit, Problem 6450, Advanced Problems, The American Mathematical Monthly, Vol. 91, No. 1 (1984), pp. 59-60; Two series, solution to Problem 6450, ibid., Vol. 92, No. 7 (1985), pp. 513-514.
Robert Walker, Self Similar Sloth Canon Number Sequences.
Eric Weisstein's World of Mathematics, Digit Sum.

Cf. A231672, A231673, A231674, A231675, A138530.
Sum of digits of n written in bases 2-16: A000120, A053735, A053737, A053824, this sequence, A053828, A053829, A053830, A007953, A053831, A053832, A053833, A053834, A053835, A053836.
Cf. A173526. - Omar E. Pol, Feb 21 2010

[&+Intseq(n,6):n in [0..105]]; // Marius A. Burtea, Aug 24 2019

Table[Plus @@ IntegerDigits[n, 6], {n, 0, 100}] (* or *)
Nest[ Flatten[ #1 /. a_Integer -> Table[a + i, {i, 0, 5}]] &, {0}, 4] (* Robert G. Wilson v, Jul 27 2006 *)

PARI
```
a(n)=if(n<1,0,if(n%6,a(n-1)+1,a(n/6)))
```

a(n) = sumdigits(n, 6); \\ Michel Marcus, Aug 24 2019

From Benoit Cloitre, Dec 19 2002: (Start)
a(0) = 0, a(6n+i) = a(n)+i for 0 <= i <= 5.
a(n) = n-5*(Sum_{k>0} floor(n/6^k)) = n-5*A054895(n). (End)
a(n) = A138530(n,6) for n > 5. - Reinhard Zumkeller, Mar 26 2008
a(n) = Sum_{k>=0} A030567(n,k). - Philippe Deléham, Oct 21 2011
a(0) = 0; a(n) = a(n - 6^floor(log_6(n))) + 1. - Ilya Gutkovskiy, Aug 23 2019
Sum_{n>=1} a(n)/(n*(n+1)) = 6*log(6)/5 (Shallit, 1984). - Amiram Eldar, Jun 03 2021

A010064 Base 4 self or Colombian numbers (not of form k + sum of base 4 digits of k).

Original entry on oeis.org

1, 3, 8, 13, 18, 20, 25, 30, 35, 37, 42, 47, 52, 54, 59, 64, 73, 78, 83, 85, 90, 95, 100, 102, 107, 112, 117, 119, 124, 129, 138, 143, 148, 150, 155, 160, 165, 167, 172, 177, 182, 184, 189, 194, 203, 208, 213, 215, 220, 225, 230, 232, 237, 242, 247, 249, 254

Offset: 1

Leonid Broukhis

Steven R. Finch, Mathematical Constants, Cambridge, 2003, Section 2.24, pp. 179-180.
József Sándor and Borislav Crstici, Handbook of Number theory II, Kluwer Academic Publishers, 2004, Chapter 4, pp. 384-386.

Donovan Johnson, Table of n, a(n) for n = 1..10000
Index entries for Colombian or self numbers and related sequences

Cf. A003052, A010061, A010067, A010070, A230631-A230635.

Related base-4 sequences: A053737, A230631, A230632, A010064, A230633, A230634,A230635, A230636, A230637, A230638, A010065 (trajectory of 1)

s[n_] := n + Plus @@ IntegerDigits[n, 4]; m = 250; Complement[Range[m], Array[s, m]] (* Amiram Eldar, Nov 28 2020 *)

A138530 Triangle read by rows: T(n,k) = sum of digits of n in base k representation, 1<=k<=n.

Original entry on oeis.org

1, 2, 1, 3, 2, 1, 4, 1, 2, 1, 5, 2, 3, 2, 1, 6, 2, 2, 3, 2, 1, 7, 3, 3, 4, 3, 2, 1, 8, 1, 4, 2, 4, 3, 2, 1, 9, 2, 1, 3, 5, 4, 3, 2, 1, 10, 2, 2, 4, 2, 5, 4, 3, 2, 1, 11, 3, 3, 5, 3, 6, 5, 4, 3, 2, 1, 12, 2, 2, 3, 4, 2, 6, 5, 4, 3, 2, 1, 13, 3, 3, 4, 5, 3, 7, 6, 5, 4, 3, 2, 1, 14, 3, 4, 5, 6, 4, 2, 7, 6, 5, 4, 3, 2, 1

Offset: 1

Reinhard Zumkeller, Mar 26 2008

A131383(n) = sum of n-th row;
A000027(n) = T(n,1);
A000120(n) = T(n,2) for n>1;
A053735(n) = T(n,3) for n>2;
A053737(n) = T(n,4) for n>3;
A053824(n) = T(n,5) for n>4;
A053827(n) = T(n,6) for n>5;
A053828(n) = T(n,7) for n>6;
A053829(n) = T(n,8) for n>7;
A053830(n) = T(n,9) for n>8;
A007953(n) = T(n,10) for n>9;
A053831(n) = T(n,11) for n>10;
A053832(n) = T(n,12) for n>11;
A053833(n) = T(n,13) for n>12;
A053834(n) = T(n,14) for n>13;
A053835(n) = T(n,15) for n>14;
A053836(n) = T(n,16) for n>15;
A007395(n) = T(n,n-1) for n>1;
A000012(n) = T(n,n).

			Start of the triangle for n in base k representation:
......................1
....................11....10
......... ........111....11...10
................1111...100...11..10
..............11111...101...12..11..10
............111111...110...20..12..11..10
..........1111111...111...21..13..12..11..10
........11111111..1000...22..20..13..12..11..10
......111111111..1001..100..21..14..13..12..11..10
....1111111111..1010..101..22..20..14..13..12..11..10
..11111111111..1011..102..23..21..15..14..13..12..11..10
111111111111..1100..110..30..22..20..15..14..13..12..11..10,
and the triangle of sums of digits starts:
......................1
.....................2...1
......... ..........3...2...1
...................4...1...2...1
..................5...2...3...2...1
.................6...2...2...3...2...1
................7...3...3...4...3...2...1
...............8...1...4...2...4...3...2...1
..............9...2...1...3...5...4...3...2...1
............10...2...2...4...2...5...4...3...2...1
...........11...3...3...5...3...6...5...4...3...2...1
..........12...2...2...3...4...2...6...5...4...3...2...1.

Alois P. Heinz, Rows n = 1..141, flattened
Eric Weisstein's World of Mathematics, Digit Sum

Cf. A007953. See A240236 for another version.

Cf. A002260.

a138530 n k = a138530_tabl !! (n-1) !! (k-1)
a138530_row n = a138530_tabl !! (n-1)
a138530_tabl = zipWith (map . flip q) [1..] a002260_tabl where
   q 1 n = n
   q b n = if n < b then n else q b n' + d where (n', d) = divMod n b
-- Reinhard Zumkeller, Apr 29 2015

T[n_, k_] := If[k == 1, n, Total[IntegerDigits[n, k]]];
Table[T[n, k], {n, 1, 14}, {k, 1, n}] // Flatten (* Jean-François Alcover, Oct 25 2021 *)

A230638 Smallest number m such that u + (sum of base-4 digits of u) = m has exactly n solutions.

Original entry on oeis.org

0, 17, 16385, 16777234

Offset: 1

N. J. A. Sloane, Oct 31 2013

Indices of records in A230632: a(n) is the index of the first n in A230632.
The terms are a(1)=0, a(2)=4^2+1, a(3)=4^7+1, a(4)=4^12+17+1, a(5)=4^5368+17+1, a(6)=4^10924+16385+1, a(7)=4^5597880+16385+20. Note that a(7) breaks the pattern of the first six terms.
a(8) = 4^16777229 + 4^12 + 19.
For the leading power of 4 see A230637.

			n=2: the two solutions to u+(base-4 digit-sum of u) = 17 are 13 and 16.
n=3: the three solutions to u+(base-4 digit-sum of u) = 4^7+1 are 4^7, 4^7-15, 4^7-18.
n=4: the four solutions to u+(base-4 digit-sum of u) = 4^12+17+1 are 4^12+{16, 13, -14, -17}.

Max Alekseyev, Table of expressions for a(n), for n=1..100
Max A. Alekseyev and N. J. A. Sloane, On Kaprekar's Junction Numbers, arXiv:2112.14365, 2021; Journal of Combinatorics and Number Theory 12:3 (2022), 115-155.
Index entries for Colombian or self numbers and related sequences

Cf. A230637.
Related base-4 sequences:  A053737, A230631, A230632, A010064, A230633, A230634, A230635, A230636, A230637, A230638, A010065 (trajectory of 1)
Smallest number m such that u + (sum of base-b digits of u) = m has exactly n solutions, for bases 2 through 10: A230303, A230640, A230638, A230867, A238840, A238841, A238842, A238843, A006064.

a(8) from Max Alekseyev, Oct 31 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

A053735 Sum of digits of (n written in base 3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

MATLAB

Magma

Maple

Mathematica

PARI

PARI

Scheme

Formula

A194959 Fractalization of (1 + floor(n/2)).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A008611 a(n) = a(n-3) + 1, with a(0)=a(2)=1, a(1)=0.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Formula