MELLIN TRANSFORMS AND ASYMPTOTICS: DIGITAL SUMS

Philippe Flajolet^{1,2}, Peter Grabner^{3}, Peter Kirschenhofer^{1}, Helmut Prodinger^{1}, and Robert F. Tichy^{1,3}

Abstract. Arithmetic functions related to number representation systems exhibit various periodicity phenomena. For instance, a well known theorem of Delange expresses the total number of ones in the binary representations of the first n integers in terms of a periodic fractal function.

We show that such periodicity phenomena can be analyzed rather systematically using classical tools from analytic number theory, namely the Mellin–Perron formulæ. This approach yields naturally the Fourier series involved in the expansions of a variety of digital sums related to number representation systems.

1. Introduction

Let S(n) represent the total number of 1-digits in the binary representations of the integers 1, 2, …, n − 1. It is not hard to see that

(1.1)  S(n) = \frac{1}{2}n log_{2} n + o(n log n),

since asymptotically the binary representations contain roughly as many 0’s as 1’s. The Trollope–Delange formula is more surprising. It expresses S(n) by an exact formula [De75]

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

where F_{0}(u), a fractal function, is a continuous, periodic, nowhere differentiable function; F_{0}(u) has an explicit Fourier expansion that involves the Riemann zeta function, its Fourier coefficient of order k, k ≠ 0, being

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

The argument given by Delange relies on a combinatorial decomposition of binary representations of integers, followed by a computation of the Fourier coefficients of the fractal

Typeset by AMS-TEX

1 Research of these authors was supported by the French-Austrian scientific cooperation programme.

2 Research of this author was supported in part by the Basic Research Action of the E.C. under contract No. 7141 (Project ALCOM 2).

3 Research of these authors was supported by the Austrian science foundation (Project Nr. P8274PHY).

function. Our approach instead is more direct and in line with classical methods from analytic number theory. It is based on an integral representation (see Eq. (3.2)), here

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

itself closely related to Mellin transforms and the classical Perron formula. In this context, the periodicity present in S(n) simply arises, by the residue theorem, from poles of the integrand at the regularly spaced points s = 2πik/ log 2.

In other words, as is customary from standard analytic number theory (e.g., the prime number theorem), fluctuations in a number-theoretic function appear to be directly related to singularities of an associated Dirichlet series.

The Mellin Perron formulæ are reviewed briefly in Section 2. In general, they provide asymptotic rather than exact summation formulæ. An additional argument is then needed in order to establish an exact representation like (1.1). Similar exact formulæ are established for the standard sum–of–digit function (Section 3), for the more general case of the number of blocks in binary representations and Gray codes (Section 4), and for a function related to the Cantor set (Section 5),

h (∑_{i} 2^{e_{i}}) = ∑_{i} 3^{e_{i}},

where the exponents e_{i} are strictly increasing.

Sections 6 and 7 deal primarily with asymptotic summation formulæ. Section 6 is concerned with the asymptotic evaluation of the function

(1.3)  Φ(n) = ∑_{k=0}^{n−1} 2^{ν(k)},

where ν(k) denotes the binary sum-of-digits function. The value Φ(n) is also equal to the number of odd binomial coefficients in the first n rows of Pascal’s triangle. Stolarsky [Sto77] earlier gave upper and lower bounds for this expression. Applying the Mellin-Perron formula and a pseudo–Tauberian argument the Fourier coefficients of the corresponding fractal function are computed. (Estimates were also given by Harborth [Ha77] and in the q-ary case by Stein [Ste89].) It is found that \frac{Φ(N)}{N^{ρ}} is a periodic function of log_{2} N, with ρ = log_{2} 3, see Figure 1 for a graphical rendering. Section 7 is concerned with the asymptotic evaluation of

S_{3}(n) = ∑_{k=0}^{n−1}(−1)^{ν(3k)},

a function obviously related to the distribution of 1–digits in the multiples of three which was first studied by Newman [Ne69]. J. Coquet [Co83] established a Delange type theorem in this case.

Figure 1. The representation of \frac{Φ(n)}{n^{ρ}} plotted against n in a logarithmic scale; Φ(n) represents the number of odd binomial coefficients in the first n rows of Pascal’s triangle and is also defined by Eq. (1.3); ρ = log_{2} 3.

The asymptotic formulæ obtained in connection with Φ(n) and S_{3}(n) when matched against exact formulæ obtained by direct combinatorial reasoning, lead to new Fourier expansions. This mixed combinatorial–analytic process constitutes another source for summatory formulæ with explicit Fourier coefficients developed in Sections 6 and 7.

Exact summation formulæ related to number representations arise at various places in elementary (combinatorial) number theory as well as in the average case analysis of algorithms.

As general references in number theory, we refer to Stolarsky’s survey [Sto77] and to [KPT85]. An especially important paper by the spectrum of its analysis techniques is Brillhart, Erdős and Morton’s work [BEM83]. It concerns the Rudin–Shapiro sequence, r(n), which gives the parity of the number of blocks 11 in the binary representation of n.

The summatory formulæ considered here are closely related to number–theoretic functions arising in the context of iterated substitutions and so–called automatic sequences (see Allouche’s paper for a survey [Al87]), which constitute a natural framework in which several of our analyses could have been cast. In that framework Dumont and Thomas [DT89] have used elementary methods to derive for linear functionals of iterated substitution sequences a whole class of asymptotic forms of the type

n^{β}(log_{θ} n)^{γ}F (log n) + o(n^{β}(log_{θ} n)^{γ}),

involving some fluctuating function F. Allouche and Cohen have shown that Dirichlet generating functions associated to automatic sequences have meromorphic continuations (see [Al87, p.261] and [AC85]). Techniques developed in this paper could then be used in order to provide alternative derivations for some of the results of Dumont and Thomas.

The present work is also related to the notion of regular sequences, a generalization of automatic sequences, that was introduced by Allouche and Shallit in [AS92]. In fact, the sequences under study here fall into that category. In this context, some of our results are complemented by the recent work of Cateland [Ca92] who established precisely non– differentiability properties for several of our periodic functions (like the ones for Gray code or block occurrences).

Figure 2. Pascal’s triangle modulo 2. The odd numbers are represented by black squares, the even numbers by white squares.

In the area of the average case analysis of algorithms, combinatorial sums involving number–theoretic functions often present themselves. Delange’s formula was employed in order to analyze register allocation strategies, or equivalently the order of random channel networks in [FRV79]. It was later extended to some non-standard digital representations of integers, like Gray code [FR80], for the purpose of analyzing sorting networks, as well as to occurrences of blocks of digits in standard q-ary representations [Ki83] and subblock occurrences in Gray code representation [KP84] or to Newman sequence related to the binary representations of multiples of three [Co83]. (In a recent paper [GT91], Delange’s result was even further generalized to digit expansions with respect to linear recurrences.)

