# On the average number of registers required for evaluating arithmetic expressions

Jean-Claude Raoult, Jean Vuillemin, Philippe Flajolet

<figure><img src="image_1.png" /></figure>

## To cite this version:

Jean-Claude Raoult, Jean Vuillemin, Philippe Flajolet. On the average number of registers required for evaluating arithmetic expressions. [Research Report] IRIA-RR-228, IRIA. 1977, pp.34. hal-04716477

HAL Id: hal-04716477

https://inria.hal.science/hal-04716477v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
IRIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

<figure><img src="image_3.png" /></figure>

ON THE AVERAGE
NUMBER OF REGISTERS
REQUIRED FOR EVALUATING
ARITHMETIC EXPRESSIONS

Philippe FLAJOLET
Jean Claude RAOULT
Jean VUILLEMIN

Rapport de Recherche N° 228

Avril 1977
# ON THE AVERAGE NUMBER OF REGISTERS REQUIRED FOR EVALUATING ARITHMETIC EXPRESSIONS

P. Flajolet, J.C. Raoult, J. Vuillemin*

<figure><img src="image_4.png" /></figure>

## Résumé :

Nous étudions le nombre moyen $A_n$ de registres nécessaires pour évaluer les expressions arithmétiques de taille n. Ceci correspond aussi à la hauteur minimale de pile nécessaire pour explorer un arbre binaire aléatoire ayant r1 nœuds. Après avoir fourni diverses expressions pour $A_n$, nous montrons que :

$$A_n = \log_4 (n) + D (\log_4 n) + o(1)$$

où D est continue, périodique de période 1.

## Abstract :

Let $A_n$ be the average number of registers required for evaluating arithmetic expressions of size n, or, equivalently, the minimal stack needed for exploring binary trees with n nodes. We give explicit expressions for $A_n$ and related quantities and show that :

$$A_n = \log_4 (n) + D (\log_4 n) + o(1)$$

where D is continuous and periodic of period one.

<footnote>* IRIA-LABORIA, 78150 Rocquencourt & Université de Paris-Sud, Bat. 425, 91405, Orsay (France).</footnote>
# 1. COMPUTATION OF ARITHMETIC EXPRESSIONS AND EXPLORATION OF TREES

Consider an arithmetic expression, say :

$$ (a) (x+y^3)xt. $$

The traditional computer science representation of this expression is the binary tree. In order to evaluate (a), for given

<figure><img src="image_5.png" /></figure>

values of x,y,z,t, in a digital computer, we have to use registers and
produce code such as :

RO ← x
R1 ← y
R2 ← z
R1 ← R1↑R2
RO ← RO+R1
R1 ← t
RO ← RO×R1

which leaves the desired result in register RO, using the two registers R1 and R2 for storing intermediate values. For this particular expression, it is also possible to use the code:

RO ← y
R1 ← z
RO ← RO↑R1
<figure><img src="image_6.png" /></figure>

which is better than the previous one since it uses one less register. It
has been shown, see for instance [Se, 70] that there exists an optimal
strategy (w.r.t. the number of registers) for the computation of general
expressions formed with binary operators ; the optimal evaluation of
expression E uses one register for storing the final result, and a certain
number of extra registers, say Reg(E), for keeping intermediate results.
The value of Reg(E) only depends upon the shape of the tree representing
E ; thus, it is in fact a function from trees to integers defined by the
rules :

$$
(1) \quad (i) \ \mathrm{Reg}(\Box) = 0
$$

$$
(ii) \ \mathrm{Reg} \left( \bigcirc \atop L \atop R \right) = \min \left\{ \mathcal{L}, \mathcal{R} \right\}
$$

with $\mathcal{L}$ = max {Reg(L), 1+Reg(R)}

and $\mathcal{R} = \max \{1+\text{Reg}(L), \text{Reg}(R)\}$

This gives for example :

<figure><img src="image_7.png" /></figure>

If E is an expression involving n operators, i.e. its binary tree
representation has n internal nodes ○ and (n+1) leaves □, it is straight-
forward to show that :
$$ (2) \quad \text{Reg}(E) \leq \lfloor \log_2(n+1) \rfloor. $$

Assuming all binary trees with n internal nodes to be equally probable, we are set to study the average number $A_n$ of registers required for evaluating expressions of size n, i.e. involving n operator and (n+1) operands.

For example, if $n = 3$, we have :

<figure><img src="image_8.png" /></figure>

<figure><img src="image_9.png" /></figure>

This same quantity also arises in the analysis of an interesting algorithm for traversing (i.e. visiting each node of) binary trees.

One popular method for visiting binary trees has been named preorder by Knuth [Kn, 68] and can be described by the Alglish procedure :

```
proc PREORDER(T)
    {binary tree T}
    if T ≠ Ø : VISIT(r(T)); PREORDER(g(T)); PREORDER(d(T)) fi
cproc
```

In this notation, T is a non empty binary tree, r(T) represents its root, g(T) and d(T) its left and right subtrees ; the procedure VISIT performs some action on each of the nodes of T. Such a recursive procedure can be implemented non-recursively with the help of a stack (see [Kn, 68], [Kn, 74], [F1, 77]) as in :
proc PREORDER(T)

{binary tree T, stack S}

do do while T ≠ Ø :

VISIT(T) ; S ← d(T) ;

T ← g(T)

od

while S ≠ Ø : T ← S

od

cproc

Here ($S \Leftarrow a$) pushes $a$ on the stack $S$, ($a \Leftarrow S$) pops the top of the stack and the control structure `do B1 while p : B2 od` is equivalent to Algol's $B1; while p do begin B2; B1 end$.

The parameter we are worried about in the analysis of this algorithm is the size of the stack $S$. For a tree of size $n$ like this, this number is equal to one, while it is equal to $n$ for $n$. Although it has been shown in [de Br 72] that the average size of the stack is only :

<figure><img src="image_10.png" /></figure>

$$ \sqrt{\pi n} - \frac{1}{2} + O\left(\frac{\log n}{\sqrt{n}}\right), $$

assuming all binary trees of size $n$ to be equally probable, there are applications for which such an extra storage requirement is prohibitive.

In order to cut down on the stack size, rather than stick to a fixed order in which to enumerate subtrees, left then right in our example, it is interesting to explore the "cheap" subtree first, and the "expensive" one later. Here, "cheap" refers to the stack size required to explore the corresponding subtree. Precisely, we define the EORDER (for economical order) traversing of binary trees by the program :
proc EORDER(T)

{binary tree T}

if T ≠ O : VISIT(r(T)) ;

if Stack (g(T)) ≤ Stack (d(T)) : EORDER(g(T)) ; EORDER(d(T))

elif Stack (g(T)) ≤ Stack (d(T)) : EORDER(d(T)) ; EORDER(g(T))

