A self-avoiding curve associated with sums of digits

Abstract

For each $n\in N^{\ast }$, we write $s_n=\left(1,\dots ,1,0\right)$ with $n$ times $1$. For each $a\in N$, we consider the binary representation ${\left(a_i\right)}_{i\in -N}$ of $a$ with $a_i=0$ for nearly each $i$; we denote by ${\alpha }_n(a)$ the number of integers $i$ such that $\left(a_i,\dots ,a_{i+n}\right)=s_n$. We consider the curve $C_n={\left(S_{n,k}\right)}_{k\in N^{\ast }}$ which consists of consecutive segments of length $1$ such that, for each $k$, $S_{n,k+1}$ is obtained from $S_{n,k}$ by turning right if $k+{\alpha }_n(k)-{\alpha }_n(k-1)$ is even and left otherwise. $C_1$ is self-avoiding since it is the curve associated to the alternating folding sequence. In [1], M. Mendès France and J. Shallit conjectured that the curves $C_n$ for $n\ge 2$ are also self-avoiding. In the present paper, we show that this property is true for $n=2$. We also prove that $C_2$ has some properties similar to those which were shown in [2], [3] and [4] for folding curves.

10 pages, 5 figures