Digits and beyond

Helmut Prodinger

ABSTRACT: This is a survey about digits from a personal point of view. Counting the occurrences of digits (and, more generally, subblocks) is discussed in the context of various positional number systems. The methods to achieve this are Delange’s elementary method and Flajolet’s idea to use the Mellin–Perron summation (or integral) formula.

Then we move to problems from Theoretical Computer Science (register function of binary trees, number of exchanges in Baxter’s odd–questions are also discussed. An open problem from physicists Yekutieli and Mandelbrot can also be treated in that fashion.

Furthermore, we consider representations of numbers where some digits are forbidden. As a representative example, we discuss the Cantor distribution and its moments, asymptotically analyzed by Mellin transforms. Other problems in this context lead to sums involving Bernoulli numbers which can be attacked by analytic Depoissonization.

Very briefly we mention carry propagation, mergesort parameters and jump interpolation search trees.

1 Introduction

This is a survey about digits from a personal point of view, i. e., I will talk about digit expansions but stress those things that are in one way or another related to my own research.

We are interested in the binary expansion, and, more generally in base q– expansion, with an integer q ≥ 2, and digits {0, …, q−1}. Delange [3] has analyzed the sum–of–digits function S(n) (sometimes, especially for q = 2, written as ν(n)), and found in particular the following result for the mean value

\frac{1}{m} ∑_{0≤n<m} S(n) = \frac{q − 1}{2} log_{q} m + F (log_{q} m),

with a periodic function F (x) of period 1, which is continuous but nowhere differentiable, and with explicitly known Fourier coefficients. Perhaps even more important than his result, is his method which is based on finding an explicit formula for the individual digits, in terms of floor functions, rewriting them as integrals over piecewise constant functions. Forming the mean value just means the union of the intervals of integration, which makes things easier. Then one pulls out the main (logarithmic) term and finds that what remains is a periodic function of {log_{q} m} (the fractional part of log_{q} m) which can be brought into some standard form from which one also gets the Fourier coefficients.

In Section 2 we consider such a Delange type analysis for the system with base q but digits {d, d + 1, …, d + q − 1}, where d = 0 means the standard case. The restriction for the parameter d is that 0 must be in the set of digits. We are counting how often a given digit i occurs in the representation of a natural number, more precisely, we consider the mean value of this counting function. This is based on the paper [26] which contains slightly more general results, namely not only counting individual digits i but rather a given (contiguous) subblock w. So, as an example, one knows how often “on average” the subblock 123014 occurs in the base 5 representation of n.

Delange’s technique is elementary and nice, however, in more complicated situations, it can become quite messy. Flajolet came up with an alternative method [10]: It is based on the Mellin–Perron summation formula, which allows to write the counting function of interest as a contour integral in the complex plane. Shifting the line of integration produces then the terms in the explicit formula. As it often happens in this type of problems, one gets exact formulæ. The fact that the error term disappears completely is based on

0 = ∫_{− \frac{1}{4} −i∞}^{− \frac{1}{4} +i∞} ζ(s)n^{s} \frac{ds}{s(s + 1)}

or similar results. In most instances, this technique is somewhat superior to Delange’s elementary approach. As an additional reading we recommend Marko Riedel’s master’s thesis [43].

In Section 3, we describe the technique for Delange’s result (q = 2), and also for a related number system called the Gray code, which is obtained from the binary representation by a series of reflections. Interestingly enough, the sections of Knuth’s The Art of Computer Programming, Vol. 4, dealing with Gray codes, are already available at the web, see Knuth’s homepage http://Sunburn.Stanford.EDU/ knuth/.

In Section 4, we discuss a symmetric number system with base q (an even integer) and digits {−q/2, …, q/2}. This redundant system is made unique by some conditions which in the instance q = 2 simply say that no two adjacent nonzero digits can occur. This instance q = 2 was rediscovered many times; perhaps the earliest reference is [42]. Some historical remarks can be found in [40]. We discuss again the problem of counting digits and subblocks in such a symmetric signed system.

Digits occur however in counting problems related to the Analysis of Algorithms. In Section 6 we deal with the Register function of binary trees (in the literature often appearing as Horton–Strahler numbers; here are some (random) references: [35, 30, 5, 4, 49, 33, 34]).

The question about the average value of the register function was solved independently by Flajolet–Raoult–Vuillemin [14] and Kemp [25], compare also [32]. The quantity v_{2}(n), defined to be k if n = 2^{k}(2i+1), plays a crucial role here. It is related to the sum–of–digits function S(n), since ∑_{k≤n} v_{2}(k) = n − S(n). Consequently one can, after some manipulations, invoke Delange’s result. This was the route taken by Flajolet–Raoult–Vuillemin. Another approach (Kemp) is, after approximating the explicit quantities using real analysis, to consider Mellin transforms, which leads to Dirichlet series of the type ∑_{n≥1} v_{2}(n)/n^{s}. Perhaps the method that is most advanced [12], also uses Mellin transforms, but on the level of generating functions, in order to find the local behaviour of a generating function closely related to the desired average values. Once this is established, singularity analysis of generating functions (transfer theorems), developed in [11], provides the asymptotics of the, say, average value of the register function of binary trees of size n.

Section 7 is in a sense the companion of Section 6. The analysis of Batcher’s odd–even method (see Knuth [29]) was originally left open and eventually solved by Sedgewick [44]. What was the binary expansion and the quantity v_{2}(n) for the register problems is now the Gray code representation and the function ϑ(k) which is 1 for k = 2^{m}(4i + 1), and −1 for k = 2^{m}(4i + 3). Flajolet and Ramshaw [13] use a result analogous to Delange’s but for the Gray code representation (also included in Section 3), and proceed along the lines of [14]. The more advanced technique (singularity analysis of generating functions) is also described here and was worked out a long time ago for the proceedings of a French summer school in Ile de Ré [38].

The next Section 8 deals with an open problem which is related to the register function of binary trees. It was posed by Yekutieli and Mandelbrot [49] and solved in [39]. The register function can be extended by attaching a value to each internal node in the binary tree (which is the register function of the subtree having that node as the root), the value at the root being the register function of the tree. The question was to count the number of internal nodes having register function exactly 1 less than the register function of the entire tree. It was observed empirically that the expected value of this parameter is asymptotically a periodic function of log_{4} n if all trees of size n (n internal nodes) are considered to be equally likely. Here, the following arithmetic function ψ(m) plays a role: ψ(m) = −k if m = 2^{i}(4k + 1) and ψ(m) = k + 1 if m = 2^{i}(4k + 3). Otherwise, the same comments about the methodology as for the previous sections apply here.

The Section 9 deals with sets of numbers which have representations avoiding digits from a subset of forbidden digits. The most common case is q = 3 with forbidden digit 1. If one considers numbers of the form ∑_{k≥1} a_{k}3^{−k} where a_{k} ∈ {0, 2}, one obtains the classical Cantor set. One question is about the moments of the Cantor distribution (strings of the form ∑_{k≥1} a_{k}3^{−k} are produced at random, where “random” means that each digit might be 0 or 2, with probability 1/2). Grabner and I could satisfactorily solve this problem, which originated in [31], using the method of Mellin transforms. Another problem, suggested in [23], was eventually solved by A. Knopfmacher and myself [27]: If one draws n random numbers, according to the Cantor distribution, what is the expected value of their minimum? Using exponential generating functions to solve the relevant difference equations, one can relate it to “the hardest asymptotic nut” from [28]. These days, one has alternative methods to attack the sums coming out in the analysis à la “asymptotic nut;” these are techniques known as Rice’s method [15] which are again intimately related to Mellin transforms, and (analytic) Depoissonization, which was floating around for years in the literature, an early example being perhaps [45]. Recently it has been polished and systematized by Jacquet and Szpankowski [24].

The last sections are very brief and mention carry propagation in positional number systems, mergesort, and jump interpolation search trees.

2 A Delange type analysis

We describe Delange’s technique by considering the number system with base q and digits {d, d + 1, …, d + q − 1} where 1 − q ≤ d ≤ 0. We are going to study B_{i}(n), the number of occurrences of digit i ≠ 0 in the representation of n. This is not a real restriction since the number of occurrences of digit 0 can be obtained as the difference of the length of the representation and the number of the other digits. A full treatment, even for subblocks instead of just digits, is in [26].

First, one needs an explicit formula: If n is written as … a_{2}a_{1}a_{0} in the (q, d)– system, then a_{k} = i iff

⌊\frac{n}{q^{k+1}} + 1 − \frac{i}{q} − \frac{d}{q(q − 1)} + \frac{1}{q}⌋ − ⌊\frac{n}{q^{k+1}} + 1 − \frac{i}{q} − \frac{d}{q(q − 1)}⌋ = 1.

Consequently,

B_{i}(n) = ∑_{k≥1} ( ⌊\frac{n}{q^{k}} + 1 − \frac{i}{q} − \frac{d}{q(q − 1)} + \frac{1}{q}⌋ − ⌊\frac{n}{q^{k}} + 1 − \frac{i}{q} − \frac{d}{q(q − 1)}⌋ ).

Delange’s simple but extremely useful observation is that one can write the floor functions as integrals. We are considering an average of the function B_{i}(n):

\frac{1}{m} ∑_{n=0}^{m−1} B_{i}(n) = \frac{1}{m} ∑_{n=0}^{m−1} ∑_{k≥1} ( ⌊\frac{n}{q^{k}} + 1 − \frac{i}{q} − \frac{d}{q(q−1)} + \frac{1}{q}⌋ − ⌊\frac{n}{q^{k}} + 1 − \frac{i}{q} − \frac{d}{q(q−1)}⌋ )

= \frac{1}{m} ∫_{0}^{m} ∑_{k≥1} ( ⌊\frac{t}{q^{k}} + 1 − \frac{i}{q} − \frac{d}{q(q−1)} + \frac{1}{q}⌋ − ⌊\frac{t}{q^{k}} + 1 − \frac{i}{q} − \frac{d}{q(q−1)}⌋ )dt.

It can be readily checked that nonzero contributions are only possible for k ≤ l+1, with l = ⌊log_{q} m−log_{q}(1+ \frac{d}{q−1})⌋. After a simple change of variable in the integrals, it turns out that one should study functions like

g_{β}(x) = ∫_{0}^{x} ( ⌊u + β + \frac{1}{q}⌋ − ⌊u + β⌋ − \frac{1}{q})du, h_{β}(x) = ∑_{k≥0} q^{−k}g_{β}(xq^{k})

and

H_{β}(x) = \frac{1 − γ − \{−γ + x\}}{q} + q^{1−γ−\{−γ+x\}}h_{β}(q^{\{−γ+x\}−1+γ}),

with \{x\} = x − ⌊x⌋ (the fractional part of x) and γ = log_{q}(1 + \frac{d}{q−1}).

Eventually one finds that

\frac{1}{m} ∑_{n=0}^{m−1} B_{i}(n) = \frac{log_{q} m}{q} + H_{β}(log_{q} m),

where β depends on the digit i in a simple way: β = 1 − \frac{i}{q} − \frac{d}{q(q−1)} − \frac{1}{q}.

Since the function H_{β}(x) is periodic with period 1, it is natural to study its Fourier series expansion. The result is: H_{β}(x) = ∑_{k∈ℤ} h_{k}e^{2πikx}, with

h_{0} = log_{q} \frac{Γ(1 − \{β + \frac{1}{q}\})}{Γ(1 − \{β\})} − \frac{1}{q}(\frac{1}{2} + \frac{1}{log q} ),

h_{k} = \frac{ζ(χ_{k}, 1 − \{β + \frac{1}{q}\}) − ζ(χ_{k}, 1 − \{β\})}{log q · χ_{k}(1 + χ_{k})}, k ≠ 0,

with χ_{k} = 2πik/ log q and the Hurwitz’ zeta function ζ(z, a).

The computation of the Fourier coefficients is relatively straight forward; one has to use results like

∫_{1}^{∞} \frac{⌊u⌋ du}{u^{s+1}} = ∑_{k≥1} k ∫_{k}^{k+1} \frac{du}{u^{s+1}} = \frac{1}{s} ∑_{k≥1} k(\frac{1}{k^{s}} − \frac{1}{(k + 1)^{s}} ) = \frac{1}{s} ∑_{k≥1} \frac{1}{k^{s}} = \frac{1}{s}ζ(s).

The computations in the case of counting subblocks are more complicated, and in the end an additional error term of order 1/m occurs.

3 The Mellin–Perron summation formula

This section is based on [10]. Let f(x) be a function defined over [0, +∞). Its Mellin transform f^{∗}(s) = M[f(x); s] is defined by f^{∗}(s) = ∫_{0}^{∞} f(x)x^{s−1}dx. By linearity and the rescaling property we have

F (x) = ∑_{k} λ_{k}f(μ_{k}x) ⟹ F^{∗}(s) = ( ∑_{k} λ_{k}μ_{k}^{−s})f^{∗}(s).  (1)

The condition is for s to belong to a ‘fundamental strip’ defined by the property that the integral giving f^{∗}(s) and the sum ∑_{k} λ_{k}μ_{k}^{−s} are both absolutely convergent. Similar to the Laplace transform there is an inversion theorem (cf. [7]). When applied to (1), it provides

∑_{k} λ_{k}f(μ_{k}x) = \frac{1}{2πi} ∫_{c−i∞}^{c+i∞} ( ∑_{k} λ_{k}μ_{k}^{−s})f^{∗}(s)x^{−s}ds,  (2)

with c in the fundamental strip.

Formula (2) could be called Mellin’s summation formula. It is especially useful when the integral can be computed by residues, and in that case each residue contributes a term in an asymptotic expansion of F (x).

This formula lends itself to various number theoretic applications, most notably proofs of the prime number theorem. Introduce the step function H_{0}(x) defined by

H_{0}(x) = \begin{cases}1 & if x ∈ [0, 1], \\ 0 & if x > 1, \end{cases}

together with the functions H_{m}(x) = (1−x)^{m}H_{0}(x). In the interesting case where μ_{k} ≡ k, we obtain from (2), formulæ of the Perron type that provide integral representations for the iterated summations of arithmetic functions in terms of their Dirichlet generating function.

Let c > 0 lie in the half–plane of absolute convergence of ∑_{k} λ_{k}k^{−s}. Then for any m ≥ 1, we have

\frac{1}{m!} ∑_{1≤k<n} λ_{k}(1 − \frac{k}{n})^{m} = \frac{1}{2πi} ∫_{c−i∞}^{c+i∞} ( ∑_{k≥1} \frac{λ_{k}}{k^{s}} )n^{s} \frac{ds}{s(s + 1) ⋯ (s + m)}. (3)

For m = 0,

∑_{1≤k<n} λ_{k} + \frac{λ_{n}}{2} = \frac{1}{2πi} ∫_{c−i∞}^{c+i∞} ( ∑_{k≥1} \frac{λ_{k}}{k^{s}} )n^{s} \frac{ds}{s}.

Formula (3) is obtained from (2) by setting x ≡ n^{−1}, f(x) ≡ H_{m}(x), and observing that H_{m}^{∗}(s) = m!(s(s + 1) ⋯ (s + m))^{−1}. For m = 0 the formula has to be modified slightly by taking a principal value for the sum, since H_{0}(x) is discontinuous at x = 1. For instance, if we use λ_{k} ≡ 1 and m = 1, we get

\frac{n − 1}{2} = \frac{1}{2πi} ∫_{2−i∞}^{2+i∞} ζ(s)n^{s} \frac{ds}{s(s + 1)}.

Shifting the line of integration to the left and taking residues into account we obtain

0 = ∫_{− \frac{1}{4} −i∞}^{− \frac{1}{4} +i∞} ζ(s)n^{s} \frac{ds}{s(s + 1)}.  (4)

Identity (4) is the basis for the existence of several exact rather than plainly asymptotic summation formulæ. We use this Mellin–Perron technique to derive an alternative proof of Delange’s theorem: The sum–of–digits function S(n) satisfies

S(n) = \frac{1}{2}n log_{2} n + nF_{0}(log_{2} n),

where F_{0}(u) can be represented by the Fourier series F_{0}(u) = ∑_{k∈ℤ} f_{k}e^{2πiku} and

f_{0} = \frac{log_{2} π}{2} − \frac{1}{2 log 2} − \frac{3}{4},

f_{k} = −\frac{1}{log 2} \frac{ζ(χ_{k})}{χ_{k}(χ_{k} + 1)} for χ_{k} = \frac{2πik}{log 2} , k ≠ 0.

Let v_{2}(k) be the exponent of 2 in the prime decomposition of k and ν(k) be the number of 1-digits in the binary representation of k. We have ν(k)−ν(k −1) = 1 − v_{2}(k), so that S(n) resembles a double summation of v_{2}(k). Furthermore, it is well-known (and also rederived in Section 6) that

∑_{k≥1} \frac{v_{2}(k)}{k^{s}} = \frac{ζ(s)}{2^{s} − 1}.

Thus, from (3), with λ_{k} = v_{2}(k) and m = 1, we get the basic integral representation

S(n) = \frac{n(n − 1)}{2} − \frac{n}{2πi} ∫_{2−i∞}^{2+i∞} \frac{ζ(s)}{2^{s} − 1}n^{s} \frac{ds}{s(s + 1)}.

The integrand has a simple pole at s = 1 (originationg from the ζ–function), a double pole at s = 0 and simple poles at s = χ_{k}. Shifting the line of integration to ℜ(s) = −\frac{1}{4} and taking residues into account we get

S(n) = \frac{1}{2}n log_{2} n + nF_{0}(log_{2} n) − nR(n),

where the Fourier series (akin to F_{0}) \frac{1}{log 2} ∑_{k∈ℤ} \frac{ζ(χ_{k})}{χ_{k}(χ_{k}+1)}n^{χ_{k}} occurs as the sum of residues of the integrand at the imaginary poles s = χ_{k}. The remainder term is

R(n) = \frac{1}{2πi} ∫_{− \frac{1}{4} −i∞}^{− \frac{1}{4} +i∞} \frac{ζ(s)}{2^{s} − 1}n^{s} \frac{ds}{s(s + 1)},  (5)

so that there only remains to prove that R(n) ≡ 0 when n is an integer. The integral converges since |ζ(−\frac{1}{4} +it)| ≪ |t|^{3/4} (cf. [48]). Using the expansion \frac{1}{2^{s}−1} = −1 − 2^{s} − 2^{2s} − 2^{3s} − ⋯ in (5), which is legitimate since now ℜ(s) < 0, we find that R(n) is a sum of terms of the form

\frac{1}{2πi} ∫_{− \frac{1}{4} −i∞}^{− \frac{1}{4} +i∞} ζ(s)(2^{k}n)^{s} \frac{ds}{s(s + 1)},

and each of these terms is 0 by virtue of (4).

It is clear from the discussion above that an exact formula for a sum–of–digits function is obtained each time a similar Dirichlet generating function can be introduced. Let us illustrate this point by the integral representation for the sum–of– digits function associated to Gray code representations. The Gray code representation of the integers starts like 0, 1, 11, 10, 110, 111, 101, 100, 1100, 1101, …; its characteristic is that the representations of n and n + 1 differ in exactly one binary position and it is constructed in a simple manner by reflections based on powers of two (for a definition, see, e. g., [13]). Let γ(k) be the number of 1-digits in the Gray code representation of k, and δ_{k} = γ(k) − γ(k − 1). It is easy to see that δ_{2k} = δ_{k}, and the pattern for odd values is δ_{2k+1} = (−1)^{k}. Thus the Dirichlet generating function δ(s) of {δ_{k}} is

δ(s) = \frac{2^{s}L(s)}{2^{s} − 1} with L(s) = ∑_{k≥0} \frac{(−1)^{k}}{(2k + 1)^{s}} .

Thus by (2.4), the summatory function G(n) = ∑_{k<n} γ(k) admits the integral representation

G(n) = \frac{n}{2πi} ∫_{2−i∞}^{2+i∞} \frac{2^{s}L(s)}{2^{s} − 1}n^{s} \frac{ds}{s(s + 1)}.

The summatory function G(n) of sum–of–digits function of Gray–code satisfies

G(n) = \frac{1}{2}n log_{2} n + nF_{1}(log_{2} n),

where F_{1}(x) is representable by the Fourier series

F_{1}(x) = 2 log_{2} Γ(\frac{1}{4}) − \frac{3}{2} − log_{2} π + \frac{1}{log 2} ∑_{k∈ℤ\\{0\}} \frac{L(χ_{k})}{χ_{k}(χ_{k} + 1)}e^{2kπix}.

4 Symmetric signed digit expansions

Recently, Heuberger and I [22] have considered a symmetric system with an even base q and digits −\frac{q}{2}, …, \frac{q}{2}. Such a system is a priori redundant because of the existence of both ±\frac{q}{2} but made unique by the condition that n = ∑_{j≥0} ε_{j}q^{j}, where |ε_{j}| ≤ q/2 and |ε_{j}| = q/2 implies that 0 ≤ sign(ε_{j})ε_{j+1} < q/2. (Equivalent conditions where discussed in [22].) We call this expansion the symmetric signed digit expansion of n and denote it by (… ε_{2}(n)ε_{1}(n)ε_{0}(n)). For q = 2, this system was already considered by Reitwiesner in a computer science context [42]. Here is an algorithm to compute it from right to left (Algorithm 1):

Algorithm 1 Computation of the symmetric signed digit expansion of n Input: n > 0, q ≥ 2 integers. Output: The representation ε.

ε ← (); m ← n while m > 0 do

a ← (m mod q)

if a > q/2 or (a = q/2 and {m/q^{2}} ≥ 1/2) then

a ← a − q end if m ← (m − a)/q; ε ← ε & a

end while

We were able to derive an explicit formula for the digit ε_{r}, which for q = 2 is

ε_{r} = ⌊\frac{n}{2^{r+2}} + \frac{5}{6}⌋ − ⌊\frac{n}{2^{r+2}} + \frac{4}{6}⌋ − ⌊\frac{n}{2^{r+2}} + \frac{2}{6}⌋ + ⌊\frac{n}{2^{r+2}} + \frac{1}{6}⌋ ,

and was already obtained in [40]. For q = 6 it reads

ε_{r} = + ⌊y + \frac{248}{252}⌋ + ⌊y + \frac{241}{252}⌋ + ⌊y + \frac{234}{252}⌋ − 5 ⌊y + \frac{228}{252}⌋ + ⌊y + \frac{221}{252}⌋ + ⌊y + \frac{214}{252}⌋

+ ⌊y + \frac{206}{252}⌋ + ⌊y + \frac{199}{252}⌋ + ⌊y + \frac{192}{252}⌋ − 5 ⌊y + \frac{186}{252}⌋ + ⌊y + \frac{179}{252}⌋ + ⌊y + \frac{172}{252}⌋

+ ⌊y + \frac{164}{252}⌋ + ⌊y + \frac{157}{252}⌋ + ⌊y + \frac{150}{252}⌋ − 5 ⌊y + \frac{144}{252}⌋ + ⌊y + \frac{137}{252}⌋ + ⌊y + \frac{130}{252}⌋

+ ⌊y + \frac{122}{252}⌋ + ⌊y + \frac{115}{252}⌋ − 5 ⌊y + \frac{108}{252}⌋ + ⌊y + \frac{102}{252}⌋ + ⌊y + \frac{95}{252}⌋ + ⌊y + \frac{88}{252}⌋

+ ⌊y + \frac{80}{252}⌋ + ⌊y + \frac{73}{252}⌋ − 5 ⌊y + \frac{66}{252}⌋ + ⌊y + \frac{60}{252}⌋ + ⌊y + \frac{53}{252}⌋ + ⌊y + \frac{46}{252}⌋

+ ⌊y + \frac{38}{252}⌋ + ⌊y + \frac{31}{252}⌋ − 5 ⌊y + \frac{24}{252}⌋ + ⌊y + \frac{18}{252}⌋ + ⌊y + \frac{11}{252}⌋ + ⌊y + \frac{4}{252}⌋ ,

where y = n/6^{r+2}. In general, it has q^{2} terms.

One sees the pattern 0, 1, 2, 3, −2, −1 appearing 3 times followed by 0, 1, 2, −3, −2, −1, also 3 times. The digits 0, 1, 2, 3, −2, −1 are not symmetric around 0, and 0, 1, 2, −3, −2, −1 are not, either. However, in combination, both coming with “probability” 1/2, the distribution of the digits becomes symmetric.

In a recent paper with Grabner and Heuberger [16] we are addressing the subblock counting problem in symmetric signed digit expansions. To announce our principal findings, we need some notation. If a block b = (b_{s}, …, b_{0}) is given, we denote its value by value(b) = ∑_{ℓ} b_{ℓ}q^{ℓ}.

We also use Iverson’s notation, popularized in [19]: [P] is defined to be 1 if condition P is true, and 0 otherwise. With this notation we can count the number of subblock occurrences of b in (the symmetric signed digit expansions of) n via

∑_{k≥0} [(ε_{k+r−1}(n), …, ε_{k}(n)) = b] .

We only consider admissible blocks b: these blocks represent the number value(b) in the symmetric signed digit expansion. For interest we note that there are \frac{2+q}{1+q} q^{r} − \frac{1}{1+q} (−1)^{r} admissible blocks of length r; this was implicitly proved in [22]. We are studying the quantity

S_{b}(N) = ∑_{n<N} ∑_{k≥0} [(ε_{k+r−1}(n), …, ε_{k}(n)) = b] .

This is our main result:

Let q ≥ 2 be an even integer and r ≥ 1. For an admissible block b = (b_{r−1}, …, b_{0}) with |b_{r−1}| < \frac{q}{2} and b ≠ 0^{r} the number of occurrences of the block b in the symmetric signed digit expansions of the positive integers less than N satisfies

S_{b}(N) = \frac{Q(b_{0})}{q^{r}(q + 1)}N log_{q} N + h_{0}(b)N + NH_{b}(log_{q} N) + o(N),

where

Q(η) =q + \begin{cases}2 & for η = 0, \\ 0 & for η = ±\frac{q}{2}, \\ 1 & else, \end{cases}

H_{b}(x) = ∑_{k∈ℤ\{0}} h_{k}(b)e^{2kπix},

h_{k}(b) = \frac{log q}{2kπi(log q + 2kπi)}(ζ (\frac{2kπi}{log q}, [value(b) < 0] + q^{−r} value(b) + \frac{R_{min}(b_{0})}{q^{r}(q+1)})

− ζ (\frac{2kπi}{log q}, [value(b) < 0] + q^{−r} value(b) + \frac{R_{max}(b_{0})}{q^{r}(q+1)})) for k ≠ 0,

h_{0}(b) = log_{q} Γ ([value(b) < 0] + q^{−r} value(b) + \frac{R_{min}(b_{0})}{q^{r}(q + 1)})

− log_{q} Γ ([value(b) < 0] + q^{−r} value(b) + \frac{R_{max}(b_{0})}{q^{r}(q + 1)})

− \frac{Q(b_{0})}{q^{r}(q + 1)} (r + \frac{1}{2} + \frac{1}{log q} − \frac{1}{q + 1}) + \frac{1}{q^{r−1}(q + 1)},

R_{min}(η) = − \frac{q}{2} − [(η − 1) mod q ≥ \frac{q}{2}] ,  R_{max}(η) = \frac{q}{2} + [η mod q < \frac{q}{2}] .

The function H_{b}(x) is a periodic continuous function of period 1 and mean 0. As usual ζ(s, x) denotes the Hurwitz ζ–function.

The case of blocks b with most significant digit b_{r−1} = ±\frac{q}{2} can also be obtained from that, by a trivial argument taking differences.

The instance r = 1 (counting digits) was discussed in [22], although without mentioning the periodic fluctuations in explicit form. Thuswaldner [47] has used Dirichlet series and the Mellin–Perron summation formula to exhibit this fluctuating behaviour in the case q = 2 and r = 1.

The analysis is based on the Mellin–Perron formula, but with a slight twist:

∑_{n<N}(N − n)a_{n} = \frac{1}{2πi} ∫_{c−i∞}^{c+i∞} ∑_{n≥1} \frac{a_{n}}{(n − α)^{s}} (N − α)^{s+1} \frac{ds}{s(s + 1)},

where 0 ≤ α < 1 and c is in the half-plane of absolute convergence of the Dirichlet series. This slightly more general situation 0 ≤ α < 1 was discussed in [17]. Without this version with the parameter α, one could still proceed successfully, as in [47], but that would be considerably more cumbersome and less elegant.

5 Representations of natural numbers as sums of 3 squares

This brief account is based on [46, 36, 43]. It is an old result that n is not representable as a sum of 3 squares iff n = 4^{i}(8k + 7), which means that in base-four representation, the last two nonzero digits are either 13 or 33. Let Q(m) be the counting function of the numbers that are representable as a sum of 3 squares:

Q(m) = ∑_{0<n≤m} [n representable as a sum of 3 squares] = m − ∑_{0<n≤m} κ(n),

with κ(n) = 1 if n = 4^{i}(8k + 7), κ(n) = 0 otherwise. It is a good idea to separate the main term and write Q(m) = \frac{5}{6}m + Δ(m). Osbaldestin and Shiu provide a Delange type analysis of the following formula:

\frac{1}{N} ∑_{0≤n<N} Δ(n) = \frac{3}{8} log_{4} N + F (log_{4} N) + \frac{1}{8} [N is odd] ,

with F (x) = ∑_{k∈ℤ} f_{k}e^{2πikx} and

f_{0} = −\frac{31}{48} − \frac{3}{8 log 4} − \frac{1}{log 4}(ζ′(0, \frac{7}{16}) + ζ′(0, \frac{15}{16})),
f_{k} = −\frac{1}{log 4} \frac{1}{χ_{k}(1 + χ_{k})}(ζ(χ_{k}, \frac{7}{16}) + ζ(χ_{k}, \frac{15}{16})), k ≠ 0, χ_{k} = \frac{2πik}{log 4} .

It was announced already in [10] that a proof of this result using the Mellin– Perron summation formula would be possible, and Marko Riedel has worked out the details in his Master’s thesis [43].

6 The average number of registers to evaluate a binary tree of size n

The function “number of registers” reg is given recursively by Reg(□) = 0 and

Reg ([figure: ◯; t_{1}; t_{2}] ) = \begin{cases}max\{Reg(t_{1}), Reg(t_{2})\} & if Reg(t_{1}) ≠ Reg(t_{2}), \\ 1 + Reg(t_{1}) & otherwise. \end{cases}

The problem is the evaluation of R_{n}, the average value of the function reg, based on the set of binary trees of size n. This was first studied in [14, 25]; for a tutorial see [38]. We have

R_{n} = \frac{1}{b_{n}} [z^{n}]E(z),  with  E(z) = ∑_{n≥0} z^{n} ∑_{t of size n} Reg(t)

and b_{n} = \frac{1}{n+1} \binom{2n}{n} being the number of binary trees with n nodes. One can derive the following for the function E(z), using the substitution z = u/(1 + u)^{2}:

E(z) = \frac{1 − u^{2}}{u} ∑_{p≥1} \frac{u^{2^{p}}}{1 − u^{2^{p}}} = \frac{1 − u^{2}}{u} ∑_{p≥1} ∑_{λ≥1} u^{λ2^{p}} = \frac{1 − u^{2}}{u} ∑_{n≥2} v_{2}(n)u^{n},

where v_{2}(n) is the exponent of 2 in the prime number decomposition of n. If we write in a unique way n = 2^{m}(1 + 2i), (m ≥ 1, i ≥ 0), we have v_{2}(n) = ∑_{p=1}^{m} 1 = m. The quantity v_{2}(n) (which we have seen already in Section 3) is often called “dyadic valuation,” for obvious reasons. One can get the coefficients, e. g., using the Lagrange inversion formula:

[z^{n}]E(z) = ∑_{k≥1} v_{2}(n)[\binom{2n}{n − k} − 2\binom{2n}{n − k − 1} + \binom{2n}{n − k − 2}].

One strategy to proceed is the following (that was the method of Flajolet, Raoult, and Vuillemin): One application of partial summation brings, via ν(k) = k − ∑_{j≤k} v_{2}(j), the sum of digits function in, and a second application of partial summation makes the summatory function of the sum–of–digits function appear, which, according to Delange’s analysis, is completely known! That means on the other side that the second difference of the binomial coefficients becomes eventually a fourth difference, but that causes no problems. The final result is this: The average number R_{n} of registers to evaluate a binary tree of size n satisfies

R_{n} = log_{4} n + D(log_{4} n) + o(1),

where D(x) is a continuous periodic function of period 1; this function can be expanded in a Fourier series as D(x) = ∑_{k∈ℤ} d_{k}e^{2kπix}, with

d_{0} = \frac{1}{2} − \frac{γ}{2 log 2} − \frac{1}{log 2} + log_{2} π

and

d_{k} = \frac{1}{log 2}ζ(χ_{k})Γ(\frac{χ_{k}}{2} )(χ_{k} − 1), k ≠ 0, χ_{k} = \frac{2πik}{log 2} .

Another strategy, used by Kemp, is as follows: Approximation of the binomial coefficients leads eventually to the study of series of the type

f(x) := ∑_{k≥1} v_{2}(k)e^{−k^{2}x^{2}};

the Mellin transform then brings in Dirichlet series g(s) := ∑_{k≥1} v_{2}(k)k^{−s}; but this one is easily evalutated, using v_{2}(2k) = 1 + v_{2}(k) and v_{2}(2k + 1) = 0:

g(s) = ∑_{k≥1} (1 + v_{2}(k))(2k)^{−s} = 2^{−s}(ζ(s) + g(s)),

from which one gets g(s) = ζ(s)/(2^{s} − 1).

A third strategy is more on the lines of [12] and based on singularity analysis of generating functions: One must study E(z) for z → \frac{1}{4}, i. e., for u → 1, and sets u = e^{−t} and considers E(z) for t → 0. The second factor of E(z), which is denoted by V (t), is the challenging one. The Mellin transform of V (t) is denoted by V^{∗}(s):

V^{∗}(s) = ∫_{0}^{∞} x^{s−1} ∑_{k≥1} v_{2}(k)e^{−kx}dx = ∑_{k≥1} v_{2}(k)k^{−s} ∫_{0}^{∞} x^{s−1}e^{−x}dx.

This gives V^{∗}(s) = \frac{Γ(s)ζ(s)}{2^{s}−1}. The Mellin inversion formula then leads to

V (t) = \frac{1}{2πi} ∫_{2−i∞}^{2+i∞} V^{∗}(s)t^{−s}ds,

and we shift the line of integration to the left, taking the residues of the integrand V^{∗}(s)t^{−s} into account. Using some classical expansions we get

V (t) ∼ \frac{1}{t} + \frac{1}{2} log_{2} t − \frac{1}{2} log_{2} 2π + \frac{1}{4} + \frac{γ}{2 log 2} + \frac{1}{log 2} ∑_{k≠0} Γ(χ_{k})ζ(χ_{k})t^{−χ_{k}} + …

which gives the local expansion for the function E(z); the rest is then singularity analysis of generating functions [11].

7 Odd–even merge

In the analysis of a sorting algorithm (Batcher’s odd–even merge [28]), one has to consider the quantity

B_{n} = ∑_{k≥1} \begin{matrix}( & {2n \atop n−k} & ) \\ ( & {2n \atop n} & ) \end{matrix}(2F (k) + k),

representing the number of exchanges in the odd–even merge of 2n elements. In this equation, F (k) = ∑_{0≤j<k} f(j) and f(j) is the number of digits “1” in the Gray code representation of j. The numbers ϑ(j) := f(j) − f(j − 1) equal ±1: if k is of the form k = 2^{m}(4i + 1), ϑ(k) = 1; if k is of the form k = 2^{m}(4i + 3), ϑ(k) = −1. We might recognize a great similarity between ϑ(k) and v_{2}(k) from Section 6.

Indeed, there are again basically 3 lines of attack: The Flajolet–Ramshaw approach [13] uses partial summation and uses an explicit result for the summatory function of the sum of digits function in the Gray code representation, as derived in Section 3; this is analogous to [14]. The next one, analogous to [25], was used by Sedgewick [44]: Approximating binomial coefficients, one has to study series à la

f(x) := ∑_{k≥1} ϑ(k)e^{−k^{2}x^{2}},

or, after using Mellin transforms, Dirichlet series like g(s) := ∑_{k≥1} ϑ(k)k^{−s}, but this one is again easily evaluated:

g(s) = ∑_{m,i≥0} (2^{m}(4i + 1))^{−s} − ∑_{m,i≥0} (2^{m}(4i + 3))^{−s} = \frac{1}{2^{s}(2^{s} − 1)}[ζ(s, \frac{1}{4}) − ζ(s, \frac{3}{4})],

where the Hurwitz ζ(s, a)-function is defined by ζ(s, a) = ∑_{n≥0}(n + a)^{−s} for ℜ(s) > 1. Recall that the function from Section 3 can be expressed as L(s) = 4^{−s}[ζ(s, \frac{1}{4}) − ζ(s, \frac{3}{4})].

The third approach, using singularity analysis of generating functions, is presented in the tutorial [38]: One has to study the function

\frac{u(1 + u)}{(1 − u)^{3}} ∑_{i≥1} ϑ(i)u^{i}

near u = 1. Eventually one finds:

The average number of exchanges in the odd–even merge of 2n elements satisfies

B_{n} ∼ \frac{1}{4}n log_{2} n + nB( log_{4} n),

where B(x) is a continuous periodic function of period 1; this function can be expanded as a Fourier series B(x) = ∑_{k∈ℤ} b_{k}e^{2kπix}, with

b_{0} = −\frac{1}{2 log 2} − \frac{γ}{4 log 2} − \frac{3}{4} + 2 log_{2} Γ(\frac{1}{4}) − log_{2} π

and for k ≠ 0

b_{k} = \frac{1}{log 2}ζ(χ_{k}, \frac{1}{4})\frac{Γ(χ_{k}/2)}{1 + χ_{k}}.

8 A problem of Yekutieli and Mandelbrot

The following problem was left open (and attacked empirically) in [49] and later solved in [39].

If we have an extended binary tree, we label the leaves with 0, and, recursively, if the left subtree of a node is labeled with a and the right subtree with b, we label the node with max{a, b} if a ≠ b and with a + 1 otherwise. The value attached to the root is called the register function of the tree t. The value attached to a particular node is the register function of the subtree having this node as its root, as already discussed earlier in this paper.

The authors in [49] consider the bifurcation ratio (at the root). It is meant to be the number of maximal subtrees (which is not the same as the number of internal nodes (!)) having register function exactly 1 less than the register function of the entire tree. It was observed empirically that the expected value of this parameter is asymptotically a periodic function of log_{4} n if all trees of size n (n internal nodes) are considered to be equally likely. Here, we want to settle this problem by explicitly describing the periodic function in terms of the Fourier coefficients. In principle, a full asymptotic expansion could be given, but the computation of the lower order term becomes more and more complicated.

Now, let w_{p,k,n} be the number of binary trees with n nodes, register function p, and Yekutieli–Mandelbrot–parameter k, and let

W_{p}(z, y) = ∑_{n,k≥0} w_{p,k,n} y^{k}z^{n}

be its bivariate generating function.

To find the expected values, we have to work with T_{p}(z) = \frac{∂}{∂y} W_{p}(z, y)|_{y=1} and T (z) = ∑_{p≥1} T_{p}(z). The coefficient of z^{n} in T (z), divided by \frac{1}{n+1} \binom{2n}{n}, is the expected value sought by Yekutieli and Mandelbrot. One finds for p ≥ 1

W_{p}(z, y) = zy^{2}R_{p−1}^{2}(z) + 2zyW_{p}(z, y)R_{p−1}(z) + 2zW_{p}(z, y)(B(z) − S_{p−1}(z)),

with R_{p}(z) being the generating function of binary trees and register function = p, and S_{p}(z) = ∑_{j≥p} R_{j}(z). Therefore

T_{p}(z) = 2zR_{p−1}^{2}(z) + 2zR_{p}(z)R_{p−1}(z) + 2zT_{p}(z)(B(z) − S_{p}(z)),

and eventually (again with z = u/(1 + u)^{2})

T (z) = 2u + 2\frac{1 − u^{2}}{u} ∑_{p≥1} \frac{u^{3·2^{p−1}}}{(1 + u^{2^{p}})^{2}(1 − u^{2^{p}})}.

One has to study the series

σ = ∑_{p≥1} \frac{u^{3·2^{p−1}}}{(1 + u^{2^{p}})^{2}(1 − u^{2^{p}})} = ∑_{p≥0,k≥1} u^{2^{p}(2k+1)}(−1)^{k−1} ⌊\frac{k+1}{2}⌋

= − ∑_{p,k≥0} ku^{2^{p}(4k+1)} + ∑_{p,k≥0}(k + 1)u^{2^{p}(4k+3)}.

Now, one performs a Mellin transform analysis in order to find the local behaviour

T (z) ∼ 3 − (\frac{4C}{(log 2)π} + 5) \sqrt{1 − 4z} − \frac{8}{log 2} ∑_{k≠0} Γ(χ_{k})β(χ_{k} − 1)(1 − 4z)^{(1−χ_{k})/2}.

Here, β(s) = ζ(s, \frac{1}{4}) − ζ(s, \frac{3}{4}), which is the function that appeared already in the odd–even merge problem, χ_{k} = 2πik/log 2, and C = ∑_{k≥0} (−1)^{k}/(2k + 1)^{2} = 0.9159655942 … is Catalan’s constant. Consequently we get this result: The average value of the Yekutieli–Mandelbrot parameter, if all binary trees of size n are considered to be equally likely, is given by

\frac{2C}{(log 2)π} + \frac{5}{2} + δ(log_{4} n) + O(\frac{1}{n}).

The periodic function δ(x) has mean value 0 and admits the following representation as a Fourier series,

δ(x) = −\frac{2}{log 2} ∑_{k≠0}(χ_{k} − 1)Γ(\frac{χ_{k}}{2} )β(χ_{k} − 1)e^{2kπix}.

One could also perform an analysis along the lines of Kemp resp. Sedgewick [25, 44]; it would be based on the exact formula

[z^{n}]T (z) = \frac{2}{n + 1}\binom{2n}{n}+2 ∑_{m≥1} ψ(m) [\binom{2n}{n + 1 − m} − 2\binom{2n}{n − m} + \binom{2n}{n − 1 − m}]

with ψ(m) = \begin{cases}−k & if m = 2^{i}(4k + 1) for some i and k, \\ k + 1 & if m = 2^{i}(4k + 3) for some i and k. \end{cases}

9 Missing digits

Interesting phenomena occur if several digits are forbidden. We describe here the instance of q = 3 and digits {0, 2}, i. e., the digit 1 is forbidden. The set of strings 0.a_{1}a_{2} …, with a_{i} ∈ {0, 2} is the classical Cantor set. Thus considering 2 ∑_{i≥1} X_{i}3^{−i}, where the X_{i} are independent and identically distributed with probability distribution ℙ{X = 0} = ℙ{X = 1} = 1/2, we get a probability distribution on the interval [0, 1] which is conveniently called Cantor distribution. In [18], the moments of a slightly more general distribution were investigated, motivated by an earlier paper of Lad and Taylor [31]; we sketch the procedure. Denote a_{n} the nth moment of the Cantor distribution; it is not hard to see that

a_{n} = \frac{1}{2(3^{n} − 1)} ∑_{i=0}^{n−1} \binom{n}{i}2^{n−i}a_{i}, n ≥ 1, a_{0} = 1.

If one rewrites it as (2 − 3^{−n})a_{n} = ∑_{i=0}^{n} \binom{n}{i}2^{n−i}a_{i} and introduces the exponential generating function A(z) = ∑_{n≥0} a_{n}z^{n}/n!, it translates into

2A(z) − 2 − A(\frac{z}{3}) + 1 = e^{2z/3}A(\frac{z}{3}) − 1,

or

A(z) = \frac{1 + e^{2z/3}}{2} A(\frac{z}{3}) = ∏_{k≥1} \frac{1 + e^{2z/3^{k}}}{2} ;

the last step was by iteration of the functional equation. Slightly more useful than this infinite product is the Poisson transformed generating function B(z) = e^{−z}A(z), since by a process called Depoissonization one finds that a_{n} ∼ B(n). There is a well written survey paper on the subject by Jacquet and Szpankowski [24]. We get

B(z) = \frac{1 + e^{−2z/3}}{2} B(\frac{z}{3}) = ∏_{k≥1} \frac{1 + e^{−2z/3^{k}}}{2} .

To find the asymptotic behaviour of B(z) for large z (and thus B(n) and thus a_{n}) we compute the Mellin transform B^{∗}(s) of B(z), viz.

B^{∗}(s) = \frac{1}{2}3^{s}B^{∗}(s) + \frac{1}{2} ∫_{0}^{∞} B(\frac{z}{3})e^{−2z/3}z^{s−1}dz,

or

B^{∗}(s) = \frac{1}{2 − 3^{s}} ∫_{0}^{∞} ∏_{k≥2} \frac{1 + e^{−2z/3^{k}}}{2} e^{−2z/3}z^{s−1}dz.

The standard reference for the Mellin transform in the context of asymptotic enumeration is [9]. The Mellin inversion formula gives

B(z) = \frac{1}{2πi} ∫_{c−i∞}^{c+i∞} B^{∗}(s)z^{−s}ds,

where the constant c might be chosen to be −1/2. Now one shifts the line of integration to the right and collects negative residues. They come from the solutions of 2 − 3^{s} = 0, i. e., s = log_{3} 2 + 2πik/ log 3, for k ∈ ℤ. If one calls them f_{k}, then B(n) ∼ ∑_{k∈ℤ} f_{k}n^{− log_{3} 2−2πik/ log 3}, which is of the form n^{− log_{3} 2}δ(log_{3} n), with a periodic function δ(x) of period 1. Typically, the amplitudes of such periodic functions are quite small, so the most interesting term is obtained for k = 0. The negative residue at s = log_{3} 2 is

\frac{1}{2 log 3} ∫_{0}^{∞} ∏_{k≥2} \frac{1 + e^{−2z/3^{k}}}{2} e^{−2z/3}z^{log_{3} 2−1}dz = 0.734 …,

and so a_{n} ∼ B(n) ≃ f_{0}n^{− log_{3} 2} ≈ 0.734 n^{−0.631}.

Another interesting question was triggered by Hosking [23] and solved in [27]: Assume that we draw n random numbers (independently) according to the Cantor distribution. What is the expected value of the minimum of them? If one would draw from the interval [0, 1] according to the uniform distribution, then it is fairly easy to see that it is 1/(n + 1). If we call that minimum a_{n}, we get

a_{n} = \frac{1}{3}2^{−n} ∑_{k=1}^{n} \binom{n}{k}a_{k} + \frac{1}{3}2^{−n}(2 + a_{n}), a_{0} := 0.

This recursion is obtained by observing that the minimum is obtained from one of the random strings starting with a zero, provided there is one. In the rare event that all strings start with 2, this first digit contributes 2/3 (additively), and the minimum is sought from all the n participants. Rearranging the recursion and introducing the exponential generating function A(z) := ∑_{k≥0} a_{k}z^{k}/k!, one finds

A(2z) = \frac{1}{3}(1 + e^{z})A(z) + \frac{2}{3}(e^{z} − 1).

Now we introduce, following Knuth [28], the function Â(z) := A(z)/(e^{z} − 1) = ∑_{k≥0} â_{k}z^{k}/k! and get

Â(2z) = \frac{1}{3}Â(z) + \frac{2}{3} \frac{1}{e^{z} + 1},

from which one finds

â_{n} = −\frac{2}{3} \frac{B_{n+1}}{n + 1} \frac{2^{n+1} − 1}{2^{n} − \frac{1}{3}},

with Bernoulli numbers B_{n}. Hence one gets the explicit solution

a_{n} = −\frac{2}{3} ∑_{k=0}^{n−1} \binom{n}{k}\frac{B_{k+1}}{k + 1} \frac{2^{k+1} − 1}{2^{k} − \frac{1}{3}}.

In order to study the asympotic behaviour of that quantity one can use Rice’s method [15], which is related to Mellin transforms, and eventually write

a_{n} = −\frac{2}{3(n + 1)} · \frac{1}{2πi} ∫_{C} \frac{(−1)^{n}n!}{z(z − 1) … (z − n)}( − zζ(1 − z))\frac{2^{z} − 1}{2^{z−1} − \frac{1}{3}} dz,

where the contour C encloses the poles 1, 2, …, n − 1 and no others. Deforming the contour of integration reduces the problem to the computation of residues; the dominant ones are the solutions of 2^{z−1} − \frac{1}{3} = 0, i. e., 1 − log_{2} 3 + 2kπi/ log 2, for all k ∈ ℤ. Eventually one finds, apart from a periodic function as above, that

a_{n} ≃ n^{log_{2} 3} \frac{2}{3 log 2}Γ(log_{2} 3)ζ(log_{2} 3).

Another type of moments are Cantor’s singular moments: Consider the unique non–decreasing function on [0, 1] such that, if x = 2 ∑_{j≥1} ε_{j}3^{−j} with ε_{j} ∈ {0, 1}, then F (x) = ∑_{j≥1} ε_{j}2^{−j}. It was a question in the problem section of the American Mathematical Monthly [6] to compute the moments; the following solution came out:

J_{n} = ∫_{0}^{1} (F (x))^{n}dx = \frac{2}{3(n + 1)} ∑_{j=0}^{n} \binom{n + 1}{j}\frac{B_{j}}{3 · 2^{j−1} − 1} for n ≥ 1 and J_{0} = 1;

the case n = −1 was left open and treated by me in [41]: Since one can show that J_{−1} = ∑_{n≥0} J_{n}, and, again by Rice’s method,

J_{n} = \frac{2}{3} · \frac{1}{2πi} ∫_{− \frac{1}{2} −i∞}^{− \frac{1}{2} +i∞} \frac{Γ(n + 1)Γ(1 − s)}{Γ(n + 2 − s)} \frac{ζ(1 − s)}{3 · 2^{s−1} − 1} ds,

one finds

∑_{n=0}^{N} J_{n} = J_{0} + \frac{2}{3} · \frac{1}{2πi} ∫_{− \frac{1}{2} −i∞}^{− \frac{1}{2} +i∞} \frac{Γ(N + 2)Γ(1 − s)}{Γ(N + 2 − s)s} \frac{ζ(1 − s)}{3 · 2^{s−1} − 1} ds

− \frac{2}{3} · \frac{1}{2πi} ∫_{− \frac{1}{2} −i∞}^{− \frac{1}{2} +i∞} \frac{Γ(2)Γ(1 − s)}{Γ(2 − s)s} \frac{ζ(1 − s)}{3 · 2^{s−1} − 1} ds.

Now we perform the limit N → ∞ and get eventually (the computations are not displayed here):

∑_{n≥0} J_{n} = \frac{4}{3} + \frac{2}{3} ∑_{k,m≥1} 3^{−k} · \frac{1}{2πi} ∫_{\frac{3}{2} −i∞}^{\frac{3}{2} +i∞} \frac{1}{s(s − 1)}(\frac{2^{k}}{m} )^{s} ds

= −\frac{1}{3} + \frac{2}{3} ∑_{k≥1} (\frac{2}{3})^{k}H_{2^{k}} = 3.36465 07281 00925 16083 89349 6289 …,

with harmonic numbers H_{n} = ∑_{1≤k≤n} \frac{1}{k}.

More general results of this type are currently worked out in collaboration with F. Bassino [1].

10 Von Neumann’s addition algorithm

This brief description is based on a recent paper with Heuberger [21].

Knuth [29] has analyzed von Neumann’s addition algorithm: Assume that two integers are given in q–ary notation, say (… y_{2}y_{1}y_{0})_{q} and (… y_{2}y_{1}y_{0})_{q}; then the integer (… s_{2}s_{1}s_{0})_{q} with s_{i} = (x_{i} +y_{i}) mod q is formed, as well as (… c_{2}c_{1}c_{0})_{q} (the carries), where c_{i+1} = [x_{i} + y_{i} ≥ q]. The process is iterated by adding (… s_{2}s_{1}s_{0})_{q} with s_{i} = (x_{i} + y_{i}) mod q and (… c_{2}c_{1}c_{0})_{q} until the string of carries contains only zeros. Knuth studied the average number of iterations, assuming two random integers with n digits. The result is ∼ log_{q} n; it turns out that the longest subsequence of the form … i(q − 1)(q − 1) … (q − 1)j … with i ≠ q − 1 and j ≥ q in ( … (x_{2} +y_{2})(x_{1} +y_{1})(x_{0} +y_{0}))_{q} is responsible for the number of iterations. We extended Knuth’s results to other positional number systems, namely for the basis q and the set of q digits {d, d+1, …, d+q−1}. Note carefully that carries might now be ±1 and that the sequence of sums might be oscillating, being smaller or larger than the true value of the sum of the two integers. This is in sharp contrast to the traditional q–ary system, where the sums are monotonically increasing until the algorithm stops. Thus it is perhaps natural that the description of subsequences being responsible for the number of iterations is significantly more complicated. Here is an example for q = 5, d = −1, and ¯1 = −1:

\begin{matrix}(12¯1¯1¯113)_{(5,−1)} = & (… x_{2}x_{1}x_{0})_{(5,−1)} = & 21108 \\ (22¯10¯123)_{(5,−1)} = & (… y_{2}y_{1}y_{0})_{(5,−1)} = & 36863 \\ (3¯13¯1331)_{(5,−1)} = & (… z_{2}z_{1}z_{0})_{(5,−1)} = & 45591 \\ (1¯10¯1010)_{(5,−1)} = & (… c_{2}c_{1}c_{0})_{(5,−1)} = & 12380 \\ (¯13333¯11)_{(5,−1)} = & (… z_{2}z_{1}z_{0})_{(5,−1)} = & −3929 \\ (1¯10¯10100)_{(5,−1)} = & (… c_{2}c_{1}c_{0})_{(5,−1)} = & 61900 \\ (13323¯1¯11)_{(5,−1)} = & (… z_{2}z_{1}z_{0})_{(5,−1)} = & 135971 \\ (¯10001000)_{(5,−1)} = & (… c_{2}c_{1}c_{0})_{(5,−1)} = & −78000 \\ (0332¯1¯1¯11)_{(5,−1)} = & (… z_{2}z_{1}z_{0})_{(5,−1)} = & 57346 \\ (00010000)_{(5,−1)} = & (… c_{2}c_{1}c_{0})_{(5,−1)} = & 625 \\ (0333¯1¯1¯11)_{(5,−1)} = & (… z_{2}z_{1}z_{0})_{(5,−1)} = & 57971 \\ (00000000)_{(5,−1)} = & (… c_{2}c_{1}c_{0})_{(5,−1)} = & 0 \end{matrix}

The generating function where the coefficient of z^{n} counts the number of pairs of integers of length ≤ n, such that ≤ k + 2 iterations are necessary, is given by

G^{≤k}(z) = \frac{s_{0}(z) + (z/q)^{k}r_{1}(z) + (z/q^{2})^{k}r_{2}(z) + (z^{2}/q^{3})^{k}r_{3}(z)}{(1 − z)s_{0}(z) + (z/q)^{k}s_{1}(z) + (z/q^{2})^{k}s_{2}(z) + (z^{2}/q^{3})^{k}s_{3}(z)},

where s_{0}(z) = −2q^{4}(q − 1)(q^{2} − z(1 − d))(q^{2} − z(q + d)). The terms r_{1}(z), r_{2}(z), r_{3}(z), s_{1}(z), s_{2}(z), s_{3}(z) are polynomials in z, q, d which are independent of k.

From this one can derive, essentially by bootstrapping, approximations, and Mellin transforms, that the expected number t_{n} of carry propagations satisfies

t_{n} = log_{q} n + log_{q} δ + \frac{γ}{log q} + \frac{1}{2} + ψ(log_{q} n + log_{q} δ) + O (\frac{log^{4} n}{n}) ,

where δ = \frac{(q^{3}+(2d−2)q^{2}+(2d−1)(d−1)q−(d−1)d)(q−1)(q+1)}{2(q^{2}−q−d)(q^{2}+d−1)} and ψ(x) is again a periodic function.

For the instance of the symmetric signed digit expansion, one can also perform such an analysis, but this is more involved, and we refer to the original paper.

11 Mergesort

Because of space restrictions, we cannot describe the algorithm and/or any details. Basically, there is a top–down version where one needs to study functions like

(k + 1)n − 2(2^{k+1} − 1) + 2 ∑_{0≤j≤k} \frac{2^{j}}{⌊\frac{n}{2^{j+1}} ⌋ + 2} + 2 ∑_{0≤j≤k} \frac{(1 − b_{j})(2^{j} − (b_{j−1} … b_{0})_{2})}{( ⌊\frac{n}{2^{j+1}} ⌋ + 1)( ⌊\frac{n}{2^{j+1}} ⌋ + 2)},

where (b_{k} … b_{0})_{2} is the binary representation of n. This can be efficiently done by a method introduced by Flajolet and Golin [8]. This worked well because such quantities were obtained by so–called divide–and–conquer recursions.

The bottom–up version that I studied with Panny [37] led to even more involved expressions, and no divide–and–conquer recursions were available, so we had to resort to some Delange type analysis. More recently, Hwang and his coworkers [2] developed techniques to deal with quite general versions of Mergesort, including the top–down and bottom–up variants; further mergesort papers of Hwang’s can be found on his homepage http://algo.stat.sinica.edu.tw/.

12 Jump interpolation search trees

Güntzer and Paul have used symmetric signed digit representations for the classical case q = 2 to construct a data structure that they called jump interpolation search trees [20]. All numbers with representations of length ≤ n are in the tree, and the number 0, its length being zero; it serves as the root. Node y is a child of node x, if the least significant nonzero digit in y is replaced by 0, resulting in x. Thus, the depth of a node is the number of nonzero digits. This construction can be verbatim translated to the case of general even q. The computations are analogous to the ones in [40]. The admissible words allow the representation

ε + (\frac{q}{2} + L + \frac{−q}{2} + L̄)(L\frac{q}{2} + 0\frac{q}{2} + L̄\frac{−q}{2} + 0\frac{−q}{2} + L + L̄ + 0)^{∗}

with L = \{1, …, \frac{q}{2} − 1\} and L̄ = \{−\frac{q}{2} + 1, …, −1\},

To mark the length of the representations by z and the depth by u, we replace L and L̄ by (\frac{q}{2} − 1)zu, ±\frac{q}{2} by zu, and 0 by z, and of course f^{∗} by 1/(1 − f). The coefficient of z^{n} then refers to words of length n; since we are interested in words of length ≤ n, we divide the result by 1 − z and obtain

\frac{1 + (−1 + 2u)z − u(uq − 2u + 2)z^{2}}{(1 − z)(1 + (2u − 1 − uq)z − u(uq − 2u + 2)z^{2})}.  (6)

From this, we get first, by setting u = 1, that the number of words of length ≤ n is given by

\frac{q^{2}}{(q + 1)(q − 1)}q^{n} + \frac{q − 2}{2(q − 1)} − \frac{q}{2(q + 1)}(−1)^{n}.  (7)

Differentiating (6) with respect to u, and then setting u = 1 leads to \frac{zq(1−z+(q−2)z^{2})}{(1−z)(1+z)^{2}(1−zq)^{2}} , and the coefficient of z^{n} in it is given by

[\frac{q(q^{2}−2)}{(q−1)(q+1)^{2}} n + \frac{q(q^{2}−q+2)}{(q−1)^{2}(q+1)^{3}} ]q^{n} + \frac{q(q − 2)}{4(1 − q)^{2}} − [\frac{q^{2}}{2(q+1)^{2}} n + \frac{(q^{2}+3q+6)q}{4(q+1)^{3}} ](−1)^{n}. (8)

Taking the quotient of (8) and (7) gives us then that the average depth of a random node in the tree is

\frac{q^{2} − 2}{q(q + 1)}n − \frac{q^{2} − q + 2}{q(q + 1)^{2}(q − 1)} + o(1);

for q = 2, we get again the old result n/3 from [20].

References

[1] F. Bassino and H. Prodinger. (q, δ)-numeration systems with missing digits. In preparation, 2002.

[2] W. M. Chen, H. K. Hwang, and G. H. Chen. The cost distribution of queuemergesort, optimal mergesorts, and power-of-2 rules. J. Algorithms, 30:423–448, 1999.

[3] H. Delange. Sur la fonction sommatoire de la fonction somme des chiffres. Enseignement Mathématique, 21:31–47, 1975.

[4] L. Devroye and P. Kruszewski. A note on the Horton–Strahler number for random trees. Inform. Process. Lett., 56:95–99, 1995.

[5] L. Devroye and P. Kruszewski. On the Horton–Strahler number for random tries. RAIRO Inform. Théor. Appl., 30:443–456, 1996.

[6] H. G. Diamond and B. Reznick. Problems and solutions. American Mathematical Monthly, 106:175–176, 1999.

[7] G. Doetsch. Handbuch der Laplace-Transformation, 3 volumes. Birkhäuser Verlag, Basel, 1972.

[8] P. Flajolet and M. Golin. Mellin transforms and asymptotics. The mergesort recurrence. Acta Inform., 31:673–696, 1994.

[9] P. Flajolet, X. Gourdon, and P. Dumas. Mellin transforms and asymptotics: Harmonic sums. Theoretical Computer Science, 144:3–58, 1995.

[10] P. Flajolet, P. Grabner, P. Kirschenhofer, H. Prodinger, and R. Tichy. Mellin transforms and asymptotics: Digital sums. Theoretical Computer Science, 123:291–314, 1994.

[11] P. Flajolet and A. Odlyzko. Singularity analysis of generating functions. SIAM Journal on Discrete Mathematics, 3:216–240, 1990.

[12] P. Flajolet and H. Prodinger. Register allocation for unary–binary trees. SIAM J. Comput., 15:629–640, 1986.

[13] P. Flajolet and L. Ramshaw. A note on Gray code and odd–even merge. SIAM J. Comput., 9(1):142–158, 1980.

[14] P. Flajolet, J.-C. Raoult, and J. Vuillemin. The number of registers required for evaluating arithmetic expressions. Theoretical Computer Science, 9:99–125, 1979.

[15] P. Flajolet and R. Sedgewick. Mellin transforms and asymptotics: Finite differences and Rice’s integrals. Theoretical Computer Science, 144:101–124, 1995.

[16] P. Grabner, C. Heuberger, and H. Prodinger. Subblock occurrences in signed digit representations. Submitted.

[17] P. Grabner, P. Kirschenhofer, and H. Prodinger. The sum–of–digits function for complex bases. J. London Math. Soc., 57:20–40, 1998.

[18] P. Grabner and H. Prodinger. Asymptotic analysis of the moments of the Cantor distribution. Statistics and Probability Letters, 26:243–248, 1996.

[19] R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete mathematics. A foundation for computer science. Addison-Wesley, second edition, 1994.

[20] U. Güntzer and M. Paul. Jump interpolation search trees and symmetric binary numbers. Information Processing Letters, 26:193–204, 1987/88.

[21] C. Heuberger and H. Prodinger. Carry propagation in signed digit representations. submitted, 2001.

[22] C. Heuberger and H. Prodinger. On minimal expansions in redundant number systems: Algorithms and quantitative analysis. Computing, 66:377–393, 2001.

[23] J. R. M. Hosking. Moments of order statistics of the Cantor distribution. Statistics and Probability Letters, 19:161–165, 1994.

[24] P. Jacquet and W. Szpankowski. Analytical de-Poissonization and its applications. Theoretical Computer Science, 201:1–62, 1998.

[25] R. Kemp. The average number of registers needed to evaluate a binary tree optimally. Acta Inform., 11:363–372, 1978/79.

[26] P. Kirschenhofer and H. Prodinger. Subblock occurrences in positional number systems and Gray code representation. Journal of Information and Optimization Sciences, 5:29–42, 1984.

[27] A. Knopfmacher and H. Prodinger. Exact and asymptotic formulæ for average values of order statistics of the Cantor distribution. Statistics and Probability Letters, 27:189–194, 1996.

[28] D. E. Knuth. The Art of Computer Programming, volume 3: Sorting and Searching. Addison-Wesley, 1973. Second edition, 1998.

[29] D. E. Knuth. The average time for carry propagation. Indagationes Mathematicæ, 40:238–242, 1978.

[30] P. Kruszewski. A note on the Horton–Strahler number for random binary search trees. Inform. Process. Lett., 69:47–51, 1999.

[31] F. R. Lad and W. F. C. Taylor. The moments of the Cantor distribution. Statistics and Probability Letters, 13:307–310, 1992.

[32] A. Meir, J. W. Moon, and J. R. Pounder. On the order of random channel networks. SIAM J. Algebraic Discrete Methods, 1:25–33, 1980.

[33] J. W. Moon. An extension of Horton’s law of stream numbers. Math. Colloq. Univ. Cape Town, 12:1–15 (1980), 1978/79.

[34] J. W. Moon. On Horton’s law for random channel networks. Ann. Discrete Math., 8:117–121, 1980. Combinatorics 79 (Proc. Colloq., Univ. Montréal, Montreal, Que., 1979), Part I.

[35] M. Nebel. On the Horton–Strahler number for combinatorial tries. Theor. Inform. Appl., 34:279–296, 2000.

[36] A. H. Osbaldestin and P. Shiu. A correlated digital sum problem associated with sums of three squares. Bull. London Math. Soc., 21:369–374, 1989.

[37] W. Panny and H. Prodinger. Bottom-up mergesort—a detailed analysis. Algorithmica, 14:340–354, 1995.

[38] H. Prodinger. Some analytic techniques for the investigation of the asymptotic behaviour of tree parameters. EATCS Bulletin, 47:180–199, 1992.

[39] H. Prodinger. On a problem of Yekutieli and Mandelbrot about the bifurcation ratio of binary trees. Theoretical Computer Science, 181:181–194, 1997.

[40] H. Prodinger. On binary representations of integers with digits −1, 0, 1. Integers, pages A8, 14 pp. (electronic), 2000.

[41] H. Prodinger. On Cantor’s singular moments. Southwest J. Pure Appl. Math., 2000(1):27–29 (electronic), 2000.

[42] G. Reitwiesner. Binary arithmetic. Vol. 1 of Advances in Computers, Academic Press, pages 231–308, 1960.

[43] M. Riedel. Applications of the Mellin–Perron formula in number theory. Technical report, University of Toronto, 1996.

[44] R. Sedgewick. Data movement in odd–even merging. SIAM J. Comput., 7:239–272, 1978.

[45] L. A. Shepp and S. P. Lloyd. Ordered cycle lengths in a random permutation. Trans. Amer. Math. Soc., 121:340–357, 1966.

[46] P. Shiu. Counting sums of three squares. Bull. London Math. Soc., 20:203–208, 1988.

[47] J. Thuswaldner. Summatory functions of digital sums occurring in Cryptography. Periodica Math. Hungarica, 38:111–130, 1999.

[48] E. T. Whittaker and G. N. Watson. A Course of Modern Analysis. Cambridge University Press, fourth edition, 1927. Reprinted 1973.

[49] I. Yekutieli and B. Mandelbrot. Horton–Strahler ordering of random binary trees. J. Phys. A, 27:285–293, 1994.

Helmut Prodinger The John Knopfmacher Centre for Applicable Analysis and Number Theory School of Mathematics, University of the Witwatersrand P. O. Wits, 2050 Johannesburg, South Africa

helmut@staff.ms.wits.ac.za
http://www.wits.ac.za/helmut/index.htm