A011371 a(n) = n minus (number of 1's in binary expansion of n). Also highest power of 2 dividing n!.
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
Offset: 0
Examples
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 + ...
References
- K. Atanassov, On Some of Smarandache's Problems, section 7, on the 61st 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.
- R. Honsberger, Mathematical Gems II, Dolciani Mathematical Expositions, 1976, pp. 1-6.
Links
- Hieronymus Fischer, Table of n, a(n) for n = 0..10000 (first 1000 terms from T. D. Noe)
- Laurent Alonso, Edward M. Reingold, and René Schott, Determining the majority, Inform. Process. Lett. 47 (1993), no. 5, 253-255.
- Laurent Alonso, Edward M. Reingold, and René 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, 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
- R. Hinze, Concrete stream calculus: An extended study, J. Funct. Progr. 20 (5-6) (2010) 463-535, 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): 338-346. See omega_2.
- S-C Liu and J. C.-C. Yeh, Catalan numbers modulo 2^k, J. Int. Seq. 13 (2010), 10.5.4, eq. (5).
- 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 [q-bio.PE], 2012.
- A. M. Oller-Marcen and J. Maria Grau, On the Base-b Expansion of the Number of Trailing Zeros of b^k!, J. Int. Seq. 14 (2011) 11.6.8.
- Michael E. Saks and Michael Werman, On computing majority by comparisons, Combinatorica 11 (1991), no. 4, 383-387.
- Ralf Stephan, Some divide-and-conquer sequences ...
- Ralf Stephan, Table of generating functions.
- Zhujun Zhang, A Note on Counting Binomial Heaps, ResearchGate (2019).
Crossrefs
Programs
-
Haskell
a011371 n = n - a000120 n -- Reinhard Zumkeller, Jan 24 2014
-
Magma
[Valuation(Factorial(n), 2): n in [0..80]]; // Bruno Berselli, Aug 05 2013
-
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) 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} ] -
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
-
Python
[n - bin(n)[2:].count("1") for n in range(101)] # Indranil Ghosh, Apr 09 2017 -
Python
# 3.10+ def A011371(n): return n-n.bit_count() # Chai Wah Wu, Jul 09 2022
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.
From Hieronymus Fischer, Jun 25 and Aug 13 2007: (Start)
a(n) = Sum_{k=2..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, otherwise b(k) = 0.
G.f.: g(x) = (1/(1-x))*Sum_{k>0} c(k)*x^k, 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..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
a(n) = Sum_{k=1..floor(n/2)} floor(log_2(n/k)). - Ammar Khatab, Feb 01 2025
Extensions
Examples added by Hieronymus Fischer, Jun 06 2012
Comments