%I A005187 M2330
%S A005187 0,1,3,4,7,8,10,11,15,16,18,19,22,23,25,26,31,32,34,35,38,39,41,42,46,
%T A005187 47,49,50,53,54,56,57,63,64,66,67,70,71,73,74,78,79,81,82,85,86,88,89,
%U A005187 94,95,97,98,101,102,104,105,109,110,112,113,116,117,119,120,127,128
%N A005187 a(n)=a([n/2])+n; also denominators in expansion of 1/sqrt(1-x) are 2^a(n); 
               also 2n - number of 1's in binary expansion of 2n.
%C A005187 Also the power of 2 in (2n)!.
%C A005187 Write n in binary: 1ab..yz, then a(n) = 1ab..yz + ... + 1ab + 1a + 1. 
               - Ralf Stephan (ralf(AT)ark.in-berlin.de), Aug 27 2003
%C A005187 Also numbers having a partition into distinct Mersenne numbers >0; A079559(a(n))=1; 
               complement of A055938. [From Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), 
               Mar 18 2009]
%D A005187 Laurent Alonso; Edward M. Reingold; Ren\`e Schott, Determining the majority, 
               Inform. Process. Lett. 47 (1993), no. 5, 253-255.
%D A005187 Laurent Alonso; Edward M. Reingold; Ren\`e Schott, The average-case complexity 
               of determining the majority, SIAM J. Comput. 26 (1997), no. 1, 1-14.
%D A005187 Michael E. Saks; Michael Werman, On computing majority by comparisons. 
               Combinatorica 11 (1991), no. 4, 383-387.
%D A005187 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%H A005187 T. D. Noe, <a href="b005187.txt">Table of n, a(n) for n=0..1000</a>
%H A005187 R. Stephan, <a href="somedcgf.html">Some divide-and-conquer sequences 
               ...</a>
%H A005187 R. Stephan, <a href="a079944.ps">Table of generating functions</a>
%F A005187 For m>0, let q=[ log_2(m) ]; a(2m+1)=2^q+3m+sum([ (m-2^q)/2^k ], k=1..infinity); 
               a(2m)=a(2m+1)-1 - Len Smiley (smiley(AT)math.uaa.alaska.edu)
%F A005187 a(n) = Sum{k >= 0}[ n/2^k ] = n+A011371(n). - Henry Bottomley (se16(AT)btinternet.com), 
               Jul 03 2001
%F A005187 G.f.: A(x) = Sum(k=0, infinity, x^(2^k)/((1-x)*(1-x^(2^k)))). - Ralf 
               Stephan (ralf(AT)ark.in-berlin.de), Dec 24 2002
%F A005187 a(n) = Sum(k = 1 through n) A001511(k) - number of 1's in binary representation 
               of n. - Gary W. Adamson (qntmpkt(AT)yahoo.com), Jun 15 2003
%F A005187 Conjecture : a(n)=2n+O(log(n)) - Benoit Cloitre (benoit7848c(AT)orange.fr), 
               Oct 07 2003
%F A005187 Sum_{n, 2^k<=n<2^(k+1)} a(n) = 3*4^k - (k+4)*2^(k-1) = A085354(k). - 
               DELEHAM Philippe (kolotoko(AT)wanadoo.fr), Feb 19 2004
%F A005187 a(n)= A011371(n)+n, n>=0.
%F A005187 Recurrence: a(n)=n+a(floor(n/2)); a(2n)=2n+a(n); a(n*2^m)=2*n*(2^m-1)+a(n). 
               - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Aug 14 2007
%F A005187 a(2^m)=2^(m+1)-1, m>=0. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), 
               Aug 14 2007
%F A005187 Asymptotic behavior: a(n)=2n+O(log(n)), a(n+1)-a(n)=O(log(n)); this follows 
               from the inequalities below. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), 
               Aug 14 2007
%F A005187 a(n)<=2n-1; equality holds for powers of 2. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), 
               Aug 14 2007
%F A005187 a(n)>=2n-1-floor(log_2(n)); equality holds for n=2^m-1, m>0. - Hieronymus 
               Fischer (Hieronymus.Fischer(AT)gmx.de), Aug 14 2007
%F A005187 lim inf (2n-a(n))=1, for n-->oo. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), 
               Aug 14 2007
%F A005187 lim sup (2n-log_2(n)-a(n))=0, for n-->oo. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), 
               Aug 14 2007
%F A005187 lim sup (a(n+1)-a(n)-log_2(n))=1, for n-->oo. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), 
               Aug 14 2007
%F A005187 a(n)=2n-A000120(n); - Paul Barry (pbarry(AT)wit.ie), Oct 26 2007
%F A005187 PURRS demo results: Bounds for a(n) = n+a(1/2*n) with initial conditions 
               a(1) = 1: a(n) >= -2+2*n-log(n)*log(2)^(-1), a(n) <= 1+2*n for each 
               n >= 1 - Alexander R. Povolotsky (pevnev(AT)juno.com), Apr 06 2008
%F A005187 If n = 2^a_1 + 2^a_2 + ... + 2^a_k, then a(n) = n-k. This can be used 
               to prove that 2^n maximally divides (2n!)/n!. [From Jon Perry (johnandruth(AT)jrperry.orangehome.co.uk), 
               Jul 16 2009]
%t A005187 a[0] = 0; a[n_] := a[n] = a[Floor[n/2]] + n; Table[ a[n], {n, 0, 50}] 
               (* or *)
%t A005187 Table[IntegerExponent[(2n)!, 2], {n, 0, 65}] (from Robert G. Wilson v 
               (rgwv(at)rgwv.com), Apr 19 2006).
%o A005187 (PARI) a(n)=if(n<0,0,valuation((2*n)!,2))
%o A005187 (PARI) a(n)=if(n<0,0,sum(k=1,n,(2*n)\2^k))
%o A005187 (PARI) {a(n) = if( n < 0, 0, 2*n - subst( Pol( binary( n ) ), x, 1) ) 
               } /* Michael Somos Aug 28 2007 */
%Y A005187 Cf. A001790, A011371, A001511(n) = a(n+1)-a(n), A046161(n)=2^a(n).
%Y A005187 a(n)=A011371(2n+1)
%Y A005187 Partial sums of A001511.
%Y A005187 Cf. A067080, A098844, A132027, A004128, A054899.
%Y A005187 Sequence in context: A075752 A046541 A047344 this_sequence A091934 A024515 
               A138971
%Y A005187 Adjacent sequences: A005184 A005185 A005186 this_sequence A005188 A005189 
               A005190
%K A005187 nonn,easy,nice
%O A005187 0,3
%A A005187 N. J. A. Sloane (njas(AT)research.att.com), Allan Wilks (allan(AT)research.att.com)
%E A005187 More terms from Jud McCranie (j.mccranie(AT)comcast.net), Jul 04 2000