
\documentclass[12pt,reqno,a4paper]{amsart}%{article}
%\usepackage{a4ams}
\usepackage{amsfonts,amsmath,amssymb}

\allowdisplaybreaks

\topmargin 0 pt
\textheight 46\baselineskip
\advance\textheight by \topskip
\setlength{\parindent}{0pt}
\setlength{\parskip}{5pt plus 2pt minus 1pt}
\setlength{\textwidth}{155mm}

\setlength{\oddsidemargin}{5.6mm}
\setlength{\evensidemargin}{5.6mm}




\newcommand{\stwo}[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}}
\newtheorem{theorem}{Theorem}

\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}%[section]


\newtheorem{prop}{Proposition}
\numberwithin{equation}{section}

\def\Prob{\mathbb{P}}
\def\prob{\mathbb{P}}
\def\expect{\mathbb{E}}
\def\shuffle{\sqcup\kern-0.07cm\sqcup}

\def\eps{\varepsilon}
\def\al{\alpha}
\def\1{\bar{1}}

\title[On binary representations of integers]
{On binary representations of integers with digits -1, 0, 1}

\author{Helmut Prodinger}
\thanks{I started this work when standing in
(a long!) line, waiting for a visa for the U.S. 
When I arrived at Purdue in February, Prof. Szpankowski
kindly allowed me to go on with this. Thanks, Wojtek!}

