\input amstex

\documentstyle{amsppt}





\magnification=1200



% look up \baselineskip after \document command.



% For manuscript submission

%\baselineskip=18pt

%\hsize=12 true cm

%\hoffset=1.5 true cm

%\hfuzz=400pt

%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% \input graphic

% This is `graphic.tex' as of February 10, 1989 by Lutz Birkhahn

%

% Simply say `\input graphic' at the beginning of your file, and you may

% include graphics with `\includegraphic{<filename>}', where filename is

% the name of your IMG graphics file (<filename>.img) resp. the companion

% \TeX\ file (<filename>.tex).

%

% If you don't use IMGtoTEX, you have to write the \TeX\ file by yourself.

% The only two things you have to specify are the width and the height of

% the graphic: type `\grwd=<width>' and `\grht=<height>', where <width>

% and <height> are `dimen' values.

%

\newdimen\grwd \newdimen\grht

%

\def\includegraphic #1{%

 \input #1 % the companion \TeX\ file

 \setgraphic{#1}{\the\grwd}{\the\grht}%

 }

%

\def\setgraphic #1#2#3{%

% \hbox to #2{\vbox to #3{\vfil{... GRAPHICS #1 ...}}\hfil}%

 \hbox to #2{\vbox to #3{\vfil{\ }}\hfil}%

 }

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\refstyle{A}

\widestnumber\key{BEM83}





\define\({\left(}

\define\){\right)}

\define\ups{\upsilon}

\define\eps{\varepsilon}

\define\lf{\lfloor}

\define\rf{\rfloor}



\topmatter



\title 

Mellin Transforms and Asymptotics: 

Digital Sums

\endtitle



\author Philippe Flajolet$^{1,2}$, Peter Grabner$^3$,

Peter~Kirschenhofer$^1$, Helmut Prodinger$^1$, 

and Robert F. Tichy$^{1,3}$

\endauthor



\thanks $^1$ Research of these authors was supported

by the French-Austrian scientific cooperation programme.\endgraf

$^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).\endgraf

$^3$ Research of these authors was supported by the Austrian science

foundation (Project Nr. P8274PHY).

\endthanks





\leftheadtext{P. Flajolet et al.}

\address P. Flajolet, INRIA, Rocquencourt, 78150 Le Chesnay, France\endaddress

\address P. Kirschenhofer and H. Prodinger, Institut f\"ur Algebra und Diskrete

Mathematik, TU Wien, Wiedner Hauptstrasse 8--10, 1040 Wien, Austria\endaddress

\address P. Grabner and R. Tichy, Institut f\"ur Mathematik, TU Graz, Steyrergasse 30, 8010 Graz, Austria\endaddress





\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 % $1,2,\ldots,n-1$ 

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{\ae}. 

This approach yields naturally 

the Fourier series involved in

the expansions of a variety of digital sums related to number representation

systems.

\endabstract



\endtopmatter







% \abstract Digital expansions are a classical field of research in number theory

% and recently they made an appearance in various areas of theoretical computer science.

% An important result in this area is the explicit description of the sum-of-digits

% function by means of a fractal function. Using an elementary method, H.~Delange

% computed the Fourier coefficients of this function. We present a general

% analytical approach for proving such results based on Mellin-Perron summation

% formul\ae.\endabstract

% \endtopmatter



\document



%\baselineskip=18pt



%\bigskip

%\rightline{July 25, 1991. Revised, June 6, 1992}

%\rightline{Final version to appear in \it Theoretical Computer Science.}

%\bigskip\bigskip

%

\heading 1. Introduction\endheading

Let $S(n)$ represent the total number of $1$-digits in the binary representations

of the integers $1,2,\ldots,n-1$. It is not hard to see that

$$S(n)=\frac 12n\log_2n+o(n\log n),\tag 1.1$$

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~\cite{De75}

$$S(n)=\frac 12n\log_2n+nF_0(\log_2n),\tag 1.2$$

where $F_0(u)$, a {\sl 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\not=0$, being

$$f_k=-\frac1{\log2}\frac{\zeta(\chi_k)}{\chi_k(\chi_k+1)}\quad\text{for }

\chi_k=\frac{2\pi ik}{\log2}.$$





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 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\pi i}

\int\limits_{2-i\infty}^{2+i\infty}

\frac{\zeta(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\pi ik/\log2$.



In other words, as is customary from standard

analytic number theory ({\it 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{\ae} are reviewed briefly

in Section~2. In general,

they provide {\sl asymptotic\/} rather

than {\sl exact\/} summation formul{\ae}.

An additional argument is then needed in order to establish

an exact representation like~(1.1). 

Similar exact formul{\ae} 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),

% In Section 5 we consider the number

% theoretic function $h(n)$ given by

$$h\(\sum_i2^{e_i}\)=\sum_i3^{e_i},$$

where the exponents $e_i$ are strictly increasing. 

% An exact formula for the

% summatory function $H$ of $h$ is established.



Sections~6 and 7 deal primarily with asymptotic

summation formul{\ae}.

Section 6 is concerned with the asymptotic evaluation of

the function

$$\Phi(n)=\sum_{k=0}^{n-1}2^{\nu(k)},   \tag1.3$$

where $\nu(k)$ denotes the binary sum-of-digits function. 

The value $\Phi(n)$ is also equal to the number

of odd binomial coefficients in the first $n$ rows of Pascal's triangle.

Stolar\-sky \cite{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 \cite{Ha77} and in the $q$-ary case

by Stein \cite{Ste89}.) It is found that

$\frac{\Phi(N)}{N^\rho}$ is a periodic function of $\log_2N$,

with $\rho=\log_2 3$, see Figure~1 for a graphical rendering.

Section 7

is concerned with the asymptotic evaluation of

$$S_3(n)=\sum_{k=0}^{n-1}(-1)^{\nu(3k)},$$

a function obviously related to the distribution

of $1$--digits in the multiples of three

which was first studied by Newman~\cite{Ne69}.

J. Coquet \cite{Co83} established a Delange type theorem in this case.



%\topinsert

%

%\vskip 0.3 truecm

%\centerline{\includegraphic{fraktal}}

%\special{psfile=powerbino.ps hscale=45 vscale=45 hoffset=36}

%\vskip 0.1 truecm

%

%

%\noindent

{\bf Figure~1.} The representation of $\frac{\Phi(n)}{n^\rho}$ plotted

against $n$ in a logarithmic scale; $\Phi(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); $\rho=\log_2 3$.



\vskip 2cm

\medskip\noindent\hrule\medskip

%\endinsert





The asymptotic formul{\ae} obtained in connection

with $\Phi(n)$ and $S_3(n)$

when  matched against

exact formul{\ae} obtained by direct combinatorial

reasoning, lead to new Fourier expansions.

This mixed combinatorial--analytic process

constitutes another  source for % exact 

summatory formul{\ae} with explicit Fourier coefficients

developed in Sections~6 and~7.







\medskip



Exact summation formul{\ae} 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 {\sl number theory\/}, 

we refer to Stolarsky's survey

\cite{Sto77} and to \cite{KPT85}. 

An especially important paper by the spectrum of its analysis techniques

is Brillhart, Erd\H os and Morton's work \cite{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$.







% Our starting point here has been the connections

% between number representation systems and analysis. 

% In another direction, t

The summatory formul{\ae} considered here are

closely related to 

number--theoretic functions arising in

the context of iterated substitutions

and so--called {\sl automatic sequences\/}  (see Allouche's paper for a

survey \cite{Al87}), which 

constitute a natural framework in which several of our

analyses could have been cast. 

In that framework Dumont and Thomas \cite{DT89}

have used elementary methods to derive

for linear functionals of iterated substitution sequences

 a whole class of asymptotic

forms of the type

$$ n^\beta (\log_\theta n)^\gamma F(\log n) 

+o(n^\beta (\log_\theta n)^\gamma),$$

involving some fluctuating function $F$. % Closer to our objectives,

Allouche and

Cohen  have shown that  Dirichlet generating functions 

associated to automatic sequences have

meromorphic continuations (see \cite{Al87, p.261} and \cite{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 {\sl regular sequences\/},

a generalization of automatic sequences, that was

introduced by Allouche and Shallit in~\cite{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~\cite{Ca92}  who established precisely 

non--differentiability properties for several of our 

periodic functions (like the ones for Gray code or block occurrences).





%\topinsert

%\vskip 0.3 truecm

%\centerline{\includegraphic{pascal}}

%\special{psfile=pasc.ps hscale=60 vscale=60 hoffset=72}

%\vskip 0.4 truecm

%

%\noindent

%

{\bf Figure~2.} Pascal's triangle modulo 2.

The odd numbers are

represented by black squares, the even numbers by white squares.

\vskip 2cm

\medskip\noindent\hrule\medskip



%\endinsert





In the area of the {\sl 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~\cite{FRV79}.

It was later extended to some non-standard digital representations of integers, like

Gray code \cite{FR80}, for the purpose of analyzing sorting networks, as well

as to occurrences of blocks of digits in standard $q$-ary 

representations~\cite{Ki83} and subblock occurrences 

in Gray code representation \cite{KP84}

or to Newman sequence related to the binary representations of

multiples of three~\cite{Co83}.

% the subsequence $u(3n)$ of the classical Thue--Morse sequence $u(n)$.

% classical Rudin-Shapiro sequence~\cite{Co83}. 

(In a recent paper \cite{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 {\sl  divide-and-conquer recurrences\/}

that are common in theoretical computer science and

of which a typical form is

$$f_n=f_{\lfloor n/2\rfloor}+f_{\lceil n/2\rceil}+e_n,$$

with $\{e_n\}$ a usually simple sequence and $\{f_n\}$ the 

sequence to be analyzed. In a recent work, Flajolet

and Golin~\cite{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.



\medskip



{\sl Graphics.}

As an   illustration of the fractal phenomena at stake,

we have displayed in Figure~1 the ratio $\frac{\Phi(N)}{N^\rho}$

plotted against $N$ in a logarithmic scale.

When considering successive intervals $[2^{k-1},2^k]$,

we see the function

$\frac{\Phi(N)}{N^\rho}$ 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~\cite{Fa85},

a popular source for similar graphics being \cite{Wo84}.)









\heading 2. Mellin-Perron formul\ae\endheading



For completeness, we give a brief outline of the Perron

formula by relating it to the Mellin transform. 

The resulting summation formul{\ae} 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 \cite{Do50}.

Mellin summation is briefly surveyed in~\cite{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 \cite{Wo89, Chap.~III}.

The classical Perron formula is discussed at length in Apostol's

book~\cite{Ap84}, and a higher order version is for instance

given by Schwarz

(see Chapter~IV of~\cite{Sch69}).



\medskip



Let $f(x)$ be a function defined over $[0,+\infty)$. Its Mellin transform

$f^*(s)=\Cal M[f(x);s]$ is defined by

$$f^*(s)=\int_0^\infty f(x)x^{s-1}dx.\tag 2.1$$

By linearity and the rescaling property we have 

% under natural analytic conditions:

$$F(x)=\sum_k\lambda_kf(\mu_kx)

~~\Longrightarrow~~ F^*(s)=\(\sum_k\lambda_k\mu_k^{-s}\)f^*(s).\tag 2.2$$

The condition is for $s$ to belong to a

`fundamental strip' defined by the property that

