A029930 -id:A029930 - cp's OEIS frontend

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

N. J. A. Sloane

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

			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

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)

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.

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

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

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

for(n=0,100,l=length(binary(n)); print1(sum(i=1,l, component(binary(n),i)*(l-i+1)),","))

a(n) = my(b=binary(n)); b*-[-#b..-1]~; \\ Ruud H.G. van Tol, Oct 17 2023

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

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

More terms from Erich Friedman

A059867 Number of irreducible representations of the symmetric group S_n that have odd degree.

Original entry on oeis.org

1, 2, 2, 4, 4, 8, 8, 8, 8, 16, 16, 32, 32, 64, 64, 16, 16, 32, 32, 64, 64, 128, 128, 128, 128, 256, 256, 512, 512, 1024, 1024, 32, 32, 64, 64, 128, 128, 256, 256, 256, 256, 512, 512, 1024, 1024, 2048, 2048, 512, 512, 1024, 1024, 2048, 2048, 4096, 4096, 4096, 4096

Offset: 1

Noam Katz (noamkj(AT)hotmail.com), Feb 28 2001

Ayyer et al. (2016, 2016) obtain this sequence (which they call "odd partitions") as the number of partitions of n such that the dimension of the corresponding irreducible representation of S_n is odd.

			a(3) = 2 because S_3 the degrees of the irreducible representations of S_3 are 1,1,2.

Eric M. Schmidt, Table of n, a(n) for n = 1..1000
Arvind Ayyer, Amritanshu Prasad, Steven Spallone, Odd partitions in Young's lattice, arXiv:1601.01776 [math.CO], 2016.
Arvind Ayyer, A. Prasad, S. Spallone, Representations of symmetric groups with non-trivial determinant, arXiv preprint arXiv:1604.08837 [math.RT], 2016. See Eq. (14).
I. G. Macdonald, On the degrees of the irreducible representations of symmetric groups, Bulletin of the London Mathematical Society, 3(2):189-192, 1971.
John McKay, Irreducible representations of odd degree, Journal of Algebra 20, 1972 pages 416-418.
Igor Pak, Greta Panova, Bounds on Kronecker coefficients via contingency tables, Linear Algebra and its Applications (2020), Vol. 602, 157-178.

Cf. A000120, A029930; A029931: the bisection of log_2(a(n)); A073642, A089248.

a[n_] := 2^Total[Flatten[Position[Reverse[IntegerDigits[n, 2]], 1]] - 1];
Array[a, 60] (* Jean-François Alcover, Jul 21 2018 *)

A059867(n)={my(d=binary(n));prod(k=1,#d,if(d[#d+1-k],2^(k-1),1));} \\ Joerg Arndt, Apr 29 2013

a(n) = {my(b = Vecrev(binary(n))); 2^sum(k=1, #b, (k-1)*b[k]);} \\ Michel Marcus, Jan 11 2016

def A059867(n) : dig = n.digits(2); return prod(2^n for n in range(len(dig)) if dig[n]==1) # Eric M. Schmidt, Apr 27 2013

If n = sum 2^e[i] in binary, then the number of odd degree irreducible complex representations of S_n is 2^sum e[i]. In words: write n in binary and take the product of the powers of 2 that appear.
G.f.: prod(k>=0, 1 + 2^k * x^2^k). a(n) = 2^A073642(n). - Ralf Stephan, Jun 02 2003
a(1)=1, a(2n) = 2^e1(n)*a(n), a(2n+1) = a(2n), where e1(n) = A000120(n). - Ralf Stephan, Jun 19 2003

More terms from Larry Reeves (larryr(AT)acm.org), Mar 27 2001

A332382 If n = Sum (2^e_k) then a(n) = Product (prime(e_k + 2)).

Original entry on oeis.org

1, 3, 5, 15, 7, 21, 35, 105, 11, 33, 55, 165, 77, 231, 385, 1155, 13, 39, 65, 195, 91, 273, 455, 1365, 143, 429, 715, 2145, 1001, 3003, 5005, 15015, 17, 51, 85, 255, 119, 357, 595, 1785, 187, 561, 935, 2805, 1309, 3927, 6545, 19635, 221, 663, 1105, 3315, 1547, 4641, 7735, 23205

Offset: 0

Ilya Gutkovskiy, Feb 10 2020

nonn

Permutation of odd squarefree numbers (A056911).

a(n) is the n-th power of 3 in the monoid defined in A331590. - Peter Munn, May 02 2020

			21 = 2^0 + 2^2 + 2^4 so a(21) = prime(2) * prime(4) * prime(6) = 3 * 7 * 13 = 273.

Index entries for sequences related to binary expansion of n

Bisection of A019565.
Cf. A002110, A029930, A048675, A056911, A121663, A225546.
A003961, A003987, A059897, A331590, A334748 are used to express relationship between terms of this sequence.

a:= n-> (l-> mul(ithprime(i+1)^l[i], i=1..nops(l)))(convert(n, base, 2)):
seq(a(n), n=0..55);  # Alois P. Heinz, Feb 10 2020

nmax = 55; CoefficientList[Series[Product[(1 + Prime[k + 2] x^(2^k)), {k, 0, Floor[Log[2, nmax]]}], {x, 0, nmax}], x]
a[0] = 1; a[n_] := Prime[Floor[Log[2, n]] + 2] a[n - 2^Floor[Log[2, n]]]; Table[a[n], {n, 0, 55}]

a(n) = my(b=Vecrev(binary(n))); prod(k=1, #b, if (b[k], prime(k+1), 1)); \\ Michel Marcus, Feb 10 2020

G.f.: Product_{k>=0} (1 + prime(k+2) * x^(2^k)).
a(0) = 1; a(n) = prime(floor(log_2(n)) + 2) * a(n - 2^floor(log_2(n))).
a(2^(k-1)-1) = A002110(k)/2 for k > 0.
From Peter Munn, May 02 2020: (Start)
a(2n) = A003961(a(n)).
a(2n+1) = 3 * a(2n).
a(n) = A225546(4^n).
a(n+k) = A331590(a(n), a(k)).
a(n XOR k) = A059897(a(n), a(k)), where XOR denotes bitwise exclusive-or, A003987.
A048675(a(n)) = 2n.
(End)
a(n+1) = A334748(a(n)). - Peter Munn, Mar 04 2022

A294106 Sum of products of terms in all partitions of 3*n into distinct powers of 3.

Original entry on oeis.org

1, 3, 0, 9, 27, 0, 0, 0, 0, 27, 81, 0, 243, 729, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 81, 243, 0, 729, 2187, 0, 0, 0, 0, 2187, 6561, 0, 19683, 59049, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 0

Seiichi Manyama, Oct 28 2017

nonn

			n | partitions of 3*n into distinct powers of 3 | a(n)
------------------------------------------------------
1 | 3                                           |  3
2 |                                             |  0
3 | 9                                           |  9
4 | 9 + 3                                       | 27

Seiichi Manyama, Table of n, a(n) for n = 0..1000

Cf. A029930, A039966, A294298.

A309840 If n = Sum (2^e_k) then a(n) = Product (Fibonacci(e_k + 3)).

Original entry on oeis.org

1, 2, 3, 6, 5, 10, 15, 30, 8, 16, 24, 48, 40, 80, 120, 240, 13, 26, 39, 78, 65, 130, 195, 390, 104, 208, 312, 624, 520, 1040, 1560, 3120, 21, 42, 63, 126, 105, 210, 315, 630, 168, 336, 504, 1008, 840, 1680, 2520, 5040, 273, 546, 819, 1638, 1365, 2730, 4095, 8190

Offset: 0

Ilya Gutkovskiy, Aug 19 2019

nonn

			23 = 2^0 + 2^1 + 2^2 + 2^4 so a(23) = Fibonacci(3) * Fibonacci(4) * Fibonacci(5) * Fibonacci(7) = 390.

Michael De Vlieger, Table of n, a(n) for n = 0..16384
Michael De Vlieger, Fan style binary tree showing a(n) for n = 0..2^14, showing primes in red, perfect prime powers in gold, squarefree composites in green, and numbers neither squarefree nor prime powers in blue and magenta, where magenta additionally represents powerful numbers that are not perfect prime powers and bright green represents primorials.

Cf. A000045, A003266, A019565, A022290, A029930, A121663, A160009.

nmax = 55; CoefficientList[Series[Product[(1 + Fibonacci[k + 3] x^(2^k)), {k, 0, Floor[Log[2, nmax]] + 1}], {x, 0, nmax}], x]
a[0] = 1; a[n_] := Fibonacci[Floor[Log[2, n]] + 3] a[n - 2^Floor[Log[2, n]]]; Table[a[n], {n, 0, 55}]

a(n)={vecprod([fibonacci(k+2) | k<-Vec(select(b->b, Vecrev(digits(n, 2)), 1))])} \\ Andrew Howroyd, Aug 19 2019

G.f.: Product_{k>=0} (1 + Fibonacci(k + 3) * x^(2^k)).
a(0) = 1; a(n) = Fibonacci(floor(log_2(n)) + 3) * a(n - 2^floor(log_2(n))).
a(2^(k-2)-1) = A003266(k).

A309841 If n = Sum (2^e_k) then a(n) = Product ((e_k + 2)!).

Original entry on oeis.org

1, 2, 6, 12, 24, 48, 144, 288, 120, 240, 720, 1440, 2880, 5760, 17280, 34560, 720, 1440, 4320, 8640, 17280, 34560, 103680, 207360, 86400, 172800, 518400, 1036800, 2073600, 4147200, 12441600, 24883200, 5040, 10080, 30240, 60480, 120960, 241920, 725760, 1451520, 604800

Offset: 0

Ilya Gutkovskiy, Aug 19 2019

			21 = 2^0 + 2^2 + 2^4 so a(21) = 2! * 4! * 6! = 34560.

Robert Israel, Table of n, a(n) for n = 0..10000

Cf. A000142, A000178, A019565, A029930, A058295, A059590, A121663, A283477.

a:= n-> (l-> mul((i+1)!^l[i], i=1..nops(l)))(convert(n, base, 2)):
seq(a(n), n=0..40);  # Alois P. Heinz, Feb 10 2020

nmax = 40; CoefficientList[Series[Product[(1 + (k + 2)! x^(2^k)), {k, 0, Floor[Log[2, nmax]] + 1}], {x, 0, nmax}], x]
a[0] = 1; a[n_] := (Floor[Log[2, n]] + 2)! a[n - 2^Floor[Log[2, n]]]; Table[a[n], {n, 0, 40}]

a(n)={vecprod([(k+1)! | k<-Vec(select(b->b, Vecrev(digits(n, 2)), 1))])} \\ Andrew Howroyd, Aug 19 2019

G.f.: Product_{k>=0} (1 + (k + 2)! * x^(2^k)).
a(0) = 1; a(n) = (floor(log_2(n)) + 2)! * a(n - 2^floor(log_2(n))).
a(2^(k-1)-1) = A000178(k).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A059867 Number of irreducible representations of the symmetric group S_n that have odd degree.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Sage

Formula

Extensions

A332382 If n = Sum (2^e_k) then a(n) = Product (prime(e_k + 2)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A294106 Sum of products of terms in all partitions of 3*n into distinct powers of 3.

Views

Author

Keywords

Examples

Links

Crossrefs

A309840 If n = Sum (2^e_k) then a(n) = Product (Fibonacci(e_k + 3)).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A309841 If n = Sum (2^e_k) then a(n) = Product ((e_k + 2)!).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula