\documentclass[10pt]{article}


%%%%%%%%%%%%%%%%% YOU SHOULD USE THIS PACKAGE %%%%%%%%%%%%
\usepackage{pack}

%\renewcommand{\baselinestretch}{1.2}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{amsfonts,amsmath,amssymb,ifthen,url,latexsym,array}
\usepackage{algorithmic,algorithm}
\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand{\algorithmicensure}{\textbf{Output:}}

\newcommand{\assign}{\leftarrow}
\newcommand{\append}{\,\&\,}
\def\fractional#1{\left\{#1\right\}}
\def\betrag#1{\left\vert#1\right\vert}
\newcommand{\Rmin}{R_{\mathrm{min}}}
\newcommand{\Rmax}{R_{\mathrm{max}}}

\newcommand{\NOT}{\textbf{not}\ }
\newcommand{\AND}{\textbf{and}\ }
\newcommand{\OR}{\textbf{or}\ }
\DeclareMathOperator{\sign}{sign}
\newcommand{\seq}[1]{\mathbf{#1}}
\def\cond#1{\left[#1\right]}

\DeclareMathOperator{\val}{\mathsf{value}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%% THE AUTHORIZED PACKAGES %%%%%%%
%\usepackage{hyperref,graphicx,psfrag,amsfonts,amsmath,indentfirst,floatflt}

%%%%%% IF YOU WANT AN OTHER PACKAGE, CHECK THAT THERE ARE COMPATIBLE
%%%%%% WITH THESE ONES %%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{document}

%%%%%%%%%%%%%% PERSONNAL DEFINITIONS (If needed) %%%%%%%%%%%%%%%

\def \build#1#2#3{\mathrel{\mathop{\kern 0pt#1}\limits_{#2}^{#3}}}
\def \B{\Big}
\def \b{\big}
\def \l{\left}
\def \r{\right}

\def\P{\mathbb{P}}
\def\ZZ{\mathbb{Z}}
\def\eps{\varepsilon}
\def\fl#1{\left\lfloor#1\right\rfloor}
\newcommand{\reg}{\operatorname{Reg}}

%%%%%%%%%%%%%%% TITLE %%%%%%%%%%%%%
\renewcommand{\titre}{Digits and beyond}

%%%%%%%%%%%%%%% SMALLTITLE (for the head of the page) %%%%%%%%%%%%%


\renewcommand{\smalltitre}{Digits and beyond}


%%%%%%%%%%%%%%% NAMES OF THE AUTHORS (WITHOUT ADRESSES)
\renewcommand{\auts}{Helmut Prodinger}

%%%%%%%%%% CREATION OF THE TITLE  %%%%%%%%%%%%%
\tit



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

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

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

Very briefly we mention carry propagation, mergesort
parameters and jump interpolation search trees. 
\end{abstract}




\index{Mellin--Perron formula} 
\index{Digits} 
\index{Delange's method}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Introduction}
%%%%%%%%%%%%%%%%   ENVIRONMENTS   :%%%%%%%%%%%%%%%% 
%%%%% \begin{theo} \end{theo} For Theorem        %%
%%%%% \begin{pro} \end{pro}       Proposition    %%
%%%%%\begin{cor} \end{cor}        Corollary      %%
%%%%%\begin{lem}\end{cor}         Lemma          %%
%%%%%\begin{defi}\end{defi}       Definition     %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



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

We are interested in the binary expansion, and, more generally
in base $q$--expansion, with an integer $q\ge2$, and digits
$\{0,\dots,q-1\}$. Delange 
\cite{Delange75} has analyzed the sum--of--digits
function $S(n)$ (sometimes, especially for $q=2$, written as
$\nu(n)$), and found in particular the following result for
the mean value
\begin{equation*}
\frac1m\sum_{0\le n<m}S(n)=\frac{q-1}2\log_qm+F(\log_qm),
\end{equation*}
with a periodic function $F(x)$ of period 1, which is continuous
but nowhere differentiable, and with explicitly known Fourier coefficients.
Perhaps even more important than his result, is his \textsl{method}
which is based on finding an explicit formula for the individual
digits, in terms of floor functions,  rewriting them as integrals
over piecewise constant functions. Forming the mean value just
means the union of the intervals of integration, which makes things
easier. Then one pulls out the main (logarithmic) term and finds
that what remains is  a periodic function of $\{\log_qm\}$ (the fractional
part of $\log_qm$) which can be brought into some standard form from
which one also gets the Fourier coefficients. 

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

Delange's technique is elementary and nice, however, in more complicated
situations, it can become quite messy. Flajolet came up with an alternative
method \cite{FlGrKiPrTi94}: It is based on the Mellin--Perron summation
formula, which allows to write the counting function of interest as
a contour integral in the complex plane. Shifting the line of integration
produces then the terms in the explicit formula. As it often happens in
this type of problems, one gets exact formul{\ae}. The fact that the
error term disappears completely is based on
$$0=\int\nolimits_{-\frac14-i\infty}^{-\frac14+i\infty}
\zeta(s)n^s\frac{ds}{s(s+1)}
$$
or similar results. 
In most instances, this technique is somewhat superior to Delange's elementary
approach. As an additional reading we recommend Marko Riedel's master's
thesis \cite{Riedel:thesis}.

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

In Section~\ref{signed}, we discuss a symmetric number system with base
$q$ (an even integer) and digits $\{-q/2,\dots,q/2\}$. This
redundant system is made unique by some conditions which in the
instance $q=2$ simply say that no two adjacent nonzero digits can occur.
This instance $q=2$ was rediscovered many times; perhaps the
earliest reference is \cite{Reitwiesner60}. Some historical
remarks can be found in \cite{prodinger162}. We discuss again
the problem of counting digits and subblocks in such a 
\textsl{symmetric signed system}. 

Digits occur however in counting problems related to the 
\textsl{Analysis of Algorithms}. 
In Section~\ref{register:section} we deal
with the \textsl{Register function\/} of binary trees (in the literature
often appearing as Horton--Strahler numbers;
here are some (random) references: \cite{Nebel00, Kruszewski99, 
DeKr96,DeKr95,YeMa94,Moon78/79,Moon80}).

The question about the average value of the register function
was solved independently by Flajolet--Raoult--Vuillemin
\cite{FlRaVu79} and Kemp \cite{Kemp79}, compare also 
\cite{MeMoPo80}. The quantity $v_2(n)$, defined to be $k$
if $n=2^k(2i+1)$, plays a crucial role here. It is related to
the sum--of--digits function $S(n)$, since $\sum_{k\le n}v_2(k)=n-S(n)$.
Consequently one can, after some manipulations, invoke Delange's
result. This was the route taken by
Flajolet--Raoult--Vuillemin.
 Another approach (Kemp) is,
after approximating the explicit quantities using
real analysis,  to consider Mellin transforms, which leads to
Dirichlet series of the type $\sum_{n\ge1}v_2(n)/n^s$.
Perhaps the method that is most advanced \cite{FlPr86}, also
uses Mellin transforms, but \textsl{on the level of generating functions},
in order to find the local behaviour of a generating function closely
related to the desired average values. Once this is established, 
\textsl{singularity analysis of generating functions\/} (transfer theorems), 
developed in \cite{FlOd90}, provides the asymptotics of the, say,
average value of the register function of binary trees of size $n$.


 Section~\ref{odd-even-merge:section} is in a sense the companion
of  Section~\ref{register:section}. The analysis of Batcher's
odd--even method (see Knuth \cite{Knuth78}) was originally left open
and eventually solved by Sedgewick \cite{Sedgewick78}. What was the
binary expansion and the quantity $v_2(n)$ for the register problems is
now the \textsl{Gray code\/} representation and the function
$\vartheta(k)$ which is $1$  for $k=2^m(4i+1)$,
and $-1$ for $k=2^m(4i+3)$. Flajolet and Ramshaw \cite{FlRa80} use
a result analogous to Delange's
 but for the Gray code representation 
(also included in Section~\ref{Mellin:Perron}),
and proceed along the lines of \cite{FlRaVu79}. The more advanced technique
(singularity analysis of generating functions) is also described here
and was worked out a long time ago for the proceedings of a 
French summer school in Ile de R\'e \cite{Prodinger83}.

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


The Section~\ref{missing} deals with sets of numbers which 
have representations avoiding digits from a subset of
\textsl{forbidden digits}. The most common case is $q=3$ with
forbidden digit $1$. If one considers numbers of the form
$\sum_{k\ge1}a_k3^{-k}$ where $a_k\in\{0,2\}$, one obtains
the classical Cantor set. One question is about the moments of
the Cantor distribution (strings of the form
$\sum_{k\ge1}a_k3^{-k}$ are produced at random, where ``random''
means that each digit might be 0 or 2, with probability $1/2$).
Grabner and I could satisfactorily solve this problem,
which originated in \cite{LadTay92}, using
the method of Mellin transforms. 
Another problem, suggested in \cite{Hosking94}, was eventually
solved by A.~Knopfmacher and myself \cite{KnPr96}: If one
draws $n$ random numbers, according to the Cantor distribution, 
what is the expected value of their \textsl{minimum\/}? 
Using exponential generating functions to solve the relevant
difference equations, one can relate it to ``the hardest
asymptotic nut'' from \cite{Knuth98}. These days, one has
alternative methods to attack the sums coming out in the
analysis \`a la ``asymptotic nut;'' these are  techniques
known as Rice's method \cite{FlSe95} which are 
again intimately related
to Mellin transforms, and (analytic) Depoissonization, which
was floating around for years in the literature, an early example
being perhaps \cite{ShLl66}. Recently it has been 
\textsl{polished\/} and
systematized by Jacquet and Szpankowski \cite{JaSz98}.


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












\section{A Delange type analysis}\label{Delange:section}

We  describe Delange's technique by considering
the number system with base $q$ and digits $\{d,d+1,\dots,d+q-1\}$
where $1-q\le d\le0$. We are going to study $B_i(n)$, the number of
occurrences of digit $i\neq0$ in the representation of $n$. 
This is not a real restriction since the number of occurrences
of digit $0$ can be obtained as the difference of the length
of the representation and the number of the other digits.  A full treatment, 
even for subblocks instead of just digits, is in \cite{KiPr84}.

First, one needs an explicit formula: If $n$ is written as 
$\dots a_2a_1a_0$ in the $(q,d)$--system, then $a_k=i$ iff
\begin{equation*}
\fl{\frac{n}{q^{k+1}}+1-\frac iq-\frac{d}{q(q-1)}+\frac1q}-
\fl{\frac{n}{q^{k+1}}+1-\frac iq-\frac{d}{q(q-1)}}=1.
\end{equation*}
Consequently, 
\begin{equation*}
B_i(n)=\sum_{k\ge1}\bigg(
\fl{\frac{n}{q^{k}}+1-\frac iq-\frac{d}{q(q-1)}+\frac1q}-
\fl{\frac{n}{q^{k}}+1-\frac iq-\frac{d}{q(q-1)}}\bigg).
\end{equation*}
%
Delange's simple but extremely useful observation is that one
can write the floor functions as integrals. We are considering
an average of the function $B_i(n)$:
\begin{gather*}
\frac1m\sum_{n=0}^{m-1}B_i(n)=
\frac1m\sum_{n=0}^{m-1}\sum_{k\ge1}\textstyle{\Big(
\fl{\frac{n}{q^{k}}+1-\frac iq-\frac{d}{q(q-1)}+\frac1q}-
\fl{\frac{n}{q^{k}}+1-\frac iq-\frac{d}{q(q-1)}}\Big)}\\
=
\frac1m\int_{0}^{m}\sum_{k\ge1}\textstyle\Big(
\fl{\frac{t}{q^{k}}+1-\frac iq-\frac{d}{q(q-1)}+\frac1q}-
\fl{\frac{t}{q^{k}}+1-\frac iq-\frac{d}{q(q-1)}}
\displaystyle{\Big){dt}} .\\
\end{gather*}
It can be readily checked that nonzero contributions are
only possible for $k\le l+1$, with $l=\lfloor\log_qm-\log_q(1+\frac{d}{q-1})\rfloor$.
After a simple change of variable in the integrals, it turns out that
one should study  functions like
\begin{equation*}
g_{\beta}(x)=\int_0^x\Big(\fl{u+\beta+\tfrac1q}-\fl{u+\beta}-\tfrac1q
\Big)du,\qquad
h_\beta(x)=\sum_{k\ge0}{q^{-k}}g_\beta(xq^k)
\end{equation*}
%
and
\begin{equation*}
H_{\beta}(x)=\frac{1-\gamma-\{-\gamma+x\}}{q}+q^{{1-\gamma}-\{-\gamma+x\}}
h_\beta(q^{\{-\gamma+x\}-1+\gamma}),
\end{equation*}
with $\{x\}=x-\fl x$ (the fractional part of $x$) and 
$\gamma=\log_q(1+\frac d{q-1})$.

Eventually one finds that

\begin{equation*}
\frac1m\sum_{n=0}^{m-1}B_i(n)=\frac{\log_qm}{q}+H_\beta(\log_qm),
\end{equation*}
where $\beta$ depends on the digit $i$ in a simple way:
$\beta=1-\frac iq -\frac d{q(q-1)}-\frac 1q$.

Since the function $H_\beta(x)$ is periodic with period 1, it
is natural to study its \textsl{Fourier series\/} expansion. The result is:
$H_\beta(x)=\sum_{k\in\ZZ}h_ke^{2\pi i kx}$,
with
\begin{align*}
h_0&=\log_q\frac{\Gamma(1-\{\beta+\frac1q\})}{\Gamma(1-\{\beta\})}
-\frac1q\Big(\frac12+\frac1{\log q}\Big),\\
h_k&=\frac{\zeta(\chi_k,1-\{\beta+\frac1q\})-      
\zeta(\chi_k,1-\{\beta\})}
{\log q\cdot \chi_k(1+\chi_k)},\quad k\neq0,
\end{align*}
with $\chi_k=2\pi ik/\log q$ and the Hurwitz' zeta function $\zeta(z,a)$.

The computation of the Fourier coefficients
 is relatively straight forward; one has to use
results like
\begin{align*}
\int_1^\infty\frac{\fl u du}{u^{s+1}}&=\sum_{k\ge1}k\int_{k}^{k+1}
\frac{du}{u^{s+1}}=\frac1s\sum_{k\ge1}k\Big(\frac{1}{k^s}-\frac{1}{(k+1)^s}\Big)
=\frac1s\sum_{k\ge1}\frac{1}{k^s}=\frac1s\zeta(s).\\
\end{align*}
The computations in the case of counting subblocks are more complicated, 
and in the end an additional error term of order $1/m$ occurs. 





\section{The Mellin--Perron summation formula}\label{Mellin:Perron}

This section is based on \cite{FlGrKiPrTi94}.
Let $f(x)$ be a function defined over $[0,+\infty)$. Its Mellin transform
$f^*(s)=\mathcal{ M}[f(x);s]$ is defined by
$f^*(s)=\int_0^\infty f(x)x^{s-1}dx$.
By linearity and the rescaling property we have 
% under natural analytic conditions:

\begin{equation}\label{rescaling}
F(x)=\sum_k\lambda_kf(\mu_kx)
~~\Longrightarrow~~ F^*(s)=\bigg(\sum_k\lambda_k\mu_k^{-s}\bigg)f^*(s).
\end{equation}
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 
(cf.~\cite{Doetsch72}).
When applied to (\ref{rescaling}), it provides
\begin{equation}\label{sumf}
\sum_k\lambda_kf(\mu_kx)=\frac 1{2\pi i}
\int\nolimits_{c-i\infty}^{c+i\infty}\bigg(\sum_k\lambda_k\mu_k^{-s}\bigg)
f^*(s)x^{-s}ds,
\end{equation}
with $c$ in the fundamental strip.


Formula (\ref{sumf}) could be called Mellin's summation formula. 
It is especially 
useful when the integral can be computed by \textsl{residues}, 
and in that case each residue 
contributes a term in an asymptotic expansion of $F(x)$.

This formula lends itself to various number theoretic applications,
most notably proofs of the prime number theorem. 
Introduce the step function $H_0(x)$
defined by
$$H_0(x)=
\begin{cases} 1&\text{if $x\in[0,1]$,}\\0&\text{if $x>1$,}
\end{cases}
$$
together with the functions $H_m(x)=(1-x)^mH_0(x)$. In the interesting case
where $\mu_k\equiv k$, we obtain from (\ref{sumf}),
 formul\ae{} of the Perron type
that provide integral representations for the iterated summations of arithmetic
functions in terms of their Dirichlet generating function.


 Let $c>0$  lie  in the 
half--plane of absolute convergence of $\sum_{k} {\lambda_k}k^{-s}$.
Then for any $m\ge1$, we have
\begin{equation}\label{mellperr}
\frac 1{m!}\sum_{1\leq k<n}\lambda_k\Big(1-\frac kn\Big)^m=\frac 1{2\pi i}
\int\nolimits_{c-i\infty}^{c+i\infty}
\bigg(\sum_{k\geq1}\frac{\lambda_k}{k^s}\bigg)n^s\frac{ds}{s(s+1)\cdots(s+m)}.
\end{equation}
%
 For $m=0$, 
$$
\sum_{1\leq k<n}\lambda_k +{\frac{\lambda_n}2} =
\frac 1{2\pi i}
\int\nolimits_{c-i\infty}^{c+i\infty}
\bigg(\sum_{k\geq1}\frac{\lambda_k}{k^s}\bigg)n^s \, \frac{ds}{s}.
$$

Formula (\ref{mellperr}) is obtained from (\ref{sumf}) 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$. 
%
For instance, if we use $\lambda_k\equiv1$ and $m=1$, we get
$$
\frac{n-1}2=
\frac 1{2\pi i}\int\nolimits_{2-i\infty}^{2+i\infty}\zeta(s)n^s\frac{ds}{s(s+1)}.
$$
Shifting the line of integration to the left and taking residues into account
we obtain
\begin{equation}\label{zetaexact}
0=\int\nolimits_{-\frac14-i\infty}^{-\frac14+i\infty}\zeta(s)n^s\frac{ds}{s(s+1)}.
\end{equation}
Identity (\ref{zetaexact}) is the basis for the existence of 
several {\sl exact} rather
than plainly {\sl asymptotic} summation formul\ae.
We use this Mellin--Perron technique to derive 
an alternative proof of Delange's theorem:
The sum--of--digits function $S(n)$ satisfies
$$S(n)=\frac 12n\log_2n+nF_0(\log_2n),$$
where $F_0(u)$ can be represented by the Fourier series
$F_0(u)=\sum_{k\in\ZZ}f_ke^{2\pi iku}$
and
\begin{align*} 
&f_0=\frac{\log_2\pi}2-\frac 1{2\log 2}-\frac34,\\
&f_k=-\frac1{\log2}\frac{\zeta(\chi_k)}{\chi_k(\chi_k+1)}\quad\text{for}
\quad\chi_k=\frac{2\pi ik}{\log2},\quad k\not=0.
\end{align*}


 Let $v_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- v_2(k)$, so that $S(n)$ resembles a double
summation of $ v_2(k)$. Furthermore, it is well-known 
(and also rederived in Section~\ref{register:section}) that
$$\sum_{k\geq1}\frac{ v_2(k)}{k^s}=\frac{\zeta(s)}{2^s-1}.$$
Thus, from (\ref{mellperr}), with $\lambda_k= v_2(k)$ and $m=1$, we get
the basic integral representation
$$
S(n)=\frac{n(n-1)}2-\frac n{2\pi i}\int\nolimits_{2-i\infty}^{2+i\infty}
\frac{\zeta(s)}{2^s-1}n^s\frac{ds}{s(s+1)}.
$$
The integrand  has a simple pole at $s=1$ (originationg from
the $\zeta$--function), a double pole
at $s=0$ and simple poles at $s=\chi_k$. Shifting the line of integration
to $\Re(s)=-\frac14$ and taking residues into account we get
$$
S(n)=\frac12 n\log_2n+nF_0(\log_2n)-nR(n),
$$
where the Fourier series (akin to $F_0$) 
$\frac{1}{\log2}\sum_{k\in\ZZ}
\frac{\zeta(\chi_k)}{\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
\begin{equation}\label{remainder}
R(n)=\frac1{2\pi i}\int\nolimits_{-\frac14-i\infty}^{-\frac14+i\infty}
\frac{\zeta(s)}{2^s-1}n^s\frac{ds}{s(s+1)},
\end{equation}
%
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|^{3/4}$
(cf.~\cite{WhWa27}).
%
Using the expansion
$\frac1{2^s-1}=-1-2^s-2^{2s}-2^{3s}-\cdots$
in (\ref{remainder}), 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\nolimits_{-\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 (\ref{zetaexact}).



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
\textsl{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, e.\;g., \cite{FlRa80}).
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}
\quad L(s)=\sum_{k\ge0} \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\nolimits_{2-i\infty}^{2+i\infty}\frac{2^sL(s)}{2^s-1}n^s\frac{ds}{s(s+1)}.$$
%
The summatory function $G(n)$ of
sum--of--digits function of Gray--code satisfies
$$G(n)=\frac12n\log_2n+nF_1(\log_2n),$$
where $F_1(x)$ is representable by the Fourier series
$$
F_1(x)=2\log_2\Gamma\Big(\frac14\Big)-\frac32-\log_2\pi+
\frac1{\log2}\sum_{k\in\ZZ\setminus\{0\}}\frac{L(\chi_k)}
{\chi_k(\chi_k+1)}e^{2k\pi ix}.
$$







\section{Symmetric   signed digit expansions}
\label{signed}








Recently, Heuberger and I 
\cite{HePr01} have considered a symmetric system with
an \textsl{even\/} base $q$ and digits $-\frac q2,\dots,\frac q2$. 
Such a system is a priori redundant because of the 
existence of both $\pm \frac q2$
but made unique by the condition that
$  n=\sum_{j\ge0} \eps_j q^j$,
where $\betrag{\eps_j}\le q/2$ and $\betrag{\eps_j}=q/2$ implies that
$0\le \sign(\eps_j)\eps_{j+1}<q/2$. 
(Equivalent conditions where discussed in 
\cite{HePr01}.)
We call this expansion the \textsl{symmetric
  signed digit expansion} of $n$ and denote it by
$(\dots\eps_2(n)\eps_1(n)\eps_0(n))$. 
For $q=2$, this system was already considered by Reitwiesner in
a computer science context \cite{Reitwiesner60}.
Here is an algorithm to compute it from right to left (Algorithm~1):


\begin{algorithm}
  \caption{Computation of the symmetric  signed digit expansion of $n$}
  \label{alg:relaxed-pseudo-cheub}

  \begin{algorithmic}
    \REQUIRE $n>0$, $q\ge 2$ integers.
    \ENSURE The representation $\eps$.
   
    \STATE $\eps\assign()$;  $m \assign n$
    
    \WHILE{$m>0$}
       \STATE $a\assign (m \bmod q)$
       \IF{$a>q/2$ \OR ($a=q/2$ \AND $\fractional{m/q^2}\ge 1/2$)}
         \STATE $a\assign a-q$
       \ENDIF
       \STATE $m\assign (m-a)/q$; $\eps\assign\eps\append a$
    \ENDWHILE
  \end{algorithmic}
\end{algorithm}

We were able to derive an \textsl{explicit formula\/} for the digit $\eps_r$,
which for $q=2$ is
  \begin{equation*}
    \eps_r=\fl{\frac{n}{2^{r+2}}+\frac56}-
    \fl{\frac{n}{2^{r+2}}+\frac46}-
    \fl{\frac{n}{2^{r+2}}+\frac26}+
    \fl{\frac{n}{2^{r+2}}+\frac16},
  \end{equation*}
 and was already obtained in
  \cite{prodinger162}. For 
  $q=6$ it reads
  \begin{align*}
    \eps_r=&+\fl{y+\tfrac{248}{252}}
    +\fl{y+\tfrac{241}{252}}
    +\fl{y+\tfrac{234}{252}}
    -5\fl{y+\tfrac{228}{252}}
    +\fl{y+\tfrac{221}{252}}
    +\fl{y+\tfrac{214}{252}}\\&
    +\fl{y+\tfrac{206}{252}}
    +\fl{y+\tfrac{199}{252}}
    +\fl{y+\tfrac{192}{252}}
    -5\fl{y+\tfrac{186}{252}}
    +\fl{y+\tfrac{179}{252}}
    +\fl{y+\tfrac{172}{252}}\\&
    +\fl{y+\tfrac{164}{252}}
    +\fl{y+\tfrac{157}{252}}
    +\fl{y+\tfrac{150}{252}}
    -5\fl{y+\tfrac{144}{252}}
    +\fl{y+\tfrac{137}{252}}
    +\fl{y+\tfrac{130}{252}}\\&
    +\fl{y+\tfrac{122}{252}}
    +\fl{y+\tfrac{115}{252}}
    -5\fl{y+\tfrac{108}{252}}
    +\fl{y+\tfrac{102}{252}}
    +\fl{y+\tfrac{95}{252}}
    +\fl{y+\tfrac{88}{252}}\\&
    +\fl{y+\tfrac{80}{252}}
    +\fl{y+\tfrac{73}{252}}
    -5\fl{y+\tfrac{66}{252}}
    +\fl{y+\tfrac{60}{252}}
    +\fl{y+\tfrac{53}{252}}
    +\fl{y+\tfrac{46}{252}}\\&
    +\fl{y+\tfrac{38}{252}}
    +\fl{y+\tfrac{31}{252}}
    -5\fl{y+\tfrac{24}{252}}
    +\fl{y+\tfrac{18}{252}}
    +\fl{y+\tfrac{11}{252}}
    +\fl{y+\tfrac{4}{252}},
  \end{align*}
  where $y=n/6^{r+2}$. In general, it has $q^2$ terms.

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





In a recent paper with Grabner and Heuberger
\cite{GrHePr02} we are addressing the subblock counting problem
in symmetric   signed digit expansions. To announce our principal findings, we need some
notation.
If a block $\seq b=(b_s,\dots ,b_0)$ is given, we denote its
\textsl{value\/} by
$\val(\seq b)=\sum_\ell b_\ell q^\ell$. 

We also use Iverson's notation, popularized in
\cite{Graham-Knuth-Patashnik:1994}: $[P]$
is defined to be 1 if condition $P$ is true, and
0 otherwise. With this notation we can count the number of 
subblock occurrences of $\seq b$ in (the symmetric   signed digit expansions
of) $n$ via
$$
\sum_{k\ge0}
\cond{(\eps_{k+r-1}(n),\ldots,\eps_{k}(n))=\seq b}.
$$

We only consider \textsl{admissible\/} blocks $\seq b$: these blocks
represent the number $\val(\seq b)$ in the
symmetric   signed digit expansion. For interest we note
that there are 
$\frac{2+q}{1+q}q^r-\frac{1}{1+q}(-1)^r
$
admissible blocks of length $r$; this was implicitly proved in
\cite{HePr01}.
We are studying   the quantity
\begin{equation*}
S_{\seq b}(N)=\sum_{n<N}\sum_{k\ge0}
\cond{(\eps_{k+r-1}(n),\ldots,\eps_{k}(n))=\seq b}.
\end{equation*}
This is our main result:

  Let $q\geq2$ be an even integer and $r\geq1$. For an admissible block $\seq
  b=(b_{r-1},\ldots,b_0)$ with $|b_{r-1}|<\frac q2$ and $\seq b\neq0^r$ the
  number of occurrences of the block $\seq b$ in the symmetric signed digit
  expansions of the positive integers less than $N$ satisfies
\begin{equation*}
S_{\seq b}(N)=\frac{Q(b_0)}{q^r(q+1)}N\log_qN+h_0(\seq b)N+
NH_{\seq b}(\log_qN)+o(N),
\end{equation*}
where
\begin{align*}
Q(\eta)=&q+
\begin{cases}
2&\text{for }\eta=0,\\
0&\text{for }\eta=\pm\frac q2,\\
1&\text{else,}\\
\end{cases}\\
H_{\seq b}(x)&=\sum_{k\in\ZZ\setminus\{0\}}h_k(\seq b)e^{2k\pi ix},\notag\\
h_k(\seq b)&=
\frac{\log q}{2k\pi i(\log q+2k\pi i)}\textstyle{
\biggl(\zeta\left(\frac{2k\pi i}{\log q},\cond{\val(\seq b)<0}+q^{-r}\val(\seq
  b)+
  \frac{\Rmin(b_0)}{q^r(q+1)}\right)}\notag\\*
&-\textstyle{
\zeta\left(\frac{2k\pi i}{\log q},\cond{\val(\seq b)<0}+q^{-r}\val(\seq
  b)+
  \frac{\Rmax(b_0)}{q^r(q+1)}\right)\biggr)\text{ for $k\neq 0$},}\notag\\
h_0(\seq b)&=\log_q\Gamma\left(\cond{\val(\seq b)<0}+q^{-r}\val(\seq b)+
  \frac{\Rmin(b_0)}{q^r(q+1)}\right)\notag\\
&-\log_q\Gamma\left(\cond{\val(\seq b)<0}+q^{-r}\val(\seq b)+
  \frac{\Rmax(b_0)}{q^r(q+1)}\right)\notag\\
&-\frac{Q(b_0)}{q^r(q+1)}\left(r+\frac12+\frac1{\log q}-\frac 1{q+1}\right)+
\frac1{q^{r-1}(q+1)},\notag\\
\Rmin(\eta)=&-\frac q2-\cond{(\eta-1)\bmod q\geq\frac q2},\qquad
\Rmax(\eta)=\frac q2+\cond{\eta\bmod q<\frac q2}.
\end{align*}
The function $H_{\seq b}(x)$ is a periodic continuous function of period $1$
and mean $0$. As usual $\zeta(s,x)$ denotes the Hurwitz $\zeta$--function.


The case of blocks $\seq b$ with most significant digit $b_{r-1}=\pm\frac q2$
can also be obtained from that, by a trivial argument taking differences.

The instance $r=1$ (counting digits) was discussed in 
\cite{HePr01}, although 
without mentioning the periodic fluctuations in explicit form.
Thuswaldner \cite{Thuswaldner99} has used Dirichlet series and 
the Mellin--Perron
summation formula to exhibit this fluctuating behaviour in the case $q=2$
and $r=1$.

The analysis is based on the Mellin--Perron formula, but with
a slight twist:
\begin{equation*}
\sum_{n<N}(N-n)a_n=\frac1{2\pi i}\int\nolimits_{c-i\infty}^{c+i\infty}
\sum_{n\ge1}\frac{a_n}{(n-\alpha)^s}(N-\alpha)^{s+1}\frac{ds}{s(s+1)},
\end{equation*}
where $0\leq\alpha<1$ and $c$ is in the half-plane of absolute convergence of
the Dirichlet series. This  slightly
more general situation $0\leq\alpha<1$ was discussed in
\cite{GrKiPr98}. Without this version with the
parameter $\alpha$, one could still proceed successfully, as in
\cite{Thuswaldner99}, but that would be considerably more cumbersome and
less elegant.



\section{Representations of natural numbers as sums of 3 squares}

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

\begin{equation*}
Q(m)=\sum_{0<n\le m}\cond{\text{$n$ representable as a sum of 3 squares}}
=m-\sum_{0<n\le m}\kappa(n),
\end{equation*}
with $\kappa(n)=1$ if $n=4^i(8k+7)$, $\kappa(n)=0$ otherwise. It is
a good idea to separate the main term and write $Q(m)=\frac56m+\Delta(m)$.
Osbaldestin and Shiu provide a Delange type analysis of the following formula:
\begin{equation*}
\frac1N\sum_{0\le n <N}\Delta(n)=\frac38\log_4N+F(\log_4N)+\frac18
\cond{\text{$N$ is odd}},
\end{equation*}
with $F(x)=\sum_{k\in\ZZ}f_ke^{2\pi ikx}$ and
\begin{align*}
f_0&=-\frac{31}{48}-\frac{3}{8\log4}-\frac1{\log4}
\Big(\zeta'(0,\tfrac{7}{16})+\zeta'(0,\tfrac{15}{16})\Big),\\
f_k&=-\frac{1}{\log4}\frac1{\chi_k(1+\chi_k)}
\Big(\zeta(\chi_k,\tfrac{7}{16})+\zeta(\chi_k,\tfrac{15}{16})\Big),\quad k\neq0,
\quad \chi_k=\frac{2\pi i k}{\log4}. \\
\end{align*}
It was announced already in 
\cite{FlGrKiPrTi94} that a proof of this result using the Mellin--Perron
summation formula would be possible, and Marko Riedel has worked out
the details in his Master's thesis \cite{Riedel:thesis}.



















\section{The average number of registers to evaluate a binary tree of size
 $n$}\label{register:section}

The function ``number of registers'' {\it reg} 
is given recursively by $\reg(\square)=0$ and
\begin{align*}
\reg\bigg(
 \hspace*{-2.3ex}\raisebox{-1.8ex}{
       \unitlength 0.30mm \linethickness{0.4pt}
       \begin{picture}(40.5,24)
          \put(24.5,20){\makebox(0,0)[cc]{$\bigcirc$}}
          \put(22,18){\line(-1,-1){12}}
          \put(27,18){\line(1,-1){12}}
          \put(10,1){\makebox(0,0)[cc]{$t_{1}$}}
          \put(39.5,1){\makebox(0,0)[cc]{$t_{2}$}}
       \end{picture}}
\hspace*{1.1ex}
\bigg)&=
\begin{cases}
\max\{\reg(t_1), \reg(t_2)\} \quad&\text{if } \reg(t_1)\ne \reg(t_2),\\
1+\reg(t_1) \quad&\text{otherwise. }
\end{cases}
\end{align*}
The problem is the evaluation of
$R_n$, the average value of the function
{\it reg}, based on the set of binary trees of size $n$.
This was first studied in \cite{FlRaVu79, Kemp79}; for a tutorial
see \cite{Prodinger83}.
We have
$$
R_n=\frac{1}{b_n} [z^n]E(z),\qquad\text{with}\qquad
E(z)=\sum_{n\ge 0}z^n\sum_{ \text{$t$ of size $n$}}\reg(t)
$$
and $b_n=\frac1{n+1}\binom{2n}n$ being the number of binary trees
with $n$ nodes. 
One can derive the following for the function $E(z)$, using the substitution
$z=u/(1+u)^2$:

\begin{align*}
E(z)&=\frac{1-u^2}{u}\sum_{p\ge 1}\frac{u^{2^p}}{1-u^{2^p}}
=\frac{1-u^2}{u}\sum_{p\ge 1}
\sum_{\lambda \ge 1}u^{\lambda 2^p}=\frac{1-u^2}{u}\sum_{n\ge 2}v_2(n)u^n,
\end{align*}
%
where $v_2(n)$ is the exponent of 2 in the prime number  decomposition of
 $n$.
If we write in a unique way $n=2^m(1+2i)$, ($m\ge1$, 
$i\ge 0$), we have $v_2(n)=\sum\nolimits_{p=1}^m1=m$.
%
The quantity $v_2(n)$ 
(which we have seen already in Section~\ref{Mellin:Perron})
is often called ``dyadic valuation,''
for obvious reasons.
One can get the coefficients, e.\;g., using the Lagrange inversion
formula:
\begin{equation*}
[z^n]E(z)=\sum_{k\ge1}v_2(n)\bigg[\binom{2n}{n-k}
-2\binom{2n}{n-k-1}+\binom{2n}{n-k-2}\bigg].
\end{equation*}
One strategy to proceed is the following (that was the method
of Flajolet, Raoult, and Vuillemin): One application of
partial summation brings, via
$\nu(k)=k-\sum_{j\le k}v_2(j)$, the sum of digits function in, 
and a second application of partial summation
makes  the summatory function of
the sum--of--digits function appear, which, according to Delange's
analysis, is completely known! That means on the other side
that the second difference of the binomial coefficients becomes
eventually a fourth difference, but that causes no problems. 
The final result is this:
The average number $R_n$ 
of registers to evaluate a binary tree of size
$n$ satisfies
$$
R_n=\log_4n+D(\log_4n)+o(1),
$$
where $D(x)$
is a continuous periodic function of period 1; this function
can be expanded in a  Fourier series as
$
D(x)=\sum_{k\in\Bbb Z}d_ke^{2k\pi ix}$,	
with
$$
d_0=\frac 12-\frac{\gamma}{2\log2}
-\frac{1}{\log 2}+\log_2\pi
$$
and
$$
d_k=\frac{1}{\log2}\zeta(\chi_k)\Gamma\Big(\frac{\chi_k}{2}\Big)(\chi_k-1),
\quad k\ne 0, \quad \chi_k=\frac{2\pi ik}{\log2}.
$$




Another strategy, used by Kemp, is as follows: Approximation
of the binomial coefficients leads eventually to the study
of series of the type
\begin{equation*}
f(x):=\sum_{k\ge1}v_2(k)e^{-k^2x^2};
\end{equation*}
the Mellin transform then brings in Dirichlet series
$g(s):=\sum_{k\ge1}v_2(k)k^{-s}$;
but this one is easily evalutated, using $v_2(2k)=1+v_2(k)$
and $v_2(2k+1)=0$:
\begin{equation*}
g(s)=\sum_{k\ge1}\big(1+v_2(k)\big)(2k)^{-s}=2^{-s}\big(\zeta(s)+g(s)\big),
\end{equation*}
 from which one gets $g(s)=\zeta(s)/(2^s-1)$.

A third strategy is more on the lines of \cite{FlPr86} and based
on singularity analysis of generating functions:
One must study $E(z)$ for $z\to \frac 14$, i.\;e., for $u\to 1$,
and sets
$u=e^{-t}$ and considers $E(z)$ for $t\to 0$. 
The second factor of $E(z)$, which is denoted by $V(t)$, is the challenging one.
The Mellin transform of $V(t)$ is denoted by $V^*(s)$:
\begin{gather*}
V^*(s)
=\int_0^\infty x^{s-1}\sum_{k\ge 1}v_2(k)e^{-kx}dx
=\sum_{k\ge 1}v_2(k)k^{-s}\int_0^\infty x^{s-1}e^{-x}dx.
\end{gather*}
This gives
$
V^*(s)=\frac{\Gamma(s)\zeta(s)}{2^s-1}$.
The Mellin inversion formula then leads to
$$
V(t)=\frac{1}{2\pi i}\int\nolimits_{2-i\infty}^{2+i\infty}V^*(s)t^{-s}ds,
$$
and we shift the line of integration to the left, 
taking the residues of the
integrand $V^*(s)t^{-s}$ into account. Using
some  classical expansions we get

\begin{align*}
V(t)&\sim \frac 1t +\frac 12\log_2t-\frac 12\log_22\pi +\frac 14
+\frac{\gamma}{2\log 2}
+\frac{1}{\log 2}\sum_{k\ne 0}\Gamma(\chi_k)\zeta(\chi_k)t^{-\chi_k}+\dots
\end{align*}
which gives the local expansion for the 
function $E(z)$; the rest is then singularity analysis of generating
functions \cite{FlOd90}.


\section{ Odd--even merge}
\label{odd-even-merge:section}

In the analysis of a sorting algorithm (Batcher's odd--even merge
\cite{Knuth98}), one has
to consider the quantity
$$
B_n=\sum_{k\ge 1}\frac{\binom{2n}{n-k}}{\binom{2n}n}\Big(2F(k)+k\Big),
$$
representing the number of exchanges in the odd--even merge
of
$2n$ elements. In this equation,
$F(k)=\sum_{0\le j<k}f(j)$
and $f(j)$ is the number of digits ``1'' in the Gray code representation
of $j$.
The numbers $\vartheta(j):=f(j)-f(j-1)$
equal $\pm1$: if $k$ is of the form $k=2^m(4i+1)$, $\vartheta
(k)=1$; if $k$ is of the form $k=2^m(4i+3)$, $\vartheta(k)=-1$.
We might recognize a great similarity between $\vartheta(k)$ and $v_2(k)$
 from Section~\ref{register:section}. 

Indeed, there are again basically 3 lines of attack:
The Flajolet--Ramshaw approach \cite{FlRa80} uses partial summation
and uses an explicit result for the summatory function of the 
sum of digits function in the Gray code representation,
as derived in Section~\ref{Mellin:Perron};
this is analogous to \cite{FlRaVu79}. The next one, analogous
to \cite{Kemp79}, was used by Sedgewick \cite{Sedgewick78}:
Approximating binomial coefficients, one has to study series
\`a la 
\begin{equation*}
f(x):=\sum_{k\ge1}\vartheta(k)e^{-k^2x^2},
\end{equation*}
or, after using  Mellin transforms,  Dirichlet series like
$g(s):=\sum_{k\ge1}\vartheta(k)k^{-s}$,
but this one is again easily evaluated:
\begin{align*}
g(s)=\sum_{m,i\ge0}\big(2^m(4i+1)\big)^{-s}-\sum_{m,i\ge0}\big(2^m(4i+3)\big)^{-s}
=\frac{1}{2^s(2^s-1)}\Big[\zeta(s,\tfrac14)-\zeta(s,\tfrac34)\Big],
\end{align*}
where the Hurwitz $\zeta(s,a)$-function  is defined by
$\zeta(s,a)=\sum_{n\ge 0}(n+a)^{-s}$
for $\Re (s)>1$. Recall that the function from Section~\ref{Mellin:Perron}
can be expressed as $L(s)=4^{-s}\big[ \zeta(s,\frac14)-\zeta(s,\frac34)\big]$.

\smallskip

The third approach, using singularity analysis of generating
functions, is presented in the tutorial \cite{Prodinger83}:
One has to study the function
$$\frac{u(1+u)}{(1-u)^3}
\sum_{i\ge 1}\vartheta(i)u^i
$$
near $u=1$. Eventually one finds:

 The average number of exchanges in the odd--even merge
of $2n$ elements satisfies
$$
B_n\sim\frac 14n\log_2n+nB\big(\log_4n\big),
$$
where $B(x)$ is a continuous periodic function of period 1; this
function can be expanded as a Fourier series
$
B(x)=\sum_{k\in \Bbb Z}b_ke^{2k\pi ix}$,
with
$$
b_0=-\frac{1}{2\log 2}
-\frac{\gamma}{4\log 2}-\frac 34+2\log_2\Gamma\Big(\frac14
\Big)-\log_2\pi
$$
and for $k\ne 0$
$$
b_k=\frac{1}{\log 2}\zeta\big(\chi_k,\tfrac 14\big)\frac
{\Gamma(\chi_k/2)}{1+\chi_k}.
$$


\section{A problem of Yekutieli and Mandelbrot}
\label{Yekutieli}


The following  problem was left open (and attacked empirically)
in \cite{YeMa94} and later solved
in \cite{Prodinger97}. 

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


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

Now, let $w_{p,k,n}$ be the number of binary trees with $n$ nodes, 
register function $p$, and  Yekutieli--Mandelbrot--parameter $k$, and let
\begin{equation*}
W_p(z,y)=\sum_{n,k\ge0}w_{p,k,n}\,y^kz^n
\end{equation*}
be its bivariate generating function.

 To find the expected values, we have to work with
$T_p(z)=\frac{\partial}{\partial y}W_p(z,y)|_{y=1}$ and
$T(z)=\sum_{p \ge 1 }T_p(z)$.
The coefficient of $z^n$ in $T(z)$, divided by $\frac{1}{n+1}\binom{2n}{n}$,
is the expected value sought by Yekutieli and Mandelbrot.
One finds for $p\ge1$
\begin{equation*}
W_p(z,y)=zy^2R_{p-1}^2(z)+2zyW_p(z,y)R_{p-1}(z)+2zW_p(z,y)\big(B(z)-
S_{p-1}(z)\big),
\end{equation*}
with $R_p(z)$ being the generating function of binary trees and
register function $=p$, and $S_p(z)=\sum_{j\ge p}R_j(z)$.
Therefore 
\begin{equation*}
T_p(z)=2zR_{p-1}^2(z)+2zR_p(z)R_{p-1}(z)+2zT_p(z)\big(B(z)-
S_{p}(z)\big),
\end{equation*}
and eventually (again with $z=u/(1+u)^2$)
\begin{align*}
T(z)&=2u+2\frac{1-u^2}{u}
\sum_{p\ge1}
\frac{u^{3\cdot2^{p-1}}}{{(1+u^{2^{p}})}^2(1-u^{2^{p}})}.
\end{align*}
One has to study the series
\begin{align*}
\sigma&=\sum_{p\ge1}
\frac{u^{3\cdot2^{p-1}}}{{(1+u^{2^{p}})}^2(1-u^{2^{p}})}
=\sum_{p\ge0, k\ge1}u^{2^p(2k+1)}(-1)^{k-1}\left\lfloor\tfrac{k+1}{2}
\right\rfloor\\
&=-\sum_{p,k\ge0}
ku^{2^p(4k+1)}+\sum_{p,k\ge0}
(k+1)u^{2^p(4k+3)}.
\end{align*}
Now, one performs a Mellin transform analysis in order to find
the local behaviour
\begin{equation*}
T(z)\sim 3 -\left(\frac{4{\mathcal {C}}}{(\log2)\pi}+5\right)\sqrt{1-4z}-
\frac{8}{\log2}\sum_{k\ne0}{\Gamma(\chi_k)}\beta(\chi_k-1)
(1-4z)^{(1-\chi_k)/2}.
\end{equation*}
Here, $\beta(s)=\zeta(s,\tfrac14)-\zeta(s,\tfrac34)$, which is the
function that appeared already in the odd--even merge problem,
$\chi_k={2\pi ik}/{\log2}$, and
$\mathcal{C}=\sum_{k\ge0}{(-1)^k}/{(2k+1)^2}=0.9159655942\dots
$ is Catalan's constant. Consequently we get this result:
 The average value of the Yekutieli--Mandelbrot 
parameter, if all binary trees of size $n$
 are considered to be equally likely, is given by
\begin{equation*}
\frac{2{\mathcal {C}}}{(\log2)\pi}+\frac 52+\delta(\log_4n)+{\mathcal{ O}}\Big(
\frac 1n\Big).
\end{equation*}
The periodic function $\delta(x)$ has mean value 0 and admits the
following representation as a Fourier series,
\begin{equation*}
\delta(x)=-
\frac{2}{\log2}\sum_{k\ne0}
(\chi_k-1)\Gamma\Big(\frac{\chi_k}{2}\Big)\beta(\chi_k-1)
e^{ 2k\pi ix}.
\end{equation*}

One could also perform an analysis along the lines of Kemp
resp. Sedgewick \cite{Kemp79, Sedgewick78}; it would be based
on the exact formula
\begin{equation*}
[z^n]T(z)=\frac{2}{n+1}\binom{2n}{n}+2\sum_{m\ge1}\psi(m)
\left[
\binom{2n}{n+1-m}-2\binom{2n}{n-m}+\binom{2n}{n-1-m}
\right]
\end{equation*}
with
$
\psi(m)=\begin{cases} 
	-k\qquad &\text{if } m=2^i(4k+1)
		\text{\quad for some $i$ and $k$,}\\
        k+1\qquad &\text{if } m=2^i(4k+3)\text{\quad for some $i$ and $k$.}
        \end{cases}
$









\section{Missing digits}\label{missing}

Interesting phenomena occur if several digits are forbidden. 
We describe here the instance of $q=3$ and digits $\{0,2\}$, 
i.\;e., the digit $1$ is forbidden. The set of strings
$0.a_1a_2\ldots$, with $a_i\in\{0,2\}$ is the classical
\textsl{Cantor set}. Thus considering $2\sum_{i\ge1}{X_i}3^{-i}$,
where the $X_i$ are independent and identically
distributed  with probability distribution
$\P\{X=0\}=\P\{X=1\}=1/2$, we get a probability distribution
on the interval $[0,1]$ which is conveniently called 
\textsl{Cantor distribution}. In \cite{GrPr96}, the moments of
a slightly more general distribution were investigated,
motivated by an earlier paper of Lad and Taylor \cite{LadTay92}; we sketch
the procedure. Denote $a_n$ the $n$th moment of the
Cantor distribution; it is not hard to see that
\begin{equation*}
a_n=\frac{1}{2(3^{n}-1)}\sum_{i=0}^{n-1}\binom ni2^{n-i}a_i,\quad n\ge1,
\quad a_0=1.
\end{equation*}
If one rewrites it as
$(2-3^{-n})a_n=\sum_{i=0}^{n}\binom ni2^{n-i}a_i$
and introduces the exponential generating function
$A(z)=\sum_{n\ge0}a_nz^n/n!$, it translates into
\begin{equation*}
2A(z)-2-A(\tfrac z3)+1=e^{2z/3}A(\tfrac z3)-1,
\end{equation*}
or
\begin{equation*}
A(z)=\frac{1+e^{2z/3}}{2}A(\tfrac z3)=\prod_{k\ge1}
\frac{1+e^{2z/3^k}}{2};
\end{equation*}
the last step was by iteration of the functional equation.
Slightly more useful than this infinite product is the
\textsl{Poisson transformed\/} generating function
$B(z)=e^{-z}A(z)$, since by a process called
\textsl{Depoissonization} one finds that $a_n\sim B(n)$.
There is a well written survey paper on the subject
by Jacquet and Szpankowski \cite{JaSz98}. We get
\begin{equation*}
B(z)=\frac{1+e^{-2z/3}}{2}B(\tfrac z3)=\prod_{k\ge1}
\frac{1+e^{-2z/3^k}}{2}.
\end{equation*}
To find the asymptotic behaviour of $B(z)$ for large $z$
(and thus $B(n)$ and thus $a_n$) we  compute the
\textsl{Mellin transform\/} $B^*(s)$ of $B(z)$, viz.
\begin{equation*}
B^*(s)=\frac12 3^sB^*(s)+\frac12\int_0^\infty B (\tfrac z3)e^{-2z/3}z^{s-1}dz,
\end{equation*}
or
\begin{equation*}
B^*(s)=\frac1{2-3^s}\int_0^\infty 
\prod_{k\ge2}
\frac{1+e^{-2z/3^k}}{2}\;e^{-2z/3}z^{s-1}dz.
\end{equation*}
The standard reference for the Mellin transform in the context of
asymptotic enumeration is \cite{FlGoDu95}. The Mellin inversion formula
gives
\begin{equation*}
B(z)=\frac{1}{2\pi i}\int_{c-i\infty}^{c+i\infty}B^*(s)z^{-s}ds,
\end{equation*}
where  the constant $c$ might be chosen to be $-1/2$. Now one shifts
the line of integration to the right and collects negative residues. 
They come from the solutions of $2-3^s=0$, i.\;e., $s=\log_32+2\pi ik/\log3$,
for $k\in \ZZ$.
If one calls them $f_k$, then 
$B(n)\sim \sum_{k\in\ZZ}f_k n^{-\log_32-2\pi ik/\log3}$, which
is of the form $n^{-\log_32}\delta(\log_3n)$, with a periodic
function $\delta(x)$ of period $1$. Typically, the amplitudes of
such periodic functions are quite small, so the 
most interesting term is obtained for $k=0$.
The negative residue at $s=\log_32$ is
\begin{equation*}
\frac1{2\log3}\int_0^\infty 
\prod_{k\ge2}
\frac{1+e^{-2z/3^k}}{2}\;e^{-2z/3}z^{\log_32-1}dz=0.734\ldots\;,
\end{equation*}
and so $a_n\sim B(n)\simeq f_0 {n^{-\log_32}}\approx 0.734\, n^{-0.631}$.
\medskip

Another interesting question was triggered by Hosking
\cite{Hosking94} and solved in \cite{KnPr96}:

\noindent
Assume that we draw $n$ random  numbers (independently)
according
to the Cantor distribution. What is the expected value of
the minimum of them? If one would draw from the interval
$[0,1]$ according to the uniform distribution, then it
is fairly easy to see that it is $1/(n+1)$. If we call that minimum
$a_n$, we get
\begin{equation*}
a_n=\frac13 2^{-n}\sum_{k=1}^{n}\binom nk a_k+\frac132^{-n}\big(2+a_n\big),
\quad a_0:=0.
\end{equation*}
This recursion is obtained by observing that the minimum is obtained
 from one of the random strings starting with a zero, provided there
is one. In the rare event that all strings start with 2, this first
digit contributes $2/3$ (additively), and the minimum is sought from 
all the $n$ participants. Rearranging the recursion and introducing
the exponential generating function $A(z):=\sum_{k\ge0}a_kz^k/k!$,
one finds
\begin{equation*}
A(2z)=\frac13(1+e^z)A(z)+\frac23(e^z-1).
\end{equation*}
Now we introduce, following Knuth \cite{Knuth98}, the function
$\hat A(z):=A(z)/(e^z-1)=\sum_{k\ge0}\hat a_kz^k/k!$ and
get 
\begin{equation*}
\hat A(2z)=\frac13 \hat A(z)+\frac23\frac1{e^z+1},
\end{equation*}
 from which one finds
\begin{equation*}
\hat a_n=-\frac23\frac{B_{n+1}}{n+1}\frac{2^{n+1}-1}{2^n-\tfrac13},
\end{equation*}
with Bernoulli numbers $B_n$. Hence one gets the explicit solution
\begin{equation*}
a_n=-\frac23\sum_{k=0}^{n-1}\binom nk 
\frac{B_{k+1}}{k+1}\frac{2^{k+1}-1}{2^k-\tfrac13}.
\end{equation*}
In order to study the asympotic behaviour of that quantity
one can use Rice's method \cite{FlSe95}, which is related to 
Mellin transforms, and eventually write
\begin{equation*}
a_n=-\frac{2}{3(n+1)}\cdot\frac1{2\pi i}\int_{\mathcal {C}}
\frac{(-1)^nn!}{z(z-1)\dots(z-n)}\big(-z\zeta(1-z)\big)\frac{2^z-1}{2^{z-1}-\frac13}
dz,
\end{equation*}
where the contour $\mathcal{C}$ encloses the poles $1,2,\dots,n-1$ and no
others.
Deforming the contour of integration reduces the problem to the computation
of residues; the dominant ones are the solutions of $2^{z-1}-\frac13=0$,
i.\;e., $1-\log_23+2k\pi i/\log2$, for all $k\in\ZZ$. Eventually one finds,
apart from a periodic function as above, that
\begin{equation*}
a_n\simeq  n^{\log_23}\frac{2}{3\log2}\Gamma(\log_23)\zeta(\log_23).
\end{equation*}

\medskip

Another type of moments are \textsl{Cantor's singular moments\/}:
Consider the unique non--decreasing function on $[0,1]$ such that, if
$x=2\sum_{j\ge1}{\eps_j3^{-j}}$ with $\eps_j\in\{0,1\}$, then
$F(x)=\sum_{j\ge1}{\eps_j2^{-j}}$. It was a question in the 
problem section of the American Mathematical Monthly 
\cite{AMM99} to compute the moments; the following solution
came out:
\begin{equation*}
J_n=\int_0^1\big(F(x)\big)^ndx=\frac{2}{3(n+1)}\sum_{j=0}^n\binom{n+1}{j}
\frac{B_j}{3\cdot 2^{j-1}-1}\quad\text{for $n\ge1$ and $J_0=1$};
\end{equation*}
the case $n=-1$ was left open and treated by me in \cite{Prodinger00}:
Since one can show that
$J_{-1}=\sum_{n\ge0}J_n$,
and, again by Rice's method, 
\begin{align*}
J_n&=\frac{2}{3}\cdot
\frac{1}{2\pi i}\int_{-\frac12-i\infty}^{-\frac12+i\infty}
\frac{\Gamma(n+1)\Gamma(1-s)}{\Gamma(n+2-s)}
\frac{\zeta(1-s)}{3\cdot2^{s-1}-1}\,ds,
\end{align*}
one finds
\begin{align*}
\sum_{n=0}^NJ_n&=J_0+
\frac{2}{3}\cdot
\frac{1}{2\pi i}\int_{-\frac12-i\infty}^{-\frac12+i\infty}
\frac{\Gamma(N+2)\Gamma(1-s)}{\Gamma(N+2-s)s}
\frac{\zeta(1-s)}{3\cdot2^{s-1}-1}\,ds\\
&-\frac{2}{3}\cdot
\frac{1}{2\pi i}\int_{-\frac12-i\infty}^{-\frac12+i\infty}
\frac{\Gamma(2)\Gamma(1-s)}{\Gamma(2-s)s}
\frac{\zeta(1-s)}{3\cdot2^{s-1}-1}\,ds.
\end{align*}
Now we perform the limit $N\to\infty$ and get eventually (the computations
are not displayed here):
\begin{align*}
\sum_{n\ge0}J_n
&=\frac43
+\frac{2}{3}\sum_{k,m\ge1}3^{-k}\cdot
\frac{1}{2\pi i}\int_{\frac32-i\infty}^{\frac32+i\infty}
\frac{1}{s(s-1)}
\Big(\frac{2^k}{m}\Big)^s\,ds\\
&=-\frac13+\frac{2}{3}\sum_{k\ge1}
\Big(\frac23\Big)^kH_{2^k}=
3.36465\;07281\;00925\;16083\;89349\;6289
\dots,
\end{align*}
with harmonic numbers $H_n=\sum_{1\le k\le n}\frac1k$.


\smallskip

More general results of this type are currently worked out
in collaboration with F.~Bassino \cite{BaPr02}.


\section{Von Neumann's addition algorithm}

This brief description is based on a recent paper with
Heuberger \cite{HePr01b}.


Knuth \cite{Knuth78} has analyzed von Neumann's addition algorithm: 
Assume that two integers are given in $q$--ary notation,
say $(\dots y_2y_1y_0)_q$ and $(\dots y_2y_1y_0)_q$; then the integer $(\dots
s_2s_1s_0)_q$ with $s_i=(x_i+y_i)\mod q$ is formed, as well as $(\dots
c_2c_1c_0)_q$ (the carries), where $c_{i+1}=[x_i+y_i\ge q]$.
  The process is iterated by adding $(\dots s_2s_1s_0)_q$ with
$s_i=(x_i+y_i)\mod q$ and $(\dots c_2c_1c_0)_q$ until the string of carries
contains only zeros.
%
Knuth studied the average number of iterations, assuming two random integers
with $n$ digits.  The result is $\sim\log_qn$; 
it turns out that the longest subsequence of the
form $\dots i(q-1)(q-1)\dots(q-1)j\dots$ with $i\ne q-1$ and $j\ge q$ in
$\big(\dots (x_2+y_2)(x_1+y_1)(x_0+y_0)\big)_q$ is responsible for the number
of iterations.
We extended Knuth's results to other positional number
systems, namely for the basis $q$
and the set of $q$ digits $\{d,d+1,\dots,d+q-1\}$.  
 Note carefully that carries might now be $\pm1$ and that
the sequence of sums might be oscillating, being smaller or larger than the
true value of the sum of the two integers. This is in sharp contrast to the
traditional $q$--ary system, where the sums are monotonically increasing until
the algorithm stops.  Thus it is perhaps natural that the description of
subsequences being responsible for the number of iterations is significantly
more complicated. Here is an example for $q=5$, $d=-1$, and $\bar 1=-1$:
%(Table on the next page).


\begin{table}[htbp]
  \begin{center}      \def\1{\bar 1} \setlength{\extrarowheight}{2pt}
$$    \begin{array}{>{(}r<{)_{(5,-1)}}@{\;=\;}>{(}r<{)_{(5,-1)}}@{\;=\;}r}
      12\1\1\113& \dots x_2x_1x_0&21108\\
      22\10\123&  \dots y_2y_1y_0&36863\\\hline
      3\13\1331& \dots z_2z_1z_0&45591\\
      1\10\1010&\dots c_2c_1c_0&12380\\\hline
      \13333\11& \dots z_2z_1z_0&-3929\\
      1\10\10100&\dots c_2c_1c_0&61900\\\hline
      13323\1\11&\dots z_2z_1z_0&135971\\
      \10001000&\dots c_2c_1c_0&-78000\\\hline
      0332\1\1\11&\dots z_2z_1z_0&57346\\
      00010000&\dots c_2c_1c_0&625\\\hline
      0333\1\1\11&\dots z_2z_1z_0&57971\\
      00000000&\dots c_2c_1c_0&0 
    \end{array}$$
  \end{center}
\end{table}





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

\begin{align*}
G^{\le k}(z)=\frac{s_0(z)+(z/q)^{k}r_1(z)+(z/q^2)^{k}r_2(z)+(z^2/q^3)^{k}r_3(z)}
{(1-z)s_0(z)+(z/q)^{k}s_1(z)+(z/q^2)^{k}s_2(z)+(z^2/q^3)^{k}s_3(z)},
\end{align*}
where $s_0(z)=-2q^4(q-1)(q^2-z(1-d))(q^2-z(q+d))$. The terms $r_1(z)$, $r_2(z)$,
$r_3(z)$, $s_1(z)$, $s_2(z)$, $s_3(z)$ are polynomials in $z$, $q$, $d$ which
are independent of $k$. 

 From this one can derive, essentially by bootstrapping, approximations, and
Mellin transforms, that the expected number $t_n$ of carry propagations 
satisfies
  \begin{equation*}
    t_n=\log_qn + \log_q\delta +\frac{\gamma}{\log
      q}+\frac12+
    \psi(\log_q n+\log_q\delta)
    + O\left(\frac{\log^4 n}{n}\right),
  \end{equation*}
  where ${
    \delta=\frac{(q^3+(2d-2)q^2+(2d-1)(d-1)q-(d-1)d)(q-1)(q+1)}
    {2(q^2-q-d)(q^2+d-1)}}$
  and $\psi(x)$ is again a periodic function.

\medskip

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



\section{Mergesort}

Because of space restrictions, we cannot describe the algorithm
and/or any details. Basically, there is a top--down version where
one needs to study functions like
\begin{align*}
(k+1)n-2(2^{k+1}-1)+2\sum_{0\le j\le k}\frac{2^j}{\fl{\frac n{2^{j+1}}}+2}+
2\sum_{0\le j\le k}\frac{(1-b_j)\big(2^j-(b_{j-1}\dots b_0)_2\big)}
{\big(\fl{\frac n{2^{j+1}}}+1\big)\big(\fl{\frac n{2^{j+1}}}+2\big)},
\end{align*}
where $(b_k\dots b_0)_2$ is the binary representation of $n$. This can
be efficiently done by a method introduced by Flajolet and Golin
\cite{FlGo94}.
This worked well because such quantities were obtained by so--called
divide--and--conquer recursions.

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


\section{Jump interpolation search trees}

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

\begin{equation*}
\eps+(\tfrac{q}2+L+\tfrac{-q}2+\bar L)
\Big(L\tfrac{q}2+0\tfrac{q}2+
\bar L\tfrac{-q}2+0\tfrac{-q}2+L+\bar L+0\Big)^*
\end{equation*}
with $L=\{1,\dots,\frac q2-1\}$ and $\bar L=\{-\frac q2+1,\dots,-1\}$,






%
To mark the length of the representations by $z$ and the depth
by $u$, we replace $L$ and $\bar L$ by $(\frac q2-1)zu$,
$\pm \frac q2$ by $zu$, and $0$ by $z$, and of course
$f^*$ by $1/(1-f)$. The coefficient of $z^n$ then refers to words
of length $n$; since we are interested in words of length $\le n$,
we divide the result by $1-z$ and obtain
\begin{equation}\label{qpaul}
\frac{1+(-1+2u )z-u(uq-2u+2 ){z}^{2}}
{(1-z)(1+(2u-1-uq)z-u(uq-2u+2){z}^{2})}.
\end{equation}
 From this, we get first, by setting $u=1$, that the number of words
of length $\le n$ is given by
\begin{equation}\label{den}
\frac{q^2}{(q+1)(q-1)}q^n+\frac{q-2}{2(q-1)}-\frac{q}{2(q+1)}(-1)^n.
\end{equation}
Differentiating (\ref{qpaul}) with respect to $u$, and then setting
$u=1$ leads to 
$
\frac{zq(1-z+(q-2)z^2)}{(1-z)(1+z)^2(1-zq)^2}$,
and the coefficient of $z^n$ in it is given by
\begin{equation}\label{num}
\textstyle{\Big[{\frac {q ({q}^{2}-2 )}{ (q-1 )
 (q+1 )^{2}}}n+{\frac {q ({q}^{2}-q+2 )}{ (q-1 )^{2} (q+1
 )^{3}}}\Big]q^n}
+\displaystyle{\frac{q(q-2)}{4(1-q)^2}}-
\textstyle{
\Big[{\frac {{q}^{2}}{ 2(q+1 )^{2}}}n
+{\frac { ({q}^{2}+3q+6 )q}{ 4(q+1 )^{3}}}\Big]}(-1)^n.
\end{equation}
Taking the quotient of (\ref{num}) and (\ref{den}) gives us then
that the average depth of a random node in the tree is 
\begin{equation*}
\frac{q^2-2}{q(q+1)}n-\frac{q^2-q+2}{q(q+1)^2(q-1)}+o(1);
\end{equation*}
for $q=2$, we get again the old result $n/3$ from \cite{m_paul}.




%%%%%%%%%%%%%%%%%%%% REFERENCES %%%%%%%%%%%%%%%%%%%%%
%\bibliography{C:/texfiles2002/resume}

{\small
\begin{thebibliography}{10}

\bibitem{BaPr02}
F.~Bassino and H.~Prodinger.
\newblock $(q,\delta)$-numeration systems with missing digits.
\newblock {\em In preparation}, 2002.

\bibitem{ChHwCh99}
W.~M. Chen, H.~K. Hwang, and G.~H. Chen.
\newblock The cost distribution of queue-mergesort, optimal mergesorts, and
  power-of-2 rules.
\newblock {\em J. Algorithms}, 30:423--448, 1999.

\bibitem{Delange75}
H.~Delange.
\newblock Sur la fonction sommatoire de la fonction somme des chiffres.
\newblock {\em Enseignement Math\'ematique}, 21:31--47, 1975.

\bibitem{DeKr95}
L.~Devroye and P.~Kruszewski.
\newblock A note on the {H}orton--{S}trahler number for random trees.
\newblock {\em Inform. Process. Lett.}, 56:95--99, 1995.

\bibitem{DeKr96}
L.~Devroye and P.~Kruszewski.
\newblock On the {H}orton--{S}trahler number for random tries.
\newblock {\em RAIRO Inform. Th\'eor. Appl.}, 30:443--456, 1996.

\bibitem{AMM99}
H.~G. Diamond and B.~Reznick.
\newblock Problems and solutions.
\newblock {\em American Mathematical Monthly}, 106:175--176, 1999.

\bibitem{Doetsch72}
G.~Doetsch.
\newblock {\em Handbuch der {L}aplace-{T}ransformation, 3 volumes}.
\newblock Birkh\"auser Verlag, Basel, 1972.

\bibitem{FlGo94}
P.~Flajolet and M.~Golin.
\newblock Mellin transforms and asymptotics. {T}he mergesort recurrence.
\newblock {\em Acta Inform.}, 31:673--696, 1994.

\bibitem{FlGoDu95}
P.~Flajolet, X.~Gourdon, and P.~Dumas.
\newblock Mellin transforms and asymptotics: {H}armonic sums.
\newblock {\em Theoretical Computer Science}, 144:3--58, 1995.

\bibitem{FlGrKiPrTi94}
P.~Flajolet, P.~Grabner, P.~Kirschenhofer, H.~Prodinger, and R.~Tichy.
\newblock {M}ellin transforms and asymptotics: Digital sums.
\newblock {\em Theoretical Computer Science}, 123:291--314, 1994.

\bibitem{FlOd90}
P.~Flajolet and A.~Odlyzko.
\newblock Singularity analysis of generating functions.
\newblock {\em SIAM Journal on Discrete Mathematics}, 3:216--240, 1990.

\bibitem{FlPr86}
P.~Flajolet and H.~Prodinger.
\newblock Register allocation for unary--binary trees.
\newblock {\em SIAM J. Comput.}, 15:629--640, 1986.

\bibitem{FlRa80}
P.~Flajolet and L.~Ramshaw.
\newblock A note on {G}ray code and odd--even merge.
\newblock {\em SIAM J. Comput.}, 9(1):142--158, 1980.

\bibitem{FlRaVu79}
P.~Flajolet, J.-C. Raoult, and J.~Vuillemin.
\newblock The number of registers required for evaluating arithmetic
  expressions.
\newblock {\em Theoretical Computer Science}, 9:99--125, 1979.

\bibitem{FlSe95}
P.~Flajolet and R.~Sedgewick.
\newblock Mellin transforms and asymptotics: Finite differences and {R}ice's
  integrals.
\newblock {\em Theoretical Computer Science}, 144:101--124, 1995.

\bibitem{GrHePr02}
P.~Grabner, C.~Heuberger, and H.~{P}rodinger.
\newblock Subblock occurrences in signed digit representations.
\newblock {\em Submitted}.

\bibitem{GrKiPr98}
P.~Grabner, P.~Kirschenhofer, and H.~{P}rodinger.
\newblock The sum--of--digits function for complex bases.
\newblock {\em J. London Math. Soc.}, 57:20--40, 1998.

\bibitem{GrPr96}
P.~Grabner and H.~{P}rodinger.
\newblock Asymptotic analysis of the moments of the {C}antor distribution.
\newblock {\em Statistics and Probability Letters}, 26:243--248, 1996.

\bibitem{Graham-Knuth-Patashnik:1994}
R.~L. Graham, D.~E. Knuth, and O.~Patashnik.
\newblock {\em Concrete mathematics. {A} foundation for computer science}.
\newblock Addison-Wesley, second edition, 1994.

\bibitem{m_paul}
U.~G{\"u}ntzer and M.~Paul.
\newblock Jump interpolation search trees and symmetric binary numbers.
\newblock {\em Information Processing Letters}, 26:193--204, 1987/88.

\bibitem{HePr01b}
C.~Heuberger and H.~Prodinger.
\newblock Carry propagation in signed digit representations.
\newblock {\em submitted}, 2001.

\bibitem{HePr01}
C.~Heuberger and H.~Prodinger.
\newblock On minimal expansions in redundant number systems: Algorithms and
  quantitative analysis.
\newblock {\em Computing}, 66:377--393, 2001.

\bibitem{Hosking94}
J.~R.~M. Hosking.
\newblock Moments of order statistics of the {C}antor distribution.
\newblock {\em Statistics and Probability Letters}, 19:161--165, 1994.

\bibitem{JaSz98}
P.~Jacquet and W.~Szpankowski.
\newblock Analytical de-{P}oissonization and its applications.
\newblock {\em Theoretical Computer Science}, 201:1--62, 1998.

\bibitem{Kemp79}
R.~Kemp.
\newblock The average number of registers needed to evaluate a binary tree
  optimally.
\newblock {\em Acta Inform.}, 11:363--372, 1978/79.

\bibitem{KiPr84}
P.~Kirschenhofer and H.~{Prodinger}.
\newblock Subblock occurrences in positional number systems and {G}ray code
  representation.
\newblock {\em Journal of Information and Optimization Sciences}, 5:29--42,
  1984.

\bibitem{KnPr96}
A.~Knopfmacher and H.~{P}rodinger.
\newblock Exact and asymptotic formul{\ae}\ for average values of order
  statistics of the {C}antor distribution.
\newblock {\em Statistics and Probability Letters}, 27:189--194, 1996.

\bibitem{Knuth98}
D.~E. Knuth.
\newblock {\em The Art of Computer Programming}, volume 3: Sorting and
  Searching.
\newblock Addison-Wesley, 1973.
\newblock Second edition, 1998.

\bibitem{Knuth78}
D.~E. Knuth.
\newblock The average time for carry propagation.
\newblock {\em Indagationes Mathematic{\ae}}, 40:238--242, 1978.

\bibitem{Kruszewski99}
P.~Kruszewski.
\newblock A note on the {H}orton--{S}trahler number for random binary search
  trees.
\newblock {\em Inform. Process. Lett.}, 69:47--51, 1999.

\bibitem{LadTay92}
F.~R. Lad and W.~F.~C. Taylor.
\newblock The moments of the {C}antor distribution.
\newblock {\em Statistics and Probability Letters}, 13:307--310, 1992.

\bibitem{MeMoPo80}
A.~Meir, J.~W. Moon, and J.~R. Pounder.
\newblock On the order of random channel networks.
\newblock {\em SIAM J. Algebraic Discrete Methods}, 1:25--33, 1980.

\bibitem{Moon78/79}
J.~W. Moon.
\newblock An extension of {H}orton's law of stream numbers.
\newblock {\em Math. Colloq. Univ. Cape Town}, 12:1--15 (1980), 1978/79.

\bibitem{Moon80}
J.~W. Moon.
\newblock On {H}orton's law for random channel networks.
\newblock {\em Ann. Discrete Math.}, 8:117--121, 1980.
\newblock Combinatorics 79 (Proc. Colloq., Univ. Montr\'eal, Montreal, Que.,
  1979), Part I.

\bibitem{Nebel00}
M.~Nebel.
\newblock On the {H}orton--{S}trahler number for combinatorial tries.
\newblock {\em Theor. Inform. Appl.}, 34:279--296, 2000.

\bibitem{OsSh89}
A.~H. Osbaldestin and P.~Shiu.
\newblock A correlated digital sum problem associated with sums of three
  squares.
\newblock {\em Bull. London Math. Soc.}, 21:369--374, 1989.

\bibitem{PaPr95}
W.~Panny and H.~Prodinger.
\newblock Bottom-up mergesort---a detailed analysis.
\newblock {\em Algorithmica}, 14:340--354, 1995.

\bibitem{Prodinger83}
H.~Prodinger.
\newblock Some analytic techniques for the investigation of the asymptotic
  behaviour of tree parameters.
\newblock {\em EATCS Bulletin}, 47:180--199, 1992.

\bibitem{Prodinger97}
H.~Prodinger.
\newblock On a problem of {Y}ekutieli and {M}andelbrot about the bifurcation
  ratio of binary trees.
\newblock {\em Theoretical Computer Science}, 181:181--194, 1997.

\bibitem{prodinger162}
H.~Prodinger.
\newblock On binary representations of integers with digits $-1$, $0$, $1$.
\newblock {\em Integers}, pages A8, 14 pp. (electronic), 2000.

\bibitem{Prodinger00}
H.~Prodinger.
\newblock On {C}antor's singular moments.
\newblock {\em Southwest J. Pure Appl. Math.}, 2000(1):27--29 (electronic),
  2000.

\bibitem{Reitwiesner60}
G.~Reitwiesner.
\newblock Binary arithmetic.
\newblock {\em Vol.~1 of Advances in Computers, Academic Press}, pages
  231--308, 1960.

\bibitem{Riedel:thesis}
M.~Riedel.
\newblock Applications of the {M}ellin--{P}erron formula in number theory.
\newblock Technical report, University of Toronto, 1996.

\bibitem{Sedgewick78}
R.~Sedgewick.
\newblock Data movement in odd--even merging.
\newblock {\em SIAM J. Comput.}, 7:239--272, 1978.

\bibitem{ShLl66}
L.~A. Shepp and S.~P. Lloyd.
\newblock Ordered cycle lengths in a random permutation.
\newblock {\em Trans. Amer. Math. Soc.}, 121:340--357, 1966.

\bibitem{Shiu88}
P.~Shiu.
\newblock Counting sums of three squares.
\newblock {\em Bull. London Math. Soc.}, 20:203--208, 1988.

\bibitem{Thuswaldner99}
J.~Thuswaldner.
\newblock Summatory functions of digital sums occurring in {Cryptography}.
\newblock {\em Periodica Math. Hungarica}, 38:111--130, 1999.

\bibitem{WhWa27}
E.~T. Whittaker and G.~N. Watson.
\newblock {\em A Course of Modern Analysis}.
\newblock Cambridge University Press, fourth edition, 1927.
\newblock Reprinted 1973.

\bibitem{YeMa94}
I.~Yekutieli and B.~Mandelbrot.
\newblock Horton--{S}trahler ordering of random binary trees.
\newblock {\em J. Phys. A}, 27:285--293, 1994.

\end{thebibliography}

}

\bibliographystyle{plain}

%\bibliography{C:/texfiles2001/pro_bib}


%%%%%%%%%%%%%%%%%%%%% ADRESSES OF THE AUTHORS %%%%%%%%%%%%%%%%%%%

\add{Helmut Prodinger}
{The John Knopfmacher Centre for Applicable Analysis and Number
  Theory\\
School of Mathematics, University of the Witwatersrand\\
P. O. Wits, 2050 Johannesburg, South Africa\\
\texttt{helmut@staff.ms.wits.ac.za}\\
\texttt{http://www.wits.ac.za/helmut/index.htm}
}

\end{document}