Digit Count
The number N_d^((b))(n) of digits d in the base-b representation of a number n is called the b-ary digit count for d. The digit count is implemented in the Wolfram Language as DigitCount [n, b, d].
The number of 1s N_1(n)=N_1^((2))(n) in the binary representation of a number n, illustrated above, is given by
where gde(n!,2) is the greatest dividing exponent of 2 with respect to n!. This is a special application of the general result that the power of a prime p dividing a factorial (Vardi 1991, Graham et al. 1994). Writing a(n) for N_1(n), the number of 1s is also given by the recurrence relation
with a(0)=0, and by
| N_1(n)=2n-log_2(d), |
(5)
|
where d is the denominator of
![画像: 1/(n!)[(d^n)/(dx^n)(1-x)^(-1/2)]_(x=0).](/index.cgi/contrast/https://mathworld.wolfram.com/images/equations/DigitCount/NumberedEquation2.svg){kind=link}
For n=1, 2, ..., the first few values are 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, ... (OEIS A000120; Smith 1966, Graham 1970, McIlroy 1974).
For a binary number, the count of 1s N_1(n) is equal to the digit sum s_2(n). The quantity N_1(n) (mod 2) is called the parity of a nonnegative integer n.
N_0(n) and N_1(n) satisfy the beautiful identities
where gamma is the Euler-Mascheroni constant and ln(4/pi)=0.241564... (OEIS A094640) is its "alternating analog" (Sondow 2005).
Let e(n) and o(n) be the numbers of even and odd digits respectively of n. Then
where the latter (OEIS A096614) is transcendental (Borwein et al. 2004, pp. 14-15).
See also
Binary, Digit, Digit Product, Digit Sum, Parity, Stolarsky-Harborth ConstantRelated Wolfram sites
https://functions.wolfram.com/NumberTheoryFunctions/DigitCount/Explore with Wolfram|Alpha
References
Borwein, J.; Bailey, D.; and Girgensohn, R. Experimentation in Mathematics: Computational Paths to Discovery. Wellesley, MA: A K Peters, 2004.Graham, R. L. "On Primitive Graphs and Optimal Vertex Assignments." Ann. New York Acad. Sci. 175, 170-186, 1970.Graham, R. L.; Knuth, D. E.; and Patashnik, O. "Factorial Factors." §4.4 in Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, pp. 111-115, 1994.McIlroy, M. D. "The Number of 1's in Binary Integers: Bounds and Extremal Properties." SIAM J. Comput. 3, 255-261, 1974.Sloane, N. J. A. Sequences A000120/M0105, A094640, A096614 in "The On-Line Encyclopedia of Integer Sequences."Smith, N. "Problem B-82." Fib. Quart. 4, 374-365, 1966.Sondow, J. "New Vacca-type Rational Series for Euler's Constant and its 'alternating' Analog ln(4/pi)." 1 Aug 2005. https://arxiv.org/abs/math/0508042.Trott, M. The Mathematica GuideBook for Programming. New York: Springer-Verlag, p. 33, 2004. https://www.mathematicaguidebooks.org/.Vardi, I. Computational Recreations in Mathematica. Reading, MA: Addison-Wesley, p. 67, 1991.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, p. 902, 2002.Referenced on Wolfram|Alpha
Digit CountCite this as:
Weisstein, Eric W. "Digit Count." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/DigitCount.html