This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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. (Formerly M2330) 82

%I M2330

%S 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 47,49,50,53,54,56,57,63,64,66,67,70,71,73,74,78,79,81,82,85,86,88,89,

%U 94,95,97,98,101,102,104,105,109,110,112,113,116,117,119,120,127,128

%N 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 Also the power of 2 in (2n)!.

%C Write n in binary: 1ab..yz, then a(n) = 1ab..yz + ... + 1ab + 1a + 1. - _Ralf Stephan_, Aug 27 2003

%C Also numbers having a partition into distinct Mersenne numbers >0; A079559(a(n))=1; complement of A055938. - _Reinhard Zumkeller_, Mar 18 2009

%C Equals row sums of triangle A129264, starting with "1". - _Gary W. Adamson_, Nov 27 2009

%C In differential topology, after the Whitney immersion theorem, Massey went on to prove that every n-dimensional manifold is cobordant to a manifold that immerses in R^(2n - a(n)) where a(n) is the number of 1's that appear in the binary expansion of n. This was proved by Ralph Cohen (1985). - _Jonathan Vos Post_, Jan 25 2010

%C a(n) is the sum of progressive halves and floors. e.g. for a(10) we consider 20. First we halve and floor, so 10, and continue, 5,2,1, so a(10)=18. a(15) we go from 30, so 15+7+3+1=26. - _Jon Perry_, Jul 16 2010

%C a(n) is the sum of binary Hamming distances between consecutive integers up to n. - _Anunay Kulshrestha_, Jun 16 2012

%D Laurent Alonso; Edward M. Reingold; Ren\`e Schott, Determining the majority, Inform. Process. Lett. 47 (1993), no. 5, 253-255.

%D 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 Sung-Hyuk Cha, On Integer Sequences Derived from Balanced k-ary Trees, Applied Mathematics in Electrical and Computer Engineering, http://www.wseas.us/e-library/conferences/2012/CambridgeUSA/MATHCC/MATHCC-60.pdf, 2012. - From _N. J. A. Sloane_, Jun 12 2012

%D Sung-Hyuk Cha, On Complete and Size Balanced k-ary Tree Integer Sequences, INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS AND INFORMATICS, Issue 2, Volume 6, 2012, pp. 67-75; http://naun.org/multimedia/UPress/ami/16-125.pdf. - From _N. J. A. Sloane_, Dec 24 2012

%D Cohen, Ralph L., "The Immersion Conjecture for Differentiable Manifolds", The Annals of Mathematics, 1985: 237-328. [From Jonathan Vos Post, Jan 25 2010]

%D Michael E. Saks; Michael Werman, On computing majority by comparisons. Combinatorica 11 (1991), no. 4, 383-387.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H T. D. Noe, <a href="/A005187/b005187.txt">Table of n, a(n) for n = 0..1000</a>

%H A. Kulshrestha, <a href="http://arxiv.org/abs/1203.4547">On Hamming Distance between base-n representations of whole numbers</a>

%H R. Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>

%H R. Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>

%F 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 a(n) = Sum{k >= 0}[ n/2^k ] = n+A011371(n). - _Henry Bottomley_, Jul 03 2001

%F G.f.: A(x) = Sum(k=0, infinity, x^(2^k)/((1-x)*(1-x^(2^k)))). - _Ralf Stephan_, Dec 24 2002

%F a(n) = Sum(k = 1 through n) A001511(k) - number of 1's in binary representation of n. - _Gary W. Adamson_, Jun 15 2003

%F Conjecture : a(n)=2n+O(log(n)) - _Benoit Cloitre_, Oct 07 2003

%F Sum_{n, 2^k<=n<2^(k+1)} a(n) = 3*4^k - (k+4)*2^(k-1) = A085354(k). - _Philippe Deléham_, Feb 19 2004

%F a(n)= A011371(n)+n, n>=0.

%F Contribution from Hieronymus Fischer, Aug 14 2007 (Start):

%F Recurrence: a(n)=n+a(floor(n/2)); a(2n)=2n+a(n); a(n*2^m)=2*n*(2^m-1)+a(n).

%F a(2^m)=2^(m+1)-1, m>=0.

%F Asymptotic behavior: a(n)=2n+O(log(n)), a(n+1)-a(n)=O(log(n)); this follows from the inequalities below.

%F a(n)<=2n-1; equality holds for powers of 2.

%F a(n)>=2n-1-floor(log_2(n)); equality holds for n=2^m-1, m>0.

%F lim inf (2n-a(n))=1, for n-->oo.

%F lim sup (2n-log_2(n)-a(n))=0, for n-->oo.

%F lim sup (a(n+1)-a(n)-log_2(n))=1, for n-->oo. (End)

%F a(n)=2n-A000120(n); - _Paul Barry_, Oct 26 2007

%F 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_, Apr 06 2008

%F 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!. - _Jon Perry_, Jul 16 2009

%F a(n)=Sum_k>=0 {A030308(n,k)*A000225(k+1)}. - _Philippe Deléham_, Oct 16 2011.

%F a(n) = log_{2}(denominator(binomial(-1/2,n))). - _Peter Luschny_, Nov 25 2011

%F G.f. x*(1+(x-1)*x/(G(0)+x-x^2))/(1-x)^2 where G(k) = 2*(x^(2^(k+1))) - (x^(2^k)) - 1 - ((x^(2^(k+1)))-2*(x^(4*2^k))+(x^(6*2^k)))/G(k+1); (continued fraction, 1st kind, 1-step). - _Sergei N. Gladkovskii_, Jul 30 2012

%t a[0] = 0; a[n_] := a[n] = a[Floor[n/2]] + n; Table[ a[n], {n, 0, 50}] (* or *)

%t Table[IntegerExponent[(2n)!, 2], {n, 0, 65}] (* _Robert G. Wilson v_, Apr 19 2006 *)

%t Table[2n-Count[IntegerDigits[2 n,2],1],{n,0,70}] (* _Harvey P. Dale_, Oct 22 2011 *)

%o (PARI) a(n)=if(n<0,0,valuation((2*n)!,2))

%o (PARI) a(n)=if(n<0,0,sum(k=1,n,(2*n)\2^k))

%o (PARI) {a(n) = if( n < 0, 0, 2*n - subst( Pol( binary( n ) ), x, 1) ) } /* Michael Somos Aug 28 2007 */

%o (PARI) a(n)=my(s=n);while(n>>=1,s+=n);s \\ _Charles R Greathouse IV_, Apr 07 2012

%o (PARI) a(n)=2*n-hammingweight(n) \\ _Charles R Greathouse IV_, Jan 07 2013

%o a005187 n = a005187_list !! n

%o a005187_list = 0 : zipWith (+) [1..] (map (a005187 . (`div` 2)) [1..])

%o -- _Reinhard Zumkeller_, Nov 07 2011, Oct 05 2011

%o (Sage)

%o @CachedFunction

%o def A005187(n): return A005187(n//2) + n if n > 0 else 0

%o [A005187(n) for n in range(66)] # _Peter Luschny_, Dec 13 2012

%Y Cf. A001790, A011371, A067080, A098844, A132027, A004128, A054899. A001511(n) = a(n+1)-a(n), A046161(n) = 2^a(n), a(n) = A011371(2n+1). Partial sums of A001511.

%K nonn,easy,nice

%O 0,3

%A _N. J. A. Sloane_, _Allan Wilks_

%E More terms from _Jud McCranie_, Jul 04 2000

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Puzzles | Hot | Classics
Recent Additions | More pages | Superseeker | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .