Generating Functions for the Digital Sum and Other Digit Counting Sequences

Franklin T. Adams-Watters

                     FrankTAW@Netscape.net

Frank Ruskey University of Victoria Victoria, BC V8W 3P6 CANADA

                       ruskey@cs.uvic.ca

Abstract A numeration system associates a unique string, Ξ(n), with each positive integer n, where each string is over the same finite alphabet. Various digit counting statistics of Ξ(n) are of interest with respect to a numeration system. An example is the digital sum, which is the sum of the digits in the number. We present a unifying framework for deriving identities for the generating functions of such statistics in many of the more popular numeration systems.

1 Introduction

Numeration systems provide a rich source of integer sequences. There are many interesting digit counting statistics that arise from the various numeration systems. A typical example, the digital sum, is explained below.

Given a number n represented in binary, n = (b_{d}b_{d−1} ⋯ b_{1}b_{0})_{2}, the (binary) digital sum of n, denoted s_{2}(n) is b_{0} + b_{1} + ⋯ + b_{d}. The digital sum goes under several other names including sideways sum, sideways addition, population count, and Hamming weight. It is denoted νn in Knuth [5], but we use the notation used by Allouche and Shallit [1] (but due to earlier researchers; e.g., Bésineau [2] and Coquet and Toffin [3]). There are two natural ways in which we might extend the idea to k-ary numbers, either by summing digits, or by counting non-zeros. We use the notation s_{k}(n) (again following [1]) for the sum-of-digits function and c_{k}(n) for the counting non-zeros function.

According to OEIS \underline{A053735}, the ordinary generating function of s_{k}(n) has the beautiful expression given in Theorem 1 below. For k = 2 this generating function may be found in Knuth [5]; see exercise 7.1.3.41. The purpose of this short paper is to provide a proof of this and some other related generating functions that are in the OEIS — as part of a more generalized setting. Table 1 contains some of the sequences to which our results apply.

Theorem 1. For all k ≥ 2,

∑_{n≥0} s_{k}(n)z^{n} = \frac{1}{1 − z} ∑_{m≥0} \frac{z^{k^{m}} + 2z^{2k^{m}} + ⋯ + (k − 1)z^{(k−1)k^{m}}}{1 + z^{k^{m}} + z^{2k^{m}} + ⋯ + z^{(k−1)k^{m}}}

= \frac{1}{1 − z} ∑_{m≥0} \frac{z^{k^{m}} − kz^{k^{m+1}} + (k − 1)z^{(k+1)k^{m}}}{(1 − z^{k^{m}})(1 − z^{k^{m+1}})} .

2 Numeration as a sequence of columns

Imagine a table comprised of infinite columns of numbers, C_{0}, C_{1}, C_{2}, . . .. The numbers in each column are indexed starting at 0 and the numbers found in all of the columns all come from the same finite set. In a numeration system each row of the table is distinct. For example, in the binary number system, C_{j} consists of the periodic repetition of 2^{j} 0s followed by 2^{j} 1s.

What is the generating function function for the row sums of those columns? Suppose that the generating function for the m-th column is C_{m}(z). Then

A(z) = ∑_{m≥0} C_{m}(z)  (1)

is the generating function for the row sums. That is, ⟨z^{n}⟩A(z) is the sum of the numbers in the n-th row, where ⟨z^{n}⟩ means “coefficient of z^{n}”. The generating function (1) will exist so long as there are constants c_{n} such that ⟨z^{n}⟩C_{m}(z) = 0 for all m ≥ c_{n}. In many numeration systems the m-th column can be described as a infinite string of the form s_{m}t_{m}^{∞}, where s_{m} and t_{m} are strings with t_{m} ≠ ε and t_{m}^{∞} denotes the infinite string t_{m}^{∞} = t_{m}t_{m}t_{m} · · ·. Let |s| be the length of the string s. If S_{m}(z) and T_{m}(z) are the generating functions (which are actually polynomials) of s and t, respectively. Then

C_{m}(z) = S_{m}(z) + \frac{z^{|s_{m}|}T_{m}(z)}{1 − z^{|t_{m}|}}  (2)

Often s_{m} and t_{m} will have a special form that allows for further simplification of C_{m}(z)

In this paper the most general from that we use is shown below. Here the m-th column depends on integers b_{m}, a_{m} and u_{m}, and the sequence of numbers α_{0}, α_{1}, α_{2}, . . .. The following string is called the column pattern:

s_{m}t_{m}^{∞} = 0^{b_{m}}(α_{0}^{a_{m}}α_{1}^{a_{m}} ⋯ α_{(u_{m}−1)}^{a_{m}})^{∞}  (3)

For example, the column pattern for the binary digital sum is (0^{2^{m}}1^{2^{m}})^{∞}; here b_{m} = 0, a_{m} = 2^{m}, α_{0} = 1, α_{1} = 1, and u_{m} = 2. The generating function of α_{0}^{a_{m}}α_{1}^{a_{m}} ⋯ α_{(u_{m}−1)}^{a_{m}} is

A_{m}(z) = (α_{0} + α_{1}z^{a_{m}} + α_{1}z^{2a_{m}} + ⋯ + α_{u_{m}−1}z^{(u_{m}−1)a_{m}})\frac{1 − z^{a_{m}}}{1 − z}

Thus, by (2), the generating function for (3) is

\frac{z^{b_{m}}A_{m}(z)}{1 − z^{u_{m}a_{m}}} = \frac{z^{b_{m}}}{1 − z} · \frac{α_{0} + α_{1}z^{a_{m}} + α_{2}z^{2a_{m}} + ⋯ + α_{u_{m}−1}z^{(u_{m}−1)a_{m}}}{1 + z^{a_{m}} + z^{2a_{m}} + ⋯ + z^{(u_{m}−1)a_{m}}} .

Summing over m ≥ 0 we obtain

A(z) = \frac{1}{1 − z} ∑_{m≥0} \frac{z^{b_{m}}(1 − z^{a_{m}})}{1 − z^{u_{m}a_{m}}}(α_{0} + α_{1}z^{a_{m}} + α_{2}z^{2a_{m}} + ⋯ + α_{u_{m}−1}z^{(u_{m}−1)a_{m}}) (4)

= \frac{1}{1 − z} ∑_{m≥0} z^{b_{m}} \frac{α_{0} + α_{1}z^{a_{m}} + α_{2}z^{2a_{m}} + ⋯ + α_{u_{m}−1}z^{(u_{m}−1)a_{m}}}{1 + z^{a_{m}} + z^{2a_{m}} + ⋯ + z^{(u_{m}−1)a_{m}}} .  (5)

In the sections to follow we apply this generating function to various numeration systems, starting with a new addition to the OEIS.

3 The Balanced Ternary System

In the balanced ternary system each natural number n is expressed as a sum of distinct signed powers of 3. For example 5 = 9 − 3 − 1 = 3^{3} − 3^{1} − 3^{0}. The digital sum is OEIS A065363. Following Knuth [4] we use ¯1 to denote −1. It is outside the scope of this paper, but it is not difficult to show that the pattern of the m-th column is

0^{3^{m}−3^{m−1}−···−3^{0}}(1^{3^{m}} ¯1^{3^{m}}0^{3^{m}})^{∞}.

Since 3^{m} − 3^{m−1} − ⋯ − 3^{0} = (3^{m} + 1)/2, the generating function for the sum of the digits of the balanced ternary representation of n is

A(z) = \frac{1}{1 − z} ∑_{m≥0} z^{(3^{m}+1)/2} \frac{1 − z^{3^{m}}}{1 + z^{3^{m}} + z^{2·3^{m}}} = \frac{1}{1 − z} ∑_{m≥0} z^{(3^{m}+1)/2} \frac{(1 − z^{3^{m}})^{2}}{1 − z^{3^{m+1}}} .

4 The k-ary Numeration System and Morphisms

The column pattern for k-ary numbers is

(α_{0}^{k^{m}}α_{1}^{k^{m}} … α_{k−1}^{k^{m}})^{∞}.  (6)

Here the row sum of the n-th row, where

n = ∑_{k≥0} b_{k}k^{m}, is ∑_{k≥0} α_{b_{k}}k^{m}.

That is, each digit b is “weighted” by α_{b}. For the digital sum, α_{b} = b.

The special form of (6) implies that there is a “morphism” that underlies the construction; for the digital sum it is j → j, j + 1, j + 2, …, j + k − 1. For example, when k = 3 we get the sequence s_{3}(0), s_{3}(1), s_{3}(2), … as the limit (i.e., fixed-point) of a morphism noted by Robert G. Wilson in \underline{A053735}, which gives us successively

0 → 012 → 012 123 234 → 012123234 123234345 234345456 → ⋯

This limit will exist for any morphism of the form

j → j + α_{0}, j + α_{1}, …, j + α_{k−1},  (7)

so long as α_{0} = 0.

Theorem 2. The row sums of the column pattern (6) are generated by the morphism (7) so long as α_{0} = 0.

Proof. The column pattern (6) is invariant under the following two-step operation: (a) Take column m and replace each entry in the column by k identical entries, calling the new column C′_{m+1}. (b) Form a new column C′_{0} with the pattern (01 ⋯ (k − 1))^{∞}. The invariance is that C′_{m} = C_{m} for m = 0, 1, 2, . . ..

A row sum j under operations (a) and (b) becomes the k row sums j + α_{0}, j + α_{1}, …, j + α_{k−1}. This is the morphism (7).

With the pattern (6) equation (5) gives us the theorem below.

Theorem 3. If k is an integer with k ≥ 2 and α_{0} = 0, then the generating function of the limit of the morphism (7) is

A(z) = \frac{1}{1 − z} ∑_{m≥0} \frac{α_{1}z^{k^{m}} + α_{2}z^{2k^{m}} + ⋯ + α_{k−1}z^{(k−1)z^{m}}}{1 + z^{k^{m}} + z^{2k^{m}} + ⋯ + z^{(k−1)k^{m}}} .  (8)

Note that Theorem 1 is the special case where α_{i} = i for i = 0, 1, …, k − 1. The second equality in Theorem 1 follows from the fact that z + 2z + ⋯ + (k − 1)z^{k−1} = (z − kz^{k} + (k − 1)z^{k+1})/(1 − z)^{2}. We now return to the non-zero count function, c_{k}(n), which can be expressed without the inner sums used in (8).

Corollary 4. The generating function of c_{k}(n) is

C_{k}(z) = \frac{1}{1 − z} ∑_{m≥1} \frac{z^{k^{m−1}} − z^{k^{m}}}{1 − z^{k^{m}}} .  (9)

Proof. Here the morphism is j → j, j + 1, …, j + 1 and so Theorem 3 gives us the first equality below.

C_{k}(z) = \frac{1}{1 − z} ∑_{m≥0} \frac{z^{k^{m}} + z^{2k^{m}} + ⋯ + z^{(k−1)k^{m}}}{1 + z^{k^{m}} + z^{2k^{m}} + ⋯ + z^{(k−1)k^{m}}}  (10)

= \frac{1}{1 − z} ∑_{m≥0} \frac{(1 − z^{k^{m+1}})/(1 − z^{k^{m}}) − (1 − z^{k^{m}})/(1 − z^{k^{m}})}{(1 − z^{k^{m+1}})/(1 − z^{k^{m}})}

Cancelling common denominators and simplifying gives (9).

Other morphisms would give counts of the number of times individual digits occur in the obvious way. For example, j → j, j, j + 1, j is the morphism for the number of 2’s that occur in the 4-ary expansion of n (here the pattern is (0^{4^{m}}0^{4^{m}}1^{4^{m}}0^{4^{m}})^{∞}).

Theorem 5. Let d be an integer with 0 < d < k. The generating function for the number of digits equal to d in the k-ary expansion of n is

\frac{1}{1 − z} ∑_{m≥0} \frac{z^{dk^{m}}}{1 + z^{k^{m}} + z^{2k^{m}} + ⋯ + z^{(k−1)k^{m}}} = \frac{1}{1 − z} ∑_{m≥0} \frac{z^{dk^{m}}(1 − z^{k^{m}})}{1 − z^{k^{m+1}}}.  (11)

The generating function for the number of 0 digits in the k-ary expansion of n is

\frac{1}{1 − z} ∑_{m≥0} \frac{z^{k^{m+1}}}{1 + z^{k^{m}} + z^{2k^{m}} + ⋯ + z^{(k−1)k^{m}}} = \frac{1}{1 − z} ∑_{m≥0} \frac{z^{k^{m+1}}(1 − z^{k^{m}})}{1 − z^{k^{m+1}}}.  (12)

Proof. Equation (11) follows from Theorem 3 with the morphism j → j, …, j, j + 1, j, …, j where the j + 1 occurs in position d, counting from 0. To prove (12) we use the generating function

T (z) = \frac{1}{1 − z} ∑_{m≥0} z^{k^{m}}

for 1 + ⌊log_{k} n⌋, which is the number of k-ary digits in n. Adding (10) and (12) we clearly obtain T (z).

A second way of finishing the proof is to note that the column pattern

0^{k^{m}}(1^{k^{m}}2^{k^{m}} ⋯ (k − 1)^{k^{m}}0^{k^{m}})^{∞}

also describes the k-ary listing of numbers. The useful aspect of expressing it this way is that the leading 0s are correspond to the initial 0^{k^{m}} above. Thus the pattern for counting (non-leading) 0s is

0^{k^{m}}(0^{k^{m}}0^{k^{m}} ⋯ 0^{k^{m}}1^{k^{m}})^{∞}.

According to (5) the numerator inside the sum of the generating function is z^{b_{m}}z^{(u_{m}−1)a_{m}} = z^{k^{m}}z^{(k−1)k^{m}} = z^{k^{m+1}}, as desired.

4.1 Digit counts in specific positions

Let C(n, r, d) be the number of 1 bits in the binary representation of n that are in positions that are congruent to r mod d. As usual, the “positions” are indexed starting at 0 on the right. For example, 888 = (1101111000)_{2}, so C(888, 0, 3) = 3, C(888, 1, 3) = 1 and C(888, 2, 3) = 2.

Theorem 6. For all integers d ≥ 0 and integers r with 0 ≤ r < d,

∑_{n≥0} C(n, r, d)z^{n} = ∑_{m≥0} \frac{z^{2^{r+dm}}}{1 + z^{2^{r+dm}}} .  (13)

OEIS  description  comment  pattern
\underline{A023416}  0s in binary  same as \underline{A080791}  0^{2^{m}}(0^{2^{m}}1^{2^{m}})^{∞}
\underline{A000120}  1s in binary  digital sum, base 2  (0^{2^{m}}1^{2^{m}})^{∞}
\underline{A077267}  0s in base 3  same as \underline{A081602}  0^{3^{m}}(0^{3^{m}}0^{3^{m}}1^{3^{m}})^{∞}
\underline{A062756}  1s in base 3  (0^{3^{m}}1^{3^{m}}0^{3^{m}})^{∞}
\underline{A081603}  2s in base 3  (0^{3^{m}}0^{3^{m}}1^{3^{m}})^{∞}
\underline{A160380}  0s in base 4  0^{4^{m}}(0^{4^{m}}0^{4^{m}}0^{4^{m}}1^{4^{m}})^{∞}
\underline{A160381}  1s in base 4  (0^{4^{m}}1^{4^{m}}0^{4^{m}}0^{4^{m}})^{∞}
\underline{A160382}  2s in base 4  (0^{4^{m}}0^{4^{m}}1^{4^{m}}0^{4^{m}})^{∞}
\underline{A160383}  3s in base 4  (0^{4^{m}}0^{4^{m}}0^{4^{m}}1^{4^{m}})^{∞}
\underline{A160384}  non-0 base 3  (0^{3^{m}}1^{3^{m}}1^{3^{m}})^{∞}
\underline{A160385}  non-0 base 4  (0^{4^{m}}1^{4^{m}}1^{4^{m}}1^{4^{m}})^{∞}
\underline{A053735}  digital, base 3  (0^{3^{m}}1^{3^{m}}2^{3^{m}})^{∞}
\underline{A053737}  digital, base 4  (0^{4^{m}}1^{4^{m}}2^{4^{m}}3^{4^{m}})^{∞}
\underline{A034968} digital, factorial base  see also \underline{A139365}
\underline{A065363} digital, balanced base 3  0^{(3^{m}+1)/2}(1^{3^{m}} ¯1^{3^{m}}0^{3^{m}})^{∞}
\underline{A139351}  1s or 3s in base 4  1s in even positions in binary  (0^{4^{m}}1^{4^{m}}0^{4^{m}}1^{4^{m}})^{∞}
\underline{A139352}  2s or 3s in base 4  1s in odd positions in binary  (0^{4^{m}}0^{4^{m}}1^{4^{m}}1^{4^{m}})^{∞}

