A011371 - OEIS

%I #224 Feb 01 2024 02:47:47

%S 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,

%T 23,25,25,26,26,31,31,32,32,34,34,35,35,38,38,39,39,41,41,42,42,46,46,

%U 47,47,49,49,50,50,53,53,54,54,56,56,57,57,63,63,64,64,66,66,67,67,70

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

%C Terms of A005187 repeated. - _Lekraj Beedassy_, Jul 06 2004

%C 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 sum of digits raised to consecutive powers for any n > 1 falls short of equaling the value of n by the n-th term of this sequence. - _Alonso del Arte_, Jul 27 2004

%C Also the number of trailing zeros in the base-2 representation of n!. - _Hieronymus Fischer_, Jun 18 2007

%C Partial sums of A007814. - _Philippe Deléham_, Jun 21 2012

%C If n is in A089633 and n > 0, then a(n) = n - floor(log_2(n+1)). - _Douglas Latimer_, Jul 25 2012

%C For n > 1, denominators of integral numerator polynomials L(n,x) for the Legendre polynomials with o.g.f. 1/sqrt(1 - t*x + x^2). - _Tom Copeland_, Feb 04 2016

%C 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 (1752-1833) [see the Honsberger reference]. - _Bernard Schott_, Apr 07 2017

%C 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/(p-1). - _Geoffrey Critzer_, Jun 05 2017

%D K. Atanassov, On Some of Smarandache's Problems, section 7, on the 61st problem, page 42, American Research Press, 1999, 16-21.

%D G. Bachman, Introduction to p-Adic Numbers and Valuation Theory, Academic Press, 1964; see Lemma 3.1.

%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 305.

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

%D R. Honsberger, Mathematical Gems II, Dolciani Mathematical Expositions, 1976, pp. 1-6.

%H Hieronymus Fischer, <a href="/A011371/b011371.txt">Table of n, a(n) for n = 0..10000</a> (first 1000 terms from T. D. Noe)

%H Laurent Alonso, Edward M. Reingold, and René Schott, <a href="http://dx.doi.org/10.1016/0020-0190(93)90135-V">Determining the majority</a>, Inform. Process. Lett. 47 (1993), no. 5, 253-255.

%H Laurent Alonso, Edward M. Reingold, and René Schott, <a href="http://dx.doi.org/10.1137/S0097539794275914">The average-case complexity of determining the majority</a>, SIAM J. Comput. 26 (1997), no. 1, 1-14.

%H Sung-Hyuk Cha, <a href="http://www.wseas.us/e-library/conferences/2012/CambridgeUSA/MATHCC/MATHCC-60.pdf">On Integer Sequences Derived from Balanced k-ary Trees</a>, Applied Mathematics in Electrical and Computer Engineering, 2012.

%H Sung-Hyuk Cha, <a href="http://naun.org/multimedia/UPress/ami/16-125.pdf">On Complete and Size Balanced k-ary Tree Integer Sequences</a>, International Journal of Applied Mathematics and Informatics, Issue 2, Volume 6, 2012, pp. 67-75. - From _N. J. A. Sloane_, Dec 24 2012

%H R. Hinze, <a href="https://www.cs.ox.ac.uk/people/ralf.hinze/publications/CSC.pdf">Concrete stream calculus: An extended study</a>, J. Funct. Progr. 20 (5-6) (2010) 463-535, <a href="https://doi.org/10.1017/S0956796810000213">doi</a>, Section 4.4.

%H Keith Johnson and Kira Scheibelhut, <a href="http://www.jstor.org/stable/10.4169/amer.math.monthly.123.4.338">Rational polynomials that take integer values at the Fibonacci numbers</a>, American Mathematical Monthly 123.4 (2016): 338-346. See omega_2.

%H S-C Liu and J. C.-C. Yeh, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Liu2/liu6.html">Catalan numbers modulo 2^k</a>, J. Int. Seq. 13 (2010), 10.5.4, eq. (5).

%H K. Matthews, <a href="http://www.numbertheory.org/php/factorial.html">Computing the prime-power factorization of n!</a>.

%H A. Mir, F. Rossello and L. Rotger, <a href="http://arxiv.org/abs/1202.1223">A new balance index for phylogenetic trees</a>, arXiv preprint arXiv:1202.1223 [q-bio.PE], 2012.

%H A. M. Oller-Marcen and J. Maria Grau, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Oller/oller3.html">On the Base-b Expansion of the Number of Trailing Zeros of b^k!</a>, J. Int. Seq. 14 (2011) 11.6.8.

