Minimal expansions in redundant number systems: Fibonacci bases and greedy algorithms (Q2567414): Difference between revisions
From MaRDI portal
Latest revision as of 17:09, 10 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Minimal expansions in redundant number systems: Fibonacci bases and greedy algorithms |
scientific article |
Statements
Minimal expansions in redundant number systems: Fibonacci bases and greedy algorithms (English)
0 references
4 October 2005
0 references
Let \(\{G_j\}\) denote a sequence of integers. The cost of the (redundant) digit expansion \(n= \sum_{j\geq 0}\varepsilon_j G_j, \varepsilon_j\in {\mathbb Z}\) is defined as \[ c({\mathbf \varepsilon}(n))= \sum_{j\geq 0}| \varepsilon_j|. \] In the present paper minimal expansions with respect to two base sequences are examined. In part one \(G_j=F_j\), where \(F_j\) denotes the \(j\)th term of the Fibonacci sequence. A sequence \({\mathbf \varepsilon}=(\dots,\varepsilon_2,\varepsilon_1)\in \{0,\pm 1\}^{\mathbb N}\) with finitely many nonzero elements is called admissible, if \(\varepsilon_1=0\) and none of the patterns \((-1,1),(1,1),(-1,0,1),(1,0,1),(1,0,0,1)\) or their negatives appear as subsequences of \(\mathbf \varepsilon\). An admissible sequence \({\mathbf\varepsilon}\) is called an admissible expansion of an integer \(n\), if \(n=\sum_{j\geq 1}\varepsilon_j F_j\). Then there is a unique admissible expansion of every integer \(n\). Moreover it is minimal with respect to the cost function and can be calculated by a greedy algorithm and it cannot be calculated by a deterministic transducer from right to left. However, it is possible to calculate some minimal expansion from right to left. In part two some result about the Fibonacci expansion is ported back to the \(q\)-ary case, i.e. when \(G_j=q^j\) for a fixed integer \(q\geq 2\). It is proved that the symmetric signed digit expansion can be computed by a greedy algorithm.
0 references
redundant number systems
0 references
Fibonacci numbers
0 references
Greedy algorithm
0 references
optimal digit expansions
0 references
0 references