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 + ...).

%I A073642 #110 Oct 17 2023 11:28:02
%S A073642 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,
%T A073642 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,
%U A073642 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
%N 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 + ...).
%C A073642 For n >= 1, a(n) is the n-th row sum of the irregular triangle A133457. - _Vladimir Shevelev_, Dec 14 2015
%C A073642 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
%H A073642 Reinhard Zumkeller, <a href="/A073642/b073642.txt">Table of n, a(n) for n = 0..10000</a>
%H A073642 Arvind Ayyer, Amritanshu Prasad and Steven Spallone, <a href="http://arxiv.org/abs/1601.01776">Odd partitions in Young's lattice</a>, arXiv:1601.01776 [math.CO], 2016.
%H A073642 Ian G. MacDonald, <a href="https://doi.org/10.1112/blms/3.2.189">On the degrees of the irreducible representations of symmetric groups</a>, Bulletin of the London Mathematical Society, 3(2):189-192, 1971.
%F A073642 a(n) = log_2(A059867(n)).
%F A073642 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.
%F A073642 a(1)=0, a(2n) = a(n) + e1(n), a(2n+1) = a(2n), where e1(n) = A000120(n). - _Ralf Stephan_, Jun 19 2003
%F A073642 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
%F A073642 a(n) = A029931(floor(n/2)). - _Franklin T. Adams-Watters_, Oct 22 2011
%F A073642 a(n) = Sum_{k=0..A070939(n)-1} k*A030308(n,k). - _Reinhard Zumkeller_, Jun 01 2013
%F A073642 Conjecture: a(n) = (3*A011371(n) - Sum_{k=1..n} A007814(k)^2)/2 for n > 0. - _Velin Yanev_, Sep 09 2017
%F A073642 G.f.: (1/(1 - x)) * Sum_{k>=1} k*x^(2^k)/(1 + x^(2^k)). - _Ilya Gutkovskiy_, Aug 17 2019
%F A073642 From _A.H.M. Smeets_, Aug 17 2019: (Start)
%F A073642 floor(log_2(n)) <= a(n) <= floor(log_2(n+2)*(log_2(n+2)-1)/2), n > 0.
%F A073642 Lower bound: floor(log_2(n)) = a(n) for n = 2^m or n = 2^m+1, m >= 0.
%F A073642 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)
%F A073642 From _Aayush Soni_, Feb 12 2022: (Start)
%F A073642 For k < 2^n, a((2^n)+k) + a((2^n)-k-1) = n*(n+1)/2.
%F A073642 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)
%e A073642 9 = 2^3 + 2^0, hence a(9) = 3 + 0 = 3;
%e A073642 25 = 2^4 + 2^3 + 2^0, hence a(25) = 4 + 3 + 0 = 7.
%p A073642 A073642 := proc(n)
%p A073642         local bdgs ;
%p A073642         bdgs := convert(n,base,2) ;
%p A073642         add( op(i,bdgs)*(i-1), i=1..nops(bdgs)) ;
%p A073642 end proc: # _R. J. Mathar_, Nov 17 2011
%t A073642 Total[Flatten[Position[Rest[Reverse[IntegerDigits[#, 2]]], 1]]] & /@ Range[0, 87] (* _Jayanta Basu_, Jul 03 2013 *)
%o A073642 (PARI) a(n)=sum(i=1,length(binary(n)), component(binary(n),i)*(length(binary(n))-i))
%o A073642 (PARI) a(n) = my(b=binary(n)); b*-[-#b+1..0]~; \\ _Ruud H.G. van Tol_, Oct 17 2023
%o A073642 (Haskell)
%o A073642 a073642 = sum . zipWith (*) [0..] . a030308_row
%o A073642 -- _Reinhard Zumkeller_, Jun 01 2013
%o A073642 (Python)
%o A073642 def A073642(n):
%o A073642     a, i = 0, 0
%o A073642     while n > 0:
%o A073642         a, n, i = a+(n%2)*i, n//2, i+1
%o A073642     return a
%o A073642 print([A073642(n) for n in range(30)]) # _A.H.M. Smeets_, Aug 17 2019
%Y A073642 Cf. A059867, A029931, A087135, A000009, A087136, A272090.
%K A073642 easy,nonn
%O A073642 0,5
%A A073642 _Benoit Cloitre_, Aug 29 2002
%E A073642 a(0)=0 and offset corrected by _Philippe Deléham_, Apr 20 2009