%H Michael E. Saks and Michael Werman, <a href="http://dx.doi.org/10.1007/BF01275672">On computing majority by comparisons</a>, Combinatorica 11 (1991), no. 4, 383-387.

%H Ralf Stephan, <a href="/somedcgf.html">Some divide-and-conquer sequences ...</a>

%H Ralf Stephan, <a href="/A079944/a079944.ps">Table of generating functions</a>.

%H Zhujun Zhang, <a href="https://www.researchgate.net/publication/333261503_A_Note_on_Counting_Binomial_Heaps">A Note on Counting Binomial Heaps</a>, ResearchGate (2019).

%F 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

%F G.f.: A(x) = (1/(1 - x))*Sum_{k>=1} x^(2^k)/(1 - x^(2^k)). - _Ralf Stephan_, Apr 11 2002

%F a(n) = n - A000120(n). - _Lekraj Beedassy_, Sep 01 2003

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

%F a(n) = A007814(A000142(n)). - _Reinhard Zumkeller_, Apr 09 2004

%F From _Hieronymus Fischer_, Jun 25 and Aug 13 2007: (Start)

%F a(n) = Sum_{k=2..n} Sum_{j|k, j >= 2} (floor(log_2(j)) - floor(log_2(j - 1))).

%F The g.f. can be expressed in terms of a Lambert series, in that g(x) = L[b(k)](x)/(1 - x), where

%F 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.

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

%F Recurrence:

%F a(n) = floor(n/2) + a(floor(n/2));

%F a(2*n) = n + a(n);

%F a(n*2^m) = n*(2^m - 1) + a(n).

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

%F Asymptotic behavior:

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

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

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

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

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

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

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

%F a(n) = Sum_{k >= 0} A030308(n, k)*A000225(k). - _Philippe Deléham_, Oct 16 2011

%F 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

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

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

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

%e a(100) = 97.

%e a(10^3) = 994.

%e a(10^4) = 9995.

%e a(10^5) = 99994.

%e a(10^6) = 999993.

%e a(10^7) = 9999992.

%e a(10^8) = 99999988.

%e a(10^9) = 999999987.

%e 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 + ...

%p 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) ].

%p A011371 := n -> n - add(i,i=convert(n,base,2)): # _Peter Luschny_, May 02 2009

%p read("transforms") : A011371 := proc(n) n-wt(n) ; end proc: # _R. J. Mathar_, May 15 2013

%t -1 + Length[ Last[ Split[ IntegerDigits[ 2(n!), 2 ] ] ] ], FoldList[ Plus, 0, Fold[ Flatten[ {#1, #2, #1} ]&, 0, Range[ 6 ] ] ]

%t Table[IntegerExponent[n!, 2], {n, 0, 127}]

%t Table[n - DigitCount[n, 2, 1], {n, 0, 127}]

%t Table[t = 0; p = 2; While[s = Floor[n/p]; t = t + s; s > 0, p *= 2]; t, {n, 0, 100} ]

%o (PARI) {a(n) = if( n<0, 0, valuation(n!, 2))}; /* _Michael Somos_, Oct 24 2002 */

%o (PARI) {a(n) = if( n<0, 0, sum(k=1, n, n\2^k))}; /* _Michael Somos_, Oct 24 2002 */

%o (PARI) {a(n) = if( n<0, 0, n - subst( Pol( binary( n ) ), x, 1))}; /* _Michael Somos_, Aug 28 2007 */

%o (PARI) a(n)=sum(k=1,log(n+1)\log(2),n>>k) \\ _Charles R Greathouse IV_, Oct 03 2012

%o (PARI) a(n)=my(s);while(n>>=1,s+=n);s \\ _Charles R Greathouse IV_, Aug 09 2013

%o (PARI) a(n) = n - hammingweight(n); \\ _Michel Marcus_, Jun 05 2014

%o (Magma) [Valuation(Factorial(n), 2): n in [0..80]]; // _Bruno Berselli_, Aug 05 2013

%o (Haskell)

%o a011371 n = n - a000120 n  -- _Reinhard Zumkeller_, Jan 24 2014

%o (Python) [n - bin(n)[2:].count("1") for n in range(101)] # _Indranil Ghosh_, Apr 09 2017

%o (Python) # 3.10+

%o def A011371(n): return n-n.bit_count() # _Chai Wah Wu_, Jul 09 2022

%Y Cf. A000120, A005187, A054861, A032799, A067080, A098844, A132027.

%Y a(n) = Sum_{k=1..n} A007814(k), n >= 1, a(0) = 0.

%K nonn,nice,easy

%O 0,5

%A _N. J. A. Sloane_

%E Examples added by _Hieronymus Fischer_, Jun 06 2012