login
This site is supported by donations to The OEIS Foundation.

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A011371 a(n) = n minus (number of 1's in binary expansion of n). Also highest power of 2 dividing n!. 75
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; text; internal format)
OFFSET

0,5

COMMENTS

Entries of A005187 repeated. - Lekraj Beedassy, 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 del Arte, Jul 27 2004

Also the number of trailing zeros in the base-2 representation of n!. - Hieronymus Fischer, Jun 18 2007

Partial sums of A007814. - Philippe Deléham, Jun 21 2012

If n is in A089633 and n > 0, then a(n) = n - floor(log_{2}(n + 1)). - Douglas Latimer, Jul 25 2012

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.

H. Davenport, The Higher Arithmetic, 7th ed. 1999, Cambridge University Press, p. 216, exercise 1.07.

Michael E. Saks and Michael Werman, On computing majority by comparisons. Combinatorica 11 (1991), no. 4, 383-387.

LINKS

T. D. Noe and Hieronymus Fischer, Table of n, a(n) for n = 0..10000 (first 1000 terms from T. D. Noe)

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

K. Matthews, Computing the prime-power factorization of n!

A. Mir, F. Rossello and L. Rotger, A new balance index for phylogenetic trees, Arxiv preprint arXiv:1202.1223, 2012

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, Apr 24 2001

G.f.: A(x) = 1/(1 - x)*Sum(k = 1, infinity, x^(2^k)/(1 - x^(2^k))). - Ralf Stephan, Apr 11 2002

a(n) = n - A000120(n). - Lekraj Beedassy, Sep 01 2003

a(n) = A005187(n) - n, n >= 0.

a(n) = A007814(A000142(n)). - Reinhard Zumkeller, Apr 09 2004

Contribution from Hieronymus Fischer, Jun 25 and Aug 13 2007 (Start):

a(n) = sum{2 <= k <= n, sum{j|k, j >= 2, floor(log_2(j)) - floor(log_2(j - 1))}}.

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.

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))}.

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).

a(2^m) = 2^m-1, m>=0.

Asymptotic behavior:

a(n) = n + O(log(n)),

a(n + 1) - a(n) = O(log(n)), which follows from the inequalities below.

a(n) <= n - 1; equality holds for powers of 2.

a(n) >= n - 1 - floor(log_2(n)); equality holds for n = 2^m - 1, m > 0.

lim inf (n - a(n)) = 1, for n-->oo.

lim sup (n - log_2(n) - a(n)) = 0, for n-->oo.

lim sup (a(n + 1) - a(n) - log_2(n)) = 0, for n-->oo. (End)

a(n) = Sum_k >= 0 {A030308(n, k)*A000225(k)}.- From Philippe Deléham, Oct 16 2011

EXAMPLE

a(3) = 1 because 3 in binary is 11 (two 1s) and 3 - 2 = 1.

a(4) = 3 because 4 in binary is 100 (one 1 and two 0s) and 4 - 1 = 3.

a(5) = 3 because 5 in binary is 101 (a zero between two 1s) and 5 - 2 = 3.

a(100) = 97.

a(10^3) = 994.

a(10^4) = 9995.

a(10^5) = 99994.

a(10^6) = 999993.

a(10^7) = 9999992.

a(10^8) = 99999988.

a(10^9) = 999999987.

MAPLE

A011371(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) ].

A011371 := n -> n - add(i, i=convert(n, base, 2)) # From Peter Luschny, May 02 2009

read("transforms") : A011371 := proc(n) n-wt(n) ; end proc: # R. J. Mathar, May 15 2013

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))} \\ Michael Somos, Oct 24 2002

(PARI) {a(n) = if( n<0, 0, sum(k=1, n, n\2^k))} \\ Michael Somos, Oct 24 2002

(PARI) {a(n) = if( n<0, 0, n - subst( Pol( binary( n ) ), x, 1) ) } \\ Michael Somos, Aug 28 2007

(PARI) a(n)=sum(k=1, log(n+1)\log(2), n>>k) \\ Charles R Greathouse IV, Oct 03 2012

(PARI) a(n)=my(s); while(n>>=1, s+=n); s \\ Charles R Greathouse IV, Aug 09 2013

(MAGMA) [Valuation(Factorial(n), 2): n in [0..80]]; // Bruno Berselli, Aug 05 2013

(Haskell)

a011371 n = n - a000120 n  -- Reinhard Zumkeller, Jan 24 2014

CROSSREFS

Cf. A000120, A005187, A054861.

a(n) = sum(A007814(k), k = 1 .. n), n >= 1, a(0) = 0.

Cf. A032799, A067080, A098844, A132027.

Sequence in context: A240116 A007768 A180018 * A097355 A003860 A108216

Adjacent sequences:  A011368 A011369 A011370 * A011372 A011373 A011374

KEYWORD

nonn,nice,easy

AUTHOR

N. J. A. Sloane.

EXTENSIONS

More terms from Robert G. Wilson v, Oct 02 2001

Examples added by Hieronymus Fischer, Jun 06 2012

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified April 16 06:39 EDT 2014. Contains 240546 sequences.