Table 1: Relevant sequences in OEIS.

Proof. Let B(r, d) = {s ∈ ℤ:1 ≤ s < 2^{d} and ⌊s/2^{r}⌋ is odd}; in other words, the d bit binary numbers with the r-th bit equal to 1. Let B̄(r, d) = {0, 1, …, 2^{d} − 1} \ B(r, d). For example, B(1, 3) = {2, 3, 6, 7} and B(1, 3) = {0, 1, 4, 5}.

Now consider the number n written both in binary and in base 2^{d}. Note that, in the binary representation of n, the number of 1 bits in positions that are congruent to r mod d is the same as the number of digits from the set B(r, d) in the 2^{d}-ary representation of n. Thus we may apply Theorem 3 to get the generating function

∑_{n≥0} C(n, r, d)z^{n} = ∑_{m≥0} \frac{∑_{s∈B(r,d)} z^{s2^{dm}}}{∑_{0≤s<2^{d}} z^{s2^{dm}}}

Note that the numerator above can be written

∑_{s∈B(r,d)} z^{s2^{dm}} = z^{2^{r}2^{dm}} ∑_{s∈B̄(r,d)} z^{s2^{dm}}

and the denominator as

∑_{0≤s<d} z^{s2^{dm}} = ∑_{s∈B(r,d)} z^{s2^{dm}} + ∑_{s∈B̄(r,d)} z^{s2^{dm}} = (1 + z^{2^{r}2^{dm}}) ∑_{s∈B̄(r,d)} z^{s2^{dm}}.

Canceling the common sum gives the right hand side of (13).

The following corollary allows us to give a generating function for A139351 and A139352.

Corollary 7. The generating function for the number of 1’s in even positions in the binary expansion of n, and the corresponding generating function for the number of 1’s in odd positions, are given below.

\frac{1}{1 − z} ∑_{m≥0} \frac{z^{4^{m}}}{1 + z^{4^{m}}} , \frac{1}{1 − z} ∑_{m≥0} \frac{z^{2·4^{m}}}{1 + z^{2·4^{m}}} .

5 Multi-Radix Numeration Systems

In this section we consider numbers written in the multi-radix base k_{0} × k_{1} × k_{2} × · · ·. If each k_{i} = k then we get the k-ary numeration system considered in the previous section. It will prove useful to adopt the following notation: (a) k′_{j} = k_{j} − 1, (b) k̄_{j} = k_{0}k_{1} ⋯ k_{j−1}, with the usual convention for the empty product, k̄_{0} = 1. Then the column pattern is

(αk̄_{m} ; 0αk̄_{m} ; 1 ⋯ αk̄_{m} ; k′_{m})^{∞}.

Theorem 8. The generating function for the digital sum of the number n written in the multi-radix base k_{0} × k_{1} × k_{2} × ⋯ is