\address{ Helmut Prodinger\newline
The John Knopfmacher
Centre for Applicable Analysis and Number Theory\newline
 Department of Mathematics\newline
University of the Witwatersrand, P.~O. Wits\newline 
2050 Johannesburg, South Africa\newline email:
{\tt helmut@gauss.cam.wits.ac.za},\newline
homepage: {\tt http://www.wits.ac.za/helmut/index.htm}
}

\date{June 14, 2000}









\begin{document}
\begin{abstract}
G\"untzer and Paul introduced a number system with base 2 and digits
$-1,0,1$ which is characterized by separating nonzero digits by at least
one zero. We find  an explicit formula that produces the digits of
the expansion of an integer $n$ which leads us to many generalized
situations. Syntactical properties of such representations are also
discussed. 
\end{abstract}


\maketitle









\section{A binary number system}

Integers $n$ can be written in many ways as $n=\sum_{k\ge0} a_k2^k$,
where
the ``digits'' $a_k$
are taken from the set $\{-1,0,1\}$
(see section \ref{Shallit} for a more precise statement).
 Let us write $\1=-1$ for convenience.
G\"untzer and Paul have shown \cite{m_paul}, however, that the
representation is unique if the product of any two adjacent digits
must be zero, or, in other words, if any nonzero digits are separated
by (at least one) zero. (For more historial background, see 
section \ref{Shallit} .)

In this paper we want to understand this system (and some generalizations)
in more detail.

It turns out that the Paul system is obtained by writing $3n/2$ 
in binary and subtracting (bitwise) the binary representation of
$n/2$. 
For example, $25=(11001)_2$, and $\frac32\cdot 25=37.5=(100101.1)_2$,
$\frac12\cdot 25=12.5=(1100.1)_2$, and the bitwise difference is
$(10\1001)_P$, which is the representation of $25$ in the Paul system.

Clearly, the result is a representation of $n$  in
base 2 using digits $-1,0,1$. An obvious generalization is
to consider $n=(\al+1)n-\al n$. 
We  analyzed only the case that $\al$ is either an integer
or an integer divided by a power of 2 (a dyadic rational number).



\section{Experimental mathematics}

Let us write $n$ in the Paul system as $(n)_P=\dots a_2(n)a_1(n)a_0(n)$.
Empirically we find that

\begin{align*}
\big(a_0(n)\big)&=(010\1)^\omega,\\*
\big(a_1(n)\big)&=(001000\10)^\omega,\\*
\big(a_2(n)\big)&=(00011100000\1\1\100)^\omega,\\*
\big(a_3(n)\big)&=(0000001 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 \1\1\1\1\1 0 0 0 0 0)^\omega,
\end{align*}

etc., which suggests that





\begin{equation*}
a_k(n)=1\Longleftrightarrow
\left\lfloor\frac{n-\frac{1}{2}+\frac{(-1)^k}{6}}
{2^{k+2}}+\frac{5}{6} \right\rfloor-
\left\lfloor\frac{n-\frac{1}{2}+\frac{(-1)^{k-1}}{6}}
{2^{k+2}}+\frac{4}{6} \right\rfloor=1
\end{equation*}
and

\begin{equation*}
a_k(n)=\1\Longleftrightarrow
\left\lfloor\frac{n-\frac{1}{2}+\frac{(-1)^k}{6}}
{2^{k+2}}+\frac{2}{6} \right\rfloor-
\left\lfloor\frac{n-\frac{1}{2}+\frac{(-1)^{k-1}}{6}}
{2^{k+2}}+\frac{1}{6} \right\rfloor=1.
\end{equation*}
These forms are modelled to achieve the jump between the
different digits. They would give the correct digits, even for
$n$ being an arbitrary real number. 
However, for integers, the simpler

\begin{equation*}
a_k(n)=1\Longleftrightarrow
\left\lfloor\frac{n}
{2^{k+2}}+\frac{5}{6} \right\rfloor-
\left\lfloor\frac{n}
{2^{k+2}}+\frac{4}{6} \right\rfloor=1
\end{equation*}
and

\begin{equation*}
a_k(n)=\1\Longleftrightarrow
\left\lfloor\frac{n}
{2^{k+2}}+\frac{2}{6} \right\rfloor-
\left\lfloor\frac{n}
{2^{k+2}}+\frac{1}{6} \right\rfloor=1
\end{equation*}
also work!
(If the expressions on the right hand sides are not 1, they must be 0.)


Consequently we have the formula
\begin{equation*}
n=\sum_{k\ge0}\left(
\left\lfloor\frac{n}{2^{k+2}}+\frac{5}{6} \right\rfloor-
\left\lfloor\frac{n}
{2^{k+2}}+\frac{4}{6} \right\rfloor
-\left\lfloor\frac{n}{2^{k+2}}+\frac{2}{6} \right\rfloor+
\left\lfloor\frac{n}
{2^{k+2}}+\frac{1}{6} \right\rfloor
\right)2^k.
\end{equation*}
It would be possible to turn these results into a
(clumsy) formal proof. 


\section{The explanation}


The key formula (see \cite[1.2.4, Ex.~38]{Knuth68}) is


\begin{equation}\label{keyformula}
\lfloor x\rfloor+\lfloor x+\tfrac1q\rfloor+\dots+
\lfloor x+\tfrac{q-1}{q}\rfloor=\lfloor qx\rfloor,
\end{equation}
where $q$ is an integer $\ge1$ and $x$ a real number.

We can now consider the
binary representation of $\lambda n$, for a natural number
$\lambda$: The $k$th digit is given by
\begin{equation*}
a_k(\lambda n)=\sum_{i=0}^{2\lambda-1}
\left\lfloor\frac{n}{2^{k+1}}+\frac{i}{2\lambda} \right\rfloor
(-1)^{i-1};
\end{equation*}

this follows from 
\begin{equation*}
\lambda n=\sum_{k\ge0}2^k\left(
\left\lfloor\frac{\lambda n}{2^{k}} \right\rfloor
-2\left\lfloor\frac{\lambda n}{2^{k+1}} \right\rfloor
\right)
\end{equation*}


and the formula (\ref{keyformula}).







 From that one
 can get  the digits for the $n=(\alpha+1)n-\alpha n$
representation. We explain it for $\alpha=3$, from which
the general instance should be clear. Multiplication  by $4$ involves
the additive terms in the floor brackets
\begin{equation*}
\frac{7}{8},
\frac{6}{8},
\frac{5}{8},
\frac{4}{8},
\frac{3}{8},
\frac{2}{8},
\frac{1}{8},
\frac{0}{8},
		\end{equation*}


while multiplication  by $3$ involves the terms
\begin{equation*}
\frac{5}{6},
\frac{4}{6},
\frac{3}{6},
\frac{2}{6},
\frac{1}{6},
\frac{0}{6}.
\end{equation*}

These two sequence must now be merged, so that the numbers are
in decreasing order. Then appropriate signs are attached (which e.~g.
makes the terms with additive term $0$ disappear). The sequence is
\begin{equation*}
\frac{7}{8},
\frac{5}{6},
\frac{6}{8},
\frac{4}{6},
\frac{5}{8},
\frac{4}{8},
\frac{3}{6},
\frac{3}{8},
\frac{2}{6},
\frac{2}{8},
\frac{1}{6},
\frac{1}{8}.
\end{equation*}
Thus the digits are given by


\begin{align*}
a_k(4n)-a_k(3n)&=\left\lfloor\frac{n}{2^{k+1}}+\frac{7}{8} \right\rfloor
-\left\lfloor\frac{n}{2^{k+1}}+\frac{5}{6} \right\rfloor
-\left\lfloor\frac{n}{2^{k+1}}+\frac{6}{8} \right\rfloor
+\left\lfloor\frac{n}{2^{k+1}}+\frac{4}{6} \right\rfloor\\
&
+\left\lfloor\frac{n}{2^{k+1}}+\frac{5}{8} \right\rfloor
-\left\lfloor\frac{n}{2^{k+1}}+\frac{4}{8} \right\rfloor
-\left\lfloor\frac{n}{2^{k+1}}+\frac{3}{6} \right\rfloor
+\left\lfloor\frac{n}{2^{k+1}}+\frac{3}{8} \right\rfloor\\
&
+\left\lfloor\frac{n}{2^{k+1}}+\frac{2}{6} \right\rfloor
-\left\lfloor\frac{n}{2^{k+1}}+\frac{2}{8} \right\rfloor
-\left\lfloor\frac{n}{2^{k+1}}+\frac{1}{6} \right\rfloor
+\left\lfloor\frac{n}{2^{k+1}}+\frac{1}{8} \right\rfloor.
\end{align*}


This principle works also for 
$\alpha=\frac{\lambda}{2^s}$, a positive dyadic fraction. 
The 
$k$th digit is given by
\begin{equation*}
a_k(n)=\sum_{i=0}^{2\lambda-1}
\left\lfloor\frac{n}{2^{k+1+s}}+\frac{i}{2\lambda} \right\rfloor
(-1)^{i-1}.
\end{equation*}
Observe that now there are also digits after the binary point; we don't
need them, however, since we take appropriate differences,  these
digits will necessarily cancel out.

Thus the $k$th digit of the
$(\alpha+1)n-\alpha n$ representation is obtained by taking the difference
of them, once for $\lambda'=2^s+\lambda$, and once for
$\lambda$. If one want to count digits separately, it is required to
arrange the terms
\begin{equation*}
\pm\left\lfloor\frac{n}{2^{k+1+s}}+d \right\rfloor
\end{equation*}
is decreasing order (w.r.t. $d$).



In the Paul case, $\lambda=s=1$, $\lambda'=3$, and thus
the $k$th digit is given by
\begin{equation*}
a_k(n)=\sum_{i=0}^{5}
\left\lfloor\frac{n}{2^{k+2}}+\frac{i}{6} \right\rfloor
(-1)^{i-1}-
\sum_{i=0}^{1}
\left\lfloor\frac{n}{2^{k+2}}+\frac{i}{2} \right\rfloor
(-1)^{i-1}, 
\end{equation*}
which upon simplification is 

\begin{equation*}
a_k(n)=\left\lfloor\frac{n}{2^{k+2}}+\frac{5}{6} \right\rfloor-
\left\lfloor\frac{n}
{2^{k+2}}+\frac{4}{6} \right\rfloor
-\left\lfloor\frac{n}{2^{k+2}}+\frac{2}{6} \right\rfloor+
\left\lfloor\frac{n}
{2^{k+2}}+\frac{1}{6} \right\rfloor.
\end{equation*}



\section{Syntactical properties}

As mentioned in the introduction, the Paul system is characterized
by the property that two nonzero digits are always separated.

In \cite{m_paul} the rewriting rules
$$
1\1\longrightarrow01 \qquad\1 1\longrightarrow0\1 \qquad
011\longrightarrow10\1 \qquad
0\1\1\longrightarrow\1 01
$$
are presented, that can be (repeatedly) applied in any order to
transform the standard binary representation of $n\in\mathbb N$
into the Paul representation. We say ``repeatedly'' because of
a problem with carries; the following example explains what happens:

$$
01111
\longrightarrow
10\1 11
\longrightarrow
100\1 1
\longrightarrow
1000\1.
$$

A more ``algorithmic'' version is by the following {\it transducer.}
It reads the  binary representation of $n$ from right to left
(leading zeros must be added if needed). 
Of course, the output is also produced from right to left. 
The basic idea is to transform
$01^k$
into $10^{k-1}\1$ for $k\ge2$\footnote{
In a previous version, I did that also for
$k=1$; thanks to a referee this error has been removed.}.
 However, if the next group (to the left) starts
immediately with $1$, then we can't output the leading 1; it is then
a carry, belonging to the next group.
To make sure that the transduction ends in the starting state
(as it should), we
can add two leading zeros (see Figure 3).

\begin{figure}[h]\hskip-4cm
%\input paul1a.pic
%TexCad Options
%\grade{\off}
%\emlines{\off}
%\beziermacro{\on}
%\reduce{\on}
%\snapping{\off}
%\quality{2.00}
%\graddiff{0.01}
%\snapasp{1}
%\zoom{1.00}
\unitlength 1.00mm
\linethickness{0.4pt}
\begin{picture}(122.67,61.33)
\put(55.00,44.00){\circle{6.00}}
\put(55.00,10.00){\circle{6.00}}
\put(96.00,44.00){\circle{6.00}}
\put(96.00,10.00){\circle{6.00}}
%\emline(58.00,44.00)(92.67,44.00)
\put(58.00,44.00){\line(1,0){34.67}}
%\end
%\emline(93.67,42.00)(57.67,12.33)
%\multiput(93.67,42.00)(-0.15,-0.12){248}{\line(-1,0){0.15}}
%\end
%\emline(95.67,13.00)(95.67,41.00)
%\put(95.67,13.00){\line(0,1){28.00}}
%\end
%\emline(58.33,10.00)(93.00,10.00)
\put(58.33,10.00){\line(1,0){34.67}}
%\end
\bezier{156}(56.00,13.00)(69.67,28.00)(56.67,41.33)
\bezier{152}(52.33,41.67)(40.00,29.33)(53.00,13.00)
\bezier{156}(97.00,13.00)(110,28.00)(97.,41.33)
\bezier{152}(93.67,41.67)(80.00,29.33)(93.67,13.00)


\bezier{112}(52.67,46.00)(42.33,59.00)(53.67,61.00)
\bezier{124}(57.00,46.67)(67.33,60.67)(53.67,61.33)
\bezier{164}(98.67,12.33)(113.67,31.00)(115.67,13.67)
\bezier{140}(99.00,9.67)(118.67,1.33)(115.67,14.33)
%\emline(106.33,24.00)(105.00,19.33)
\multiput(106.33,24.00)(-0.11,-0.39){12}{\line(0,-1){0.39}}
%\end
%\emline(105.00,19.33)(109.33,19.33)
\put(105.00,19.33){\line(1,0){4.33}}
%\end
%\emline(45.67,53.67)(48.67,51.67)
\multiput(45.67,53.67)(0.18,-0.12){17}{\line(1,0){0.18}}
%\end
%\emline(48.67,51.67)(51.00,54.67)
\multiput(48.67,51.67)(0.12,0.15){20}{\line(0,1){0.15}}
\multiput(43.00,27.00)(0.13,-0.12){31}{\line(1,0){0.13}}

\multiput(84.00,27.00)(0.13,-0.12){31}{\line(1,0){0.13}}
\multiput(87.67,24.00)(0.12,0.12){31}{\line(1,0){0.13}}

\multiput(103.33,30.67)(0.13,-0.13){17}{\line(1,0){0.18}}
\multiput(101,28.00)(0.13,0.15){17}{\line(1,0){0.18}}


%\end
%\emline(47.00,23.33)(49.67,27.67)
\multiput(47.00,23.33)(0.12,0.19){23}{\line(0,1){0.19}}
%\end
%\emline(60.33,30.33)(61.33,34.33)
\multiput(60.33,30.33)(0.11,0.44){9}{\line(0,1){0.44}}
%\end
%\emline(61.33,34.33)(65.00,32.00)
\multiput(61.33,34.33)(0.18,-0.12){20}{\line(1,0){0.18}}
%\end
%\emline(74.00,46.67)(68.67,44.00)
\multiput(74.00,46.67)(-0.23,-0.12){23}{\line(-1,0){0.23}}
%\end
%\emline(68.67,44.00)(74.00,41.67)
\multiput(68.67,44.00)(0.27,-0.12){20}{\line(1,0){0.27}}
%\end
%\emline(74.00,29.00)(72.67,25.00)
%\multiput(74.00,29.00)(-0.11,-0.33){12}{\line(0,-1){0.33}}
%\end
%\emline(72.67,25.00)(77.33,25.00)
%\put(72.67,25.00){\line(1,0){4.66}}
%\end
%\emline(92.67,28.67)(95.33,33.00)
%\multiput(92.67,28.67)(0.12,0.19){23}{\line(0,1){0.19}}
%\end
%\emline(95.33,33.00)(98.00,28.67)
%\multiput(95.33,33.00)(0.12,-0.19){23}{\line(0,-1){0.19}}
%\end
%\emline(78.67,13.67)(83.33,10.00)
\multiput(78.67,13.67)(0.15,-0.12){31}{\line(1,0){0.15}}
%\end
%\emline(83.33,10.00)(78.33,7.00)
\multiput(83.33,10.00)(-0.19,-0.12){26}{\line(-1,0){0.19}}
%\end
\put(67.67,57.33){\makebox(0,0)[cc]{$0\mid0$}}
\put(78.33,49.67){\makebox(0,0)[cc]{$0\mid01$}}
\put(39.00,29.67){\makebox(0,0)[cc]{$1\mid\eps$}}
\put(70.33,22.67){\makebox(0,0)[cc]{$0\mid01$}}
\put(80.33,32.00){\makebox(0,0)[cc]{$1\mid0\1$}}
\put(75.00,3.00){\makebox(0,0)[cc]{$1\mid0\1$}}
\put(107.67,35.33){\makebox(0,0)[cc]{$0\mid\eps$}}
\put(122.67,18.00){\makebox(0,0)[cc]{$1\mid0$}}
\put(40.33,44.33){\makebox(0,0)[cc]{$\longrightarrow$}}
\end{picture}



\caption{The binary $\to$ Paul transformer}
\end{figure}

When dealing with number systems, it is usually very instructive
to see how the number $1$ can be added. This can normally be done
by an automaton. Here it is (see Figure 2).
The word is processed from right to left. If no continuation is
defined, the rest of the word is left unchanged. Again, possibly
leading zeros are needed to lead to one of the accepting states
to the right. The output is also recorded from right to left, usually
replacing only a suffix of the word (representation of a number),
when reaching one of the two states to the right.

\begin{figure}[h]\hskip-3cm
%TexCad Options
%\grade{\off}
%\emlines{\off}
%\beziermacro{\on}
%\reduce{\on}
%\snapping{\off}
%\quality{2.00}
%\graddiff{0.01}
%\snapasp{1}
%\zoom{1.00}
\unitlength 1.00mm
\linethickness{0.4pt}
\begin{picture}(140.67,57.00)
\put(116.67,54.00){\circle{6.00}}
\put(59.67,54.00){\line(1,0){54.00}}
\put(88.34,56.67){\line(5,-3){4.33}}
\put(92.67,54.07){\line(-5,-3){4.00}}
\put(34.67,16.00){\circle{6.00}}
\put(77.67,17.00){\circle{6.00}}
\put(137.67,17.00){\circle{6.00}}
\put(80.67,17.00){\line(1,0){54.00}}
\put(109.34,19.67){\line(5,-3){4.33}}
\put(113.67,17.07){\line(-5,-3){4.00}}
\put(37.00,18.33){\line(3,5){20.00}}
\put(76.33,19.67){\line(-3,5){19.20}}
\bezier{180}(37.67,17.67)(54.67,31.00)(74.67,18.67)
\bezier{180}(37.33,14.67)(56.00,2.33)(75.00,15.33)
\put(45.33,39.67){\line(1,-5){1.07}}
\put(46.40,34.33){\line(2,1){5.60}}
\put(68.67,39.67){\line(-1,-5){1.07}}
\put(67.60,34.33){\line(-5,3){5.27}}
\put(65.33,26.00){\line(3,-4){3.00}}
\put(68.33,22.00){\line(-3,-2){3.67}}
\put(46.67,12.67){\line(-6,-1){4.67}}
\put(42.00,11.89){\line(3,-4){2.67}}
\put(32.67,40.00){\makebox(0,0)[cc]{$1\mid\eps$}}
\put(80.33,35.67){\makebox(0,0)[cc]{$0\mid\eps$}}
\put(55.67,29.00){\makebox(0,0)[cc]{$0\mid0$}}
\put(55.33,2.33){\makebox(0,0)[cc]{$1\mid\1$}}
\put(102.00,47.67){\makebox(0,0)[cc]{$\1\mid0$}}
\put(122.00,21.67){\makebox(0,0)[cc]{$0\mid01$}}
\put(122.00,10.67){\makebox(0,0)[cc]{$\1\mid0\1$}}
\put(56.67,54.00){\circle{6.00}}
\put(42.00,53.67){\makebox(0,0)[cc]{$\longrightarrow$}}
\end{picture}



%\input paul3.pic
\caption{Adding 1 in the Paul representation}
\end{figure}



Now let us consider a few properties of the system induced by
writing $n=5n/4-n/4$:

First, we describe the syntactically correct words. There are
special sequences of nonzero digits, separated by at least two zeros,
except perhaps for the right border. A bit more formally, if
$$
B=1+\1+ 11(\11)^*(\eps+\1)+ \1\1(1\1)^*(\eps+1),
$$
then the possible representations are given by
$$
\eps+(B000^*)^*B0^*.
$$
Here are rewriting rules (that should be applied from the rightmost
possible position) to obtain the representation in question:





\begin{align*}
101&\longrightarrow 11\1\\
10\1&\longrightarrow 011\\
\1 0\1&\longrightarrow \1\1 1\\
\1 01&\longrightarrow 0\1 \1\\
01\1&\longrightarrow 001\\
0\1 1&\longrightarrow 00\1\\
01^k&\longrightarrow 10^{k-1}\1&\text{$k\ge3$}\\
\1 1^k&\longrightarrow 0^k\1&\text{$k\ge3$}\\
0\1^k&\longrightarrow \1 0^{k-1}1&\text{$k\ge3$}\\
1\1^k&\longrightarrow 0^k1&\text{$k\ge3$}\\
\end{align*}

We also show
 an automaton, producing this transformation,
by processing the word from right to left.
Input are natural numbers, written in ordinary binary notation.
The computation ends in the starting state.


\begin{figure}[h]
%TexCad Options
%\grade{\off}
%\emlines{\off}
%\beziermacro{\on}
%\reduce{\on}
%\snapping{\off}
%\quality{2.00}
%\graddiff{0.01}
%\snapasp{1}
%\zoom{1.00}
\unitlength 1.00mm
\linethickness{0.4pt}
\begin{picture}(146.33,71.67)
\put(77.00,44.00){\circle{6.00}}
\put(131.00,44.00){\circle{6.00}}
\put(53.00,14.00){\circle{6.00}}
\put(107.00,14.00){\circle{6.00}}
%links 1
%rechts 1. Teil
\put(29.33,58.33){\makebox(0,0)[cc]{$0\mid0$}}
\put(118.00,58.33){\makebox(0,0)[cc]{$1\mid0$}}
\put(50.67,50.67){\makebox(0,0)[cc]{$1\mid\eps$}}
\put(100.67,50.67){\makebox(0,0)[cc]{$0\mid\eps$}}
\put(28.00,25.00){\makebox(0,0)[cc]{$0\mid001$}}
\put(57.67,32.00){\makebox(0,0)[cc]{$0\mid\eps$}}
\put(95.33,31.67){\makebox(0,0)[cc]{$1\mid\eps$}}
\put(126.00,26.33){\makebox(0,0)[cc]{$1\mid00\1$}}
\put(77.67,23.33){\makebox(0,0)[cc]{$0\mid1$}}
\put(77.67,2.33){\makebox(0,0)[cc]{$1\mid\1$}}
\put(28.67,44.00){\line(1,0){45.33}}
\put(80.00,44.00){\line(1,0){47.67}}
\put(50.67,16.00){\line(-5,6){23.06}}
\put(109.67,15.67){\line(3,4){19.50}}
\put(74.67,42.00){\line(-4,-5){20.00}}
\bezier{216}(55.67,15.33)(79.67,27.33)(104.00,15.00)
\bezier{216}(55.67,13.00)(75.33,1.33)(104.33,12.33)
\put(105.00,16.33){\line(-1,1){25.67}}
\bezier{164}(23.33,42.33)(0.00,44.00)(11.33,57.33)
\bezier{180}(11.33,57.33)(25.00,71.67)(26.67,47.00)
\bezier{128}(128.67,46.33)(116.00,61.33)(128.67,63.00)
\bezier{168}(128.67,63.00)(146.33,65.67)(133.67,45.67)
\put(10.00,62.00){\line(1,0){7.00}}
\put(17.00,62.00){\line(-1,-4){1.42}}
\put(135.67,67.33){\line(1,-2){2.83}}
\put(138.50,61.67){\line(-4,-1){5.83}}
\put(62.67,47.00){\line(5,-3){5.33}}
\put(68.00,43.80){\line(-2,-1){5.33}}
\put(112.67,47.00){\line(-2,-1){6.33}}
\put(106.33,43.83){\line(2,-1){6.00}}
\put(66.67,36.00){\line(-1,-5){1.00}}
\put(65.67,31.00){\line(5,2){5.00}}
\put(83.33,33.67){\line(3,-1){6.33}}
\put(89.67,31.56){\line(-1,6){0.91}}
\put(120.00,36.00){\line(3,1){6.33}}
\put(126.33,33.33){\line(0,0){0.00}}
\put(39.33,24.67){\line(-1,6){1.00}}
\put(38.33,30.67){\line(5,-2){6.33}}
\put(66.00,22.33){\line(-2,-3){2.44}}
\put(63.56,18.67){\line(4,-1){4.11}}
\put(91.67,11.33){\line(4,-1){4.67}}
\put(96.33,10.17){\line(-3,-5){2.30}}
\put(126.00,37.67){\line(0,-1){6.00}}
\put(25.00,45.00){\circle{6.00}}
\put(20.00,37.00){\makebox(0,0)[cc]{$\nearrow$}}
\end{picture}



%\input paul2.pic
\caption{The binary $\to$ ``$1=5/4-1/4$'' transformer}
\end{figure}



Instead of giving the automaton to add 1 in this case, we give a
complete list of possible situations. A few rules are recursive,
which is caused by carries. Notation: $w$
is the admissible representation of an integer $n$, and $T(w)$ the
the admissible representation of $n+1$.


\begin{align*}
T(w000)&=w001\\*
T(w11(\1 1)^k00)&=w11(\1 1)^{k-1}00, &k\ge1\\
T(w11(\1 1)^k\1 00)&=w11(\1 1)^{k-1}000\1\1, &k\ge1\\
T(w\1\1(1\1)^k00)&=w\1\1(1\1)^k1\1, &k\ge0\\
T(w\1\1(1\1)^k100)&=w\1\1(1\1)^{k-1}100\1\1, &k\ge1\\
T(w\1\1100)&=w\100\1\1\\
T(w11\100)&=w11\1 1\1\\
T(w1100)&=T(w)00\1\1\\
T(w00100)&=w0011\1\\
T(w00\1 00)&=w000\1\1\\
T(w11(\1 1)^k0)&=w11(\1 1)^{k-1}00\1, &k\ge1\\
T(w110)&=T(w)00\1\\
T(w11(\1 1)^k\1 0)&=w11(\1 1)^{k+1}, &k\ge0\\
T(w\1\1(1\1)^k0)&=w\1\1(1\1)^k1,&k\ge0\\
T(w\1\1(1\1)^k10)&=w\1\1(1\1)^{k-1}100\1,&k\ge1\\
T(w\1\110)&=w\100\1\\
T(w0010)&=w0011\\
T(w00\10)&=w000\1\\
T(w11(\11)^k)&=w11(\11)^{k-1}00,&k\ge1\\
T(w11)&=T(w)00\\
T(w11(\11)^k\1)&=w11(\11)^k0,&k\ge0\\
T(\1\1(1\1)^k)&=w\1\1(1\1)^{k-1}10,&k\ge1\\
T(w\1\1)&=w\10\\
T(w001)&=T(w00)0\\
T(w00\1)&=w000
\end{align*}



\section{Path length}\label{pathlength}

Let us first reconsider the Paul case with generating functions.
G\"untzer and Paul arranged
 all numbers with length $\le n $ in the tree, where
the length means the number of digits, starting with no leading
zeros.
The number 0 is also in the tree, 
and its length is zero; it serves as the root.
Node $y$ is a child\footnote{The recent third edition
of \cite{Knuth68} has already this politically correct form.} 
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.
Now consider
\begin{equation*}
\eps+(X0^+)^*X0^*, \qquad \text{where $X=1+\1$,}
\end{equation*}
which describes the set of admissible representations in a 
unique way.
Translating accordingly
(we mark the digits $\1,0,1$ by a variable $z$,
and also each $X$ by $u$, to keep track of the
depth), we obtain a generating function such that the
coefficient of $z^nu^k$ is the number
of representations (words) of length $n$ and depth $k$, viz.
\begin{equation*}
1+\frac{1}{1-\frac{2z^2u}{1-z}}\frac{2zu}{1-z}.
\end{equation*}


We must divide by $1-z$, because we need 
the number
of representations (words) of length $\le n$ and depth $k$.
So we get
\begin{equation*}\frac{1}{1-z}+\frac{2zu}{(1-z)(1-z-2z^2u)};
\end{equation*}
differentiate with respect to
$u$  and set $u=1$ to get the generating function
of the  total path lengths:
\begin{equation*}
\frac{2z}{(1+z)^2(1-2z)^2}.
\end{equation*}
The coefficient of $z^n$ in that is
\begin{equation*}
\frac19n2^{n+2}+\frac{1}{27}2^{n+3}-\frac29n(-1)^n-\frac8{27}(-
1)^n,
\end{equation*}
which is a result of \cite{m_paul}.

In this  way, we also
get the number of nodes in the tree;
we must consider (simply replace $u$ by $1$)  
\begin{equation*}
\frac1{1-z}+\frac{2z}{(1-z)(1-z-2z^2)}=\frac{1+2z}{(1+z)(1-2z)}
=\frac43\frac1{1-2z}-\frac13\frac1{1+z},
\end{equation*}

whence we get $2^{n+2}/3-1/3(-1)^n$; this was already reported
in \cite{m_paul}.

Dividing by the total number of nodes, we see that from the $n$ digits
approximately $\frac n3$ are nonzero digits. In fact, it was proved in
\cite{m_paul} that this representation has the least 
number of nonzero digits
of any possible representation!




Now let us consider the next (the $n=5n/4-n/4$) case;
from
\begin{equation*}
\eps+(B000^{*})^*B0^* \qquad\text{with}\qquad
B=1+\1+ 11(\11)^*(\eps+\1)+ \1\1(1\1)^*(\eps+1)
\end{equation*}


we find
\begin{equation*}
1+\frac{2z}{(1+z^2)(1-2z)},
\end{equation*}
which is the generating function of admissible words of length $n$.

The generating function of all numbers with a representation of length $\le
n$
is thus given by
\begin{equation*}
\frac1{1-z}+\frac{2z}{(1+z^2)(1-2z)(1-z)}=\frac85\cdot\frac1{1-2z}
-\frac15\cdot\frac{3+z}{1+z^2}
\end{equation*}
and the coefficients (of $z^n$) are

\begin{equation*}
\frac{2^{n+3}}{5}-\begin{cases}
\frac35(-1)^{n/2}& n\text { even}\\
\frac15(-1)^{(n-1)/2}& n\text { odd}\\
\end{cases}
\end{equation*}


or
\begin{equation*}
2\left\lfloor\frac{2^{n+2}}{5}\right\rfloor+1.
\end{equation*}




This form has the advantage that the     
 ``$+1$'' is responsible for the
number $0$, and then everything comes twice, because of
positive and negative numbers.

This time, the depth of the node is the length of the number except for
the trailing zeros.

We get the generating function for the total path length as
\begin{equation*}
\frac{2z(1-2z+z^2+4z^3-2z^4)}{(1-z)^2(1-2z)^2(1+z^2)^2};
\end{equation*}


the coefficients are  given by
\begin{equation*}
\frac n52^{n+3}-\frac152^{n+4}+O(n^2).
\end{equation*}

Dividing this by the number of nodes in the tree we get approximately $n$,
which means that
the tree is not at all useful. A related question is the total
number
of nonzero digits in all numbers with a representation of length $\le n$:
We start from the generating function
\begin{equation*}
1+\frac{2z}{(1-2z)^2(1+z^2)^2}
\end{equation*}


and get coefficients 
\begin{equation*}
\frac{1}{25}n2^{n+4}-\frac{1}{125}2^{n+6}+O(n^2).
\end{equation*}




Therefore, roughly speaking, from the $n$ letters there are $\frac{2n}{5}$
nonzero digits and $\frac{3n}{5}$ zeros. We will however see more
precise
statements in  the next section.


Here, we have a proportion of $\frac25$, which is higher that the
$\frac13$ from \cite{m_paul}.














\section{Counting digits}

We want to count the number of nonzero digits in the representations
produced by $n=(1+1/2^{t})n-n/2^t$, since this can be done it
a clean and attractive way and leave more general instances as
a problem for the interested readers. It is possible (and advisable)
to count digits $1$ and $\1$ separately.


The representation of $n$ in this number system is given by
\begin{align*}
n&=\sum_{k\ge0}2^k
\sum_{\genfrac{}{}{0pt}{}{i=1}{2^{t}+1\nmid i}}
^{2(2^t+1)}
\left\lfloor\frac{n}{2^{k+t+1}}+\frac{i}{2(2^t+1)} \right\rfloor(-
1)^{i-1}\\
&=\sum_{k\ge0}2^k
\sum_{i=1 }^{2^t}
\left\lfloor\frac{n}{2^{k+t+1}}+\frac{i}{2(2^t+1)} \right\rfloor(-
1)^{i-1}
+\sum_{k\ge0}2^k
\sum_{i=2^t+2 }^{2^{t+1}+1}
\left\lfloor\frac{n}{2^{k+t+1}}+\frac{i}{2(2^t+1)} \right\rfloor(-
1)^{i-1}
\end{align*}


We want to count the average number of digits $1$ (resp. $\1$) in all the
integers $n=0,1,\dots,m-1$.


To give a flavour of what is going on we note that a term like
$$
\left\lfloor x+\frac{i+1}{q} \right\rfloor
-\left\lfloor x+\frac{i}{q} \right\rfloor
$$
is responsible for the digit 1, and
$$
-\left\lfloor x+\frac{i+1}{q} \right\rfloor
+\left\lfloor x+\frac{i}{q} \right\rfloor
$$
for the digit $\1$. The pattern of signs is like $+-+-\dots$, but
because there is one index missing, it switches to
$-+-+\dots$\;. So the counting function for the digit 1 in the number $n$ is
given by


\begin{align*}
\sum_{k\ge0}
\sum_{i=2^t+2 }^{2^{t+1}+1}
\left\lfloor\frac{n}{2^{k+t+1}}+\frac{i}{2(2^t+1)} \right\rfloor(-
1)^{i-1},
\end{align*}

and the counting function for the digit $\1$ is given by
\begin{align*}
\sum_{k\ge0}
\sum_{i=1 }^{2^t}
\left\lfloor\frac{n}{2^{k+t+1}}+\frac{i}{2(2^t+1)} \right\rfloor(-
1)^{i}.
\end{align*}


We are not repeating derivations that apply here and can be found in
\cite{KiPr84}; they are based on a method due to Delange \cite{Delange75}.

A typical result is this:
\begin{equation*}
\sum_{n=0}^{m-1}
\sum_{k\ge0}\left(
\left\lfloor\frac{n}{2^{k+2}}+\frac{5}{6} \right\rfloor-
\left\lfloor\frac{n}
{2^{k+2}}+\frac{4}{6} \right\rfloor\right)
=\frac16m\log_2m+m\delta(\log_2m)+E,
\end{equation*}

where $\delta(x)$ is a certain periodic function of period 1 that
could be computed explicitly, as well as its Fourier coefficients, and
$E$ is a certain error term, that
could also
be computed explicitly. (We use $\delta$ and $E$ as generic
names; they usually vary with the parameters.)


A bit more generally, we have




\begin{multline*}
\sum_{n=0}^{m-1}\sum_{k\ge0}\Bigg(
\left\lfloor\frac{n}{2^{k+t+1}}+\frac{i+1}{2(2^t+1)} \right\rfloor
-\left\lfloor\frac{n}{2^{k+t+1}}+\frac{i}{2(2^t+1)} \right\rfloor
\Bigg)\\=
\frac{1}{2(2^t+1)}m\log_2m+m\delta(\log_2m)+E.
\end{multline*}
Now since in our digit counting problem
we have $2^t$ such terms,
the average number of nonzero digits amongst the numbers
$0,1,\dots,m-1$ is given by

\begin{align*}
\frac{2^{t-1}}{2^t+1}\log_2m+\delta(\log_2m)+\frac Em.
\end{align*}
Note that $t=1$ produces the factor $\frac13$ from the Paul fame
\cite{m_paul}; $t=2$ gives $\frac25$, which we have seen previously, 
and so on; the factor in front of the logarithmic term approaches $\frac12$
as $t$ gets large.

\section{More examples}

Consider the system $\alpha=1$, i.~e. $n=2n-n$.
Then the admissible words are
\begin{equation*}
\eps+(10^*\10^*)^*,
\end{equation*}
and the digits are produced by
\begin{equation*}
a_k(n)=\left\lfloor\frac{n}{2^{k+1}}+\frac{3}4 \right\rfloor-
\left\lfloor\frac{n}{2^{k+1}}+\frac{2}4 \right\rfloor-
\left\lfloor\frac{n}{2^{k+1}}+\frac{2}4 \right\rfloor+
\left\lfloor\frac{n}{2^{k+1}}+\frac{1}4 \right\rfloor.
\end{equation*}
(The first two terms are responsible for the digit $1$,
the remaining ones for $\1$.
The average number of nonzero digits
in the integers $0,1,\dots,m-1$ is thus given by
(leading term only)
\begin{equation*}
\frac{1}{2}\log_2m.
\end{equation*}

For $\alpha=2$   the digits are given by



\begin{align*}
a_k(n)&=\left\lfloor\frac{n}
{2^{k+1}}+\frac56 \right\rfloor
-\left\lfloor\frac{n}{2^{k+1}}+\frac{3}4 \right\rfloor
-\left\lfloor\frac{n}
{2^{k+1}}+\frac23 \right\rfloor
+\left\lfloor\frac{n}{2^{k+1}}+\frac{1}2 \right\rfloor\\*
&+\left\lfloor\frac{n}{2^{k+1}}+\frac{1}2 \right\rfloor
-\left\lfloor\frac{n}
{2^{k+1}}+\frac13 \right\rfloor
-\left\lfloor\frac{n}{2^{k+1}}+\frac{1}4 \right\rfloor
+\left\lfloor\frac{n}
{2^{k+1}}+\frac16 \right\rfloor;
\end{align*}
 we get the Paul digits (shifted by one position)
minus the digits from the system $\alpha=2$.
After all, this is not too unexpected, regarding what
multiplication by 3 (resp. $3/2$)
 does to a binary representation of
an integer.

The average number of nonzero digits
in the integers $0,1,\dots,m-1$ is thus given by
(leading term only)
\begin{equation*}
\frac{1}{2}\log_2m.
\end{equation*}
Observe that the constant $\frac12$ is computed here as
\begin{equation*}
\frac{1}{2}=\left(\frac{5}{6}-\frac{3}{4}\right)
+\left(\frac{2}{3}-\frac{1}{2}\right)
+\left(\frac{1}{2}-\frac{1}{3}\right)
+\left(\frac{1}{4}-\frac{1}{6}\right).
\end{equation*}

Our last example is the instance $\alpha=\frac34$.
The digits are given by
\begin{align*}
a_k(n)&=\left\lfloor\frac{n}{2^{k+1}}+\frac{13}{14} \right\rfloor
-\left\lfloor\frac{n}{2^{k+1}}+\frac {12}{14} \right\rfloor
-\left\lfloor\frac{n}{2^{k+1}}+\frac56 \right\rfloor
+\left\lfloor\frac{n}{2^{k+1}}+\frac{11}{14} \right\rfloor\\
&-\left\lfloor\frac{n}{2^{k+1}}+\frac{10}{14} \right\rfloor
+\left\lfloor\frac{n}{2^{k+1}}+\frac46 \right\rfloor
+\left\lfloor\frac{n}{2^{k+1}}+\frac{9}{14} \right\rfloor
-\left\lfloor\frac{n}{2^{k+1}}+\frac{8}{14} \right\rfloor\\
&-\left\lfloor\frac{n}{2^{k+1}}+\frac{6}{14} \right\rfloor
+\left\lfloor\frac{n}{2^{k+1}}+\frac{5}{14} \right\rfloor
+\left\lfloor\frac{n}{2^{k+1}}+\frac{2}6 \right\rfloor
-\left\lfloor\frac{n}{2^{k+1}}+\frac{4}{14} \right\rfloor\\
&+\left\lfloor\frac{n}{2^{k+1}}+\frac{3}{14} \right\rfloor
-\left\lfloor\frac{n}{2^{k+1}}+\frac{1}{6} \right\rfloor
-\left\lfloor\frac{n}{2^{k+1}}+\frac{2}{14} \right\rfloor
+\left\lfloor\frac{n}{2^{k+1}}+\frac{1}{14} \right\rfloor.
\end{align*}

The average number of nonzero digits
in the integers $0,1,\dots,m-1$ is thus given by
(leading term only)
\begin{equation*}
\frac{10}{21}\log_2m.
\end{equation*}


\section{Coquet}

Coquet \cite{Coquet83}
dealt with the sum--of--digits function of $3n$.
Probably it was never noted that the digits of $3n$ are given
by
\begin{align*}
a_k(3n)&=\left\lfloor\frac{n}{2^{k+1}}+\frac{5}{6} \right\rfloor
-\left\lfloor\frac{n}{2^{k+1}}+\frac{4}{6} \right\rfloor
+\left\lfloor\frac{n}{2^{k+1}}+\frac{3}{6} \right\rfloor\\&
-\left\lfloor\frac{n}{2^{k+1}}+\frac{2}{6} \right\rfloor
+\left\lfloor\frac{n}{2^{k+1}}+\frac{1}{6} \right\rfloor
-\left\lfloor\frac{n}{2^{k+1}} +\frac{0}{6}\right\rfloor.
\end{align*}
However, it is not clear whether one can derive his
main theorem from that.

\section{Conclusion}

We have demonstrated that an idea about 
an exotic
 data structure (jump interpolation search trees)
leads to interesting problems in elementary number theory.

Further research could concentrate on more general values
of $\al$, as well as the general 
(syntactical) study of admissible
representations. Also, one could start from different systems
than the binary one, and replace the simple difference
$(\al+1)n-\al n$  by more fancy expressions.


\section{Shallit}\label{Shallit}

After this paper was finished, I learnt about an unfinished
and unpublished draft of Shallit\footnote{Thanks, Jeffrey
 for providing
it and for several helpful remarks.} \cite{Shallit92} that
is of some relevance here. For instance, it shows that
each natural number $n$ has {\it infinitely\/} many
representations as $\sum_k a_k2^k$ with $a_k\in\{-1,0,1\}$.

This draft contains also a substantial list of references that
are otherwise not easy to find;  the subset of the more
relevant ones is
\cite{Avizienis61, Booth51,
JeMi89, Reitwiesner60}. In particular, the Paul system goes back at least to
Reitwiesner \cite{Reitwiesner60}.
Some more recent references are \cite{Thuswaldner99,
OConnor99}.

The draft also contains a transducer from ``binary'' to
``Paul'' and recursion formul\ae{}\ for the sum--of--digits
function, connecting it with $k$--regular sequences in
the sense of Allouche and Shallit \cite{AlSh92}.

Furthermore, it also has the $\frac{2^n-(-1)^n}{3}$ formula,
which relates to the number of nodes in the tree, 
see section~\ref{pathlength}, as well as an algorithm
to generate the Paul representation.

 
\bibliographystyle{plain}
\begin{thebibliography}{10}

\bibitem{AlSh92}
J.-P. Allouche and J.~Shallit.
\newblock The ring of $k$--regular sequences.
\newblock {\em Theoretical Computer Science}, 98:163--197, 1992.

\bibitem{Avizienis61}
A.~Avizienis.
\newblock Signed--digit number representation for fast parallel arithmetic.
\newblock {\em IRE Trans. Electron. Comput.}, 10:389--400, 1961.

\bibitem{Booth51}
A.~Booth.
\newblock A signed binary multiplication technique.
\newblock {\em Quart. J. Mech. Appl. Math.}, 4:236--240, 1951.

\bibitem{Coquet83}
J.~Coquet.
\newblock A summation formula related to the binary digits.
\newblock {\em Inventiones Mathematic{\ae}}, 73:107--115, 1983.

\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{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{JeMi89}
J.~Jedwab and C.~Mitchell.
\newblock Minimum weight modified signed--digit representations and fast
  exponentiation.
\newblock {\em Electronics Letters}, 25:1171--1172, 1989.

\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{Knuth68}
D.~E. Knuth.
\newblock {\em The Art of Computer Programming}, volume 1: Fundamental
  Algorithms.
\newblock Addison-Wesley, 1968.
\newblock Third edition, 1997.

\bibitem{OConnor99}
L.~O'Connor.
\newblock An analysis of exponentiation based on formal languages.
\newblock {\em Advances in cryptography--{EUROCRYPT}~'99 (Prague), Lecture
  Notes in Computer Science}, 1592:375--388, 1999.

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

\bibitem{Shallit92}
J.~Shallit.
\newblock A primer on balanced binary representations (7 pages).
\newblock 1992.

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

\end{thebibliography}



%\bibliography{C:/texfiles/pro_bib}





\end{document}


