Analysis of an Infinite Product Algorithm
Jean‐Paul Allouche, P. Hajnal, Jeffrey O. Shallit · SIAM Journal on Discrete Mathematics · 1989
Let $w \in (0 + 1)^*$ be a finite nonempty string of zeros and ones, and let $a_w (n)$ denote the number of (possibly overlapping) occurrences of w in the binary expansion of n. Allouche and Shallit have recently shown that there exists an effectively computable rational function $b_w (n)$ such that \[ \sum_{n\geqq 0} \log_2 (b_w (n))X^{a_w (n)} = \frac{1}{X - 1} \] for all complex X such that $| X |\leqq 1$ and $X e 1$. They gave an algorithm to determine $b_w (n)$. It is shown that the algorithm to determine $b_w (n)$ is related to a certain labeled binary tree $T(w)$. This observation allows two identities to be proven for the rational functions $b_w (n)$. Combinatorial methods are used to investigate the structure of the tree $T(w)$. As the running time of the algorithm is proportional to the total number of nodes in the tree $T(w)$, the algorithm in this paper is shown to run in polynomial time by proving that $|T(w)| =O(|w|^{11.1})$. The existence of infinitely many strings w such that $| T(w) |\geqq c| w |^3 $ is also shown.