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

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice
• tabf
• look

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

Also the sum of binary indices of n, where a binary index of n (A048793) is any position of a 1 in its reversed binary expansion. For example, the binary indices of 11 are {1,2,4}, so a(11) = 7. - Gus Wiseman, May 22 2024

Examples

			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
		

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)

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, A124757.

Row sums of A048793 and A272020.

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

Contains exactly A000009(n) copies of n.

For length instead of sum we have A000120, complement A023416.

For minimum instead of sum we have A001511, opposite A000012.

For maximum instead of sum we have A029837 or A070939, opposite A070940.

For product instead of sum we have A096111.

The reverse version is A230877, row sums of A371572.

The reverse complement is A359359, row sums of A371571.

The complement is A359400, row sums of A368494.

Numbers k such that a(k) is prime are A372689.

A014499 lists binary indices of prime numbers.

A019565 gives Heinz number of binary indices, inverse A048675.

A372471 lists binary indices of primes, row-sums A372429.

Cf. A000009, A030101, A359401, A359402.

Programs

Haskell

a029931 = sum . zipWith (*) [1..] . a030308_row
-- Reinhard Zumkeller, Feb 28 2014

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 *)

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

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

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

Extensions

More terms from Erich Friedman