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
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
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 of n-th row of the triangle in A213629. - Reinhard Zumkeller, Jun 17 2012
From Reinhard Zumkeller, Feb 28 2014: (Start)
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.
Contains exactly A000009(n) copies of n.
For product instead of sum we have A096111.
Numbers k such that a(k) is prime are A372689.
A014499 lists binary indices of prime numbers.
KEYWORD
AUTHOR
EXTENSIONS
More terms from Erich Friedman
STATUS
approved