

A011371


a(n) = n minus (number of 1's in binary expansion of n). Also highest power of 2 dividing n!.


126



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 nth number of this sequence.  Alonso del Arte, Jul 27 2004
Also the number of trailing zeros in the base2 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
For n > 1, denominators for integral numerator polynomials L(n,x) for the Legendre polynomials with o.g.f. 1 / sqrt(1tx+x^2).  Tom Copeland, Feb 04 2016
The definition of this sequence explains why, for n>1, the highest power of 2 dividing n! added to the number of 1's in the binary expansion of n is equal to n. This result is due to the French mathematician Adrien Legendre (17521833) [see the Honsberger reference].  Bernard Schott, Apr 07 2017
a(n) is the total number of 2's in the prime factorizations over the first n positive integers. The expected number of 2's in the factorization of an integer n is 1 (as n>infinity). Generally, the expected number of p's (for a prime p) is 1/(p1).  Geoffrey Critzer, Jun 05 2017


REFERENCES

K. Atanassov, On Some of Smarandache's Problems, section 7, on the 61st problem, page 42, American Research Press, 1999, 1621.
G. Bachman, Introduction to pAdic 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.
R. Honsberger, Mathematical Gems II, Dolciani Mathematical Expositions, 1976, pages 16.


LINKS

T. D. Noe and Hieronymus Fischer, Table of n, a(n) for n = 0..10000 (first 1000 terms from T. D. Noe)
Laurent Alonso; Edward M. Reingold; René Schott, Determining the majority, Inform. Process. Lett. 47 (1993), no. 5, 253255.
Laurent Alonso; Edward M. Reingold; René Schott, The averagecase complexity of determining the majority, SIAM J. Comput. 26 (1997), no. 1, 114.
SungHyuk Cha, On Integer Sequences Derived from Balanced kary Trees, Applied Mathematics in Electrical and Computer Engineering, 2012.
SungHyuk Cha, On Complete and Size Balanced kary Tree Integer Sequences, International Journal of Applied Mathematics and Informatics, Issue 2, Volume 6, 2012, pp. 6775.  From N. J. A. Sloane, Dec 24 2012
R. Hinze, Concrete stream calculus: An extended study, J. Funct. Progr. 20 (56) (2010) 463535, doi, Section 4.4.
Keith Johnson and Kira Scheibelhut, Rational polynomials that take integer values at the Fibonacci numbers, American Mathematical Monthly 123.4 (2016): 338346. See omega_2.
SC Liu, J. C.C. Yeh, Catalan numbers modulo 2^k, J. Int. Seq. 13 (2010), 10.5.4, eq. (5).
K. Matthews, Computing the primepower factorization of n!
A. Mir, F. Rossello and L. Rotger, A new balance index for phylogenetic trees, arXiv preprint arXiv:1202.1223 [qbio.PE], 2012.
A. M. OllerMarcen, J. Maria Grau, On the Baseb Expansion of the Number of Trailing Zeros of b^k!, J. Int. Seq. 14 (2011) 11.6.8
Michael E. Saks; Michael Werman, On computing majority by comparisons, Combinatorica 11 (1991), no. 4, 383387.
Zhujun Zhang, A Note on Counting Binomial Heaps, ResearchGate (2019).
R. Stephan, Some divideandconquer sequences ...
R. Stephan, Table of generating functions


FORMULA

a(n) = a(floor(n/2)) + floor(n/2) = floor(n/2) + floor(n/4) + floor(n/8) + floor(n/16) + ...  Henry Bottomley, Apr 24 2001
G.f.: A(x) = (1/(1  x))*Sum_{k>=1} 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
From Hieronymus Fischer, Jun 25 and Aug 13 2007: (Start)
a(n) = Sum_{k=2..n} Sum_{jk, 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)/(1x), where c(k) = Sum_{j > 1, jk} (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).  Philippe Deléham, Oct 16 2011
a(n) = (Sum_{k=0..(floor(log_2(n + 1))))*f^(k + 1)(n), where f(n) = (n  (n mod 2))/2 and f^(k + 1) is the (k + 1)th composition of f.  Joseph Wheat, Mar 01 2018


EXAMPLE

a(3) = 1 because 3 in binary is 11 (two 1's) and 3  2 = 1.
a(4) = 3 because 4 in binary is 100 (one 1 and two 0's) and 4  1 = 3.
a(5) = 3 because 5 in binary is 101 (a zero between two 1's) 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.
G.f. = x^2 + x^3 + 3*x^4 + 3*x^5 + 4*x^6 + 4*x^7 + 7*x^8 + 7*x^9 + 8*x^10 + ...


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)): # Peter Luschny, May 02 2009
read("transforms") : A011371 := proc(n) nwt(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
(PARI) a(n) = n  hammingweight(n); \\ Michel Marcus, Jun 05 2014
(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
(Python) [n  bin(n)[2:].count("1") for n in range(101)] # Indranil Ghosh, Apr 09 2017


CROSSREFS

Cf. A000120, A005187, A054861, A032799, A067080, A098844, A132027.
a(n) = Sum_{k=1..n} A007814(k), n >= 1, a(0) = 0.
Sequence in context: A240116 A007768 A180018 * A325123 A097355 A258057
Adjacent sequences: A011368 A011369 A011370 * A011372 A011373 A011374


KEYWORD

nonn,nice,easy


AUTHOR

N. J. A. Sloane


EXTENSIONS

Examples added by Hieronymus Fischer, Jun 06 2012


STATUS

approved