Finally, the subject of this paper is also close to the classical divide-and-conquer recurrences that are common in theoretical computer science and of which a typical form is

f_{n} = f_{⌊n/2⌋} + f_{⌈n/2⌉} + e_{n},

with {e_{n}} a usually simple sequence and {f_{n}} the sequence to be analyzed. In a recent work, Flajolet and Golin [FG92] treat several instances that appear in a diversity of recursive divide-and-conquer algorithms like mergesort, heapsort, Karatsuba multiplication, or maxima finding in multidimensional space.

Graphics. As an illustration of the fractal phenomena at stake, we have displayed in Figure 1 the ratio \frac{Φ(N)}{N^{ρ}} plotted against N in a logarithmic scale. When considering successive intervals [2^{k−1}, 2^{k}], we see the function \frac{Φ(N)}{N^{ρ}} which gets refined in a stepwise manner. The picture clearly illustrates the fractal nature of the graph. Figure 2 shows Pascal’s triangle reduced modulo 2. The picture reveals another aspect of the fractal structure underlying the problem. (Performing an easy transformation one obtains the famous Sierpinski triangle [Fa85], a popular source for similar graphics being [Wo84].)

2. Mellin-Perron formulæ

For completeness, we give a brief outline of the Perron formula by relating it to the Mellin transform. The resulting summation formulæ are classical, so that we content ourselves with a sketchy description of the analysis involved.

The major reference for Mellin transforms is Doetsch’s book [Do50]. Mellin summation is briefly surveyed in [FRS84] which is directed towards applications in the average case analysis of algorithms, while in the context of integrals (rather than sums), a useful reference is [Wo89, Chap. III]. The classical Perron formula is discussed at length in Apostol’s book [Ap84], and a higher order version is for instance given by Schwarz (see Chapter IV of [Sch69]).

Let f(x) be a function defined over [0, +∞). Its Mellin transform f^{∗}(s) = M[f(x); s] is defined by

(2.1)  f^{∗}(s) = ∫_{0}^{∞} f(x)x^{s−1}dx.

By linearity and the rescaling property we have

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

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. [Do50]). When applied to (2.2), it provides

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

with c in the fundamental strip.

Formula (2.3) 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{matrix}1 & if x ∈ [0, 1] \\ 0 & if x > 1, \end{matrix}

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

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

(2.4)  \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)}.

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 (2.4) is obtained from (2.3) 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. See also [Ap84, p.245] for a direct proof of the m = 0 case.

For instance, if we use λ_{k} ≡ 1 and m = 1, we get

(2.5)  \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

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

Identity (2.6) is the basis for the existence of several exact rather than plainly asymptotic summation formulæ.

3. Sum-of-Digits Functions

We apply the Mellin–Perron technique described in the preceding section in order to derive a new proof of Delange’s theorem.

Theorem 1. [Delange] 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) is representable 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.

Proof. Let υ_{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 − υ_{2}(k), so that S(n) resembles a double summation of υ_{2}(k). Furthermore it is well-known that

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

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

(3.2)  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 in (3.2) has a simple pole at s = 1, a double pole at s = 0 and simple poles at s = χ_{k}. Shifting the line of integration^{1} to ℜ(s) = −\frac{1}{4} and taking residues into account we get

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

1Technically, we integrate along a rectangle with upper and lower sides passing through ±(2N + 1)iπ/ log 2, and let N → ∞. Due to growth properties of the zeta function, the contribution along the horizontal segments vanishes. This also proves directly that the sum of residues at the complex points (which gives the Fourier series) converges.

where the Fourier series akin to F_{0}

\frac{1}{log 2} ∑_{∈ℤ} \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

(3.4)  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)},

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|^{\frac{3}{4}} (cf. [WW27]).

Using the expansion

\frac{1}{2^{s} − 1} = −1 − 2^{s} − 2^{2s} − 2^{3s} − ⋯

in (3.4) 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 (2.6). □

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., [FR80]). 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

(3.5)  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)}.

Theorem 2. [Flajolet, Ramshaw] 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}(u) is representable by the Fourier series

F_{1}(u) = 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πiu}.

Proof. Starting with the representation (3.5), the proof runs along the same line as for the sum–of–digits function; this theorem is also a corollary of Theorem 3 proved in Section 4. □

Remark 1. The functions F_{0} and F_{1} are continuous but nowhere differentiable.

4. Subblock occurrences and the Gray Code

In this section we want to demonstrate that the idea used in the previous section for the analysis of the sum-of-digits function is also well suited to establish a much more general result on occurrences of patterns in the binary representation of integers. The main terms of Theorem 3 were already found by Kirschenhofer in [Ki83], but only an estimate of the remainder term was given. The remainder term has been also investigated independently by Cateland [Ca92] using elementary methods of the Delange type.

Theorem 3. Let (n; w) denote the number of occurrences of the 0-1-string w as a contiguous subblock in the binary representation of the integer n. (If w starts with 0, we also count occurrences that overhang to the left of the most significant digit of n; we only exclude strings w consisting solely of 0’s^{2}.) Then the mean number of occurrences, \frac{1}{n} ∑_{k<n}(k; w), is given by

\frac{1}{n} ∑_{k<n}(k; w) = \frac{log_{2} n}{2^{|w|}} + H_{w} (log_{2} n) + \frac{E_{w}(n)}{n}.

There |w| denotes the length of the string w, H_{w}(u) is a continuous periodic function of period 1 with Fourier expansion H_{w}(u) = ∑_{k∈ℤ} h_{k}e^{2kπiu},

h_{0} = log_{2} (\frac{Γ((0.w)_{2})}{Γ((0.w)_{2} + 2^{−|w|})}) − \frac{1}{2^{|w|}} (|w| − \frac{1}{2} + \frac{1}{log 2})
h_{k} = \frac{ζ(χ_{k}, (0.w)_{2}) − ζ(χ_{k}, (0.w)_{2} + 2^{−|w|})}{(log 2)χ_{k}(χ_{k} + 1)},

2A formula for this case exists, but is unpleasant to formulate

ζ(z, a) the Hurwitz ζ-function, (x)_{2} denotes the real number with binary representation x and E_{w}(n) is a dyadic rational with denominator 2^{|w|} which is described explicitly below in (4.9).

