|
| |
|
|
A011371
|
|
a(n) = n minus (number of 1's in binary expansion of n). Also highest power of 2 dividing n!.
|
|
138
|
|
|
|
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
|
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
Also the number of trailing zeros in the base-2 representation of n!. - Hieronymus Fischer, Jun 18 2007
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
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
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
|
|
|
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
|
Laurent Alonso, Edward M. Reingold, and René Schott, Determining the majority, Inform. Process. Lett. 47 (1993), no. 5, 253-255.
|
|
|
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) = 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
|
|
|
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) ].
|
|
|
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) = n - hammingweight(n); \\ Michel Marcus, Jun 05 2014
(Magma) [Valuation(Factorial(n), 2): n in [0..80]]; // Bruno Berselli, Aug 05 2013
(Haskell)
(Python) [n - bin(n)[2:].count("1") for n in range(101)] # Indranil Ghosh, Apr 09 2017
(Python) # 3.10+
|
|
|
CROSSREFS
|
a(n) = Sum_{k=1..n} A007814(k), n >= 1, a(0) = 0.
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
