The OEIS is supported by the many generous donors to the OEIS Foundation.

 Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 59th year, we have over 358,000 sequences, and we’ve crossed 10,300 citations (which often say “discovered thanks to the OEIS”). Other ways to Give
 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A005187 a(n) = a(floor(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) 231
 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, 47, 49, 50, 53, 54, 56, 57, 63, 64, 66, 67, 70, 71, 73, 74, 78, 79, 81, 82, 85, 86, 88, 89, 94, 95, 97, 98, 101, 102, 104, 105, 109, 110, 112, 113, 116, 117, 119, 120, 127, 128 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 COMMENTS Also exponent of the largest power of 2 dividing (2n)! (A010050) and (2n)!! (A000165). Write n in binary: 1ab..yz, then a(n) = 1ab..yz + ... + 1ab + 1a + 1. - Ralf Stephan, Aug 27 2003 Also numbers having a partition into distinct Mersenne numbers > 0; A079559(a(n))=1; complement of A055938. - Reinhard Zumkeller, Mar 18 2009 Wikipedia's article on the "Whitney Immersion theorem" mentions that the quantity 2n - a(n) is involved in the differential topology of manifolds, notably the Immersion Conjecture proved by Ralph Cohen in 1985." - Jonathan Vos Post, Jan 25 2010 For n > 0, denominators for consecutive pairs of integral numerator polynomials L(n+1,x) for the Legendre polynomials with o.g.f. 1 / sqrt(1-tx+x^2). - Tom Copeland, Feb 04 2016 a(n) is the total number of pointers in the first n elements of a perfect skip list. - Alois P. Heinz, Dec 14 2017 a(n) is the position of the n-th a (indexing from 0) in the fixed point of the morphism a -> aab, b -> b. - Jeffrey Shallit, Dec 24 2020 REFERENCES N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence). LINKS N. J. A. Sloane and T. D. Noe, Table of n, a(n) for n = 0..20000 (first 1000 terms from T. D. Noe) J.-P. Allouche, J. Betrema, and J. Shallit, Sur des points fixes de morphismes d'un monoïde libre, RAIRO-Theor. Inf. Appl. 23 (1989), 235-249. Laurent Alonso, Edward M. Reingold, and René Schott, Determining the majority, Inform. Process. Lett. 47 (1993), no. 5, 253-255. Laurent Alonso, Edward M. Reingold, and René Schott, The average-case complexity of determining the majority, SIAM J. Comput. 26 (1997), no. 1, 1-14. Sung-Hyuk Cha, On Integer Sequences Derived from Balanced k-ary Trees, Applied Mathematics in Electrical and Computer Engineering, 2012. 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. - From N. J. A. Sloane, Dec 24 2012 Ralph L. Cohen, The Immersion Conjecture for Differentiable Manifolds, The Annals of Mathematics, 1985: 237-328. [From Jonathan Vos Post, Jan 25 2010] Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint, 2016. Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585. Keith Johnson and Kira Scheibelhut, Rational Polynomials That Take Integer Values at the Fibonacci Numbers, American Mathematical Monthly 123.4 (2016): 338-346. See p. 340. Tanya Khovanova, There are no coincidences, arXiv preprint 1410.2193 [math.CO], 2014. A. Kulshrestha, On Hamming Distance between base-n representations of whole numbers, arXiv:1203.4547 [cs.DM], 2012. Michael E. Saks and Michael Werman, On computing majority by comparisons, Combinatorica 11 (1991), no. 4, 383-387. Ralf Stephan, Some divide-and-conquer sequences ... Ralf Stephan, Table of generating functions Wikipedia, Whitney Immersion Theorem. Allan Wilks, Email to N. J. A. Sloane, Jul 7 1988. FORMULA a(n) = A011371(2n+1) = A011371(n) + n, n >= 0. A046161(n) = 2^a(n). For m>0, let q = floor(log_2(m)); a(2m+1) = 2^q + 3m + Sum_{k>=1} floor((m-2^q)/2^k); a(2m) = a(2m+1) - 1. - Len Smiley a(n) = Sum_{k >= 0} floor(n/2^k) = n + A011371(n). - Henry Bottomley, Jul 03 2001 G.f.: A(x) = Sum_{k>=0} x^(2^k)/((1-x)*(1-x^(2^k))). - Ralf Stephan, Dec 24 2002 a(n) = Sum_{k=1..n} A001511(k), sum of binary Hamming distances between consecutive integers up to n. - Gary W. Adamson, Jun 15 2003 Conjecture: a(n) = 2n + O(log(n)). - Benoit Cloitre, Oct 07 2003 [true as a(n) = 2*n - hamming_weight(2*n). Joerg Arndt, Jun 10 2019] Sum_{n=2^k..2^(k+1)-1} a(n) = 3*4^k - (k+4)*2^(k-1) = A085354(k). - Philippe Deléham, Feb 19 2004 From Hieronymus Fischer, Aug 14 2007: (Start) Recurrence: a(n) = n + a(floor(n/2)); a(2n) = 2n + a(n); a(n*2^m) = 2*n*(2^m-1) + a(n). a(2^m) = 2^(m+1) - 1, m >= 0. Asymptotic behavior: a(n) = 2n + O(log(n)), a(n+1) - a(n) = O(log(n)); this follows from the inequalities below. a(n) <= 2n-1; equality holds for powers of 2. a(n) >= 2n-1-floor(log_2(n)); equality holds for n = 2^m-1, m > 0. lim inf (2n - a(n)) = 1, for n-->oo. lim sup (2n - log_2(n) - a(n)) = 0, for n-->oo. lim sup (a(n+1) - a(n) - log_2(n)) = 1, for n-->oo. (End) a(n) = 2n - A000120(n). - Paul Barry, Oct 26 2007 PURRS demo results: Bounds for a(n) = n + a(n/2) 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 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 a(n) = Sum_{k>=0} A030308(n,k)*A000225(k+1). - Philippe Deléham, Oct 16 2011 a(n) = log_2(denominator(binomial(-1/2,n))). - Peter Luschny, Nov 25 2011 a(2n+1) = a(2n) + 1. - M. F. Hasler, Jan 24 2015 a(n) = A004134(n) - n. - Cyril Damamme, Aug 04 2015 G.f.: (1/(1 - x))*Sum_{k>=0} (2^(k+1) - 1)*x^(2^k)/(1 + x^(2^k)). - Ilya Gutkovskiy, Jul 23 2017 EXAMPLE G.f. = x + 3*x^2 + 4*x^3 + 7*x^4 + 8*x^5 + 10*x^6 + 11*x^7 + 15*x^8 + ... MAPLE A005187 := n -> 2*n - add(i, i=convert(n, base, 2)): seq(A005187(n), n=0..65); # Peter Luschny, Apr 08 2014 MATHEMATICA a[0] = 0; a[n_] := a[n] = a[Floor[n/2]] + n; Table[ a[n], {n, 0, 50}] (* or *) Table[IntegerExponent[(2n)!, 2], {n, 0, 65}] (* Robert G. Wilson v, Apr 19 2006 *) Table[2n-DigitCount[2n, 2, 1], {n, 0, 70}] (* Harvey P. Dale, May 24 2014 *) PROG (PARI) {a(n) = if( n<0, 0, valuation((2*n)!, 2))}; /* Michael Somos, Oct 24 2002 */ (PARI) {a(n) = if( n<0, 0, sum(k=1, n, (2*n)\2^k))}; /* Michael Somos, Oct 24 2002 */ (PARI) {a(n) = if( n<0, 0, 2*n - subst( Pol( binary( n ) ), x, 1) ) }; /* Michael Somos, Aug 28 2007 */ (PARI) a(n)=my(s=n); while(n>>=1, s+=n); s \\ Charles R Greathouse IV, Apr 07 2012 (PARI) a(n)=2*n-hammingweight(n) \\ Charles R Greathouse IV, Jan 07 2013 (Haskell) a005187 n = a005187_list !! n a005187_list = 0 : zipWith (+) [1..] (map (a005187 . (`div` 2)) [1..]) -- Reinhard Zumkeller, Nov 07 2011, Oct 05 2011 (Sage) @CachedFunction def A005187(n): return A005187(n//2) + n if n > 0 else 0 [A005187(n) for n in range(66)] # Peter Luschny, Dec 13 2012 (Magma) [n + Valuation(Factorial(n), 2): n in [0..70]]; // Vincenzo Librandi, Jun 11 2019 (Python) def A005187(n): return 2*n-bin(n).count('1') # Chai Wah Wu, Jun 03 2021 CROSSREFS Cf. A001790, A011371, A067080, A098844, A132027, A004128, A054899, A046161. Cf. A001511 (first differences), A122247 (partial sums). Cf. A004134, A010050, A000165. Sequence in context: A324470 A219897 A047344 * A184835 A184823 A242921 Adjacent sequences: A005184 A005185 A005186 * A005188 A005189 A005190 KEYWORD nonn,easy,nice AUTHOR N. J. A. Sloane, May 20 1991; Allan Wilks, Dec 11 1999 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified December 10 02:09 EST 2022. Contains 358712 sequences. (Running on oeis4.)