|
| |
|
|
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)
|
|
81
|
|
|
|
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 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. - Reinhard Zumkeller, Mar 18 2009
Equals row sums of triangle A129264, starting with "1". - 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). - 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. - Jon Perry, Jul 16 2010
a(n) is the sum of binary Hamming distances between consecutive integers up to n. - Anunay Kulshrestha, Jun 16 2012
|
|
|
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.
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
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
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
A. Kulshrestha, On Hamming Distance between base-n representations of whole numbers
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). - Philippe Deléham, Feb 19 2004
a(n)= A011371(n)+n, n>=0.
Contribution 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(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!. - 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
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
|
|
|
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-Count[IntegerDigits[2 n, 2], 1], {n, 0, 70}] (* 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 */
(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
|
|
|
CROSSREFS
|
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.
Sequence in context: A046541 A219897 A047344 * A184835 A184823 A091934
Adjacent sequences: A005184 A005185 A005186 * A005188 A005189 A005190
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
N. J. A. Sloane, _Allan Wilks_
|
|
|
EXTENSIONS
|
More terms from Jud McCranie, Jul 04 2000
|
|
|
STATUS
|
approved
|
| |
|
|
