cp's OEIS Frontend

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.

%I A005187 M2330 #255 Mar 01 2025 12:11:38
%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(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.
%C A005187 Also exponent of the largest power of 2 dividing (2n)! (A010050) and (2n)!! (A000165).
%C A005187 Write n in binary: 1ab..yz, then a(n) = 1ab..yz + ... + 1ab + 1a + 1. - _Ralf Stephan_, Aug 27 2003
%C A005187 Also numbers having a partition into distinct Mersenne numbers > 0; A079559(a(n))=1; complement of A055938. - _Reinhard Zumkeller_, Mar 18 2009
%C A005187 Wikipedia's article on the "Whitney Immersion theorem" mentions that the a(n)-dimensional sphere arises in the Immersion Conjecture proved by Ralph Cohen in 1985. - _Jonathan Vos Post_, Jan 25 2010
%C A005187 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
%C A005187 a(n) is the total number of pointers in the first n elements of a perfect skip list. - _Alois P. Heinz_, Dec 14 2017
%C A005187 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
%C A005187 Numbers that can be expressed as the sum of distinct numbers of the form 2^k - 1 (lenient Mersenne numbers, A000225). This follows from the 2N - Hamming weight definition. A corollary is that these are the numbers with no 2 in their skew-binary representation (cf. A169683). - _Allan C. Wechsler_, Feb 25 2025
%D A005187 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005187 N. J. A. Sloane, <a href="/A005187/b005187.txt">Table of n, a(n) for n = 0..20000</a> (first 1000 terms from T. D. Noe)
%H A005187 Jean-Paul Allouche, Jean Bétréma, and Jeffrey Shallit, <a href="https://doi.org/10.1051/ita/1989230302351">Sur des points fixes de morphismes d'un monoïde libre</a>, RAIRO-Theor. Inf. Appl. 23 (1989), 235-249.
%H A005187 Laurent Alonso, Edward M. Reingold, and René Schott, <a href="http://dx.doi.org/10.1016/0020-0190(93)90135-V">Determining the majority</a>, Inform. Process. Lett. 47 (1993), no. 5, 253-255.
%H A005187 Laurent Alonso, Edward M. Reingold, and René Schott, <a href="http://dx.doi.org/10.1137/S0097539794275914">The average-case complexity of determining the majority</a>, SIAM J. Comput. 26 (1997), no. 1, 1-14.
%H A005187 Barry Brent, <a href="https://doi.org/10.20944/preprints202306.1164.v6">On the Constant Terms of Certain Laurent Series</a>, Preprints (2023) 2023061164.
%H A005187 Sung-Hyuk Cha, <a href="http://www.wseas.us/e-library/conferences/2012/CambridgeUSA/MATHCC/MATHCC-60.pdf">On Integer Sequences Derived from Balanced k-ary Trees</a>, Applied Mathematics in Electrical and Computer Engineering, 2012.
%H A005187 Sung-Hyuk Cha, <a href="http://naun.org/multimedia/UPress/ami/16-125.pdf">On Complete and Size Balanced k-ary Tree Integer Sequences</a>, International Journal of Applied Mathematics and Informatics, Issue 2, Volume 6, 2012, pp. 67-75. - From _N. J. A. Sloane_, Dec 24 2012
%H A005187 Ralph L. Cohen, <a href="http://www.jstor.org/stable/1971304">The Immersion Conjecture for Differentiable Manifolds</a>, The Annals of Mathematics, 1985: 237-328.
%H A005187 Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, <a href="http://www2.math.uu.se/~svante/papers/sj315.pdf">Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications</a>, preprint, 2016.
%H A005187 Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, <a href="https://doi.org/10.1145/3127585">Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications</a>, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
%H A005187 Keith Johnson and Kira Scheibelhut, <a href="http://www.jstor.org/stable/10.4169/amer.math.monthly.123.4.338">Rational Polynomials That Take Integer Values at the Fibonacci Numbers</a>, American Mathematical Monthly 123.4 (2016): 338-346. See p. 340.
%H A005187 Tanya Khovanova, <a href="http://arxiv.org/abs/1410.2193">There are no coincidences</a>, arXiv preprint 1410.2193 [math.CO], 2014.
%H A005187 Anunay Kulshrestha, <a href="http://arxiv.org/abs/1203.4547">On Hamming Distance between base-n representations of whole numbers</a>, arXiv:1203.4547 [cs.DM], 2012.
%H A005187 Michael E. Saks and Michael Werman, <a href="http://dx.doi.org/10.1007/BF01275672">On computing majority by comparisons</a>, Combinatorica 11 (1991), no. 4, 383-387.
%H A005187 Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>
%H A005187 Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>
%H A005187 Wikipedia, <a href="http://en.wikipedia.org/wiki/Whitney_immersion_theorem">Whitney Immersion Theorem</a>.
%H A005187 Allan Wilks, <a href="/A005187/a005187.pdf">Email to N. J. A. Sloane</a>, Jul 7 1988.
%F A005187 a(n) = A011371(2n+1) = A011371(n) + n, n >= 0.
%F A005187 A046161(n) = 2^a(n).
%F A005187 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_
%F A005187 a(n) = Sum_{k >= 0} floor(n/2^k) = n + A011371(n). - _Henry Bottomley_, Jul 03 2001
%F A005187 G.f.: A(x) = Sum_{k>=0} x^(2^k)/((1-x)*(1-x^(2^k))). - _Ralf Stephan_, Dec 24 2002
%F A005187 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
%F A005187 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]
%F A005187 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
%F A005187 From _Hieronymus Fischer_, Aug 14 2007: (Start)
%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).
%F A005187   a(2^m) = 2^(m+1) - 1, m >= 0.
%F A005187 Asymptotic behavior: a(n) = 2n + O(log(n)), a(n+1) - a(n) = O(log(n)); this follows from the inequalities below.
%F A005187 a(n) <= 2n-1; equality holds for powers of 2.
%F A005187 a(n) >= 2n-1-floor(log_2(n)); equality holds for n = 2^m-1, m > 0.
%F A005187 lim inf (2n - a(n)) = 1, for n-->oo.
%F A005187 lim sup (2n - log_2(n) - a(n)) = 0, for n-->oo.
%F A005187 lim sup (a(n+1) - a(n) - log_2(n)) = 1, for n-->oo. (End)
%F A005187 a(n) = 2n - A000120(n). - _Paul Barry_, Oct 26 2007
%F A005187 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
%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!. - _Jon Perry_, Jul 16 2009
%F A005187 a(n) = Sum_{k>=0} A030308(n,k)*A000225(k+1). - _Philippe Deléham_, Oct 16 2011
%F A005187 a(n) = log_2(denominator(binomial(-1/2,n))). - _Peter Luschny_, Nov 25 2011
%F A005187 a(2n+1) = a(2n) + 1. - _M. F. Hasler_, Jan 24 2015
%F A005187 a(n) = A004134(n) - n. - _Cyril Damamme_, Aug 04 2015
%F A005187 G.f.: (1/(1 - x))*Sum_{k>=0} (2^(k+1) - 1)*x^(2^k)/(1 + x^(2^k)). - _Ilya Gutkovskiy_, Jul 23 2017
%e A005187 G.f. = x + 3*x^2 + 4*x^3 + 7*x^4 + 8*x^5 + 10*x^6 + 11*x^7 + 15*x^8 + ...
%p A005187 A005187 := n -> 2*n - add(i, i=convert(n, base, 2)):
%p A005187 seq(A005187(n), n=0..65); # _Peter Luschny_, Apr 08 2014
%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}] (* _Robert G. Wilson v_, Apr 19 2006 *)
%t A005187 Table[2n-DigitCount[2n,2,1],{n,0,70}] (* _Harvey P. Dale_, May 24 2014 *)
%o A005187 (PARI) {a(n) = if( n<0, 0, valuation((2*n)!, 2))}; /* _Michael Somos_, Oct 24 2002 */
%o A005187 (PARI) {a(n) = if( n<0, 0, sum(k=1, n, (2*n)\2^k))}; /* _Michael Somos_, Oct 24 2002 */
%o A005187 (PARI) {a(n) = if( n<0, 0, 2*n - subst( Pol( binary( n ) ), x, 1) ) }; /* _Michael Somos_, Aug 28 2007 */
%o A005187 (PARI) a(n)=my(s=n);while(n>>=1,s+=n);s \\ _Charles R Greathouse IV_, Apr 07 2012
%o A005187 (PARI) a(n)=2*n-hammingweight(n) \\ _Charles R Greathouse IV_, Jan 07 2013
%o A005187 (Haskell)
%o A005187 a005187 n = a005187_list !! n
%o A005187 a005187_list = 0 : zipWith (+) [1..] (map (a005187 . (`div` 2)) [1..])
%o A005187 -- _Reinhard Zumkeller_, Nov 07 2011, Oct 05 2011
%o A005187 (Sage)
%o A005187 @CachedFunction
%o A005187 def A005187(n): return A005187(n//2) + n if n > 0 else 0
%o A005187 [A005187(n) for n in range(66)]  # _Peter Luschny_, Dec 13 2012
%o A005187 (Magma) [n + Valuation(Factorial(n), 2): n in [0..70]]; // _Vincenzo Librandi_, Jun 11 2019
%o A005187 (Python)
%o A005187 def A005187(n): return 2*n-bin(n).count('1') # _Chai Wah Wu_, Jun 03 2021
%Y A005187 Cf. A001790, A011371, A067080, A098844, A132027, A004128, A054899, A046161.
%Y A005187 Cf. A001511 (first differences), A122247 (partial sums), A055938 (complement).
%Y A005187 Cf. A004134, A010050, A000165.
%Y A005187 Cf. A000120, A079559, A085354, A030308, A000225.
%K A005187 nonn,easy,nice
%O A005187 0,3
%A A005187 _N. J. A. Sloane_, May 20 1991; _Allan Wilks_, Dec 11 1999