A272090 -id:A272090 - cp's OEIS frontend

A073642 Replace 2^k in the binary representation of n with k (i.e., if n = 2^b + 2^c + 2^d + ... then a(n) = b + c + d + ...).

0, 0, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 6, 6, 4, 4, 5, 5, 6, 6, 7, 7, 7, 7, 8, 8, 9, 9, 10, 10, 5, 5, 6, 6, 7, 7, 8, 8, 8, 8, 9, 9, 10, 10, 11, 11, 9, 9, 10, 10, 11, 11, 12, 12, 12, 12, 13, 13, 14, 14, 15, 15, 6, 6, 7, 7, 8, 8, 9, 9, 9, 9, 10, 10, 11, 11, 12, 12, 10, 10, 11, 11, 12, 12, 13, 13

Offset: 0

Benoit Cloitre, Aug 29 2002

For n >= 1, a(n) is the n-th row sum of the irregular triangle A133457. - Vladimir Shevelev, Dec 14 2015

For n >= 0, 2^a(n) is the number of partitions of n whose dimension (given by the hook-length formula) is an odd integer. See the MacDonald reference. - Arvind Ayyer, May 12 2016

			9 = 2^3 + 2^0, hence a(9) = 3 + 0 = 3;
25 = 2^4 + 2^3 + 2^0, hence a(25) = 4 + 3 + 0 = 7.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Arvind Ayyer, Amritanshu Prasad and Steven Spallone, Odd partitions in Young's lattice, arXiv:1601.01776 [math.CO], 2016.
Ian G. MacDonald, On the degrees of the irreducible representations of symmetric groups, Bulletin of the London Mathematical Society, 3(2):189-192, 1971.

Cf. A059867, A029931, A087135, A000009, A087136, A272090.

a073642 = sum . zipWith (*) [0..] . a030308_row
-- Reinhard Zumkeller, Jun 01 2013

A073642 := proc(n)
        local bdgs ;
        bdgs := convert(n,base,2) ;
        add( op(i,bdgs)*(i-1), i=1..nops(bdgs)) ;
end proc: # R. J. Mathar, Nov 17 2011

Total[Flatten[Position[Rest[Reverse[IntegerDigits[#, 2]]], 1]]] & /@ Range[0, 87] (* Jayanta Basu, Jul 03 2013 *)

a(n)=sum(i=1,length(binary(n)), component(binary(n),i)*(length(binary(n))-i))

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

def A073642(n):
    a, i = 0, 0
    while n > 0:
        a, n, i = a+(n%2)*i, n//2, i+1
    return a
print([A073642(n) for n in range(30)]) # A.H.M. Smeets, Aug 17 2019

a(n) = log_2(A059867(n)).
It seems that for n > 10 a(n) < n/(2*log(n)) and that Sum_{k=1..n} a(k) is asymptotic to C*n*log(n)^2 with 1/2 > C > 0.47.
a(1)=0, a(2n) = a(n) + e1(n), a(2n+1) = a(2n), where e1(n) = A000120(n). - Ralf Stephan, Jun 19 2003
If n = 2^log_2(n) then a(n) = log_2(n); otherwise, a(n) = log_2(n) + a(n-2^log_2(n)), where log_2=A000523. a(2*n+1) = a(2*n), as the least significant bit of n does not contribute to a(n). - Reinhard Zumkeller, Aug 17 2003, edited by A.H.M. Smeets, Aug 17 2019
a(n) = A029931(floor(n/2)). - Franklin T. Adams-Watters, Oct 22 2011
a(n) = Sum_{k=0..A070939(n)-1} k*A030308(n,k). - Reinhard Zumkeller, Jun 01 2013
Conjecture: a(n) = (3*A011371(n) - Sum_{k=1..n} A007814(k)^2)/2 for n > 0. - Velin Yanev, Sep 09 2017
G.f.: (1/(1 - x)) * Sum_{k>=1} k*x^(2^k)/(1 + x^(2^k)). - Ilya Gutkovskiy, Aug 17 2019
From A.H.M. Smeets, Aug 17 2019: (Start)
floor(log_2(n)) <= a(n) <= floor(log_2(n+2)*(log_2(n+2)-1)/2), n > 0.
Lower bound: floor(log_2(n)) = a(n) for n = 2^m or n = 2^m+1, m >= 0.
Upper bound: a(n) = floor(log_2(n+2)*(log_2(n+2)-1)/2) for n = 2^m-2 or n = 2^m-1, m >= 0. (End)
From Aayush Soni, Feb 12 2022: (Start)
For k < 2^n, a((2^n)+k) + a((2^n)-k-1) = n*(n+1)/2.
Proof: Any (n+1)-bit number 111...11_2 can only be split into two numbers 2^n + k and 2^n - k - 1 which never share any bits in common. Since a(111...11_2) = 0+1+2+...+n, this implies the stated formula. (End)

a(0)=0 and offset corrected by Philippe Deléham, Apr 20 2009

A045923 Number of irreducible representations of symmetric group S_n for which every matrix has determinant 1.

Original entry on oeis.org

1, 1, 1, 2, 2, 7, 7, 10, 10, 34, 40, 53, 61, 103, 112, 143, 145, 369, 458, 579, 712, 938, 1127, 1383, 1638, 2308, 2754, 3334, 3925, 5092, 5818, 6989, 7759, 12278, 14819, 17881, 21477, 25887, 30929, 36954, 43943, 52918, 62749, 74407, 87854, 104534, 122706, 144457

Offset: 1

Richard Stanley

Irreducible representations of S_n contained in the special linear group were first considered by L. Solomon (unpublished).

			a(5)=2, since only the irreducible representations indexed by the partitions (5) and (3,2) are contained in the special linear group.

R. P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge University Press, Cambridge and New York, 1999, Exercise 7.55.

Amritanshu Prasad, Table of n, a(n) for n = 1..999
A. Ayyer, A. Prasad and S. Spallone, Representations of symmetric groups with non-trivial determinant, arXiv:1604.08837 [math.RT] (2016).

Cf. A000041, A272090.

b[1] = 0;
b[n_] := Module[{bb, e, pos, k, r},
bb = Reverse[IntegerDigits[n, 2]];
e = bb[[1]];
pos = DeleteCases[Flatten[Position[bb, 1]], 1] - 1;
r = Length[pos];
Do[k[i] = pos[[i]], {i, 1, r}];
2^Sum[k[i], {i, 2, r}] (2^(k[1] - 1) + Sum[2^((v + 1) (k[1] - 2) - v (v - 1)/2), {v, 1, k[1] - 1}] + e 2^(k[1] (k[1] - 1)/2))
];
a[n_] := PartitionsP[n] - b[n];
Array[a, 50] (* Jean-François Alcover, Aug 09 2018, after Amritanshu Prasad *)

a(n) = A000041(n) - A272090(n). - Amritanshu Prasad, May 11 2016

a(31)-a(48) from Amritanshu Prasad, May 11 2016

cp's OEIS Frontend

A073642 Replace 2^k in the binary representation of n with k (i.e., if n = 2^b + 2^c + 2^d + ... then a(n) = b + c + d + ...).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI