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


where d is the denominator of


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 Constant

Related Wolfram sites

Explore with Wolfram|Alpha


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., M. The Mathematica GuideBook for Programming. New York: Springer-Verlag, p. 33, 2004., 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 Count

Cite this as:

Weisstein, Eric W. "Digit Count." From MathWorld--A Wolfram Web Resource.

Subject classifications