\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 n1$,}
\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 k0$, $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_{n1$. 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}