the integral giving $f^*(s)$ and the

sum $\sum_k\lambda_k\mu_k^{-s}$ are both absolutely convergent.



Similar to the Laplace transform there is an inversion theorem 

({\sl cf}.~\cite{Do50}).

When applied to \thetag{2.2}, it provides

$$\sum_k\lambda_kf(\mu_kx)=\frac 1{2\pi i}\int\limits_{c-i\infty}^{c+i\infty}\(\sum_k\lambda_k\mu_k^{-s}\)f^*(s)x^{-s}ds,\tag 2.3$$

with $c$ in the fundamental strip.





Formula \thetag{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. %(cf.\cite{Sch69}). 

Introduce the step function $H_0(x)$

defined by

$$H_0(x)=\cases 1&\text{if $x\in[0,1]$}\\0&\text{if $x>1$,}\endcases$$

together with the functions $H_m(x)=(1-x)^mH_0(x)$. In the interesting case

where $\mu_k\equiv k$, we obtain from \thetag{2.3} formul\ae{} of the Perron type

that provide integral representations for the iterated summations of arithmetic

functions in terms of their Dirichlet generating function.



\proclaim{Theorem 0} Let $c>0$  lie  in the 

half--plane of absolute convergence of $\sum_{k} {\lambda_k}k^{-s}$.

Then for any $m\ge1$, we have

$$\frac 1{m!}\sum_{1\leq k<n}\lambda_k\(1-\frac kn\)^m=\frac 1{2\pi i}

\int\limits_{c-i\infty}^{c+i\infty}

\(\sum_{k\geq1}\frac{\lambda_k}{k^s}\)n^s\frac{ds}{s(s+1)\cdots(s+m)}.

\tag2.4$$

% for $m\geq 1$; for $m=0$ the formula has to be modified slightly.

For $m=0$, 

$$

\sum_{1\leq k<n}\lambda_k +{\lambda_n\over2} =

\frac 1{2\pi i}

\int\limits_{c-i\infty}^{c+i\infty}

\(\sum_{k\geq1}\frac{\lambda_k}{k^s}\)n^s \, \frac{ds}{s}.

$$

\endproclaim



Formula \thetag{2.4} is obtained from \thetag{2.3} by setting 

$x \equiv n^{-1}$, $f(x)\equiv H_m(x)$,

and observing that $H^*_m(s)=m!(s(s+1)\cdots(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~\cite{Ap84, p.245} for

a direct proof of the $m=0$ case.



%The real $c$ must be

%taken in the half plane of convergence of $\lambda(s)=\sum_k\lambda_kk^{-s}$.



For instance, if we use $\lambda_k\equiv1$ and $m=1$, we get

$$\frac{n-1}2=\frac 1{2\pi i}\int\limits_{2-i\infty}^{2+i\infty}\zeta(s)n^s\frac{ds}{s(s+1)}.\tag2.5$$

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

we obtain

$$0=\int\limits_{-\frac14-i\infty}^{-\frac14+i\infty}\zeta(s)n^s\frac{ds}{s(s+1)}.\tag2.6$$

Identity \thetag{2.6} is the basis for the existence of 

several {\sl exact} rather

than plainly {\sl asymptotic} summation formul\ae.



\heading 3. Sum-of-Digits Functions\endheading



% As announced in the introduction 

We apply the Mellin--Perron technique described in the

preceding section in order to derive a new proof of Delange's theorem.



\proclaim{Theorem 1}{\rm[Delange]}

The sum-of-digits function $S(n)$ satisfies

$$S(n)=\frac 12n\log_2n+nF_0(\log_2n),$$

where $F_0(u)$ is representable by the Fourier series

$F_0(u)=\sum_{k\in\Bbb Z}f_ke^{2\pi iku}$

and

$$\align &f_0=\frac{\log_2\pi}2-\frac 1{2\log 2}-\frac34\cr

&f_k=-\frac1{\log2}\frac{\zeta(\chi_k)}{\chi_k(\chi_k+1)}\quad\text{for }\chi_k=\frac{2\pi ik}{\log2},\quad k\not=0.\endalign$$

\endproclaim

\demo{Proof} Let $\ups_2(k)$ be the exponent of $2$ in the prime decomposition

of $k$ and $\nu(k)$ be the number of $1$-digits in the binary representation

of $k$. We have $\nu(k)-\nu(k-1)=1-\ups_2(k)$, so that $S(n)$ resembles a double

summation of $\ups_2(k)$. Furthermore it is well-known that

$$\sum_{k\geq1}\frac{\ups_2(k)}{k^s}=\frac{\zeta(s)}{2^s-1}.\tag3.1$$

Thus, from \thetag{2.4}, with $\lambda_k=\ups_2(k)$ and $m=1$, we get

the basic integral representation

$$S(n)=\frac{n(n-1)}2-\frac n{2\pi i}\int\limits_{2-i\infty}^{2+i\infty}\frac{\zeta(s)}{2^s-1}n^s\frac{ds}{s(s+1)}.\tag3.2$$

The integrand in \thetag{3.2} has a simple pole at $s=1$, a double pole

at $s=0$ and simple poles at $s=\chi_k$. Shifting the line of integration%

\footnote{Technically, we  integrate along a rectangle with upper

and lower sides passing through $\pm (2N+1)i\pi/\log2$, and let

$N\to\infty$. 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.

}

to $\Re(s)=-\frac14$ and taking residues into account we get

$$S(n)=\frac12 n\log_2n+nF_0(\log_2n)-nR(n),\tag3.3$$

where the Fourier series akin to $F_0$

$${1\over\log2}\sum_{\in\Bbb Z}

{\zeta(\chi_k)\over\chi_k(\chi_k+1)}n^{\chi_k}$$

occurs as the sum of residues of the integrand at the imaginary poles

$s=\chi_k$.

The remainder term is

$$R(n)=\frac1{2\pi i}\int\limits_{-\frac14-i\infty}^{-\frac14+i\infty}\frac{\zeta(s)}{2^s-1}n^s\frac{ds}{s(s+1)},\tag3.4$$

so that there only remains to prove that $R(n)\equiv 0$ when $n$ is an

integer. The integral converges since $|\zeta(-\frac14+it)|\ll|t|^{\frac34}$

(cf. \cite{WW27}).



Using the expansion

$$\frac1{2^s-1}=-1-2^s-2^{2s}-2^{3s}-\cdots$$

in \thetag{3.4} which is legitimate since now $\Re(s)<0$, we find that $R(n)$

is a sum of terms of the form

$$\frac 1{2\pi i}\int\limits_{-\frac14-i\infty}^{-\frac14+i\infty}\zeta(s)(2^kn)^s\frac{ds}{s(s+1)},$$

and each of these terms is $0$ by virtue of \thetag{2.6}.

\qed\enddemo

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,\ldots;$$

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, {\it e.g.}, \cite{FR80}).

Let $\gamma(k)$ be the number of $1$-digits in the Gray code representation 

of $k$, and $\delta_k=\gamma(k)-\gamma(k-1)$. It is easy to see that

$\delta_{2k}=\delta_k$, and the pattern for odd values is 

$\delta_{2k+1}=(-1)^k$. Thus the Dirichlet generating function

$\delta(s)$ of $\{\delta_k\}$ is 

$$\delta(s)=\frac{2^sL(s)}{2^s-1}\quad\text{with }L(s)=\sum_{k=0}^\infty \frac{(-1)^k}{(2k+1)^s}.$$

Thus by \thetag{2.4}, the summatory function $G(n)=\sum_{k<n}\gamma(k)$

admits the integral representation

$$G(n)=\frac n{2\pi i}\int\limits_{2-i\infty}^{2+i\infty}\frac{2^sL(s)}{2^s-1}n^s\frac{ds}{s(s+1)}.\tag3.5$$

\proclaim{Theorem 2}{\rm[Flajolet, Ramshaw]}

The summatory function $G(n)$ of

sum-of-digits function of Gray-code satisfies

$$G(n)=\frac12n\log_2n+nF_1(\log_2n),$$

where $F_1(u)$ is representable by the Fourier series

$$F_1(u)=2\log_2\Gamma(\frac14)-\frac32-\log_2\pi+\frac1{\log2}\sum_{k\in\Bbb Z\setminus\{0\}}\frac{L(\chi_k)}{\chi_k(\chi_k+1)}e^{2k\pi iu}.$$

\endproclaim



\demo{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.~\qed

\enddemo



{\bf Remark 1.} % Note that 

The functions $F_0$ and $F_1$ are continuous

but nowhere differentiable.









\heading

4. Subblock occurrences and the Gray Code

\endheading



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 % an elegant proof of 

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 \cite{Ki83}, but only an estimate of the remainder term was given.

The remainder term has been also investigated independently by

Cateland~\cite{Ca92} using elementary methods of the Delange type.



\proclaim{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\footnote{A formula for this

case exists, but is unpleasant to formulate}.)

Then the mean number of occurrences, $\frac 1n \sum\limits_{k<n}(k;w)$, is given by

$$\frac 1n \sum_{k<n}(k;w)=

\frac{\log_2n}{2^{|w|}}+H_w\left(\log_2n\right)+\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)=\sum_{k\in\Bbb Z}h_ke^{2k\pi iu}$,

$$\align h_0&=\log_2\(\frac{\Gamma((0.w)_2)}{\Gamma((0.w)_2+2^{-|w|})}\)

-\frac{1}{2^{|w|}}\left(|w|-\frac 12+\frac{1}{\log 2}\right)\\

h_k&=\frac{\zeta(\chi_k,(0.w)_2)-\zeta(\chi_k,(0.w)_2+2^{-|w|})}

{(\log 2)\chi_k(\chi_k+1)},\endalign$$

$\zeta(z,a)$ the Hurwitz $\zeta$-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 \thetag{4.9}.

\endproclaim

\demo{Proof}

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

$$\sum_{k<n}(k;w)=\sum_{k<n}\Delta_w(k)(n-k), \tag 4.1$$

where

$\Delta_w(k)=(k;w)-(k-1;w)$.

The differences $\Delta_w(k)$ obey the following recurrence relation:

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

$$\Delta_w(n)=\Delta_w\left(\frac n2\right)+\cases 1&\text{if $(w)_2=r$}\\

-1&\text{if $(w)_2=r-1$}\\0&\text{otherwise}\endcases\tag 4.2$$

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

$$\Delta_w(n)=\cases 1&\text{if $(w)_2=r$}\\-1&\text{if $(w)_2=r-1$}\\

0&\text{otherwise.}\endcases\tag4.3$$

>From the recurrences \thetag{4.2} and \thetag{4.3} it easily follows that the Dirichlet 

series $A_w(s)$ of the differences $\Delta_w(n)$ satisfies

$$\align A_w(s)=\sum_{n\ge 1}\frac{\Delta_w(n)}{n^s}=

\sum_{k\ge 1}\frac{\Delta_w(k)}{(2k)^s}

&+\sum_{k\ge 0}\frac{1}{\left(2^{|w|}k+(w)_2\right)^s}-\\

&-\sum_{k\ge 0}\frac{1}{\left(2^{|w|}k+(w)_2+1\right)^s},\endalign$$

so that 

$$\left(1-\frac{1}{2^s}\right)A_w(s)=\frac{1}{2^{|w|s}}

\left(\zeta(s,(0.w)_2)-\zeta(s,(0.w)_2+2^{-|w|})\right),\tag 4.4$$

where

$$\zeta(s,a)=\sum_{n\ge 0}\frac{1}{(n+a)^s}$$

is the Hurwitz $\zeta$-function \cite{WW27}

and $(0.w)_2$ denotes the rational number $(w)_22^{-|w|}$.



>From \thetag{4.1} and \thetag{4.4} we find using Perron's formula for $m=1$:

$$\align \frac{1}{n}\sum_{k<n}(k;w)=\frac{1}{2\pi i}

\int\limits_{\frac 32-i\infty}^{\frac 32+i\infty}\frac{1}{2^{|w|s}}

&\left(\zeta((s,(0.w)_2)-\zeta(s,(0.w)_2+2^{-|w|})\right)\times\\

&\times\frac{(2n)^sds}{\left(2^s-1\right)s(s+1)}\endalign$$

Shifting the contour of integration to the left, we observe that the 

first order 

poles of the Hurwitz $\zeta$-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

$$C_1\log_2n+\frac{C_2}{\log 2}+C_1\left(\frac 12-|w|-\frac{1}{\log 2}\right),\tag 4.5$$

with

$$C_1=\zeta(0,(0.w)_2)-\zeta(0,(0.w)_2+2^{-|w|})=2^{-|w|},$$ 

since

$\zeta(0,a)=\frac 12-a$ 

and

$$C_2=\zeta'(0,(0.w)_2)-\zeta'(0,(0.w)_2+2^{-|w|})=

\log\dfrac{\Gamma((0.w)_2)}{\Gamma((0.w)_2+2^{-|w|})},$$

since

$\zeta'(0,a)=\log\Gamma(a)-\frac 12\log(2\pi)$ \cite{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

$\chi_k=\frac{2\pi ik}{\log 2}$, $k\ne 0$.



We still have to analyze the remainder term

$$\aligned R_n&=\frac 1{2\pi i}\int\limits_{-\frac 14-i\infty}^{-\frac 14+i\infty}

\frac 1{2^{|w|s}}

\(\zeta(s,(0.w)_2)-\zeta(s,(0.w)_2+2^{-|w|})\)\times\\

&\times\frac{(2n)^sds}{\(2^s-1\)s(s+1)}

=-\sum_{k\ge 0} R'_{2^kn},\endaligned\tag 4.6$$

where

$$R'_n=\frac{1}{2\pi i}\int\limits_{-\frac 14-i\infty}^{-\frac 14+i\infty}

\frac{1}{2^{|w|s}}\left(\zeta(s,(0.w)_2)-\zeta(s,(0.w)_2+2^{-|w|})\right)

\frac{(2n)^sds}{s(s+1)}.$$

After shifting the contour {\sl back\/}

to the right, we find, by taking into account

the residues at $s=0$,

$$R'_n=-\frac{1}{2^{|w|}}+

\sum_{k<2n}\lambda_k\left(1-\frac{k}{2n}\right), \tag 4.7$$

where

$$\lambda_k=\cases 1 &\text{if $k\equiv (w)_2 \!\mod 2^{|w|}$}\\

-1 &\text{if $k\equiv (w)_2 +1\!\mod 2^{|w|}$}\\

0 &\text{otherwise.}\endcases $$

The sum in \thetag{4.7} can be computed explicitly to give

$$R'_n=

\cases \frac{2^{|w|}-1-r}{2^{|w|+1}}\frac 1n

    &\text{if $r=(2n-1\bmod 2^{|w|})\ge (w)_2$}\\

\frac{-1-r}{2^{|w|+1}}\frac 1n 

    &\text{if $r=(2n-1\bmod 2^{|w|})< (w)_2$.}

\endcases\tag 4.8$$

>From \thetag{4.8} we see that $R'_{2^kn}$ will   be zero for

$k\ge|w|-1$, so that in fact \thetag{4.6} reduces to

$$\frac{E_w(n)}{n}=-\sum_{k=0}^{|w|-2}R'_{2^kn},\tag 4.9$$

and this completes the proof.\qed

\enddemo

Theorem 3 and formula \thetag{4.9} have a number of consequences of

interest. In particular, they contain as special cases the results on

binary representations and Gray code.

\proclaim{Corollary 1} 

{\rm [Delange]}

If $|w|=1$ and $w$ is the $1$-digit, {\it i.e.} in the case

of the sum-of-digits function, we have $E_w(n)=0$, as stated already in Theorem 1.

\endproclaim



\proclaim{Corollary 2} If $|w|=2$, the remainder terms $E_w(n)$ are given by the scheme

$$\matrix&\phantom{-}E_{01}(n)&E_{10}(n)&E_{11}(n)\\

\text{$n$ even}&\phantom{-}0&0&0\\

\text{$n$ odd}&-\frac14&\frac14&\frac14\endmatrix$$

\endproclaim



\proclaim{Corollary 3} 

{\rm [Flajolet, Ramshaw]}  

The mean value of the sum of digits in the

% binary reflected 

Gray Code of $n$ is given by

$$\frac{\log_2n}{2}+F_1\left(\log_2n\right),$$

where $F_1=H_{01}+H_{10}$ is as described in Theorem 2.

\endproclaim



\demo{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

$$\align&2\frac{\log_2n}{4}+H_{01}\left(\log_2n\right)+H_{10}\left(\log_2n\right)

+\frac{E_{01}(n)}{n}+\frac{E_{10}(n)}{n}\\

&=\frac{\log_2n}{2}+F_1\left(\log_2n\right),\endalign$$

which also relates $F_1$ to $H_{01}$ and $H_{10}$.~\qed

\enddemo



{\bf 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 % could 

get an alternative proof of a result due to Osbaldestin and Shiu \cite{OS89}

concerning the number of integers $\leq n$ 

that are representable as a sum of three squares.

\heading 5. Triadic Binary Numbers\endheading

Let $h(n)$ be 

% the number theoretic function defined in the introduction; {\it i.e.},

% $h(n)$ is 

the number that results from 

interpreting in base $3$ the binary representation of $n$, {\it i.e.},

$$h\(\sum_i2^{e_i}\)=\sum_i3^{e_i},$$

where the exponents $e_i$ are strictly increasing. 

It is known that $h(1)<h(2)<\ldots<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.









\proclaim{Theorem 4} For the summatory function 

$H(n)=\sum_{k<n}h(k)$ we have

$$H(n)=n^{\rho+1}F_3(\log_2n)-\frac14n,$$

where $\rho=\log_23$ and $F_3(u)$ is the Fourier series

$$F_3(u)=\frac1{3\log2}\sum_{k\in\Bbb Z}\zeta(\rho+\chi_k)\frac{e^{2\pi iku}}{(\rho+\chi_k)(\rho+\chi_k+1)},$$

with $\chi_k=\frac{2\pi i k}{\log2}$.

\endproclaim

\demo{Proof} Using $h(n)-h(n-1)=\frac12(3^{\ups_2(n)}+1)$ we obtain

$$\align&\sum_{n=1}^\infty\frac{h(n)-h(n-1)}{n^s}=\frac12\sum_{n=1}^\infty\frac{3^{\ups_2(n)}}{n^s}+\frac12\zeta(s)\cr

=&\frac12\sum_{k=0}^\infty\frac{3^k}{2^{ks}}\sum_{n=1}^\infty\frac1{(2n-1)^s}+\frac12\zeta(s)\cr

=&\frac{2^s-2}{2^s-3}\zeta(s).\endalign$$

Applying the Mellin-Perron summation formula \thetag{2.4} with $c=3$ and

shifting the line of integration yields

$$\align H(n)&=\frac n{2\pi i}\int\limits_{-\frac14-i\infty}^{-\frac14+i\infty}\frac{2^s-2}{2^s-3}\zeta(s)n^s\frac{ds}{s(s+1)}\cr

&+n^{\rho+1}\sum_{k\in\Bbb Z}\frac1{3\log2}\zeta(\rho+\chi_k)\frac{n^{\chi_k}}{(\rho+\chi_k)(\rho+\chi_k+1)}+\frac12\zeta(0)n.\endalign$$

The remainder integral is $0$ by the same argument 

as for the sum--of--digits function, and the proof is complete.

\qed\enddemo



{\bf Remark 3.} Obviously the base $3$ can be replaced by an arbitrary number

$\alpha>1$ and $\alpha\not=2$. The corresponding exact formula is

$$\sum_{k<n}h_\alpha(k)=n^{\rho+1}F_\alpha(\log_2n)-\frac1{2(\alpha-1)}n,$$

where $F_\alpha$ has a Fourier expansion similar to $F_3$ and $\rho=\log_2\alpha$.



{\bf Remark 4.} The function $g$ defined by $h(n)=n^\rho g(\log_2n)$

is periodic with period $1$ but not continuous.





\heading 6. Odd Numbers in Pascal's Triangle \endheading



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

$$\Phi(n)=\sum_{0\leq k<n}2^{\nu(k)}.$$

As pointed out in the introduction,

$\Phi(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)\cdots(s+m-1))$,

which decreases at infinity like $|s|^{-m}$. Thus,

higher summations lead to better converging (inverse Mellin) integrals.



For the problem of $\Phi(n)$, we thus start with

the  double summatory function

$$\Psi(N)=\sum_{1\leq n<N}(\Phi(n)-1),$$

where Mellin--Perron

 is easier to apply since the Fourier expansion converges absolutely

(We have to subtract $1$, because the summation in \thetag{2.4} starts at

$n=1$.) The formula that we get in this way is {\sl asymptotic}.



\proclaim{Theorem 5} 

The arithmetic function $\Psi(N)$ satisfies the asymptotic

estimate

$$\Psi(N)=N^{\rho+1}G(\log_2N)+O(N^{2+\eps}),\qquad\rho={\log_2 3}$$

for arbitrary $\eps>0$, 

where $G$ is a continuous periodic function with period $1$. $G$ admits an

absolutely convergent Fourier expansion

$$G(u)=\sum_{k\in\Bbb Z}g_ke^{2\pi iku}$$

with

$$g_k=\frac2{\log2}\frac{(1-B(\rho_k))}{\rho_k(\rho_k+1)},$$

where $\rho_k=\rho+\frac{2k\pi i}{\log2}$ and

$$B(s)=\frac1{\Gamma(s)}\int_0^\infty\(\(1-e^{-t}\)

\(\prod_{k=1}^\infty\(1+2e^{-t2^k}\)\)-1\)t^{s-1}dt.\tag 6.1$$

\endproclaim



In order to come back to the Fourier expansion of $F$ we need an external

argument in order to convert the expansion of $\Psi(N)$

into an expansion for $\Phi(n)$. 

One ingredient is a direct combinatorial proof 

of {\sl existence\/} for the fluctuating part of $\Phi(n)$;

this induces corresponding periodicities for $\Psi(N)$,

and by identification, we {\sl indirectly\/} derive the Fourier

expansion relative to $\Phi(n)$. (This 

process is in a way a pseudo--Tauberian argument!)



\proclaim{Theorem 6} The summatory function $\Phi(n)$ satisfies the exact

formula

$$\Phi(n)=n^\rho F(\log_2n),\tag 6.2$$

where $\rho=\log_23$ and $F$ is a continuous function

of period $1$. The Fourier coefficients of $F(u)$ are given by

$$f_k=\frac2{\log2}\frac{(1-B(\rho_k))}{\rho_k},\tag 6.3$$

and in particular the

mean value of $F(u)$ is approximately % $0.8636\ldots$.

$$f_0\approx 0.86360\; 49963\; 99079\; 60496\; 05033\; 61308\;09499.$$

$F(u)$ is represented by its Fourier series in the sense

of standard $(\hbox{\bf C},1)$ Ces\`aro averages.

\endproclaim



% {\bf Remark 5.} 

Observe that from \cite{Ha77} it is already known that

$$0.812\leq F(u)\leq1.$$





% We use Mellin of course, but start with the double summatory function

% $$\Psi(N)=\sum_{1\leq n<N}(\Phi(n)-1),$$

% where it is easier to apply since the Fourier expansion converges absolutely

% (We have to subtract $1$, because the summation in \thetag{2.4} starts at

% $n=1$.).

% In order to come back to the Fourier expansion of $F$ we later need some sort

% of Tauberian argument. First we establish



\demo{Proof} (Theorem 5)

Let

$$A(s)=\sum_{n=1}^\infty\frac{2^{\nu(n)}}{n^s}\tag 6.4$$

be the Dirichlet generating function of $2^{\nu(n)}$. Since $\Psi(N)$ is a

double summation of $2^{\nu(k)}$ we have an integral representation by means

of the iterated Mellin-Perron formula \thetag{2.4}. We get

$$\Psi(N)=\frac N{2\pi i}\int\limits_{3-i\infty}^{3+i\infty}A(s)N^s\frac{ds}{s(s+1)},\tag6.5$$

where the abscissa $\Re(s)=3$ has been chosen, since $A(3)$ converges absolutely.

We need to locate the singularities of $A(s)$. From the recurrences

$$\nu(2k+1)=\nu(k)+1\quad\text{and }\nu(2k)=\nu(k)$$

we get

$$\align A(s)&=\sum_{k\equiv 0\!\mod 2}\frac{2^{\nu(k)}}{n^s}+\sum_{k\equiv 1\!\mod 2}\frac{2^{\nu(k)}}{k^s}=\cr

&=\frac1{2^s}A(s)+2\sum_{l=0}^\infty\frac{2^{\nu(l)}}{(2l+1)^s}=\cr

&=\frac3{2^s}A(s)+2-2B(s)\endalign$$

with

$$B(s)=\sum_{k=1}^\infty 2^{\nu(k)}\(\frac1{(2k)^s}-\frac1{(2k+1)^s}\).\tag6.6$$

Using summation by parts and Stolarsky's elementary

estimate (cf. \cite{Sto77})

$$\frac13<\frac{\Phi(n)}{n^\rho}<3\tag 6.7$$

we know that $B(s)$ converges for $\Re(s)>\rho-1$ and by

$$A(s)=\frac{2^s}{2^s-3}\(2-2B(s)\)\tag 6.7$$

$A(s)$ has abscissa of convergence equal to $\rho$. This expression also provides

us with the analytic continuation of $A(s)$ for $\Re(s)>\rho-1$. We see that

$A(s)$ is meromorphic with simple poles at the points $\rho_k=\rho+\frac{2\pi ik}{\log2}$.



In order to shift the contour of integration in \thetag{6.5} to the left we need that

$A(s)$ does not grow too large along vertical lines. For $s=\sigma+it$,

with $\sigma>1$ and $|t|>\frac\sigma{\sqrt3}$, we have

$$\left|1-\(1-\frac1{2k+1}\)^s\right|\leq\min\(2,\frac{|t|}k\).$$

Thus we obtain

$$\align|B(s)|&=\left|\sum_{k=1}^\infty\frac{2^{\nu(k)}}{(2k)^s}\(1-\(1-\frac1{2k+1}\)^s\)\right|\leq\cr

&\leq2\sum_{1\leq k\leq2|t|}\frac{2^{\nu(k)}}{(2k)^\sigma}+\sum_{k>2|t|}\frac{2^{\nu(k)}}{(2k)^\sigma}\frac{|t|}k\ll |t|^{2-\sigma}.\endalign$$

Shifting the line of integration to $\Re(s)=1+\eps<\rho$, noting that

$|A(1+\eps+it)|\ll|t|^{1-\eps}$ and taking the residues at the poles $\rho_k$

into account we get

$$\align\Psi(N)&

	=\frac N{2\pi i}\int\limits_{1+\eps-i\infty}^{1+\eps+i\infty}

	A(s)N^s\frac{ds}{s(s+1)}+\cr

	&\qquad +N^{\rho+1}\sum_{k\in\Bbb Z}

	\frac2{\log2}\frac{1-B(\rho_k)}{\rho_k(\rho_k+1)}N^{\chi_k}.

\endalign$$

Estimating the integral trivially we derive the asymptotic formula for $\Psi(N)$.



So far, $B(s)$ is defined in terms of

the sequence $\{2^{\nu(k)}\}$ itself. An integral representation

derives from an ordinary generating function,

setting

$$\varphi(t)=\sum_{k=0}^\infty2^{\nu(k)}e^{-kt}=

\prod_{j=0}^\infty\(1+2e^{-2^jt}\).$$

Consider the Mellin transform of $(1-e^{-t})\varphi(2t)-1$;

by Formula~(2.2) (with $\mu_k=k$, $f(t)=e^{-t}$), we get

the integral representation for $B(s)$. Thus the proof of Theorem 5

 is completed.

\qed\enddemo



In order to get information on the number-theoretic function $\Phi(n)$

itself, we first work out a refinement of

Stolarsky's elementary approach.

\proclaim{Proposition 1} There exists an exact summation formula

$$\Phi(n)=n^\rho F(\log_2n)\tag6.8$$

with $F$ continuous and periodic with period $1$.

\endproclaim

\demo{Proof} From \cite{Sto77} there is an alternative formula

$$\Phi\(n=\sum_{i=1}^r2^{e_i}\)=\sum_{i=1}^r2^{i-1}3^{e_i}\tag6.9$$

with decreasing exponents $e_i$. Pulling out the main term we get

$$\Phi(n)=3^{e_1}\sum_{i=1}^r2^{i-1}3^{e_i-e_1},\tag6.10$$

where $e_1=\lf\log_2n\rf$.



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

Let

$$x=\sum_{j=0}^\infty2^{-d_j}$$

with $0=d_0<d_1<\ldots$. Then we set

$$\psi(x)=\sum_{j=0}^\infty 2^j3^{-d_j}.\tag6.11$$

Note that $\psi$ is well-defined since the dyadic rationals are written in their

infinite representation. Next we show the continuity of $\psi$. As the representation

of dyadic irrationals is unique the continuity at these points follows

immediately, since (because of $d_j\geq j$) the expansion \thetag{6.11}

converges faster than a geometric series  with quotient $\frac 23$.

For the proof of continuity at dyadic rationals we have to show

$$\psi\(\sum_{j=0}^k2^{-d_j}\)=\psi\(\sum_{j=0}^{k-1}2^{-d_j}+\sum_{l=d_k+1}^\infty2^{-l}\),$$

which follows immediately by direct computation. Note that $\psi(1)=1$ and

$\psi(2)=3$ and that $\psi$ satisfies a Lipschitz--H{\"o}lder

condition

$$|\psi(x)-\psi(y)|\leq C|x-y|^{\rho-1}.$$



Using the function $\psi$ we can write

$$\Phi(n)=3^{\lf\log_2n\rf}\psi\(\frac n{2^{\lf\log_2n\rf}}\),\tag6.12$$

since $\frac n{2^{\lf\log_2n\rf}}$ is nothing but $n$ ``scaled'' in binary

to the interval $[1,2)$. Formula \thetag{6.12} thus transforms into

$$\Phi(n)=n^\rho F(\{\log_2n\}),$$

where

$$F(u)=3^{-u}\psi\(2^u\)$$

is defined over the interval $[0,1]$ and $\{x\}=x-\lf x\rf$ denotes the

fractional part. $F$ can be extended into a periodic function since

$F(0)=F(1)$. The proof of Proposition 1 is completed.\qed

\enddemo



For the computation of the Fourier coefficients of $F$ we make use

of Theorem~5

and the following simple pseudo--Tauberian argument.



\proclaim{Proposition 2} Let $f$ be a continuous function,

periodic with period $1$, and let $\tau$ be a complex number with $\Re(\tau)>0$.

Then there exists a continuously differentiable function $g$ of period $1$

such that

$$\frac 1{N^{\tau+1}}\sum_{n<N}n^\tau f(\log_2n)=g(\log_2 N)+o(1)\tag6.13$$

$$\int_0^1g(u)du=\frac 1{\tau+1}\int_0^1f(u)du.\tag6.14$$

\endproclaim



\demo{Proof} We set

$$g(u)=\log2\cdot\frac{2^{-(\tau+1)u}}{2^{\tau+1}-1}\int_0^12^{(\tau+1)t}f(t)dt+

\log2\cdot2^{-(\tau+1)u}\int_0^u2^{(\tau+1)t}f(t)dt.\tag6.15$$

Obviously $g$ is continuously differentiable and \thetag{6.14} follows by a

straightforward application of integration by parts. Further we note that

$g(0)=g(1)$.



In order to prove \thetag{6.13} we proceed as follows

$$\align&\frac1{N^{\tau+1}}\sum_{n<N}n^\tau f(\log_2n)=\cr

=&\frac1{N^{\tau+1}}\sum_{p=0}^{\lf\log_2N\rf-1}\sum_{2^p\leq n<2^{p+1}}n^\tau f(\log_2n)+

\frac1{N^{\tau+1}}\sum_{n=2^{\lf\log_2N\rf}}^Nn^\tau f(\log_2n)=\cr

=&\frac1{N^{\tau+1}}\sum_{p<\lf\log_2N\rf}2^{p(\tau+1)}\sum_{1\leq x<2}x^\tau f(\log_2x)\Delta x+\cr

+&\frac1{N^{\tau+1}}2^{\lf\log_2N\rf(\tau+1)}\sum_{1\leq x<y}x^\tau f(\log_2x)\Delta x,\endalign$$

where $x=\frac n{2^p}$, $y=\frac N{2^{\lf\log_2N\rf}}$  and $x$ runs through

all dyadic rationals with denominator $2^p$ and $\Delta x=2^{-p}$, $p=0,\ldots,\lf\log_2N\rf$.

Now we interpret the sums over $x$ as Riemann sums. Thus we have with

remainder terms $\eps(p)$ tending to $0$ (for $p\to\infty$)

$$\align&\frac1{N^{\tau+1}}\sum_{n<N}n^\tau f(\log_2n)=\cr

=&\sum_{p<\lf\log_2N\rf}2^{(p-\lf\log_2N\rf)(\tau+1)}y^{-(\tau+1)}\(\int_1^2x^\tau f(\log_2x)dx+\eps(p)\)+\cr

+&y^{-(\tau+1)}\(\int_1^yx^\tau f(\log_2x)dx+\eps(\lf\log_2N\rf)\)=\cr

=&g(\log_2y)+y^{-(\tau+1)}\sum_{p=0}^{\lf\log_2N\rf}\eps(p)2^{-(\lf\log_2N\rf-p)}.\endalign$$

We note that only $\eps(\lf\log_2N\rf)$ 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.\qed

\enddemo



\demo{Proof} (Theorem 6) 

We can now conclude and determine the Fourier coefficients $f_k$ of the 

fractal function

$F$ in Theorem 6. We set $\tau=\rho_k$ in Proposition 2 and apply \thetag{6.14}

$$f_k=\int_0^1F(u)e^{-2\pi iku}du=(\rho_k+1)\int_0^1G(u)e^{-2\pi iku}du=(\rho_k+1)g_k.$$

Inserting the value of $g_k$ yields

$$f_k=\frac2{\log2}\frac{1-B(\rho_k)}{\rho_k}.$$

Using $|B(\rho_k)|\ll k^{2-\rho}$ 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\'er's theorem \cite{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.~\qed

\enddemo



\heading 7. The Newman--Coquet Function\endheading



In this section we investigate the function

$$S_3(n)=\sum_{k<n}(-1)^{\nu(3k)}.\tag7.1$$

The motivation for the study of this function goes back to

Newman \cite{Ne69} who noted that examination of the multiples of three,

$3,6,9,12,15,18,21,24,27,\ldots$,

 written in the base two,

$$11,~110,~1001,~1100,~1111,~10010,~10101,~11000,~11011,\ldots,$$

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 \cite{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. 





\proclaim{Theorem 7} The summatory function $S_3$ satisfies the exact formula

$$S_3(n)=n^\alpha\psi(\log_4n)+\frac{\eta(n)}3,$$

where $\psi$ is a continuous nowhere differentiable function of period $1$,

$\eta$ is given by

$$\eta(n)=\cases 0&\text{if $n$ is even}\\ (-1)^{\nu(3n-1)}&\text{if $n$ is odd}\endcases$$

and $\alpha=\frac{\log3}{\log4}$. The Fourier expansion

$\psi(u)=\sum_{k\in\Bbb Z}\psi_ke^{2k\pi iu}$ is given by

$$\align\psi_k&=\frac{3^{\alpha_k}(-1)^k}{\alpha_k6\sqrt3\log2}

\Bigl(3+(-1)^k\sqrt3-\(1+(-1)^k\sqrt3\)f_0(\alpha_k)+\cr

&+\(2+(-1)^k\sqrt3\)f_1(\alpha_k)-f_2(\alpha_k)\Bigr),\endalign$$

where $\alpha_k=\alpha+\frac{k\pi i}{\log2}$ and

$$\align

&f_0(s)=\frac1{3\Gamma(s)}\int\limits_0^\infty\(F\(e^{-t}\)+F\(\zeta

e^{-t}\)+ F\(\zeta^2e^{-t}\)-3\)\(1-e^{-\frac t2}\) t^{s-1}dt\cr

&f_1(s)=\frac1{3\Gamma(s)}\int\limits_0^\infty\(F\(e^{-t}\)+\zeta^2

F\(\zeta e^{-t}\)+ 

\zeta F\(\zeta^2e^{-t}\)\)\(1-e^{-\frac t2}\)t^{s-1}dt\cr

&f_2(s)=\frac1{3\Gamma(s)}\int\limits_0^\infty\(F\(e^{-t}\)+

\zeta F\(\zeta e^{-t}\)+

\zeta^2 F\(\zeta^2e^{-t}\)\)\(1-e^{-\frac t2}\)t^{s-1}dt\endalign$$

with $\zeta=e^{\frac{2\pi i}3}$ and

$$F(z)=\prod_{k=0}^\infty\(1-z^{2^k}\).\tag7.2$$

In particular, a rough estimate of the mean value $\psi_0$ is

$$\psi_0\approx

%% 2.93039\;13325\;63657\;25112\;43191\;20179.$$

%% now divide this by log(2) since PF had omitted it in Maple

%% computations. Next EMPIRICALLY, further divide by 3 and the result

%% matches that of Peter G.

1.40922\;03477\;84529\;82145\;02895\;25994.$$

\endproclaim



Observe that the extreme values of $\psi(u)$ are already known from

Coquet's work~\cite{Co84}:

$$1.15470 \le \psi(u)\le 1.60196\,.$$



\demo{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 

% elaborate 

than in Section 6. We first

prove an asymptotic formula for the double summatory function

$$T(N)=\sum_{1\leq n<N}\(S_3(n)-1\).$$

For this purpose we need some information on the function

$$\xi_0(s)=\sum_{n=1}^\infty\frac{(-1)^{\nu(3n)}}{(3n)^s}.$$



Using the function $F$ given by \thetag{7.2}

that satisfies $F(z)=(1-z)F(z^2)$, and setting

$$\align&\Xi_0(z)=\frac13\(F(z)+F(\zeta z)+F(\zeta^2z)\)\cr

&\Xi_1(z)=\frac13\(F(z)+\zeta^2F(\zeta z)+\zeta F(\zeta^2z)\)\cr

&\Xi_2(s)=\frac13\(F(z)+\zeta F(\zeta z)+\zeta^2F(\zeta^2z)\)\endalign$$

we obtain the functional equations

$$\aligned&\Xi_0(z)=\Xi_0(z^2)-z\Xi_1(z^2)\cr

&\Xi_1(z)=\Xi_2(z^2)-z\Xi_0(z^2)\cr

&\Xi_2(z)=\Xi_1(z^2)-z\Xi_2(z^2).\endaligned\tag7.3$$



Consider now the companion Dirichlet series

$\xi_k$, for $k=1,2$, defined in a way similar to $\xi_0$, where

summation runs through the other residue classes $\mod3$,

$$

\xi_k(s)=\sum_{n=0}^\infty\frac{(-1)^{\nu(3n+k)}}{(3n+k)^s}

\quad\text{for $k=1,2$.}$$

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

$$\aligned&\xi_0(s)=\frac1{\Gamma(s)}\int\limits_0^\infty\(\Xi_0\(e^{-t}\)-1\)t^{s-1}dt\cr

&\xi_k(s)=\frac1{\Gamma(s)}\int\limits_0^\infty\Xi_k\(e^{-t}\)t^{s-1}dt

\quad\text{for $k=1,2$.}\endaligned\tag7.4$$

% The functions $\xi_k$ $k=1,2$ are defined in a way similar to $\xi_0$, but

% summation runs through the residue class of $k\mod3$. 

% Combining this with \thetag{7.3}

The image of the collection of functional equations \thetag{7.3}

is then the system of equations

$$\matrix &\(1-2^{-s}\)&\xi_0(s)&+&2^{-s}&\xi_1(s)&&&&=&2^{-s}f_1(s)&\\

&2^{-s}&\xi_0(s)&+&&\xi_1(s)&-&2^{-s}&\xi_2(s)&=&2^{-s}f_0(s)&-1\\

&&&-&2^{-s}&\xi_1(s)&+&\(1+2^{-s}\)&\xi_2(s)&=&2^{-s}f_2(s),&\endmatrix\tag7.5$$

where the functions $f_k$ % $k=0,1,2$ 

are given by

$$\align &f_0(s)=\sum_{n=1}^\infty(-1)^{\nu(3n)}\(\frac1{(3n)^s}-\frac1{(3n+\frac12)^s}\)\cr

&f_k(s)=\sum_{n=0}^\infty(-1)^{\nu(3n+k)}\(\frac1{(3n+k)^s}-\frac1{(3n+k+\frac12)^s}\)

\quad\text{for $k=1,2$.}\endalign$$

These functions are defined for $\Re(s)>0$ and satisfy $|f_k(\sigma+it)|\ll|t|^{1-\sigma}$

for $0<\sigma<1$, which can be shown using the same arguments as in Section 6.



Solving \thetag{7.5} yields

$$\xi_0(s)=\frac1{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)\).\tag7.6$$

This equation provides us with the analytic continuation of $\xi_0$ and shows

that all poles of this function have to satisfy the equation $4^s=3$.



After these preparations we can write using \thetag{2.4}

$$T(N)=\frac N{2\pi i}\int\limits_{2-i\infty}^{2+i\infty}3^s\xi_0(s)N^s\frac{ds}{s(s+1)}.\tag7.7$$

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

yields

$$T(N)=N^{\alpha+1}\sum_{k\in\Bbb Z}\frac{\psi_k}{\alpha_k+1}e^{2k\pi i\log_4N}+O(N^{1+\eps}),\tag7.8$$

where the term $O(N^{1+\eps})$ is obtained by trivial estimation of the integral

from $\eps-i\infty$ to $\eps+i\infty$ over the same integrand as in \thetag{7.7}.



Now using the exact formula due to Coquet and the adapted version of

Proposition~2 yields the Fourier expansion of the function $\psi$.

\qed\enddemo

{\bf Remark 5.} The method employed

above can also be used to gather information

on the summatory functions

$$\sum_{k<n}(-1)^{\nu(3k+1)},\quad\sum_{k<n}(-1)^{\nu(5k)}$$

and other functions of this type.



{\bf 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 $\omega(s)$ to its values 

$\omega(s+1),\omega(s+2)$, etc.

Since $\omega(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 $\omega(s+m-1)$, $\omega(s+m-2)$, etc, till $\omega(s)$.

Related infinite functional equations are given in~\cite{AC85}.



The principles of such infinite functional equations are well known in

the case of the Riemann zeta functions (see pp.~273--276

of~\cite{La74}).

Take for instance the problem of evaluating $A(s)$ and $B(s)$ defined

in Section~6:

$$A(s)=\sum_{k=1}^\infty {2^{\nu(k)}\over k^s}

\qquad\hbox{and}\qquad

B(s)=\sum_{k=1}^\infty 2^{\nu(k)}\(\frac1{(2k)^s}-\frac1{(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~\thetag{6.6}:

$$A(s)=\frac3{2^s}A(s)+2-2B(s).$$

Now, $B(s)$ can be rewritten as

$$B(s)=\sum_{k=1}^\infty {2^{\nu(k)}\over (2k)^s}

\left[1-{1\over(1+(2k)^{-1})^{s}}\right].$$

Using the binomial expansion of $(1+(2k)^{-1})^{-s}$, and regrouping

terms, we get

$$B(s)={1\over 2^s} \left[

{s\choose 1} {A(s+1)\over 2^1}-{s\choose 2}{A(s+2)\over

2^2}+{s\choose 3}{A(s+3)\over2^3}-\cdots\right].$$ 

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.)



\heading 8. Conclusion \endheading



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

{\it a priori\/} asymptotic. They can be converted into exact formul{\ae}

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~\cite{FG92}, which further

exemplifies the usefulness of complex analytic methods in this range

of problems.



% \heading 8. Computer Graphics\endheading

% In this concluding section we present some computer graphics illustrating 

% the

% problem of odd numbers in Pascal's triangle.





\Refs



\ref\key Al87

\by J.-P. Allouche

\paper Automates finis en th\'eorie des nombres

\jour Expos. Math.

\vol 5

\pages 239--266

\yr1987

\endref



\ref\key AC85\by J.-P. Allouche and H. Cohen\paper Dirichlet Series and Curious

Infinite Products\jour Bull. London Math. Soc.\vol 17\pages 531--538\yr 1985\endref



\ref\key AS92

\by J.-P. Allouche and J. Shallit

\paper The Ring of $k$--regular Sequences

\jour Theoretical Computer Science

\vol 98

\pages 163--197

\yr 1992

\endref



\ref\key Ap84\by T.M. Apostol\book Introduction to Analytic Number Theory\publ Springer Verlag

\publaddr Berlin-Heidel\-berg-New York\yr 1984\endref

\ref\key BEM83\by J. Brillhart, P. Erd\H os and P. Morton\paper On Sums of

Rudin-Shapiro coefficients II\jour Pacific J. Math.\vol 107\pages 39--69\yr 1983\endref

\ref\key BM78\by J. Brillhart and P. Morton\paper \"Uber Summen von Rudin-Shapiroschen

Koeffizienten\jour Illinois J. Math.\vol 22\pages 126--148\yr 1978\endref



\ref\key Ca92

\by E.  Cateland

\book Suites digitales et suites $k$--r\'eguli\`eres

\publ Th\`ese

\publaddr Universit\'e de Bordeaux~I

\yr 1992

\endref



\ref\key Co83

\by J. Coquet

\paper A Summation Formula Related to the Binary Digits

\jour Invent. Math.

\vol 73\pages 107--115\yr1983

\endref



\ref\key De75

\by H. Delange

\paper Sur la fonction sommatoire de la fonction ``Somme des Chiffres''

\jour Enseignement Math.(2)

\vol 21

\pages 31--47

\yr1975

\endref



\ref\key Do50\by G. Doetsch\book Handbuch der Laplace Transformation\publ Birkh\"auser Verlag

\publaddr Basel\yr 1950\endref



\ref\key DT89

\by J.-M. Dumont and A. Thomas

\paper Syst\`emes de num\'eration

et fonctions fractales relatifs aux substitutions

\jour Theoretical Computer  Science

\vol 65\pages 153--169\yr 1989

\endref



\ref\key Fa85\by K.J. Falconer\book The Geometry of Fractal Sets\publ Cambridge

University Press\yr 1985\endref



\ref\key FG92

\by P. Flajolet and M. Golin

\paper Mellin Transforms and Asymptotics: The Mergesort Recurrence

\jour INRIA Research Report

\vol 1612

\yr 1992

\endref





\ref\key FR80\by P. Flajolet and L. Ramshaw\paper A Note on Gray Code and Odd-Even Merge

\jour SIAM J. Comput.\vol 9\pages 142--158\yr 1980\endref



\ref\key FRV79

\by P. Flajolet, J.C. Raoult and J. Vuillemin

\paper The Number

of Registers Required for Evaluating Arithmetic Expressions

\jour Theoretical  Computer Science

\vol 9\pages 99--125\yr 1979

\endref



\ref\key FRS84\by P. Flajolet, M. Regnier and R. Sedgewick\paper

Some Uses of the Mellin Integral Transform in the Analysis of Algorithms

\inbook Combinatorial Algorithms on Words\eds A. Apostolico and Z. Galil

\publ Springer Verlag\publaddr Berlin-Heidelberg\yr1985\endref



\ref\key GT91\by P.J. Grabner and R.F. Tichy\paper $\alpha$-Expansions, Linear

Recurrences and the Sum-of-Digits Function\jour Manuscripta Math.\vol70

\pages311--324\yr1991\endref

\ref\key GKP89\by R.L. Graham, D.E. Knuth and O. Patashnik\book Concrete

Mathematics\publ Addison Wesley\yr 1989\endref

\ref\key Ha77\by H. Harborth\paper Number of Odd Binomial Coefficients

\jour Proc. Amer. Math. Soc.\vol 62\pages 19--22\yr1977\endref

\ref\key Ki83\by P. Kirschenhofer\paper Subblock Occurrences in the $q$-ary

Representation of $n$\jour SIAM J. Alg. Discr. Meth.\vol 4\pages 231--236\yr1983\endref

\ref\key KP84\by P. Kirschenhofer and H. Prodinger\paper Subblock Occurrences

in Positional Number Systems and Gray Code Representation\jour J. Inf. Opt. Sci.

\vol 5\pages 29--42\yr1984\endref



\ref\key KPT85

\by P. Kirschenhofer, H. Prodinger and R.F. Tichy

\paper \"Uber die Ziffernsumme nat\"urlicher Zahlen und verwandte Probleme

\inbook Zahlentheoretische Analysis, Lecture Notes 1114

\ed E. Hlawka

\pages 55--65\endref



\ref\key Ko88

\by T. W. K{\H o}rner

\book Fourier Analysis

\publ Cambridge University Press

\publaddr Cambridge

\yr 1988

\endref





\ref\key La74

\by E.  Landau

\book Handbuch der Lehre von der Verteilung der Primzahlen

\publ Chelsea Publishing Company

\yr 1974

\endref



\ref\key Ne69\by D.J. Newman\paper On the Number of Binary Digits in a Multiple

of Three\jour Proc. Amer. Math. Soc.\vol 21\pages 719--721\yr 1969\endref

\ref\key OS89\by A.H. Osbaldestin and P. Shiu\paper A correlated digital sum

problem associated with sums of three squares\jour Bull. London Math. Soc.\vol 21

\pages 369--374\yr 1989\endref

\ref\key Sch69\by W. Schwarz\book Einf\"uhrung in Methoden und Ergebnisse der

Primzahltheorie\publ Bibliographisches Institut\publaddr Mannheim\yr 1969\endref

\ref\key Ste89\by A.H. Stein\paper Exponential Sums of Digit Counting Functions

\inbook Th\'eorie des nombres, Comptes Rendus de la Conf\'erence Internationale

de Th\'eorie des Nombres tenue \`a l'Universit\'e Laval en 1987\eds J.M. De Koninck

et C. Levesque\publ de Gruyter\publaddr Berlin-New York\yr 1989\endref

\ref\key Sto77\by K.B. Stolarsky\paper Power and Exponential Sums of Digital

Sums Related to Binomial Coefficient Parity\jour SIAM J. Appl. Math.\vol 32

\pages 717--730\yr1977\endref

\ref\key WW27\by E.T. Whittaker and G.N. Watson\book A Course in Modern

Analysis\publ Cambridge University Press\yr 1927\endref



\ref\key Wo84

\by S. Wolfram

\paper Geometry of binomial coefficients

\jour Amer. Math. Monthly

\vol 91\pages 566--571\yr 1984

\endref



\ref\key Wo89

\by R. Wong

\book Asymptotic Approximations of Integrals

\publ Academic Press

\publaddr San Diego

\yr 1989

\endref



\endRefs





\enddocument



