A029931 If 2n = Sum 2^e_i, a(n) = Sum e_i.

0, 1, 2, 3, 3, 4, 5, 6, 4, 5, 6, 7, 7, 8, 9, 10, 5, 6, 7, 8, 8, 9, 10, 11, 9, 10, 11, 12, 12, 13, 14, 15, 6, 7, 8, 9, 9, 10, 11, 12, 10, 11, 12, 13, 13, 14, 15, 16, 11, 12, 13, 14, 14, 15, 16, 17, 15, 16, 17, 18, 18, 19, 20, 21, 7, 8, 9, 10, 10, 11, 12, 13, 11, 12, 13, 14, 14, 15, 16

Offset

0,3

Comments

Write n in base 2, n = sum b(i)*2^(i-1), then a(n) = sum b(i)*i. - Benoit Cloitre, Jun 09 2002

May be regarded as a triangular array read by rows, giving weighted sum of compositions in standard order. The standard order of compositions is given by A066099. - Franklin T. Adams-Watters, Nov 06 2006

Sum of all positive integer roots m_i of polynomial {m,k} - see link [Shevelev]; see also A264613. - Vladimir Shevelev, Dec 13 2015

Links

T. D. Noe, Table of n, a(n) for n = 0..1023

J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197, ex. 10. See also DOI.

Vladimir Shevelev, The number of permutations with prescribed up-down structure as a function of two variables, INTEGERS, 12 (2012), #A1. (See Section 3, Theorem 21 and Section 8, Theorem 50)

Formula

a(n) = a(n - 2^L(n)) + L(n) + 1 [where L(n) = floor(log_2(n)) = A000523(n)] = sum of digits of A048794 [at least for n < 512]. - Henry Bottomley, Mar 09 2001

a(0) = 0, a(2n) = a(n) + e1(n), a(2n+1) = a(2n) + 1, where e1(n) = A000120(n). a(n) = log_2(A029930(n)). - Ralf Stephan, Jun 19 2003

G.f.: (1/(1-x)) * Sum_{k>=0} (k+1)*x^2^k/(1+x^2^k). - Ralf Stephan, Jun 23 2003

a(n) = Sum_{k>=0} A030308(n,k)*A000027(k+1). - Philippe Deléham, Oct 15 2011

a(n) = sum of n-th row of the triangle in A213629. - Reinhard Zumkeller, Jun 17 2012

From Reinhard Zumkeller, Feb 28 2014: (Start)

a(A089633(n)) = n and a(m) != n for m < A089633(n).

a(n) = Sum_{k=1..A070939(n)} k*A030308(n,k-1). (End)

a(n) = A073642(n) + A000120(n). - Peter Kagey, Apr 04 2016

Example

14 = 8+4+2 so a(7) = 3+2+1 = 6.
Composition number 11 is 2,1,1; 1*2+2*1+3*1 = 7, so a(11) = 7.
The triangle starts:
  0
  1
  2 3
  3 4 5 6
The reversed binary expansion of 18 is (0,1,0,0,1) with 1's at positions {2,5}, so a(18) = 2 + 5 = 7. - Gus Wiseman, Jul 22 2019

Maple

HammingWeight := n -> add(i, i = convert(n, base, 2)):
a := proc(n) option remember; `if`(n = 0, 0,
ifelse(n::even, a(n/2) + HammingWeight(n/2), a(n-1) + 1)) end:
seq(a(n), n = 0..78); # Peter Luschny, Oct 30 2021

Mathematica

a[n_] := (b = IntegerDigits[n, 2]).Reverse @ Range[Length @ b]; Array[a, 78, 0] (* Jean-François Alcover, Apr 28 2011, after B. Cloitre *)

Prog

(PARI) for(n=0, 100, l=length(binary(n)); print1(sum(i=1, l, component(binary(n), i)*(l-i+1)), ", "))
(PARI) a(n) = my(b=binary(n)); b*-[-#b..-1]~; \\ Ruud H.G. van Tol, Oct 17 2023
(Haskell)
a029931 = sum . zipWith (*) [1..] . a030308_row
-- Reinhard Zumkeller, Feb 28 2014
(Python)
def A029931(n): return sum(i if j == '1' else 0 for i, j in enumerate(bin(n)[:1:-1], 1)) # Chai Wah Wu, Dec 20 2022
(C#)
ulong A029931(ulong n) {
    ulong result = 0, counter = 1;
    while(n > 0) {
        if (n % 2 == 1)
          result += counter;
        counter++;
        n /= 2;
    }
    return result;
} // Frank Hollstein, Jan 07 2023

Crossrefs

Other sequences that are built by replacing 2^k in the binary representation with other numbers: A022290 (Fibonacci), A059590 (factorials), A073642, A089625 (primes), A116549, A326031.

Cf. A001793 (row sums), A011782 (row lengths), A059867, A066099, A070939, A124757.

Row sums of A048793 and A272020.

Cf. A000120, A035327, A056239, A291166, A295235, A326669, A326674, A326675, A326699/A326700.

Sequence in context: A203899 A202704 A273004 * A350311 A331297 A322806

Adjacent sequences: A029928 A029929 A029930 * A029932 A029933 A029934

Keyword

nonn,easy,nice,tabf,look

Author

N. J. A. Sloane

Extensions

More terms from Erich Friedman

Status

approved