\frac{1}{1 − z} ∑_{m≥0} \frac{zk̄_{m} + 2z^{2k̄_{m}} + ⋯ + k′_{m}z^{k′_{m}·k̄_{m}}}{1 + zk̄_{m} + z^{2k̄_{m}} + ⋯ + z^{k′_{m}·k̄_{m}}} .

Proof. The generating function is (5) with b_{m} = 0, α_{i} = i, u_{m} = k′_{m}, and a_{m} = k̄_{m}.

In the factorial base, k_{j} = j+1, so that k̄_{j} = j!. For example, 99 = 3·4!+0·3!+2·2!+1·1!. We now obtain a generating function for \underline{A034968} in the following corollary.

Corollary 9. The generating function for the digital sum of the number n written in the factorial base is

\frac{1}{1 − z} ∑_{m≥1} \frac{z^{m!} + 2z^{2m!} + ⋯ + mz^{m·m!}}{1 + z^{m!} + z^{2m!} + ⋯ + z^{m·m!}} .

Proof. This follows directly from the previous theorem. Note that the numerator is zero when m = 0, so that the summation starts at 1.

6 Final Remarks

It is also possible to approach the derivation of the generating functions used here using “divide-and-conquer” recurrence relations. See Stephan [8] for examples of this approach in the k = 2 case. For example the recurrence relation corresponding to the morphism (7) is a(0) = 0 and a(km + i) = α_{i} + a(m) for integer indices i with 0 ≤ i < k. These recurrence relations are very useful for actually computing the sequences.

As we have shown here, finding a generating function for the sum of the digits is straightforward when dealing with a simple radix, or a mixed radix system where each positional multiplier is a multiple of the previous one. When this does not hold, the problem is much more difficult.

The simplest example of such a system is the Zeckendorf [9] or “base Fibonacci” representation (\underline{A014417}, digital sum in \underline{A007895}). Attempting the same sort of one digit at a time approach, the low order digit is the infinite Fibonacci word, \underline{A003849}. Since this sequence includes arbitrarily long repeated segments, but is not periodic, it does not have a rational generating function.

References

[1] J.-P. Allouche and J. O. Shallit, Automatic Sequences, Cambridge University Press, 2003.

[2] J. Bésineau, Indépendance statistique d’ensembles liés à la fonctions “somme des chiffres”, Acta Arith. 20 (1972), 401–416.

[3] J. Coquet and P. Toffin, Représentations des entiers naturels et indépendance statistique, Bull. Sci. Math., 105 (1981), 289–298.

[4] D. E. Knuth, The Art of Computer Programming, Volume 2, Seminumerical Algorithms, 3rd edition, Addison-Wesley, 1998.

[5] D. E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise Tricks & Techniques and Binary Decision Diagrams, Addison-Wesley, 2009.

[6] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, second edition, 1994.

[7] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences,

    www.research.att.com/^{∼}njas/sequences/, accessed April 2009.

[8] R. Stephan, Divide-and-conquer generating functions, part I: elementary sequences,

    http://arxiv.org/abs/math/0307027, 2003.

[9] E. Zeckendorf, Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Roy. Sci. Liège, 41 (1972), 179–182.

2000 Mathematics Subject Classification: Primary 05A15; Secondary 05A10. Keywords: Generating function, numeration system, digital sum, sideways addition, digit counting, morphism, factorial base, balanced ternary numbers.

(Concerned with sequences \underline{A000120}, \underline{A003849}, \underline{A007895}, \underline{A014417}, \underline{A023416}, \underline{A034968}, \underline{A053735}, \underline{A053737}, \underline{A062756}, \underline{A065363}, \underline{A077267}, \underline{A080791}, \underline{A081602}, \underline{A081603}, \underline{A139351}, \underline{A139352}, \underline{A139365}, \underline{A160380}, \underline{A160381}, \underline{A160382}, \underline{A160383}, \underline{A160384}, and \underline{A160385}.)

Received June 19 2009; revised version received July 11 2009. Published in Journal of Integer Sequences, July 12 2009.

Return to Journal of Integer Sequences home page.