\documentclass[11pt]{article} \textwidth= 6.25in \textheight= 9.0in \topmargin = -10pt \evensidemargin=10pt \oddsidemargin=10pt \headsep=25pt \parskip=10pt \font\smallit=cmti10 \font\smalltt=cmtt10 \font\smallrm=cmr9 %\usepackage{a4ams} \usepackage{amsfonts,amsmath,amssymb} \allowdisplaybreaks \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}} \begin{document} \begin{center} {\bf ON BINARY REPRESENTATIONS OF INTEGERS WITH DIGITS -1, 0, 1} \vskip 20pt {\bf Helmut Prodinger\footnote{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!} }\\ {\smallit The John Knopfmacher Centre for Applicable Analysis and Number Theory\\ Department of Mathematics, University of the Witwatersrand,\\ P.~O. Wits, 2050 Johannesburg, South Africa\\ {\tt helmut@gauss.cam.wits.ac.za}\\ {\tt http://www.wits.ac.za/helmut/index.htm}\\} \end{center} \vskip 30pt \centerline{\smallit Received: 4/28/00, Revised: 6/15/00, Accepted: 7/11/00, Published: 7/12/00 } \vskip 30pt \centerline{\bf Abstract} \noindent 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. \pagestyle{myheadings} \markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 0 (2000), \#A08\hfill} \thispagestyle{empty} \baselineskip=15pt \vskip 30pt \section*{\normalsize 1. 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~10 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 historical background, see Section~10.) 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 when $\al$ is either an integer or an integer divided by a power of 2 (a dyadic rational number). \vskip 30pt \section*{\normalsize 2. 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 integers. 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. \vskip 30pt \section*{\normalsize 3. The explanation} The key formula (see \cite[1.2.4, Ex.~38]{Knuth68}) is \begin{equation*} \lfloor x\rfloor+\lfloor x+\tfrac1q\rfloor+\dots+ \lfloor x+\tfrac{q-1}{q}\rfloor=\lfloor qx\rfloor,\tag{1} \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 (1). 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*} \vskip 30pt \section*{\normalsize 4. 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]\hskip0cm %\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 transducer} \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 two 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-0.5cm %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$'' transducer} \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*} \vskip 30pt \section*{\normalsize 5. Path length} 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}. \vskip 30pt \section*{\normalsize 6. 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. \vskip 30pt \section*{\normalsize 7. 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*} \vskip 30pt \section*{\normalsize 8. 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. \vskip 30pt \section*{\normalsize 9. 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. \vskip 30pt \section*{\normalsize 10. 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~5, as well as an algorithm to generate the Paul representation. \vskip 30pt \bibliographystyle{plain} \renewcommand{\refname}{\normalsize References} %\section*{\normalsize References} \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}