Proof. As in Section 3 we start with summation by parts to find

(4.1)  ∑_{k<n}(k; w) = ∑_{k<n} Δ_{w}(k)(n − k),

where Δ_{w}(k) = (k; w) − (k − 1; w). The differences Δ_{w}(k) obey the following recurrence relation: If n = 2^{|w|}k + r is even, we have

(4.2)  Δ_{w}(n) = Δ_{w} (\frac{n}{2}) + \{ \begin{matrix}1 & if (w)_{2} = r \\ −1 & if (w)_{2} = r − 1 \\ 0 & otherwise \end{matrix}

If n = 2^{|w|}k + r is odd, we simply have

(4.3)  Δ_{w}(n) = \{ \begin{matrix}1 & if (w)_{2} = r \\ −1 & if (w)_{2} = r − 1 \\ 0 & otherwise. \end{matrix}

¿From the recurrences (4.2) and (4.3) it easily follows that the Dirichlet series A_{w}(s) of the differences Δ_{w}(n) satisfies

A_{w}(s) = ∑_{n≥1} \frac{Δ_{w}(n)}{n^{s}} = ∑_{k≥1} \frac{Δ_{w}(k)}{(2k)^{s}} + ∑_{k≥0} \frac{1}{(2^{|w|}k + (w)_{2})^{s}} −

− ∑_{k≥0} \frac{1}{(2^{|w|}k + (w)_{2} + 1)^{s}} ,

so that

(4.4)  (1 − \frac{1}{2^{s}} ) A_{w}(s) = \frac{1}{2^{|w|s}} (ζ(s, (0.w)_{2}) − ζ(s, (0.w)_{2} + 2^{−|w|})) ,

where

ζ(s, a) = ∑_{n≥0} \frac{1}{(n + a)^{s}}

is the Hurwitz ζ-function [WW27] and (0.w)_{2} denotes the rational number (w)_{2}2^{−|w|}. ¿From (4.1) and (4.4) we find using Perron’s formula for m = 1:

\frac{1}{n} ∑_{k<n}(k; w) = \frac{1}{2πi} ∫_{\frac{3}{2} −i∞}^{\frac{3}{2} +i∞}\frac{1}{2^{|w|s}} (ζ((s, (0.w)_{2}) − ζ(s, (0.w)_{2} + 2^{−|w|})) ×

× \frac{(2n)^{s}ds}{(2^{s} − 1) s(s + 1)}

Shifting the contour of integration to the left, we observe that the first order poles of the Hurwitz ζ-functions at s = 1 cancel since both have residue 1, so that the main contribution comes from the second order pole s = 0. The residue is

(4.5)  C_{1} log_{2} n + \frac{C_{2}}{log 2} + C_{1} (\frac{1}{2} − |w| − \frac{1}{log 2}) ,

with

C_{1} = ζ(0, (0.w)_{2}) − ζ(0, (0.w)_{2} + 2^{−|w|}) = 2^{−|w|},

since ζ(0, a) = \frac{1}{2} − a and

C_{2} = ζ′(0, (0.w)_{2}) − ζ′(0, (0.w)_{2} + 2^{−|w|}) = log \frac{Γ((0.w)_{2})}{Γ((0.w)_{2} + 2^{−|w|})},

since ζ′(0, a) = log Γ(a) − \frac{1}{2} log(2π) [WW27].

Thus the main term and the mean h_{0} of the fluctuating term are established. The other Fourier coefficients h_{k} are easily derived from the residues at the simple poles χ_{k} = \frac{2πik}{log 2} , k ≠ 0.

We still have to analyze the remainder term

(4.6)  \begin{aligned}R_{n} & = \frac{1}{2πi} ∫_{− \frac{1}{4} −i∞}^{− \frac{1}{4} +i∞}\frac{1}{2^{|w|s}} (ζ(s, (0.w)_{2}) − ζ(s, (0.w)_{2} + 2^{−|w|})) × \\ & × \frac{(2n)^{s}ds}{(2^{s} − 1) s(s + 1)} = − ∑_{k≥0} R′_{2^{k}n}, \end{aligned}

where

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

After shifting the contour back to the right, we find, by taking into account the residues at s = 0,

(4.7)  R′_{n} = −\frac{1}{2^{|w|}} + ∑_{k<2n} λ_{k} (1 − \frac{k}{2n}) ,

where

λ_{k} = \{ \begin{matrix}1 & if k ≡ (w)_{2} mod 2^{|w|} \\ −1 & if k ≡ (w)_{2} + 1 mod 2^{|w|} \\ 0 & otherwise. \end{matrix}

The sum in (4.7) can be computed explicitly to give

(4.8)  R′_{n} = \{ \begin{matrix}\frac{2^{|w|}−1−r}{2^{|w|+1}} \frac{1}{n} & if r = (2n − 1 mod 2^{|w|}) ≥ (w)_{2} \\ \frac{−1−r}{2^{|w|+1}} \frac{1}{n} & if r = (2n − 1 mod 2^{|w|}) < (w)_{2}. \end{matrix}

¿From (4.8) we see that R′_{2^{k}n} will be zero for k ≥ |w| − 1, so that in fact (4.6) reduces to

(4.9)  \frac{E_{w}(n)}{n} = − ∑_{k=0}^{|w|−2} R′_{2^{k}n},

and this completes the proof. □

Theorem 3 and formula (4.9) have a number of consequences of interest. In particular, they contain as special cases the results on binary representations and Gray code.

Corollary 1. [Delange] If |w| = 1 and w is the 1-digit, i.e. in the case of the sum-of-digits function, we have E_{w}(n) = 0, as stated already in Theorem 1.

Corollary 2. If |w| = 2, the remainder terms E_{w}(n) are given by the scheme

E_{01}(n) E_{10}(n) E_{11}(n)
n even  0  0  0
n odd  −\frac{1}{4}  \frac{1}{4}  \frac{1}{4}

Corollary 3. [Flajolet, Ramshaw] The mean value of the sum of digits in the Gray Code of n is given by

\frac{log_{2} n}{2} + F_{1} (log_{2} n) ,

where F_{1} = H_{01} + H_{10} is as described in Theorem 2.

Proof. An alternative proof to that of Theorem 2 runs as follows. The k-th bit in the Gray Code GC(n) of n is given by the sum modulo 2 of the k–th and k +1–st digit in the binary representation of n. Thus the number of 1’s in GC(n) is just (n; 01) + (n; 10), where we have to count the one occurrence of 01 overhanging to the left of the most significant 1 in the binary representation of n. It follows that the mean is given by

2\frac{log_{2} n}{4} + H_{01} (log_{2} n) + H_{10} (log_{2} n) + \frac{E_{01}(n)}{n} + \frac{E_{10}(n)}{n}

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

which also relates F_{1} to H_{01} and H_{10}. □

Remark 2. All results in Sections 3 and 4 are easily generalized to base q representations. As an application of the special instance q = 4 we get an alternative proof of a result due to Osbaldestin and Shiu [OS89] concerning the number of integers ≤ n that are representable as a sum of three squares.

5. Triadic Binary Numbers

Let h(n) be the number that results from interpreting in base 3 the binary representation of n, i.e.,

h (∑_{i} 2^{e_{i}}) = ∑_{i} 3^{e_{i}},

where the exponents e_{i} are strictly increasing. It is known that h(1) < h(2) < … < h(n) is the ‘minimal’ sequence of n positive integers not containing an arithmetic progression. The sequence is also an analog of Cantor’s triadic set. An exact formula for the summatory function H of h is established.

Theorem 4. For the summatory function H(n) = ∑_{k<n} h(k) we have

H(n) = n^{ρ+1}F_{3}(log_{2} n) − \frac{1}{4}n,

where ρ = log_{2} 3 and F_{3}(u) is the Fourier series

F_{3}(u) = \frac{1}{3 log 2} ∑_{k∈ℤ} ζ(ρ + χ_{k})\frac{e^{2πiku}}{(ρ + χ_{k})(ρ + χ_{k} + 1)},

with χ_{k} = \frac{2πik}{log 2} .

Proof. Using h(n) − h(n − 1) = \frac{1}{2}(3^{υ_{2}(n)} + 1) we obtain

∑_{n=1}^{∞} \frac{h(n) − h(n − 1)}{n^{s}} = \frac{1}{2} ∑_{n=1}^{∞} \frac{3^{υ_{2}(n)}}{n^{s}} + \frac{1}{2}ζ(s)

=\frac{1}{2} ∑_{k=0}^{∞} \frac{3^{k}}{2^{ks}} ∑_{n=1}^{∞} \frac{1}{(2n − 1)^{s}} + \frac{1}{2}ζ(s)

=\frac{2^{s} − 2}{2^{s} − 3}ζ(s).

Applying the Mellin-Perron summation formula (2.4) with c = 3 and shifting the line of integration yields

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

+ n^{ρ+1} ∑_{k∈ℤ} \frac{1}{3 log 2}ζ(ρ + χ_{k})\frac{n^{χ_{k}}}{(ρ + χ_{k})(ρ + χ_{k} + 1)} + \frac{1}{2}ζ(0)n.

The remainder integral is 0 by the same argument as for the sum–of–digits function, and the proof is complete. □

Remark 3. Obviously the base 3 can be replaced by an arbitrary number α > 1 and α ≠ 2. The corresponding exact formula is

∑_{k<n} h_{α}(k) = n^{ρ+1}F_{α}(log_{2} n) − \frac{1}{2(α − 1)}n,

where F_{α} has a Fourier expansion similar to F_{3} and ρ = log_{2} α.

Remark 4. The function g defined by h(n) = n^{ρ}g(log_{2} n) is periodic with period 1 but not continuous.

6. Odd Numbers in Pascal’s Triangle

In this section we establish an exact formula for the summatory function

Φ(n) = ∑_{0≤k<n} 2^{ν(k)}.

As pointed out in the introduction, Φ(n) is the number of odd binomial coefficients in the first n rows of Pascal’s triangle.

The application of Mellin–Perron techniques requires convergence of the complex integral of Theorem 0. For an m–fold summation, the ‘kernel’ in the integral involves 1/(s(s + 1) ⋯ (s + m − 1)), which decreases at infinity like |s|^{−m}. Thus, higher summations lead to better converging (inverse Mellin) integrals.

For the problem of Φ(n), we thus start with the double summatory function

Ψ(N) = ∑_{1≤n<N}(Φ(n) − 1),

where Mellin–Perron is easier to apply since the Fourier expansion converges absolutely (We have to subtract 1, because the summation in (2.4) starts at n = 1.) The formula that we get in this way is asymptotic.

Theorem 5. The arithmetic function Ψ(N) satisfies the asymptotic estimate

Ψ(N) = N^{ρ+1}G(log_{2} N) + O(N^{2+ε}), ρ = log_{2} 3

for arbitrary ε > 0, where G is a continuous periodic function with period 1. G admits an absolutely convergent Fourier expansion

G(u) = ∑_{k∈ℤ} g_{k}e^{2πiku}

with

g_{k} = \frac{2}{log 2} \frac{(1 − B(ρ_{k}))}{ρ_{k}(ρ_{k} + 1)},

where ρ_{k} = ρ + \frac{2kπi}{log 2} and

(6.1)  B(s) = \frac{1}{Γ(s)} ∫_{0}^{∞} ((1 − e^{−t}) (∏_{k=1}^{∞} (1 + 2e^{−t2^{k}})) − 1) t^{s−1}dt.

In order to come back to the Fourier expansion of F we need an external argument in order to convert the expansion of Ψ(N) into an expansion for Φ(n). One ingredient is a direct combinatorial proof of existence for the fluctuating part of Φ(n); this induces corresponding periodicities for Ψ(N), and by identification, we indirectly derive the Fourier expansion relative to Φ(n). (This process is in a way a pseudo–Tauberian argument!)

Theorem 6. The summatory function Φ(n) satisfies the exact formula

(6.2)  Φ(n) = n^{ρ}F (log_{2} n),

where ρ = log_{2} 3 and F is a continuous function of period 1. The Fourier coefficients of F (u) are given by

(6.3)  f_{k} = \frac{2}{log 2} \frac{(1 − B(ρ_{k}))}{ρ_{k}},

and in particular the mean value of F (u) is approximately

f_{0} ≈ 0.86360 49963 99079 60496 05033 61308 09499.

F (u) is represented by its Fourier series in the sense of standard (C, 1) Cesàro averages.

Observe that from [Ha77] it is already known that

0.812 ≤ F (u) ≤ 1.

Proof. (Theorem 5) Let

(6.4)  A(s) = ∑_{n=1}^{∞} \frac{2^{ν(n)}}{n^{s}}

be the Dirichlet generating function of 2^{ν(n)}. Since Ψ(N) is a double summation of 2^{ν(k)} we have an integral representation by means of the iterated Mellin-Perron formula (2.4). We get

(6.5)  Ψ(N) = \frac{N}{2πi} ∫_{3−i∞}^{3+i∞}A(s)N^{s} \frac{ds}{s(s + 1)},

where the abscissa ℜ(s) = 3 has been chosen, since A(3) converges absolutely. We need to locate the singularities of A(s). From the recurrences

ν(2k + 1) = ν(k) + 1 and ν(2k) = ν(k)

we get

A(s) = ∑_{k≡0 mod 2} \frac{2^{ν(k)}}{n^{s}} + ∑_{k≡1 mod 2} \frac{2^{ν(k)}}{k^{s}} =

= \frac{1}{2^{s}} A(s) + 2 ∑_{l=0}^{∞} \frac{2^{ν(l)}}{(2l + 1)^{s}} =

= \frac{3}{2^{s}} A(s) + 2 − 2B(s)

with

(6.6)  B(s) = ∑_{k=1}^{∞} 2^{ν(k)} (\frac{1}{(2k)^{s}} − \frac{1}{(2k + 1)^{s}} ) .

Using summation by parts and Stolarsky’s elementary estimate (cf. [Sto77])

(6.7)  \frac{1}{3} < \frac{Φ(n)}{n^{ρ}} < 3

we know that B(s) converges for ℜ(s) > ρ − 1 and by

(6.7)  A(s) = \frac{2^{s}}{2^{s} − 3} (2 − 2B(s))

A(s) has abscissa of convergence equal to ρ. This expression also provides us with the analytic continuation of A(s) for ℜ(s) > ρ − 1. We see that A(s) is meromorphic with simple poles at the points ρ_{k} = ρ + \frac{2πik}{log 2} .

In order to shift the contour of integration in (6.5) to the left we need that A(s) does not grow too large along vertical lines. For s = σ + it, with σ > 1 and |t| > \frac{σ}{\sqrt{3}}, we have

|1 − (1 − \frac{1}{2k + 1})^{s}| ≤ min (2, \frac{|t|}{k}) .

Thus we obtain

|B(s)| = |∑_{k=1}^{∞} \frac{2^{ν(k)}}{(2k)^{s}} (1 − (1 − \frac{1}{2k + 1})^{s})| ≤

≤ 2 ∑_{1≤k≤2|t|} \frac{2^{ν(k)}}{(2k)^{σ}} + ∑_{k>2|t|} \frac{2^{ν(k)}}{(2k)^{σ}} \frac{|t|}{k} ≪ |t|^{2−σ}.

Shifting the line of integration to ℜ(s) = 1 + ε < ρ, noting that |A(1 + ε + it)| ≪ |t|^{1−ε} and taking the residues at the poles ρ_{k} into account we get

Ψ(N) = \frac{N}{2πi} ∫_{1+ε−i∞}^{1+ε+i∞}A(s)N^{s} \frac{ds}{s(s + 1)}+

+ N^{ρ+1} ∑_{k∈ℤ} \frac{2}{log 2} \frac{1 − B(ρ_{k})}{ρ_{k}(ρ_{k} + 1)}N^{χ_{k}}.

Estimating the integral trivially we derive the asymptotic formula for Ψ(N).

So far, B(s) is defined in terms of the sequence {2^{ν(k)}} itself. An integral representation derives from an ordinary generating function, setting

φ(t) = ∑_{k=0}^{∞} 2^{ν(k)}e^{−kt} = ∏_{j=0}^{∞} (1 + 2e^{−2^{j}t}) .

Consider the Mellin transform of (1 − e^{−t})φ(2t) − 1; by Formula (2.2) (with μ_{k} = k, f(t) = e^{−t}), we get the integral representation for B(s). Thus the proof of Theorem 5 is completed. □

In order to get information on the number-theoretic function Φ(n) itself, we first work out a refinement of Stolarsky’s elementary approach.

Proposition 1. There exists an exact summation formula

(6.8)  Φ(n) = n^{ρ}F (log_{2} n)

with F continuous and periodic with period 1.

Proof. From [Sto77] there is an alternative formula

(6.9)  Φ (n = ∑_{i=1}^{r} 2^{e_{i}}) = ∑_{i=1}^{r} 2^{i−1}3^{e_{i}}

with decreasing exponents e_{i}. Pulling out the main term we get

(6.10)  Φ(n) = 3^{e_{1}} ∑_{i=1}^{r} 2^{i−1}3^{e_{i}−e_{1}},

where e_{1} = ⌊log_{2} n⌋.

We now define a real function ψ(x) on the interval [1, 2] as follows. Let

x = ∑_{j=0}^{∞} 2^{−d_{j}}

with 0 = d_{0} < d_{1} < . . .. Then we set

(6.11)  ψ(x) = ∑_{j=0}^{∞} 2^{j}3^{−d_{j}}.

Note that ψ is well-defined since the dyadic rationals are written in their infinite representation. Next we show the continuity of ψ. As the representation of dyadic irrationals is unique the continuity at these points follows immediately, since (because of d_{j} ≥ j) the expansion (6.11) converges faster than a geometric series with quotient \frac{2}{3}. For the proof of continuity at dyadic rationals we have to show

ψ (∑_{j=0}^{k} 2^{−d_{j}} ) = ψ (∑_{j=0}^{k−1} 2^{−d_{j}} + ∑_{l=d_{k}+1}^{∞} 2^{−l}) ,

which follows immediately by direct computation. Note that ψ(1) = 1 and ψ(2) = 3 and that ψ satisfies a Lipschitz–Hölder condition

|ψ(x) − ψ(y)| ≤ C|x − y|^{ρ−1}.

Using the function ψ we can write

(6.12)  Φ(n) = 3^{⌊log_{2} n⌋}ψ (\frac{n}{2^{⌊log_{2} n⌋}} ) ,

since \frac{n}{2^{⌊log_{2} n⌋}} is nothing but n “scaled” in binary to the interval [1, 2). Formula (6.12) thus transforms into

Φ(n) = n^{ρ}F ({log_{2} n}),

where

F (u) = 3^{−u}ψ (2^{u})

is defined over the interval [0, 1] and {x} = x − ⌊x⌋ denotes the fractional part. F can be extended into a periodic function since F (0) = F (1). The proof of Proposition 1 is completed. □

For the computation of the Fourier coefficients of F we make use of Theorem 5 and the following simple pseudo–Tauberian argument.

Proposition 2. Let f be a continuous function, periodic with period 1, and let τ be a complex number with ℜ(τ) > 0. Then there exists a continuously differentiable function g of period 1 such that

(6.13)  \frac{1}{N^{τ+1}} ∑_{n<N} n^{τ} f(log_{2} n) = g(log_{2} N) + o(1)

(6.14)  ∫_{0}^{1} g(u)du = \frac{1}{τ + 1} ∫_{0}^{1} f(u)du.

Proof. We set

(6.15)  g(u) = log 2 · \frac{2^{−(τ+1)u}}{2^{τ+1} − 1} ∫_{0}^{1} 2^{(τ+1)t}f(t)dt + log 2 · 2^{−(τ+1)u} ∫_{0}^{u} 2^{(τ+1)t}f(t)dt.

Obviously g is continuously differentiable and (6.14) follows by a straightforward application of integration by parts. Further we note that g(0) = g(1).

In order to prove (6.13) we proceed as follows

\frac{1}{N^{τ+1}} ∑_{n<N} n^{τ} f(log_{2} n) =

=\frac{1}{N^{τ+1}} ∑_{p=0}^{⌊log_{2} N⌋−1} ∑_{2^{p}≤n<2^{p+1}} n^{τ} f(log_{2} n) + \frac{1}{N^{τ+1}} ∑_{n=2^{⌊log_{2} N⌋}}^{N} n^{τ} f(log_{2} n) =

=\frac{1}{N^{τ+1}} ∑_{p<⌊log_{2} N⌋} 2^{p(τ+1)} ∑_{1≤x<2} x^{τ} f(log_{2} x)Δx+

+\frac{1}{N^{τ+1}} 2^{⌊log_{2} N⌋(τ+1)} ∑_{1≤x<y} x^{τ} f(log_{2} x)Δx,

where x = \frac{n}{2^{p}}, y = \frac{N}{2^{⌊log_{2} N⌋}} and x runs through all dyadic rationals with denominator 2^{p} and Δx = 2^{−p}, p = 0, …, ⌊log_{2} N⌋. Now we interpret the sums over x as Riemann sums. Thus we have with remainder terms ε(p) tending to 0 (for p → ∞)

\frac{1}{N^{τ+1}} ∑_{n<N} n^{τ} f(log_{2} n) =

= ∑_{p<⌊log_{2} N⌋} 2^{(p−⌊log_{2} N⌋)(τ+1)}y^{−(τ+1)} (∫_{1}^{2} x^{τ} f(log_{2} x)dx + ε(p)) +

+y^{−(τ+1)} (∫_{1}^{y} x^{τ} f(log_{2} x)dx + ε(⌊log_{2} N⌋)) =

=g(log_{2} y) + y^{−(τ+1)} ∑_{p=0}^{⌊log_{2} N⌋} ε(p)2^{−(⌊log_{2} N⌋−p)}.

We note that only ε(⌊log_{2} N⌋) depends on y. Since the convergence of Riemann sums is uniform with respect to the upper limit y, the remainder term tends to 0. Thus the proof of Proposition 2 is complete. □

Proof. (Theorem 6) We can now conclude and determine the Fourier coefficients f_{k} of the fractal function F in Theorem 6. We set τ = ρ_{k} in Proposition 2 and apply (6.14)

f_{k} = ∫_{0}^{1} F (u)e^{−2πiku}du = (ρ_{k} + 1) ∫_{0}^{1} G(u)e^{−2πiku}du = (ρ_{k} + 1)g_{k}.

Inserting the value of g_{k} yields

f_{k} = \frac{2}{log 2} \frac{1 − B(ρ_{k})}{ρ_{k}}.

Using |B(ρ_{k})| ≪ k^{2−ρ} we obtain the L^{2}-convergence of the Fourier expansion of F. Also, since we know that F (u) is continuous, its Fourier series converges in the mean by Fejér’s theorem [Ko88]. (More information on the convergence of the Fourier series would have to depend on a more detailed knowledge of the analytical behaviour of the function B.) This completes the proof of Theorem 6. □

7. The Newman–Coquet Function

In this section we investigate the function

(7.1)  S_{3}(n) = ∑_{k<n}(−1)^{ν(3k)}.

The motivation for the study of this function goes back to Newman [Ne69] who noted that examination of the multiples of three, 3, 6, 9, 12, 15, 18, 21, 24, 27, …, written in the base two,

11, 110, 1001, 1100, 1111, 10010, 10101, 11000, 11011, …,

shows a definite preponderance of those containing an even number of one–digits over those containing an odd number. Newman proved that this strange behaviour persists forever. Coquet [Co83] gave an exact formula by Delange type computations. Our method uses this result and allows us to compute the Fourier coefficients (especially the mean value) of the related fractal function.

Theorem 7. The summatory function S_{3} satisfies the exact formula

S_{3}(n) = n^{α}ψ(log_{4} n) + \frac{η(n)}{3},

where ψ is a continuous nowhere differentiable function of period 1, η is given by

η(n) = \{ \begin{matrix}0 & if n is even \\ (−1)^{ν(3n−1)} & if n is odd \end{matrix}

and α = \frac{log 3}{log 4}. The Fourier expansion ψ(u) = ∑_{k∈ℤ} ψ_{k}e^{2kπiu} is given by

ψ_{k} = \frac{3^{α_{k}}(−1)^{k}}{α_{k}6\sqrt{3} log 2}(3 + (−1)^{k}\sqrt{3} − (1 + (−1)^{k}\sqrt{3}) f_{0}(α_{k})+
+ (2 + (−1)^{k}\sqrt{3}) f_{1}(α_{k}) − f_{2}(α_{k})),

where α_{k} = α + \frac{kπi}{log 2} and

f_{0}(s) = \frac{1}{3Γ(s)} ∫_{0}^{∞}(F (e^{−t}) + F (ζe^{−t}) + F (ζ^{2}e^{−t}) − 3) (1 − e^{− \frac{t}{2}} ) t^{s−1}dt

f_{1}(s) = \frac{1}{3Γ(s)} ∫_{0}^{∞}(F (e^{−t}) + ζ^{2}F (ζe^{−t}) + ζF (ζ^{2}e^{−t})) (1 − e^{− \frac{t}{2}} ) t^{s−1}dt

f_{2}(s) = \frac{1}{3Γ(s)} ∫_{0}^{∞}(F (e^{−t}) + ζF (ζe^{−t}) + ζ^{2}F (ζ^{2}e^{−t})) (1 − e^{− \frac{t}{2}} ) t^{s−1}dt

with ζ = e^{\frac{2πi}{3}} and

(7.2)  F (z) = ∏_{k=0}^{∞} (1 − z^{2^{k}}) .

In particular, a rough estimate of the mean value ψ_{0} is

ψ_{0} ≈ 1.40922 03477 84529 82145 02895 25994.

Observe that the extreme values of ψ(u) are already known from Coquet’s work [Co84]:

1.15470 ≤ ψ(u) ≤ 1.60196 .

Sketch of the proof. The proof runs along the same lines as the proof of Theorem 5; the only difference is that the computation of the Dirichlet generating function is slightly more involved than in Section 6. We first prove an asymptotic formula for the double summatory function

T (N) = ∑_{1≤n<N} (S_{3}(n) − 1) .

For this purpose we need some information on the function

ξ_{0}(s) = ∑_{n=1}^{∞} \frac{(−1)^{ν(3n)}}{(3n)^{s}} .

Using the function F given by (7.2) that satisfies F (z) = (1 − z)F (z^{2}), and setting

Ξ_{0}(z) = \frac{1}{3} (F (z) + F (ζz) + F (ζ^{2}z))

Ξ_{1}(z) = \frac{1}{3} (F (z) + ζ^{2}F (ζz) + ζF (ζ^{2}z))

Ξ_{2}(s) = \frac{1}{3} (F (z) + ζF (ζz) + ζ^{2}F (ζ^{2}z))

we obtain the functional equations

(7.3)

Ξ_{0}(z) = Ξ_{0}(z^{2}) − zΞ_{1}(z^{2})
Ξ_{1}(z) = Ξ_{2}(z^{2}) − zΞ_{0}(z^{2})
Ξ_{2}(z) = Ξ_{1}(z^{2}) − zΞ_{2}(z^{2}).

Consider now the companion Dirichlet series ξ_{k}, for k = 1, 2, defined in a way similar to ξ_{0}, where summation runs through the other residue classes mod 3,

ξ_{k}(s) = ∑_{n=0}^{∞} \frac{(−1)^{ν(3n+k)}}{(3n + k)^{s}} for k = 1, 2.

By Mellin transforms again, Eq. (2.2), we derive the alternative expressions,

(7.4)  \begin{matrix}ξ_{0}(s) = \frac{1}{Γ(s)} ∫_{0}^{∞}(Ξ_{0} (e^{−t}) − 1) t^{s−1}dt \\ ξ_{k}(s) = \frac{1}{Γ(s)} ∫_{0}^{∞}Ξ_{k} (e^{−t}) t^{s−1}dt for k = 1, 2. \end{matrix}

The image of the collection of functional equations (7.3) is then the system of equations

(7.5)  \begin{aligned}(1 − 2^{−s}) & ξ_{0}(s) & + & 2^{−s} & ξ_{1}(s) & & & & = & 2^{−s}f_{1}(s) \\ 2^{−s} & ξ_{0}(s) & + & & ξ_{1}(s) & − & 2^{−s} & ξ_{2}(s) & = & 2^{−s}f_{0}(s) & −1 \\ & & − & 2^{−s} & ξ_{1}(s) & + & (1 + 2^{−s}) & ξ_{2}(s) & = & 2^{−s}f_{2}(s), \end{aligned}

where the functions f_{k} are given by

f_{0}(s) = ∑_{n=1}^{∞}(−1)^{ν(3n)} (\frac{1}{(3n)^{s}} − \frac{1}{(3n + \frac{1}{2})^{s}} )

f_{k}(s) = ∑_{n=0}^{∞}(−1)^{ν(3n+k)} (\frac{1}{(3n + k)^{s}} − \frac{1}{(3n + k + \frac{1}{2})^{s}} ) for k = 1, 2.

These functions are defined for ℜ(s) > 0 and satisfy |f_{k}(σ + it)| ≪ |t|^{1−σ} for 0 < σ < 1, which can be shown using the same arguments as in Section 6.

Solving (7.5) yields

(7.6)  ξ_{0}(s) = \frac{1}{2^{s}(4^{s} − 3)} (4^{s} + 2^{s} − (2^{s} + 1) f_{0}(s) + (4^{s} + 2^{s} − 1) f_{1}(s) − f_{2}(s)) .

This equation provides us with the analytic continuation of ξ_{0} and shows that all poles of this function have to satisfy the equation 4^{s} = 3.

After these preparations we can write using (2.4)

(7.7)  T (N) = \frac{N}{2πi} ∫_{2−i∞}^{2+i∞}3^{s}ξ_{0}(s)N^{s} \frac{ds}{s(s + 1)}.

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

(7.8)  T (N) = N^{α+1} ∑_{k∈ℤ} \frac{ψ_{k}}{α_{k} + 1}e^{2kπi log_{4} N} + O(N^{1+ε}),

where the term O(N^{1+ε}) is obtained by trivial estimation of the integral from ε − i∞ to ε + i∞ over the same integrand as in (7.7).

Now using the exact formula due to Coquet and the adapted version of Proposition 2 yields the Fourier expansion of the function ψ. □

Remark 5. The method employed above can also be used to gather information on the summatory functions

∑_{k<n}(−1)^{ν(3k+1)}, ∑_{k<n}(−1)^{ν(5k)}

and other functions of this type.

Remark 6. The numerical estimates of the mean value constants throughout this paper were derived from infinite functional equations satisfied by the corresponding Dirichlet series. Such functional equations relate a Dirichlet series ω(s) to its values ω(s+1), ω(s+2), etc. Since ω(s + m) is easily evaluated numerically for a large enough integer m (the series then reduces essentially to its first few terms), the functional equation can then be used to compute backwards the values of ω(s + m − 1), ω(s + m − 2), etc, till ω(s). Related infinite functional equations are given in [AC85].

The principles of such infinite functional equations are well known in the case of the Riemann zeta functions (see pp. 273–276 of [La74]). Take for instance the problem of evaluating A(s) and B(s) defined in Section 6:

A(s) = ∑_{k=1}^{∞} \frac{2^{ν(k)}}{k^{s}}  and  B(s) = ∑_{k=1}^{∞} 2^{ν(k)} (\frac{1}{(2k)^{s}} − \frac{1}{(2k + 1)^{s}} ) .

First A(s) is related to B(s) by separating odd and even terms then using the recurrence equations satisfied by the coefficients, which leads to the equation obtained earlier, immediately before (6.6):

A(s) = \frac{3}{2^{s}} A(s) + 2 − 2B(s).

Now, B(s) can be rewritten as

B(s) = ∑_{k=1}^{∞} \frac{2^{ν(k)}}{(2k)^{s}} [1 − \frac{1}{(1 + (2k)^{−1})^{s}} ] .

Using the binomial expansion of (1 + (2k)^{−1})^{−s}, and regrouping terms, we get

B(s) = \frac{1}{2^{s}} [\binom{s}{1}\frac{A(s + 1)}{2^{1}} − \binom{s}{2}\frac{A(s + 2)}{2^{2}} + \binom{s}{3}\frac{A(s + 3)}{2^{3}} − ⋯] .

This is an infinite functional equation for A(s) since B(s) is itself linearly related to A(s).

In this way, all our constants can be evaluated to about 50 digits of accuracy in just a few billion elementary operations—a matter of minutes—using computer algebra systems. (Our computations were completed under the Maple system.)

8. Conclusion

Arithmetic sequences related to binary representation systems have often been studied by means of real variable methods. We have shown here that the classical methods of analytic number theory can be used instead in a variety of cases. The results obtained in this way are a priori asymptotic. They can be converted into exact formulæ either when the associated Dirichlet series are of a simple enough form (sums of digits, block occurrences) or when they can be combined with direct elementary methods (odd binomial coefficients, triadic numbers). Fluctuations are then obtained directly as Fourier series.

The analysis of divide–and–conquer recurrences by related techniques is pursued in a companion paper [FG92], which further exemplifies the usefulness of complex analytic methods in this range of problems.

References

[Al87] J.-P. Allouche, Automates finis en théorie des nombres, Expos. Math. 5 (1987), 239–266.

[AC85] J.-P. Allouche and H. Cohen, Dirichlet Series and Curious Infinite Products, Bull. London Math. Soc. 17 (1985), 531–538.

[AS92] J.-P. Allouche and J. Shallit, The Ring of k–regular Sequences, Theoretical Computer Science 98 (1992), 163–197.

[Ap84] T.M. Apostol, Introduction to Analytic Number Theory, Springer Verlag, Berlin-Heidelberg-New York, 1984.

[BEM83] J. Brillhart, P. Erdős and P. Morton, On Sums of Rudin-Shapiro coefficients II, Pacific J. Math. 107 (1983), 39–69.

[BM78] J. Brillhart and P. Morton, Über Summen von Rudin-Shapiroschen Koeffizienten, Illinois J. Math. 22 (1978), 126–148.

[Ca92] E. Cateland, Suites digitales et suites k–régulières, Thèse, Université de Bordeaux I, 1992.

[Co83] J. Coquet, A Summation Formula Related to the Binary Digits, Invent. Math. 73 (1983), 107– 115.

[De75] H. Delange, Sur la fonction sommatoire de la fonction “Somme des Chiffres”, Enseignement Math.(2) 21 (1975), 31–47.

[Do50] G. Doetsch, Handbuch der Laplace Transformation, Birkhäuser Verlag, Basel, 1950.

[DT89] J.-M. Dumont and A. Thomas, Systèmes de numération et fonctions fractales relatifs aux substitutions, Theoretical Computer Science 65 (1989), 153–169.

[Fa85] K.J. Falconer, The Geometry of Fractal Sets, Cambridge University Press, 1985.

[FG92] P. Flajolet and M. Golin, Mellin Transforms and Asymptotics: The Mergesort Recurrence, INRIA Research Report 1612 (1992).

[FR80] P. Flajolet and L. Ramshaw, A Note on Gray Code and Odd-Even Merge, SIAM J. Comput. 9 (1980), 142–158.

[FRV79] P. Flajolet, J.C. Raoult and J. Vuillemin, The Number of Registers Required for Evaluating Arithmetic Expressions, Theoretical Computer Science 9 (1979), 99–125.

[FRS84] P. Flajolet, M. Regnier and R. Sedgewick, Some Uses of the Mellin Integral Transform in the Analysis of Algorithms, Combinatorial Algorithms on Words (A. Apostolico and Z. Galil, eds.), Springer Verlag, Berlin-Heidelberg, 1985.

[GT91] P.J. Grabner and R.F. Tichy, α-Expansions, Linear Recurrences and the Sum-of-Digits Function, Manuscripta Math. 70 (1991), 311–324.

[GKP89] R.L. Graham, D.E. Knuth and O. Patashnik, Concrete Mathematics, Addison Wesley, 1989.

[Ha77] H. Harborth, Number of Odd Binomial Coefficients, Proc. Amer. Math. Soc. 62 (1977), 19–22.

[Ki83] P. Kirschenhofer, Subblock Occurrences in the q-ary Representation of n, SIAM J. Alg. Discr. Meth. 4 (1983), 231–236.

[KP84] P. Kirschenhofer and H. Prodinger, Subblock Occurrences in Positional Number Systems and Gray Code Representation, J. Inf. Opt. Sci. 5 (1984), 29–42.

[KPT85] P. Kirschenhofer, H. Prodinger and R.F. Tichy, Über die Ziffernsumme natürlicher Zahlen und verwandte Probleme, Zahlentheoretische Analysis, Lecture Notes 1114 (E. Hlawka, ed.), pp. 55– 65.

[Ko88] T. W. Kőrner, Fourier Analysis, Cambridge University Press, Cambridge, 1988.

[La74] E. Landau, Handbuch der Lehre von der Verteilung der Primzahlen, Chelsea Publishing Company, 1974.

[Ne69] D.J. Newman, On the Number of Binary Digits in a Multiple of Three, Proc. Amer. Math. Soc. 21 (1969), 719–721.

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

[Sch69] W. Schwarz, Einführung in Methoden und Ergebnisse der Primzahltheorie, Bibliographisches Institut, Mannheim, 1969.

[Ste89] A.H. Stein, Exponential Sums of Digit Counting Functions, Théorie des nombres, Comptes Rendus de la Conférence Internationale de Théorie des Nombres tenue à l’Université Laval en 1987 (J.M. De Koninck et C. Levesque, eds.), de Gruyter, Berlin-New York, 1989.

[Sto77] K.B. Stolarsky, Power and Exponential Sums of Digital Sums Related to Binomial Coefficient Parity, SIAM J. Appl. Math. 32 (1977), 717–730.

[WW27] E.T. Whittaker and G.N. Watson, A Course in Modern Analysis, Cambridge University Press, 1927.

[Wo84] S. Wolfram, Geometry of binomial coefficients, Amer. Math. Monthly 91 (1984), 566–571.

[Wo89] R. Wong, Asymptotic Approximations of Integrals, Academic Press, San Diego, 1989.

P. Flajolet, INRIA, Rocquencourt, 78150 Le Chesnay, France

P. Kirschenhofer and H. Prodinger, Institut für Algebra und Diskrete Mathematik, TU Wien, Wiedner Hauptstrasse 8–10, 1040 Wien, Austria

P. Grabner and R. Tichy, Institut für Mathematik, TU Graz, Steyrergasse 30, 8010 Graz, Austria