fi

fi

cproc

Here `Stack (T)` is an integer associated to binary trees by rule (1)
which we rewrite equivalently as :

$$
(3) \quad (i) \quad \text{Stack}(\emptyset) = \emptyset
$$

(ii) $T \neq \emptyset \Rightarrow$

Stack(T) = if Stack (g(T)) = Stack (d(T)) : 1 + Stack (g(T))

else : max {Stack (g(T)), Stack (d(T))}

fi

Of course, an efficient implementation of EORDER needs to know quickly
the value of Stack (g(T)) ≤ Stack(d(T)). A full description and analysis of
this procedure is given by Flajolet [Fl, 77]. This implementation guarantees
that the size of the stack needed for exploring a tree having n nodes is
bounded by ⌊ log₂(n+1) ⌋ (see (2)) and its average value is the quantity Aₙ.

In section 2, we derive explicit formulae for $R_{p,n}$-the number of trees
of size $n$ for which $Reg(T) = Stack(T) = p$, hence an explicit expression for
$A_n$. These results provide information on the distribution of Reg taken over
all trees of size $n$. Section 3 is devoted to a more detailed study of the
asymptotic behaviour of $A_n$, ultimately showing :

$$
A_n = \log_4 n + D(\log_4 n) + o(1)
$$

where D has period 1.
## 2. - EXPLICIT FORMULAE FOR $R_{p,n}$ AND $A_n$.

Before computing $R_{p,n}$, we need to review some results pertaining to binary trees.

### Enumeration of binary trees

Let $B_n$ denote the number of binary trees with n nodes. The value of $B_n$ is well-known (cf. [Kn, 68] for a bibliography). A binary tree with n nodes is defined by its root, its left subtree with $n_1$ nodes and its right subtree with $n_2$ nodes, hence the recurrence relation :

$$B_n = \sum_{n_1+n_2+1=n} B_{n_1} B_{n_2} \quad (n \ge 1)$$

$$B_o = 1.$$

Considering the generating function :

$$B(z) = \sum_{n \ge 0} B_n z^n,$$

the recurrence relation yields the algebraic equation :

$$B - 1 = zB^2,$$

whose solution is :

$$B = \frac{1 - \sqrt{1 - 4z}}{2z}.$$

This gives an explicit form :

$$B = 1 + z + 2z^2 + 5z^3 + 14z^4 + \dots + B_n + \dots$$
In which

$$B_n = \frac{1}{n+1} \binom{2n}{n} = \binom{2n}{n} - \binom{2n}{n+1}$$

is the n-th Catalan number.

Definition of $R_{p,n}$, $S_{p,n}$ and $M_n$.

We are studying the number $R_{p,n}$ of formulas of length n whose evaluation requires exactly p registers. From section 1, we know that for fixed n :

$$R_{p,n} = 0 \text{ provided } p > \lfloor \log_2(n+1) \rfloor$$

It is easy to evaluate $R_{1,n}$ : any tree requiring one register is necessarily a chain, which is determined by n-1 left/right choices, so $R_{1,n} = 2^{n-1}$.

Since the only tree of size $2^p-1$ requiring p registers is perfectly balanced of height $(p+1)$, we have $R_{p,2^p-1} = 1$.

We are also interested in the number $S_{p,n}$ of trees of size n whose evaluation requires at least p registers :

$$S_{p,n} = \sum_{j \ge p} R_{j,n}$$

Finally, the average number $A_n$ of registers required for evaluating expressions of size n is given by :

$$A_n = (1 / \sum_{p \ge 0} R_{p,n}) \sum_{p \ge 0} pR_{p,n} = (1 / B_n) M_n$$

with :
$$M_n = \sum_{p \ge 0} p R_{p,n} = \sum_{p \ge i} S_{p,n}.$$

An explicit formula for $R_{p,n}$.

In section 1, (3), we defined the number of registers required for evaluating $T = \bigcirc_{T_1} \bigcirc_{T_2}$ by:

$$\mathrm{Reg}(\emptyset) = 0$$

$$ \mathrm{Reg} \left( \bigcirc_{T_1} \bigcirc_{T_2} \right) = \begin{cases} \underline{\text{if}} & \mathrm{Reg}(T_1) = \mathrm{Reg}(T_2) : 1 + \mathrm{Reg}(T_1) \\ \underline{\text{else}} & \mathrm{Reg}(T_1) = \mathrm{Reg}(T_2) : \max(\mathrm{Reg}(T_1), \mathrm{Reg}(T_2)) \\ \underline{\text{fi}} & \end{cases} $$

It follows that $\mathrm{Reg} \left( \bigcirc_{T_1} \bigcirc_{T_2} \right) = p$ in either of the following three cases:

$$(i) \quad \mathrm{Reg}(T_1) = p-1 \quad \text{and} \quad \mathrm{Reg}(T_2) = p-1$$

$$(ii) \quad \mathrm{Reg}(T_1) = p \quad \text{and} \quad \mathrm{Reg}(T_2) < p$$

$$(iii) \quad \mathrm{Reg}(T_1) < p \quad \text{and} \quad \mathrm{Reg}(T_2) = p.$$

The number of trees with a left subtree of size $n_1$, a right subtree of size $n_2$ requiring $p$ registers is thus:

$$R_{p-1,n_1} \cdot R_{p-1,n_2} + R_{p,n_1} \cdot (\sum_{j<p} R_{j,n_2}) + (\sum_{j<p} R_{j,n_1}) \cdot R_{p,n_2}$$

the three terms in this sum corresponding to the three cases above.
From this we derive an expression for $R_{p,n}$ :

$$ 
\begin{aligned}
R_{p,n} &= \sum_{n_1+n_2+1=n} (R_{p-1,n_1} \cdot R_{p-1,n_2} + R_{p,n_1} \cdot \sum_{j<p} R_{j,n_2} + \sum_{j<p} R_{j,n_1} \cdot R_{p,n_2}) \\
&= \sum_{n_1+n_2+1=n} (R_{p-1,n_1} \cdot R_{p-1,n_2} + 2R_{p,n_1} \cdot \sum_{j<p} R_{j,n_2}).
\end{aligned}
$$

This relation gives $R_{p,n_2}$ from the set of $R_{j,k}$ preceding $R_{p,n}$ in the lexicographical ordering of $\mathbb{N}^2$, thus allowing to compute all $R_{p,n}$'s.

<figure><img src="image_11.png" /><figcaption>Figure 1: Table of $R_{p,n}$ for small values of $p$ and $n$</figcaption></figure>

If we consider the generating functions :

$$ R_p(z) = \sum_{n \ge 0} R_{p,n} \cdot z^n $$

and :

