Minimal expansions in redundant number systems and shortest paths in graphs (Q1969298)

Let \(n\) and \(q\) be integers, \(q \geq 2.\) In this paper the set \[ R_q(n) = \Biggl\{ ( \varepsilon_0, \dots , \varepsilon_l) : l \in {\mathbb N}, \varepsilon_i \in \{ 0, \pm 1,\dots , \pm (q-1)\}, \;n= \sum_{i=0}^l \varepsilon_i q^i \Biggr\} \] of all representations of \(n\) in the redundant radix representation to base \(q\) with digits \(|\varepsilon_i|\leq q-1\) is studied. The cost of the representation \(( \varepsilon_0, \dots , \varepsilon_l) \in R_q(n)\) is defined as \( l+1 + \sum_{i=o}^l |\varepsilon_i|.\) The following statements are proved: (1) Given integers \(n\) and \(q\), there is an algorithm, which computes a representation \(( \varepsilon_0, \dots , \varepsilon_l) \in R_q(n)\) with minimal cost in \(O(\log |n|).\) \noindent (2) Let \(n\) and \(q\) be as above. Then there exists a representation \(( \varepsilon_0, \dots , \varepsilon_l) \in R_q(n)\) with minimal cost such that \(|\varepsilon_i|\leq q/2\) for \(0 \leq i \leq l-1\) and \(\text{sgn}(\varepsilon_l) =\text{sgn}(n)\). Remark that (1) is a generalization of a theorem of \textit{J. Demetrovics, A. Pethő} and \textit{L. Rónyai} [Acta Cybern. 14, 27-36 (1999; Zbl 0957.11004)].