|
| |
|
|
A011371
|
|
n minus (number of 1's in binary expansion of n). Also highest power of 2 dividing n!.
|
|
53
| |
|
|
0, 0, 1, 1, 3, 3, 4, 4, 7, 7, 8, 8, 10, 10, 11, 11, 15, 15, 16, 16, 18, 18, 19, 19, 22, 22, 23, 23, 25, 25, 26, 26, 31, 31, 32, 32, 34, 34, 35, 35, 38, 38, 39, 39, 41, 41, 42, 42, 46, 46, 47, 47, 49, 49, 50, 50, 53, 53, 54, 54, 56, 56, 57, 57, 63, 63, 64, 64, 66, 66, 67, 67, 70
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,5
|
|
|
COMMENTS
| a(n) = A007814(A000142(n)). - Reinhard Zumkeller (reinhard.zumkeller(AT)gmail.com), Apr 09 2004
Entries of A005187 appearing twice. - Lekraj Beedassy (blekraj(AT)yahoo.com), Jul 06 2004
This sequence shows why in binary 0 and 1 are the only two numbers n such that n equals the sum of its digits raised to the consecutive powers (equivalent to the base 10 sequence A032799). 1 raised to any consecutive power is still 1 and thus any the sum of digits raised to consecutive powers for any n > 1 falls short of equaling the value of n by the n-th number of this sequence. - Alonso Delarte (alonso.delarte(AT)gmail.com), Jul 27 2004
Also the number of trailing zeros in the base-2 representation of n!. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Jun 18 2007
|
|
|
REFERENCES
| Laurent Alonso, Edward M. Reingold and Ren\`e Schott, Determining the majority, Inform. Process. Lett. 47 (1993), no. 5, 253-255.
Laurent Alonso, Edward M. Reingold and Ren\`e Schott, The average-case complexity of determining the majority, SIAM J. Comput. 26 (1997), no. 1, 1-14.
K. Atanassov, On Some of Smarandache's Problems, section 7, on the 61-st problem, page 42, American Research Press, 1999, 16-21.
G. Bachman, Introduction to p-Adic Numbers and Valuation Theory, Academic Press, 1964; see Lemma 3.1.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 305.
Michael E. Saks and Michael Werman, On computing majority by comparisons. Combinatorica 11 (1991), no. 4, 383-387.
|
|
|
LINKS
| T. D. Noe, Table of n, a(n) for n=0..1000
K. Atanassov, On Some of Smarandache's Problems
K. Matthews, Computing the prime-power factorization of n!
R. Stephan, Some divide-and-conquer sequences ...
R. Stephan, Table of generating functions
|
|
|
FORMULA
| a(n) =a([n/2])+[n/2] =[n/2]+[n/4]+[n/8]+[n/16]+... - Henry Bottomley (se16(AT)btinternet.com), Apr 24 2001
G.f.: A(x) = 1/(1-x)*Sum(k=1, infinity, x^(2^k)/(1-x^(2^k))). - Ralf Stephan (ralf(AT)ark.in-berlin.de), Apr 11 2002
a(n) = n - A000120(n). - Lekraj Beedassy (blekraj(AT)yahoo.com), Sep 01 2003
a(n)=A005187(n)-n, n>=0.
a(n)=sum{2<=k<=n, sum{j|k,j>=2, floor(log_2(j))-floor(log_2(j-1))}}. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Jun 18 2007
The g.f. can be expressed in terms of a Lambert series, in that g(x)=L[b(k)](x)/(1-x) where L[b(k)](x)=sum{k>=0, b(k)*x^k/(1-x^k)} is a Lambert series with b(k)=1, if k is a power of 2, else b(k)=0. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Jun 25 2007
G.f.: g(x)=sum{k>0, c(k)*x^k}/(1-x), where c(k)=sum{j>1,j|k, floor(log_2(j))-floor(log_2(j-1))}. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Jun 25 2007
Recurrence: a(n)=floor(n/2)+a(floor(n/2)); a(2*n)=n+a(n); a(n*2^m)=n*(2^m-1)+a(n). - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Aug 13 2007
a(2^m)=2^m-1, m>=0. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Aug 13 2007
Asymptotic behavior: a(n)=n+O(log(n)), a(n+1)-a(n)=O(log(n)), which follows from the inequalities below. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Aug 13 2007
a(n)<=n-1; equality holds for powers of 2. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Aug 13 2007
a(n)>=n-1-floor(log_2(n)); equality holds for n=2^m-1, m>0. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Aug 13 2007
lim inf (n-a(n))=1, for n-->oo. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Aug 13 2007
lim sup (n-log_2(n)-a(n))=0, for n-->oo. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Aug 13 2007
lim sup (a(n+1)-a(n)-log_2(n))=0, for n-->oo. - Hieronymus Fischer (Hieronymus.Fischer(AT)gmx.de), Aug 13 2007
a(n)=Sum_k>=0 {A030308(n,k)*A000225(k)}.- From DELEHAM Philippe, Oct 16 2011
|
|
|
MAPLE
| a(n) = RETURN(((2^(l))-1)+sum('(j*floor((n-(2^l)+2^j)/(2^(j+1))))', 'j'=1..l)); # after K. Atanassov. Here l is [ log2(n) ].
a := n -> n - add(i, i=convert(n, base, 2)) [From Peter Luschny (peter(AT)luschny.de), May 02 2009]
|
|
|
MATHEMATICA
| -1+Length[ Last[ Split[ IntegerDigits[ 2(n!), 2 ] ] ] ], FoldList[ Plus, 0, Fold[ Flatten[ {#1, #2, #1} ]&, 0, Range[ 6 ] ] ]
Table[IntegerExponent[n!, 2], {n, 0, 127}]; Table[n-DigitCount[n, 2, 1], {n, 0, 127}]
Table[t = 0; p = 2; While[s = Floor[n/p]; t = t + s; s > 0, p *= 2]; t, {n, 0, 100} ]
|
|
|
PROG
| (PARI) a(n)=if(n<0, 0, valuation(n!, 2))
(PARI) a(n)=if(n<0, 0, sum(k=1, n, n\2^k))
(PARI) {a(n) = if( n < 0, 0, n - subst( Pol( binary( n ) ), x, 1) ) } /* Michael Somos Aug 28 2007 */
|
|
|
CROSSREFS
| Cf. A000120, A005187, A054861.
a(n)=sum(A007814(k), k=1..n), n >= 1, a(0)=0.
Cf. A032799.
Cf. A067080, A098844, A132027.
Sequence in context: A198465 A007768 A180018 * A097355 A003860 A108216
Adjacent sequences: A011368 A011369 A011370 * A011372 A011373 A011374
|
|
|
KEYWORD
| nonn,nice,easy
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| More terms from Robert G. Wilson v (rgwv(AT)rgwv.com), Oct 02 2001
|
| |
|
|
