cp's OEIS Frontend

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

%I A029931 #99 May 24 2024 12:09:30
%S A029931 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,
%T A029931 14,15,6,7,8,9,9,10,11,12,10,11,12,13,13,14,15,16,11,12,13,14,14,15,
%U A029931 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
%N A029931 If 2n = Sum 2^e_i, a(n) = Sum e_i.
%C A029931 Write n in base 2, n = sum b(i)*2^(i-1), then a(n) = sum b(i)*i. - _Benoit Cloitre_, Jun 09 2002
%C A029931 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
%C A029931 Sum of all positive integer roots m_i of polynomial {m,k} - see link [Shevelev]; see also A264613. - _Vladimir Shevelev_, Dec 13 2015
%C A029931 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
%H A029931 T. D. Noe, <a href="/A029931/b029931.txt">Table of n, a(n) for n = 0..1023</a>
%H A029931 J.-P. Allouche and J. Shallit, <a href="http://www.cs.uwaterloo.ca/~shallit/Papers/as0.ps">The ring of k-regular sequences</a>, Theoretical Computer Sci., 98 (1992), 163-197, ex. 10. See also <a href="https://doi.org/10.1016/0304-3975(92)90001-V">DOI</a>.
%H A029931 Vladimir Shevelev, <a href="http://www.emis.de/journals/INTEGERS/papers/m1/m1.Abstract.html">The number of permutations with prescribed up-down structure as a function of two variables</a>, INTEGERS, 12 (2012), #A1. (See Section 3, Theorem 21 and Section 8, Theorem 50)
%F A029931 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
%F A029931 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
%F A029931 G.f.: (1/(1-x)) * Sum_{k>=0} (k+1)*x^2^k/(1+x^2^k). - _Ralf Stephan_, Jun 23 2003
%F A029931 a(n) = Sum_{k>=0} A030308(n,k)*A000027(k+1). - _Philippe Deléham_, Oct 15 2011
%F A029931 a(n) = sum of n-th row of the triangle in A213629. - _Reinhard Zumkeller_, Jun 17 2012
%F A029931 From _Reinhard Zumkeller_, Feb 28 2014: (Start)
%F A029931 a(A089633(n)) = n and a(m) != n for m < A089633(n).
%F A029931 a(n) = Sum_{k=1..A070939(n)} k*A030308(n,k-1). (End)
%F A029931 a(n) = A073642(n) + A000120(n). - _Peter Kagey_, Apr 04 2016
%e A029931 14 = 8+4+2 so a(7) = 3+2+1 = 6.
%e A029931 Composition number 11 is 2,1,1; 1*2+2*1+3*1 = 7, so a(11) = 7.
%e A029931 The triangle starts:
%e A029931   0
%e A029931   1
%e A029931   2 3
%e A029931   3 4 5 6
%e A029931 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
%p A029931 HammingWeight := n -> add(i, i = convert(n, base, 2)):
%p A029931 a := proc(n) option remember; `if`(n = 0, 0,
%p A029931 ifelse(n::even, a(n/2) + HammingWeight(n/2), a(n-1) + 1)) end:
%p A029931 seq(a(n), n = 0..78); # _Peter Luschny_, Oct 30 2021
%t A029931 a[n_] := (b = IntegerDigits[n, 2]).Reverse @ Range[Length @ b]; Array[a,78,0] (* _Jean-François Alcover_, Apr 28 2011, after B. Cloitre *)
%o A029931 (PARI) for(n=0,100,l=length(binary(n)); print1(sum(i=1,l, component(binary(n),i)*(l-i+1)),","))
%o A029931 (PARI) a(n) = my(b=binary(n)); b*-[-#b..-1]~; \\ _Ruud H.G. van Tol_, Oct 17 2023
%o A029931 (Haskell)
%o A029931 a029931 = sum . zipWith (*) [1..] . a030308_row
%o A029931 -- _Reinhard Zumkeller_, Feb 28 2014
%o A029931 (Python)
%o A029931 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
%o A029931 (C#)
%o A029931 ulong A029931(ulong n) {
%o A029931     ulong result = 0, counter = 1;
%o A029931     while(n > 0) {
%o A029931         if (n % 2 == 1)
%o A029931           result += counter;
%o A029931         counter++;
%o A029931         n /= 2;
%o A029931     }
%o A029931     return result;
%o A029931 } // _Frank Hollstein_, Jan 07 2023
%Y A029931 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.
%Y A029931 Cf. A001793 (row sums), A011782 (row lengths), A059867, A066099, A124757.
%Y A029931 Row sums of A048793 and A272020.
%Y A029931 Cf. A035327, A056239, A291166, A295235, A326669, A326674, A326675, A326699/A326700.
%Y A029931 Contains exactly A000009(n) copies of n.
%Y A029931 For length instead of sum we have A000120, complement A023416.
%Y A029931 For minimum instead of sum we have A001511, opposite A000012.
%Y A029931 For maximum instead of sum we have A029837 or A070939, opposite A070940.
%Y A029931 For product instead of sum we have A096111.
%Y A029931 The reverse version is A230877, row sums of A371572.
%Y A029931 The reverse complement is A359359, row sums of A371571.
%Y A029931 The complement is A359400, row sums of A368494.
%Y A029931 Numbers k such that a(k) is prime are A372689.
%Y A029931 A014499 lists binary indices of prime numbers.
%Y A029931 A019565 gives Heinz number of binary indices, inverse A048675.
%Y A029931 A372471 lists binary indices of primes, row-sums A372429.
%Y A029931 Cf. A000009, A030101, A359401, A359402.
%K A029931 nonn,easy,nice,tabf,look
%O A029931 0,3
%A A029931 _N. J. A. Sloane_
%E A029931 More terms from _Erich Friedman_