$$ S_p(z) = \sum_{n \ge 0} S_{p,n} \cdot z^n = \sum_{j \ge p} R_p(z), $$

the recurrence relation on $R_{p,n}$ readily translates into :
$$ (4) \quad \left\{ \begin{array}{l} R_p = z R_{p-1}^2 + 2z R_p \cdot \sum_{j<p} R_j \qquad p \ge 1 \\ \\ R_o = 1. \end{array} \right. $$

In particular :

$$ R_1 = \frac{z}{1-2z} = z + 2z^2 + 4z^4 + \dots + 2^{n-1}z^n + \dots $$

and :

$$ R_2 = \frac{z^3}{1 - 6z + 10z^2 - 4z^3} = z^3 + 6z^4 + 26z^5 + 100z^6 + \dots $$

In order to eliminate the summation sign, we divide both sides of (4) by $z R_p$, thus :

$$ \frac{1}{z} = 2 \cdot \sum_{j<p} R_j + \frac{R_j^2}{R_p} $$

sub subtracting the analogous identity obtained for $p-1$ yields :

$$ 0 = 2R_p + \frac{R_p^2}{R_p - 1} - \frac{R_{p-1}^2}{R_p} $$

Dividing by $R_p$, we get an expression involving only the ratios
$$ U_p = \frac{R_p - 1}{R_p} : $$

$$ (5) \quad \left\{ \begin{array}{l} U_{p+1} = U_p^2 - 2 \\ \\ U_1 = \frac{R_o}{R_1} = \frac{1}{z} - 2. \end{array} \right. $$
In order to solve this recurrence, we use a trigonometric change of variable, and derive simple expressions for the generating functions $R_p$, $S_p$ and $M$. Using these, we give explicit trigonometric forms for the coefficients $R_{p,n}$, $S_{p,n}$ and $M_n$. Finally, new expressions are obtained for $R_p(z)$ and $S_p(z)$ in term of the (complex) variable $z$.

The connection between trigonometric variables and our original $z$ is then established via Cauchy contour integral formula. This in turn gives expressions for $R_{p,n}$, $S_{p,n}$ and $M_n$ in term of binomial coefficients.

### Trigonometric expressions for the generating functions

We solve (5) by setting $U_1 = 2 \cos \varphi$, $U_p = 2 \cos \varphi_p$ thus $U_{p+1} = 2 \cos \varphi_{p+1} = 4 \cos^2 \varphi_p - 2 = 2 \cos 2\varphi_p$. It follows that $\varphi_{p+1} = 2\varphi_p = 2^{p-1}\varphi$ which gives the explicit form :

$$ (6) \quad \left\{ \begin{array}{l} U_p = 2 \cos 2^{p-1} \varphi \\ \\ U_1 = 2 \cos \varphi = \frac{1}{z} - 2. \end{array} \right. $$

A trigonometric expression of $R_p$ follows from computing :

$$ \frac{R_{p-1}}{R_p} \times \dots \times \frac{R_o}{R_l} = U_p \times \dots \times U_l $$

thus :

$$ \frac{1}{R_p} = (2 \cos 2^{p-1}\varphi) (\dots) (2 \cos \varphi). $$

This product collapses if we multiply by $\sin \varphi$:

$$ \frac{\sin \varphi}{R_p} = (2 \cos 2^{p-1}\varphi) \dots (2 \cos 2\varphi) (2 \cos \varphi \sin \varphi) $$
$$ 
\begin{aligned}
&= (2 \cos^p \varphi) \dots (2 \cos 4\varphi) (2 \cos 2\varphi \sin 2\varphi) \\
&= \dots = \sin 2^p \varphi.
\end{aligned}
$$

We have thus a very simple expression for $R_p$ :

$$ (7) \qquad R_p = \frac{\sin \varphi}{\sin 2^p \varphi} $$

with :

$$ (8) \qquad \cos \varphi = \frac{1}{2z} - 1, \text{ or } z = \frac{1}{4 \cos^2 \frac{\varphi}{2}} $$

This last equality only determines $\varphi$ up to its sign ; using $\sin^2 \varphi + \cos^2 \varphi = 1$ yields $\sin^2 \varphi = \frac{1}{z} - \frac{1}{4z^2}$, and we can choose either sign for $\sin \varphi$, which determines $\varphi$ completely. It is convenient to set $\frac{\sqrt{1-4z}}{2z} = +i \sin \varphi$. Recall now the expression $B = \frac{1}{2z} - \frac{\sqrt{1-4z}}{2z} = 1+\cos \varphi - i \sin \varphi$ thus :

$$ (9) \qquad B-1 = z^2 B^2 = e^{-i\varphi}. $$

Using (9), we can rewrite (7) as :

$$ (10) \qquad \left\{ \begin{array}{l} R_p = 2i \sin \varphi \frac{t^r}{1 - t^{2r}} \\ \\ t = e^{-i\varphi}, \quad r = 2^p \end{array} \right. $$

Summing up $S_p = \sum_{j \ge p} R_p$ entails computing :

$$ \sum_{\substack{j \ge p \\ r=2^j}} \frac{t^r}{1-t^{2r}} = \sum_{\substack{j \ge p \\ k \ge 0}} t^{2^j} (2k+1) = \sum_{\substack{m, k \ge 0 \\ u=t^{2^p}}} u^{2^m} (2k+1). $$
Since $(m,k) \mapsto 2^m(2k+1)$ is a bijective mapping $\mathbb{N}^2 \mapsto \mathbb{N}^+$, this last expression equals $\frac{u}{1-u}$, thus :

$$ (11) \qquad \left\{ \begin{array}{l} S_p = 2i \sin\varphi \frac{t^r}{1-t^r}. \\ t = e^{-i\varphi}, r = 2^p \end{array} \right. $$

Elementary trigonometric manipulations yield the equivalent form :

$$ (12) \qquad S_p = -i \sin \varphi + \sin \varphi \cotg 2^{p-1} \varphi . $$

Finally, the expression for $M = \sum_{p \ge 1} S_p$ follows from summing :

$$ \sum_{\substack{p \ge 1 \\ r=2^p}} \frac{t^r}{1-t^r} = \sum_{p, k \ge 1} t^{k2^p}. $$

The application $(p,k) \mapsto k2^p$ from $\mathbb{N} \times \mathbb{N}^+ \to \mathbb{N}^+$ is surjective ; the cardinality of the inverse image of $n$ is $v_2(n)$, the unique integer such that $n = 2^{v_2(n)}(2k+1)$ for $k \ge 0, n \ge 0$. The numbers $v_2(i)$ can be computed by the rules :

$$ v_2(2i + 1) = 0 \text{ for } i \ge 0 $$

and :

$$ v_2(2i) = 1 + v_2(i) $$

<table><caption>Figure 2 : The dyadic valuation $v_2(n)$.</caption><thead><tr><th>n</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10 ...</th></tr></thead><tbody><tr><th>v<sub>2</sub>(n)</th><td>0</td><td>1</td><td>0</td><td>2</td><td>0</td><td>1</td><td>0</td><td>3</td><td>0</td><td>1 ...</td></tr></tbody></table>
The generating function M then takes the expression :

$$
(13) \qquad M = 2i \sin \varphi \sum_{n>0} v_2(n) e^{-in\varphi}.
$$

Trigonometric expressions for the coefficients.

It is known since Moivre that cos rθ and $\frac{\sin r\theta}{\sin \theta}$ are polynomials in
cos θ. Indeed :

$$
(\cos \theta + i \sin \theta)^r = \cos r\theta + i \sin r\theta
$$
$$
= T_r(\cos \theta) + i \sin \theta U_{r-1}(\cos \theta),
$$

in which $T_r$ and $U_{r-1}$ are the Tchebichef polynomials with :

$$
\deg T_r = \deg U_r = r.
$$

Thus, from (10) and (8) follows :

$$
R_p = \frac{1}{\frac{1}{2^p} - 1} \quad \text{with} \quad x = \frac{1}{2z} - 1.
$$

In order to express $R_p$ as a power series we decompose it as a sum of
simple elements :

$$
R_p = \sum_k \frac{a_k}{x - s_k}
$$

Here $s_k$ is the k-th root of $U_{2^{p-1}}$, that is : $\sin 2^p \varphi_k = 0 \Leftrightarrow \varphi_k = k\frac{\pi}{2^p}$, and
$s_k = \cos \varphi_k$ :

$$
s_k = \cos k \frac{\pi}{2^p} \quad (k = 1, \dots, 2^p - 1),
$$
and :

$$a_k = \frac{1}{\frac{d}{dx} U_{2^p-1}(s_k)}.$$

To compute $a_k$, begin with :

$$\frac{d}{d(\cos \varphi)} \frac{\sin 2^p \varphi}{\sin \varphi} = \left( \frac{2^p \cos 2^p \varphi}{\sin \varphi} - \frac{\cos \varphi \sin 2^p \varphi}{\sin^2 \varphi} \right) \frac{1}{-\sin \varphi}$$

Substituting $\varphi_k$ for $\varphi$, the second term vanishes, so that :

$$\frac{d}{dx} U_{2^p-1}(s_k) = - 2^p \frac{\cos 2^p \varphi_k}{\sin^2 \varphi_k} = (-1)^{k+1} \frac{2^p}{\sin^2 \varphi_k}.$$

Now an easy computation yields :

$$R_p = \sum_{1 \le k \le 2^p-1} \frac{a_k}{\frac{1}{2^z} - 1 - \cos \varphi_k} = \sum_{1 \le k \le 2^p-1} \frac{2z a_k}{1 - 4\cos^2 \frac{\varphi_k}{2} z}$$

Each term of the sum admits a power series expansion :

$$R_p = \sum_{1 \le k \le 2^p-1} 2z a_k \sum_{n \ge 0} 4^n \cos^{2n} \frac{\varphi_k}{2} z^n.$$

Interchanging the summation signs, and identifying $R_{p,n}$ with the coefficient of $z^n$ gives the value :

$$R_{p,n} = \sum_{1 \le k \le 2^p-1} (-1)^{k+1} 2^{2-p} \sin^2 \varphi_k 4^{n-1} \cos^{2n-2} \frac{\varphi_k}{2}.$$

Considering that $\sin \varphi_k = 2 \sin \frac{\varphi_k}{2} \cos \frac{\varphi_k}{2}$, and taking $\varphi_k = k \frac{\pi}{2^p}$ yields :

$$(14) \quad R_{p,n} = \frac{4^{n+1}}{2^{p+1}} \sum_{1 \le k \le 2^p-1} (-1)^{k+1} \sin^2 k \frac{\pi}{2^{p+1}} \cos^{2n} k \frac{\pi}{2^{p+1}}.$$
If we turn now to $S_{p,n}$, we already know :

$$S_p = -i \sin \varphi + \frac{\sin \varphi}{\sin 2^{p-1}\varphi} \cos 2^{p-1}\varphi = B-1-\cos \varphi + \cos 2^{p-1}\varphi \frac{\sin \varphi}{\sin 2^{p-1}\varphi}$$

Notice that $\cos 2^{p-1}\varphi$ is non-zero whenever $\sin 2^{p-1}\varphi = 0$, so we can develop $\sin \varphi / \sin 2^{p-1}\varphi$ in the same way as before, and multiply $a_k$ by $\cos 2^{p-1}\varphi_k$ (beware : $p$ is changed for $p-1$). Thus :

$$S_p = \sum_{n \ge 0} B_n z^n - \frac{1}{2z} + \sum_{n \ge 0} \sum_{1 \le k \le 2} 2za_k \cos 2^{p-1}\varphi_k 4^n \cos 2n \frac{\varphi_k}{2} z^n$$

Observing that $\cos 2^{p-1}\varphi_k = (-1)^k$ for $\varphi_k = k\pi/2^{p-1}$, we explicit all values and find :

$$(15) \qquad S_{p,n} = B_n - \frac{4^{n+1}}{2^p} \sum_{1 \le k \le 2} \sin^2 k \frac{\pi}{2^p} \cos^2 n k \frac{\pi}{2^p}$$

## Algebraic expressions for the generating functions

We now return to rational expressions for $R_p(z)$, $S_p(z)$.

From (8), (10) and (11) :

$$R_p = \frac{\sin \frac{\varphi}{2}}{\sin 2^p \varphi} 2 \cos \frac{\varphi}{2} = \frac{2}{\sqrt{z} U_{2^{p+1}-1} \left(\frac{1}{2\sqrt{z}}\right)}$$

and :

$$S_p = -i \sin \varphi + 2 \cos \frac{\varphi}{2} \cdot \frac{\sin \frac{\varphi}{2}}{\sin 2^{p-1}\varphi} \cos 2^{p-1}\varphi \\ = -\frac{1}{2}z + B(z) + \frac{1}{\sqrt{z}} \frac{T \left( \frac{1}{2^p \sqrt{z}} \right)}{U \left( \frac{1}{2^{p-1} \sqrt{z}} \right)}$$
Classically, the $T_j$, $U_j$ satisfy :

$$T_{j+2}(x) + T_j(x) = 2xT_{j+1}(x) \quad ; \quad T_0 = 1 \, ; \, T_1 = x$$

$$U_{j+2}(x) + U_j(x) = 2xU_{j+1}(x) \quad ; \quad U_0 = 1 \, ; \, U_1 = 2x$$

which are mere translations of trigonometrical identities.

At this point it is natural to introduce :

$$\bar{T}_j(z) = z^{n/2} T_j\left(\frac{1}{2\sqrt{z}}\right) \quad \text{and} \quad \bar{U}_j(z) = z^{n/2} U_j\left(\frac{1}{2\sqrt{z}}\right),$$

which are both polynomials in $z$. They satisfy the recurrences :

$$\bar{T}_{j+2}(z) + z \bar{T}_j(z) = \bar{T}_{j+1}(z) \quad ; \quad \bar{T}_0 = 1 \, ; \, \bar{T}_1 = \frac{1}{2}$$

$$\bar{U}_{j+2}(z) + z \bar{U}_j(z) = \bar{U}_{j+1}(z) \quad ; \quad \bar{U}_0 = 1 \, ; \, \bar{U}_1 = 1.$$

In terms of $\bar{T}$ and $\bar{U}$, the preceding formulae take the form :

$$\begin{align} R_p(z) &= \frac{z^{2p-1}}{\bar{U}^{2p+1-1}(z)}, \tag{16} \\ S_p(z) &= B(z) - \frac{1}{2z} + \frac{1}{z} \frac{\bar{T}(z)}{\bar{U}^{2p}(z)} \nonumber \end{align}$$
These expressions permit a direct computation of the generating func-
tions R<sub>p</sub> and S<sub>p</sub>. Notice that R<sub>p</sub> has a particularly simple expression and
that B(z) - S<sub>p</sub>(z) is rational.

A little bit more can be said about the polynomials that appear here.
Take for instance the $\bar{U}_j$. From the recurrence relation :

$$
\bar{U}_{j+2} = \bar{U}_{j+1} - z \bar{U}_j \text{ with } \bar{U}_o = \bar{U}_1 = 1,
$$

it is easy to determine directly their coefficients.

By means of the double generating function :

$$
Y(t,z) = \sum_{j \ge 0} \bar{U}_j(z) t^j ,
$$

we see that :

$$
Y(t,z) = \frac{1}{1-t+zt}.
$$

Hence :

$$
\bar{U}_m(z) = \sum_{k \ge 0} (-1)^k \binom{m-k}{k} z^k.
$$

In other words, the coefficients of the $\bar{U}_m$ are the upward diagonals
of Pascal triangle taken with alternating signs.

These polynomials have an interesting history : they appear as coeffi-
cients when one expresses the powers of B(z) in term of B(z) itself [Ri,68],
and as such play a role in the analysis of tree-matching algorithms [F1,77].
They also appear in the generating function of the number of trees of a
given height [Kr,70], [de Br,72]. As they generalise many properties of the
Fibonacci numbers, for instance $\bar{U}_m(-1) = F_m$ is the m-th Fibonacci number,
Kreweras has proposed to call them Fibonacci polynomials. Similarly, the
polynomials $\bar{T}_n$ are seen to correspond to the Lucas number.
Expressions of $R_{p,n}$, $S_{p,n}$ and $M_n$ with binomial coefficients

Formulae (10), (11) and (13) express $R_p$, $S_p$, $M$ in terms of $\varphi$ and
$t = e^{-i\varphi}$.

The power series expansions in terms of $t$ with $r = 2^p$, are :

$$
R_p = 2i \sin \varphi \sum_{j \ge 0} t^{(2j+1)\frac{p}{2}}
$$

$$
S_p = 2i \sin \varphi \sum_{j>0} t^{jr}
$$

$$
M = 2i \sin \varphi \sum_{j>0} v_2(j) t^j.
$$

It is thus convenient to consider $F_k(\varphi) = 2i e^{-i\varphi} \sin \varphi$ and derive
its expression in terms of $z$ :

$$
F_k = \sum_{n \ge 0} A_{n,k} z^n
$$

Cauchy's integral formula provides the *explicit connection* :

$$
A_{n,k} = \frac{1}{2i\pi} \int_C F_k(\varphi) \frac{dz}{z^{n+1}},
$$

in which $C$ is an arbitrarily small circle around the origin, oriented anti-
clockwise. In order to evaluate this integral, we set $t = e^{-i\varphi}$ where :
$$z = \frac{1}{2(\cos\varphi + 1)}, \text{ so that } z = \frac{t}{(1+t)^2} \text{ (this is also the change of variable used in [de Br, 72])}.$$

Since $f(t) = \frac{t}{(1+t)^2}$ is holomorphic in a neighbourhood of the origin with
$f(0) = 0$, $\frac{d}{dt} f(0) = 1$, we have :
$$
A_{n,k} = \frac{1}{2i\pi} \int_{C'} F_k(\varphi) \cdot \frac{1-t}{1+t} \cdot (1+t)^{2n} \frac{dt}{t^{n+1}}
$$

Since :

$$
F_k(\varphi) = \left(\frac{1}{t} - t\right) t^k
$$

we have :

$$
A_{n,k} = \frac{1}{2i\pi} \int_{C'} (1-t^2)(1+t)^{2n} \frac{dt}{t^{n+2-k}},
$$

and $A_{n,k}$ is the term of order $n+1-k$ in the power serie expansion of :

$$
(1-t)^2 (1+t)^{2n} = \sum_{j \ge 0} \left[ \binom{2n}{j} - 2 \binom{2n}{j-1} + \binom{2n}{j-2} \right] t^j
$$

This provides the connection we are looking for :

$$
(17) \qquad 2i \sin \varphi e^{-ik\varphi} = \sum_{n \ge 0} \left[ \binom{2n}{n-1+k} - 2\binom{2n}{n+k} + \binom{2n}{n+1+k} \right] z^n.
$$

Direct substitution in formulae (10), (11), (13) yields :

$$
R_{p,n} = \sum_{j \ge 0} \left[ \binom{2n}{n-1+q} - 2\binom{2n}{n+q} + \binom{2n}{n+1+q} \right] \\
q = 2^p (2j+1)
$$

which, using the symmetry $\binom{2n}{n+1-q} = \binom{2n}{n-1+q}$ can be written as :

$$
(18) \quad R_{p,n} = \sum_{q=2^p(2j+1)} \left[ \binom{2n}{n+1-q} - \binom{2n}{n-q} \right],
$$

a formula in which $j \in \mathbb{Z}$ ranges over all integers.
Similarly :

$$
(19) \quad S_{p,n} = - B_n + \sum_{q=2}^{p} \left[ \binom{2n}{n+1-q} - \binom{2n}{n-q} \right] \quad j \in \mathbb{Z}
$$

and we get the simple expression :

$$
(20) \quad M_n = \sum_{j \neq 0} v_2(j) \left[ \binom{2n}{n+1-j} - \binom{2n}{n-j} \right]
$$

where $v_2$ is extended naturally to $\mathbb{Z}$ by $v_2(-q) = v_2(q)$ for $q \neq 0$.

3. - ASYMPTOTIC EVALUATIONS

Results (14), (15) from section 2 give some indications on the asymptotic
behaviour of $R_{p,n}$ and $S_{p,n}$ :

(i) For fixed p, as n → ∞

$$
R_{p,n} \sim \frac{4^{n+1}}{2^{p+1}} \sin^2 \frac{k\pi}{2^{p+1}} \cos^{2n} \frac{k\pi}{2^{p+1}}
$$

(i.e. a vanishing fraction of $B_n$).

(ii) For given n as p varies :

$$
p \le \frac{1}{2} \log_2 n - \log_2 \log n \Rightarrow S_{p,n} = B_n (1 - O(e^{-c \log^2 n}))
$$

$$
p \ge \frac{1}{2} \log_2 n - \log_2 \log n \Rightarrow S_{p,n} = B_n O(e^{-c \log^2 n})
$$
This confirms for $R_{p,n}$ a distribution with a strong peak (see Fig. 1), centered nearby $p_o = \frac{1}{2} \log_2 n$, all terms at a distance from $p_o$ greater than $\log_2 \log n$ being exponentially small.

### Asymptotic equivalent of $M_n$

We now turn to the evaluation of $M_n$ starting with the expression :

$$ (21) \qquad M_n = \sum_{i>0} v_2(i) \left[ \binom{2n}{n+i+1} - 2\binom{2n}{n+i} + \binom{2n}{n+i-1} \right] $$

At this point, it is convenient to introduce the difference operator $\Delta$ defined by $\Delta_i F = F[i+1] - F[i]$ (cf. [Jo,39]), thus expressing (21) as :

$$ M_n = \sum_{i>0} v_2(i) \Delta_i^2 \binom{2n}{n+i-1} $$

with $\Delta_i^2 = \Delta_i \Delta_i$.

The problem in the evaluation of (21) arises from the term $v_2(i)$, which has a rather erratic behaviour. In order to smooth it out, we use summation by parts (also known as Abel's transformation), thus obtaining :

$$ (22) \qquad M_n = - \sum_{i>0} \left( \sum_{0<j \le i} v_2(j) \right) \Delta_i^3 \binom{2n}{n+i-1} $$

In order to simplify the term $\sum_{0<j \le i} v_2(j)$, consider the binary representations of two consecutive integers $j-1$ and $j$, for $j \ge 1$ :

$$ \text{BIN}(j-1) = u \ 0 \ 1 \ 1 \ \dots \ 1 $$

and :

$$ \text{BIN}(j) = u \ 1 \ 0 \ 0 \ \dots \ 0 $$
with $u \in \{0,1\}^*$. The number of trailing zeroes in $\text{BIN}(j)$ is precisely $v_2(j)$. If we let $S_2(j)$ denote the sum of the digits of $j$ in its binary representation, i.e, the number of ones in $\text{BIN}(j)$, this observation shows :

$$v_2(j)-1 = S_2(j-1) - S_2(j),$$

thus :

$$\sum_{0<j\le i} v_2(j) = i - S_2(i).$$

Remark that, since $v_2$ is multiplicative, i.e., $v_2(r) + v_2(s) = v_2(r.s)$ this last expression is also $v_2(i!) = i - S_2(i)$, the exponent of 2 in the prime decomposition of i factorial. Substituting in (22) yields :

$$(23) \qquad M_n = B_n + \sum_{i>0} S_2(i) \Delta_i^3 \binom{2n}{n+i-1}$$

where

$$B_n \binom{2n}{n} - \binom{2n}{n+1} = \frac{1}{n+1} \binom{2n}{n}.$$

Another summation by part leads to :

$$(24) \qquad M_n = B_n - \sum_i \left( \sum_{0<j<i} S_2(j) \right) \Delta_i^4 \binom{2n}{n+i-2}$$

Real progress has been made here : the sum

$$T(i) = \sum_{0<j<i} S_2(j)$$

can be computed by simply counting the number of ones contained in each column of the table $\text{BIN}(1), \dots, \text{BIN}(i)$; it satisfies the recurrence :

$$T(1) = 0$$

$$\text{and} \quad T(2^P + k) = p \cdot 2^{P-1} + k + T(k) \quad \text{for } 0 \le k \le 2^P$$

From there, we can derive the elementary approximation
$$ \frac{1}{2} i \log_2 i - \frac{1}{2} i \log_2 \frac{4}{3} \le T(i) \le \frac{1}{2} i \log_2 i $$

which using the classical Gaussian approximation of binomial coefficients
(see below) eventually leads to the asymptotic estimation :

$$ A_r = \frac{M_n}{B_n} = \log_4 n + O(1) $$

Exact analytic expression of the primitive of $v_2$

A much more explicit treatment has been pointed out to us by H.Delange
who derived in [De,75] the following exact expression of T(i) :

**Theorem (Delange)** : There exists a function F, continuous over the reals
periodic with period 1, such that, for each integer $i \ge 1$ :

$$ T(i) = \frac{1}{2} i \log_2 i + i F(\log_2 i). $$

Function F is defined with the help of :

$$ g(x) = \begin{cases} + \frac{x}{2} & \text{for } 0 \le x \le \frac{1}{2} \\ \frac{1-x}{2} & \text{for } \frac{1}{2} \le x \le 1 \end{cases} $$

$$ \text{and} \quad h(x) = \sum_{r \ge 0} 2^{-r} \cdot g(2^r x). $$

Function h appears as a superposition of triangular functions, as
suggested in the figure :

<figure><img src="image_12.png" /><figcaption>Figure 3</figcaption></figure>
The function h is a continuous and non differentiable function similar
to that given by van der Waerden in [vdW, 30].

Finally,

$$
F(x) = \frac{1}{2} \alpha(x) - 2^{\alpha(x)} h(\alpha(x))
$$

with

$$
\alpha(x) = \lfloor x \rfloor + 1 - x.
$$

Function F is also continuous and non differentiable. Another relation
between F and S₂ is given in [De, 75 p.35] :

$$
\int_{0}^{x} S_{2}(\lfloor t \rfloor) \, dt = \frac{1}{2} \times \log_{2} x + x F(\log_{2} x) + h(x) \quad (25)
$$

expression which is valid for any positive real x.

Asymptotic equivalent of binomial coefficients

These results are all we ne d to handle the contribution of v₂(i) to
the sum (22). As for the binomial coefficients, we use an approximation
by Gaussian distribution, well known in probability theory (see
[Fe 57 ] ) :

$$
\binom{2n}{n+k} = \binom{2n}{n} e^{-\frac{k^2}{n}} \left(1 + O\left(\frac{\log n}{n}\right)\right)
$$

$$
\text{for} \quad 0 \le k \le \sqrt{1 \log n}. \qquad (26)
$$

Here $0 (u^*)$

is to be interpreted as $O(u^k)$ for some $k \in \mathbb{N}$,
and $\log n$ is the natural logarithm of $n$.

$$
\text{Let} \quad H_j(t) = e^{t} \frac{d^j}{dt^j} [e^{-t^2}]
$$
denote the j-th Hermite polynomial, thus

$$
H_0 = 1, H_1 = -2t, H_2 = 4t^2 - 2, H_3 = -8t^2 + 12t, \dots
$$

An elementary computation shows that

$$
\Delta_k^j \binom{2n}{n+k} \cong \binom{2n}{n} e^{-\frac{k^2}{n}} \frac{H_j\left(\frac{k}{\sqrt{n}}\right)}{h^{j/2}}
$$

for $k \le \sqrt{n} \log n$ and, in particular, one can check that:

$$
\Delta_k^3 \binom{2n}{n+k} = \frac{1}{n\sqrt{n}} \binom{2n}{n} e^{-t^2} \left[ H_3(t) + O\left( \frac{\log^n}{\sqrt{n}} \right) \right]
$$

$$
\text{for} \quad t = \frac{k}{\sqrt{n}} \le \log n \qquad (27)
$$

Detailed study of M,

Going back to M<sub>n</sub>, we write (23) as :

$$
M_n = B_n + \sum_{0<i\le\sqrt{n}} S_2(i) \Delta^3 \binom{2n}{n+i-1} + \sum_{i>\sqrt{n}} S_2(i) \Delta^3 \binom{2n}{n+i-1}.
$$

$$
\text{Since } \binom{2n}{n+i} = \binom{2n}{n} O(e^{-\log^2 n}) \text{ for } i > \sqrt{n} \log n,
$$

the last term is of order

$$
O(B_n - n^* e^{-\log^2 n}) = O(B_n) ;
$$

using (27) , we write :

$$
M_n = B_n + \sum_{t \in \mathcal{J}} S_2(t\sqrt{n}) e^{-t^2} \binom{2n}{n} \frac{1}{n\sqrt{n}} \cdot [H_3(t) + O\left(\frac{\log^n}{\sqrt{n}}\right)] + o(B_n),
$$
where

$$
\sigma = \left\{ \frac{j}{\sqrt{n}} \mid 1 \le j \le \sqrt{n} \log n \right\} .
$$

The sum between brackets can be distributed, the second term being
bounded by

$$
|\sigma| \cdot O\left(\frac{\log n}{n\sqrt{n}} \cdot \left(\frac{2n}{n}\right) \cdot \left(\frac{\log^* n}{\sqrt{n}}\right)\right) = O\left(B_n \frac{\log^* n}{\sqrt{n}}\right)
$$

$$
\text{Thus} \quad M_n = B_n + \frac{1}{n} \binom{2n}{n} \sum_{t \in \sigma} S_2(t\sqrt{n}) e^{-t^2} H_3(t) \frac{1}{\sqrt{n}} + o(B_n).
$$

The middle term is a Riemann sum of the function

$$
\varphi(t) = S_2(\lfloor t\sqrt{n} \rfloor) e^{-t^2} H_3(t)
$$

within the interval $[0, \log n]$; it can be approximated by the integral

$$
\int_{0}^{\log n} \varphi(t) dt
$$

as follows : applying Taylor's formula to

$$
[H_2(t) e^{-t^2}]^{\frac{k}{\sqrt{n}}} \text{ yields} \\
\frac{k-1}{\sqrt{n}}
$$

$$
\int \frac{k}{\sqrt{n}} H_3(t)e^{-t^2} dt = \frac{1}{\sqrt{n}} e^{-\frac{k}{n}} H_3\left(\frac{k}{\sqrt{n}}\right) - \frac{1}{2n} e^{-\tau_k^2} H_4(\tau_k) \\
\frac{k-1}{\sqrt{n}}
$$

$$
\text{for some } \frac{k-1}{\sqrt{n}} < \tau_k < \frac{k}{\sqrt{n}}.
$$

Multiplying both sides by

$$
S_2(k) = S_2(\lfloor t \rfloor)
$$

and summing for $k = 1, \dots, \lfloor \sqrt{n} \log n \rfloor$ :
$$
\int_0^{\log n} S_2(\lfloor t\sqrt{n} \rfloor) e^{-t^2} H_3(t)dt = \sum_{t \in \sigma} \frac{1}{\sqrt{n}} S_2(\lfloor t\sqrt{n} \rfloor) e^{-t^2} H_3(t) \\
- \frac{1}{2n} \sum_{1 \le k \le \sqrt{n} \log n} S_2(k) H_4(\tau_k) e^{-\tau_k^2}.
$$

Since $S_2(k) \le \lfloor \log_2 k \rfloor$,

the absolute value of the second term is bounded by

$$
\frac{1}{2n} \log_2(\sqrt{n} \log n) \sum_{1 \le k \le \sqrt{n} \log n} |H_4(\tau_k)| e^{-\tau_k^2} = o\left(\frac{\log^* n}{\sqrt{n}}\right)
$$

We have established :

$$
M_n = B_n + \frac{1}{n} \binom{2n}{n} \int_0^{\log n} S_2(\lfloor t\sqrt{n} \rfloor) e^{-t^2} H_3(t) dt + o(B_n).
$$

The corresponding integral $\int \frac{1}{\log n}$ is exponentially small since

$$
\begin{align*}
\left| \int_{\log n}^{\infty} S_2(\lfloor t\sqrt{n} \rfloor) e^{-t^2} H_3(t) dt \right| &\le \int_{\log n}^{\infty} \left| \log_2(t\sqrt{n}) \cdot e^{-t^2} H_3(t) \right| dt \\
&\le \int_{\log n}^{\infty} \left| (\log_2 t + \frac{1}{2}t) e^{-t^2} \cdot H_3(t) \right| dt = o(1)
\end{align*}
$$

We write
$$M_n = B_n + \frac{1}{n} \binom{2n}{n} I_n + o(B_n)$$

$$
\text{with} \qquad I_n = \int_0^\infty S_2(\lfloor t\sqrt{n} \rfloor) e^{-t^2} \cdot H_3(t) dt \quad (28)
$$
Using Delange's formula (25),

$$U(x) = \int_{0}^{x} S_{2}(\ln t) dt = \frac{1}{2} x \log_{2} x + x F(\log_{2} x) + h(x),$$

we compute $I_n$ by parts :

$$I_n = \left[ \frac{1}{\sqrt{n}} U(t\sqrt{n}) e^{-t^2} H_3(t) \right]_0^\infty - \frac{1}{\sqrt{n}} \int_0^\infty U(t\sqrt{n}) e^{-t^2} H_4(t) dt.$$

The first term reduces to zero for at least two reasons, and :

$$I_n = \frac{1}{\sqrt{n}} \int_0^\infty \left[ \frac{1}{2}(t\sqrt{n})\log_2(t\sqrt{n}) + (t\sqrt{n})F(\log_2(t\sqrt{n}))+h(t\sqrt{n}) \right] e^{-t^2} H_4(t) dt.$$

Splitting in four :

$$\begin{align*}
I_n &= -\frac{1}{2} \int_0^\infty t \log_2 t H_4(t) e^{-t^2} dt - \frac{1}{4} \log_2 n \int_0^\infty t H_4(t) e^{-t^2} dt \\
&\quad - \int_0^\infty t H_4(t) F\left(\frac{1}{2}\log_2 n + \log_2 t\right) e^{-t^2} dt - \frac{1}{\sqrt{n}} \int_0^\infty h(t\sqrt{n}) H_4(t) e^{-t^2} dt \\
&= -\frac{1}{2} I_1 - \frac{1}{4} \log_2 n \quad I_2 - I_3 - \frac{1}{\sqrt{n}} \quad I_4.
\end{align*}$$

Each integral is computed in turn.
$$
\begin{align*}
I_1 &= \int_0^\infty t \log_2 t H_4(t) e^{-t^2} dt = - \frac{1}{\log_2 2} \int_0^\infty (\log t+1) H_3(t) e^{-t^2} dt \\
&= - \frac{1}{\log_2 2} \int_0^\infty \log t (-8t^2+12t) e^{-t^2} dt - \frac{2}{\log_2 2} \\
&= - \frac{1}{\log_2 2} \int_0^\infty \log t^2 (-2t^2+3) e^{-t^2} dt - \frac{2}{\log_2 2} \\
&= - \frac{1}{\log_2 2} \int_0^\infty \log x (3-2x) e^{-x} dx - \frac{2}{\log_2 2} \\
&= - \frac{3}{\log_2 2} \int_0^\infty \log x e^{-x} dx + \frac{2}{\log_2 2} \int_0^\infty x \log x e^{-x} dx - \frac{2}{\log_2 2} \\
&= - \frac{1}{\log_2 2} \int_0^\infty \log x e^{-x} dx .
\end{align*}
$$

This last integral is classical (see [Bu. 33]) and its value is - γ,
γ = 0.577 being Euler's constant.

Simple integrations by parts give $I_2 = -2$; as for $I_4$, the function $h(t\sqrt{n})$ ranges between 0 and 1, thus $I_4$ has some definite value and

$$
\frac{1}{\sqrt{n}} I_4 = o(1).
$$

There just remains $I_3 = K(\log_4 n)$, where

$$
(29) \quad K(u) = \int_0^\infty t H_4(t) F(u+\log_2 t) e^{-t^2} dt
$$

Since F is periodic with period 1 then so is K. The change of
variable x = u + log₂t shows that K is indefinitely differentiable.
We have thus proved.

**Theorem** : The average number $A_n = M_n/B_n$ satisfies

$$
A_n = \log_4 n + \mathcal{O}(\log_4 n) + o(1)
$$
in which

$$D(u) = 1 - \frac{\gamma}{2\log_2} + K(u),$$

$K(u)$ being the periodic function defined by (29).

**Note**: Apart from the periodic term, one can, in principle, develop an asymptotic expansion as far as needed. H.Delange (private communication) has also computed the Fourier series of $D$:

$$D(t) = \sum_{k \in \mathbb{Z}} a_k e^{i2k\pi t}$$

and finds:

$$a_o = \frac{1}{2} - \frac{\gamma + 2}{2 \log_2 2} + \log_2 \pi,$$

which is the mean value of $D(t)$, and for $k \neq 0$,

$$a_k = \frac{2k\pi i - \log_2 2}{\log_2 2} \Gamma\left(\frac{k\pi i}{\log_2 2}\right) \zeta\left(\frac{2k\pi i}{\log_2 2}\right)$$

where $\Gamma$ and $\zeta$ are the classical gamma and Riemann's zeta functions.

The values of $A_n$ have been machine computed for $n$ ranging from 2 to 300 by means of formula (20). The results are plotted on figure 4, where the horizontal axis represents values of $n$ in a logarithmic scale and the vertical axis represents values of $A_n - \log_4 n$.
<figure><img src="image_13.png" /><figcaption>Figure 4</figcaption></figure>

The diagram shows an excellent agreement of $A_n$ to $\log_4 n$ abrealy for small values of n. It also shows the rapid convergence of $M_n - \log_4 n$ to the term $D(\log_4 n)$ centered around $a_o \approx 0.292$, whose periodicity is apparent.

Acknowledgements : We are grateful to H.Delange for his help with the asymptotic expansion. N.G. de Bruijn, by an early result on a related problem stimulated our interest. M.Fiolet and J.L.Rémy both communi-cated interesting observations on the problem.
Bibliographical references :

[Bu, 33] : R.S. Burington, "Handbook of mathematical tables and formulas", Mc Graw Hill (1933, 4-th edition 1965), integral n° 435.

[De, 75] : H.Delange, "Sur la fonction sommatoire de la fonction somme des chiffres", L'enseignement mathématique, T.XX1 fasc. 1 (1975).

[de Br, 72] : N.G.de Bruijn, D.E. Knuth, S.O.Rice, "The average height of planted plane trees", Graph theory and computing, R.C.Read (Ed.),Ac.Press (1972) pp.15-22.

[Fe, 57] : W.Feller, "An introduction to probability theory and its applications", vol.1,2.nd edition, Wiley (New-York, 1957).

[Fl, 77] : Ph.Flajolet, "Analysis of tree matching" Rapport IRIA (to appear).

[Jo, 39] : Ch.Jordan, "Calculus of finite differences", Chelsea Pub. C° (New-York, 1965)

[Kn, 68] : D.E.Knuth, "The art of computer programming" vol.1, Addison Wesley (1968) pp. 315 sq.

[Kn, 74] : D.E.Knuth, "Structured programming with go to statements", Computing surveys, vol.6, n°4 (1974) pp. 261-302.

[Kr,70] : G.Kreweras, "Sur les éventails de segments", Cahiers du B.U.R.O. 15 (1970) pp. 1-41.

[Ri, 68] : J.Riordan, "Combinatorial identities", J.Wiley & Sons (1968.)

[Se, 70] : R.Sethi, J.D. Ullman, "The generation of optimal code for arithmetic expressions", JACM 17,4 (Oct.1970) pp.715-728.

[vdW,30] : B.L. van der Waerden, "Ein einfaches Beispiel einer nicht-differenzierbaren stetigen Funktion", Math.Z. 32 (1930) pp. 474-475.