|
| |
|
|
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)
|
|
64
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| Also the power of 2 in (2n)!.
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. [From Reinhard Zumkeller, Mar 18 2009]
Equals row sums of triangle A129264, starting with "1". [From Gary W. Adamson, Nov 27 2009]
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). [From Jonathan Vos Post, Jan 25 2010]
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 [From Jon Perry, Jul 16 2010]
|
|
|
REFERENCES
| Laurent Alonso; Edward M. Reingold; Ren\`e Schott, Determining the majority, Inform. Process. Lett. 47 (1993), no. 5, 253-255.
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.
Cohen, Ralph L., "The Immersion Conjecture for Differentiable Manifolds", The Annals of Mathematics, 1985: 237-328. [From Jonathan Vos Post, Jan 25 2010]
Michael E. Saks; Michael Werman, On computing majority by comparisons. Combinatorica 11 (1991), no. 4, 383-387.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
| T. D. Noe, Table of n, a(n) for n=0..1000
R. Stephan, Some divide-and-conquer sequences ...
R. Stephan, Table of generating functions
|
|
|
FORMULA
| 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)
a(n) = Sum{k >= 0}[ n/2^k ] = n+A011371(n). - Henry Bottomley, Jul 03 2001
G.f.: A(x) = Sum(k=0, infinity, x^(2^k)/((1-x)*(1-x^(2^k)))). - Ralf Stephan, Dec 24 2002
a(n) = Sum(k = 1 through n) A001511(k) - number of 1's in binary representation of n. - Gary W. Adamson, Jun 15 2003
Conjecture : a(n)=2n+O(log(n)) - Benoit Cloitre, Oct 07 2003
Sum_{n, 2^k<=n<2^(k+1)} a(n) = 3*4^k - (k+4)*2^(k-1) = A085354(k). - DELEHAM, Feb 19 2004
a(n)= A011371(n)+n, n>=0.
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, Aug 14 2007
a(2^m)=2^(m+1)-1, m>=0. - Hieronymus Fischer, Aug 14 2007
Asymptotic behavior: a(n)=2n+O(log(n)), a(n+1)-a(n)=O(log(n)); this follows from the inequalities below. - Hieronymus Fischer, Aug 14 2007
a(n)<=2n-1; equality holds for powers of 2. - Hieronymus Fischer, Aug 14 2007
a(n)>=2n-1-floor(log_2(n)); equality holds for n=2^m-1, m>0. - Hieronymus Fischer, Aug 14 2007
lim inf (2n-a(n))=1, for n-->oo. - Hieronymus Fischer, Aug 14 2007
lim sup (2n-log_2(n)-a(n))=0, for n-->oo. - Hieronymus Fischer, Aug 14 2007
lim sup (a(n+1)-a(n)-log_2(n))=1, for n-->oo. - Hieronymus Fischer, Aug 14 2007
a(n)=2n-A000120(n); - Paul Barry, Oct 26 2007
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
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, Jul 16 2009]
a(n)=Sum_k>=0 {A030308(n,k)*A000225(k+1)}. - From DELEHAM Philippe, Oct 16 2011.
a(n) = log_{2}(denominator(binomial(-1/2,n))). - Peter Luschny, Nov 25 2011
|
|
|
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}] (from Robert G. Wilson v, Apr 19 2006).
Table[2n-Count[IntegerDigits[2 n, 2], 1], {n, 0, 70}] (* From Harvey P. Dale, Oct 22 2011 *)
|
|
|
PROG
| (PARI) a(n)=if(n<0, 0, valuation((2*n)!, 2))
(PARI) a(n)=if(n<0, 0, sum(k=1, n, (2*n)\2^k))
(PARI) {a(n) = if( n < 0, 0, 2*n - subst( Pol( binary( n ) ), x, 1) ) } /* Michael Somos Aug 28 2007 */
(Haskell)
a005187 n = a005187_list !! n
a005187_list = 0 : zipWith (+) [1..] (map (a005187 . (`div` 2)) [1..])
-- Reinhard Zumkeller, Nov 07 2011, Oct 05 2011
|
|
|
CROSSREFS
| Cf. A001790, A011371, A001511(n) = a(n+1)-a(n), A046161(n)=2^a(n).
a(n)=A011371(2n+1)
Partial sums of A001511.
Cf. A067080, A098844, A132027, A004128, A054899.
Sequence in context: A075752 A046541 A047344 * A184835 A184823 A091934
Adjacent sequences: A005184 A005185 A005186 * A005188 A005189 A005190
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com), Allan Wilks (allan(AT)research.att.com)
|
|
|
EXTENSIONS
| More terms from Jud McCranie (JudMcCranie(AT)ugaalum.uga.edu), Jul 04 2000
|
| |
|
|
