Pm Numbers, Ambiguity, and Regularity ^{∗}

Helen Cameron^{†}  Derick Wood^{†}

Abstract

We introduce the pseudo-m-ary (Pm) number system in which numbers are represented by sums of the form ∑_{i≥0} a_{i}(m^{i+1} − 1). We characterize the Pm representations that are produced by the greedy algorithm and show that they form a regular set. In addition, we show that the set of Pm representations that are the sole representations for their corresponding numbers is also a regular set.

1 Introduction

Many number systems can be viewed as ways of representing integers based on finite or infinite integer sequences 1 = u_{0} < u_{1} < u_{2} < · · ·. A common method of finding a representation of an integer in any such number system is the greedy algorithm; see Fraenkel [Fra85]. To find the greedy representation of an integer N, we find the largest u_{i} that is no larger than N and then repeatedly we set a_{i} ⟵ ⌊N/u_{i}⌋, N ⟵ N − a_{i}u_{i}, and i ⟵ i − 1, until i = 0. In some number systems, some integers may have representations other than the one obtained via the greedy algorithm. (A number that has more than one representation in the given number system is said to be ambiguous; otherwise, it is unambiguous.)

There appears to be a close relationship between the properties of number systems and the properties of formal languages; see Shallit [Sha91], for example. Two intriguing problems about this relationship are:

Problem 1.1 For which number systems are the sets of greedy representations regular?

Problem 1.2 For which number systems are the sets of unambiguous numbers regular?

∗This work was supported under a Natural Sciences and Engineering Research Council of Canada Grant No. A-5692 and under a grant from the Information Technology Research Centre.

†Data Structuring Group, Department of Computer Science, University of Waterloo, WATERLOO, Ontario N2L 3G1, CANADA

[figure: Bin(0), the empty tree; Size: 0; Bin(h); Bin(h); Bin(h + 1), for h ≥ 0; Size: 2^{h+1} − 1]

Figure 1: A recursive definition of the perfect binary tree of height h (Bin(h)).

We introduce the pseudo-m-ary (Pm) number system and show that the set of greedy representations and the set of representations of unambiguous numbers in the Pm number system are regular sets. For any fixed integer m > 1, the Pm number system is based on the sequence m^{1} − 1, m^{2} − 1, m^{3} − 1,…. As we will see, when m = 2 (in the P2 number system), every integer is representable; however, when m > 2, only multiples of m−1 are representable.

The P2 number system has been studied previously. Allouche, Betrema, and Shallit [ABS89] characterized the set of integers that can be represented by P2 representations using only the digits 0 and 1. Their interest in the P2 number system arose from a study of the sequence of parentheses occurring in the recursive definition of the integers.

We have used the characterization of the greedy representations in the P2 number system in Cameron [Cam91] and Cameron and Wood [CW91] to establish an upper bound result for a class of binary trees. Every binary tree can be viewed as a perfect binary tree (a binary tree whose leaves all appear on one level; see Figure 1) with some perfect binary subtrees removed. Each node of a perfect binary tree has two perfect binary subtrees, so each remaining node has 0, 1, or 2 perfect binary children removed by the pruning; see Figure 2. A perfect binary subtree contains 2^{h} − 1 nodes, where h is the height of the tree (the distance of the leaves from the root of the tree). Thus, we became interested in numbers of the form ∑_{i≥0} a_{i}(2^{i+1} −1), where a_{i} = 0, 1, or 2, because they give the total size of the subtrees we have removed by pruning. These numbers are exactly the P2 representations.

Similarly, each node of a perfect m-ary tree has m perfect m-ary subtrees. Pruning such a tree removes 0, 1, 2,…, or m perfect m-ary subtrees from each remaining node. Again, because a perfect m-ary tree of height h contains (m^{h} − 1)/(m − 1) nodes, we have a relationship between the

[figure: Bin(1); Bin(1); Bin(3); Prune a Bin(3) and two Bin(1); subtrees from a Bin(4) tree.; The resulting binary tree.]

Figure 2: Pruning a complete binary tree.

number of nodes pruned from a perfect m-ary tree and sums of the form ∑_{i≥0} a_{i}(m^{i+1} −1), where a_{i} = 0, 1, 2,…, or m; that is, between m-ary trees and Pm representations.

In the following sections, all numbers discussed are assumed to be nonnegative integers, and we assume that m is some fixed integer greater than 1.

2 The Pm Number System and the Greedy Algorithm

In this section, we define the Pm number system and introduce the Pm representations obtained via the greedy algorithm.

The base m number system, for some integer m > 1, is based on the integer sequence 1 = m^{0} < m^{1} < m^{2} · · · . If we wish to represent an integer in base m, then we use the digits 0,…, m − 1, and the i^{th} digit of a base m representation is the coefficient of m^{i}. (The least significant digit corresponds to index 0, and we count up from there.) We consider the pseudo-m-ary (Pm) number system, which is based on the integer sequence 1 ≤ m^{1} − 1 < m^{2} − 1 < m^{3} − 1 < · · ·. It uses the digits 0,…, m, and the i^{th} digit of a Pm representation is the coefficient of m^{i+1} − 1.

Thus, a Pm representation is either ϵ or a sequence of integers of the form a_{n} ⋯ a_{0}, where n ≥ 0, 1 ≤ a_{n} ≤ m, and 0 ≤ a_{i} ≤ m, for all i, 0 ≤ i < n. The value of the Pm representation ϵ is 0. The value of any other Pm representation a_{n} ⋯ a_{0} is denoted by value(a_{n} ⋯ a_{0}) and is defined to be ∑_{i=0}^{n} a_{i}(m^{i+1} − 1). If we consider all non-zero Pm representations with exactly n + 1 digits, for some n ≥ 0, the Pm representation consisting of a 1 digit followed by n zero digits (that is, the Pm representation 10^{n}, using the formal language notation 0^{n} to mean a string of n zeros) has the smallest value among all non-zero Pm representations with exactly n + 1 digits. Similarly, the Pm representation consisting of n+1 digits equal to m (the Pm representation m^{n+1}) has the largest value among all non-zero Pm representations with exactly n + 1 digits. Thus, the value of the non-zero Pm representation a_{n} ⋯ a_{0} is bounded by

m^{n+1} − 1 ≤ value(a_{n} ⋯ a_{0}) ≤ m (\frac{m^{n+2} − 1}{m − 1} − n − 2) .

For m = 2, we will show that every nonnegative integer has at least one Pm representation. But, if m > 2, then only some of the nonnegative integers have Pm representations. For example, when m = 3, the integer 5 has no representation in the Pm number system. We will show that an integer has a Pm representation if and only if the integer is a nonnegativeinteger multiple of m − 1. (Since m − 1 = 1 when m = 2, we will have shown that each nonnegative integer has at least one representation in the P2 number system.)

It is well-known that m − 1 divides m^{k} − 1, for all k > 0; thus, since value(a_{n} ⋯ a_{0}) = ∑_{i=0}^{n} a_{i}(m^{i+1} − 1), value(a_{n} ⋯ a_{0}) is divisible by m − 1. Now, we show that each nonnegative-integer multiple of m − 1 is representable in the Pm number system. We will use the greedy algorithm and a result of Fraenkel [Fra85].

The greedy algorithm produces a representation a_{n} ⋯ a_{0} (if one is possible) in a number system 1 ≤ u_{0} < u_{1} < u_{2} < ⋯ for a positive integer N as follows:

     Find the largest index n such that u_{n} ≤ N.

i ⟵ n

     Repeat

a_{i} ⟵ ⌊N/u_{i}⌋
N ⟵ N − a_{i}u_{i}
i ⟵ i − 1

     Until i = 0.

Note that

∑_{i=0}^{k} a_{i}u_{i} < u_{k+1}, for all k, 0 ≤ k ≤ n,

because n is the largest index such that u_{n} ≤ N and because we remove as many multiples of u_{i} as possible from what remains of N before considering lower-order digits in the greedy representation, for all i, 0 ≤ i ≤ n. The following result of Fraenkel [Fra85] implies that, in certain number systems, the greedy representation is the only representation to satisfy

∑_{i=0}^{k} a_{i}u_{i} < u_{k+1}, for all k, 0 ≤ k ≤ n,

and that every nonnegative integer has such a representation in these number systems.

Proposition 2.1 (Fraenkel) Let 1 = u_{0} < u_{1} < u_{2} < ⋯ be any finite or infinite sequence of integers. Any nonnegative integer N has precisely one representation in the system S = {u_{0}, u_{1}, u_{2},…} of the form N = ∑_{i=0}^{n} a_{i}u_{i}, where the a_{i} are nonnegative integers that satisfy

a_{k}u_{k} + a_{k−1}u_{k−1} + ⋯ + a_{0}u_{0} < u_{k+1} (k ≥ 0).

Consider the number system S_{m−1} based on the integer sequence

1 = \frac{m − 1}{m − 1} < \frac{m^{2} − 1}{m − 1} < \frac{m^{3} − 1}{m − 1} < · · · .

This system is simply the Pm number system divided by m − 1. By Proposition 2.1, we see that, in S_{m−1}, the greedy representation a_{n} ⋯ a_{0} for a nonnegative integer p is the only representation for p that satisfies

a_{k} ≥ 0

and

∑_{i=0}^{k} a_{i} \frac{m^{i+1} − 1}{m − 1} < \frac{m^{k+2} − 1}{m − 1},

for all k, 0 ≤ k ≤ n and that there is such a representation for every nonnegative integer. Therefore, in the Pm number system, the corresponding greedy representation a_{n} ⋯ a_{0} for the nonnegative integer p(m − 1) is the only representation for p(m − 1) that satisfies

a_{k} ≥ 0

and

∑_{i=0}^{k} a_{i}(m^{i+1} − 1) < m^{k+2} − 1,

for all k, 0 ≤ k ≤ n, and there is such a representation for every nonnegativeinteger multiple of (m−1). Since only nonnegative-integer multiples of m−1 have representations in the Pm number system, a nonnegative integer has a representation in the Pm number system if and only if it is a multiple of m − 1.

3 The Regularity of Greedy Representations

We will show that the following regular language captures exactly the Pm numbers that are produced by the greedy algorithm.

Definition 3.1 Let L_{G} be the regular language

L_{G} = {1,…, m − 1}{0,…, m − 1}^{∗} + {1,…, m − 1}{0,…, m − 1}^{∗}m0^{∗}
+ m0^{∗} + ϵ.

The regular language {1,…, m − 1}{0,…, m − 1}^{∗} + ϵ is the set of Pm representations that do not have any digit equal to m. The regular language {1,…, m−1}{0,…, m−1}^{∗}m0^{∗}+m0^{∗} is the set of Pm representations that have exactly one digit equal to m and all lower-order digits are zero. Note that if a_{n} ⋯ a_{0} is in L_{G}, then a_{k} ⋯ a_{0}, where a_{k} > 0, for some 0 ≤ k < n, is also in L_{G}. Also, if we consider the Pm representations with exactly n + 1 digits in L_{G}, then we see that the Pm representation that consists of the digit m followed by n zero digits has the largest value among them all; that is, the value of the Pm representation a_{n} ⋯ a_{0} in L_{G} is bounded from above by

value(a_{n} ⋯ a_{0}) ≤ m(m^{n+1} − 1).

Now, we will show that L_{G} is the set of all Pm representations produced by the greedy algorithm.

Theorem 3.1 The regular language L_{G} consists of exactly the Pm representations produced by the greedy algorithm for nonnegative-integer multiples of m−1. Hence, the set of Pm representations produced by the greedy algorithm for nonnegative-integer multiples of m − 1 is regular.

Proof: We first show that the set of greedy representatives is a subset of L_{G}. In other words, the Pm representations produced by the greedy algorithm for the number p(m − 1) is in L_{G}, for all p ≥ 0. We use induction on p. Basis: For p = 0, the greedy representative of 0 is ϵ, which is in L_{G}. For p = 1, 2,…, m, the Pm representation produced by the greedy algorithm for the number p(m − 1) is p and p is in L_{G}. Induction hypothesis: Assume that the Pm representation produced by the greedy algorithm for the number p′(m − 1) is in L_{G}, for all 0 ≤ p′ < p, for some p > m. Induction step: Let a_{n} ⋯ a_{0} be the Pm representation produced by the greedy algorithm for the number p(m − 1). There are two cases to consider: either a_{n} is the only non-zero digit in the Pm representation a_{n} ⋯ a_{0} or there is more than one non-zero digit in the Pm representation a_{n} ⋯ a_{0}.

a_{n} is the only non-zero digit. Then, a_{n} ⋯ a_{0} = a_{n}0^{n}. Since the Pm representation is produced by the greedy algorithm, value(a_{n} ⋯ a_{0}) = a_{n}(m^{n+1} − 1) < m^{n+2} − 1. Thus, a_{n} ≤ m. But, {1, 2,…, m}0^{∗} ⊂ L_{G}; therefore, if a_{n} is the only non-zero digit, then the Pm representation a_{n} ⋯ a_{0} is in L_{G}. a_{n} is not the only non-zero digit. Let k be the second largest index of a

non-zero digit in the Pm representation a_{n} ⋯ a_{0}; that is, let a_{n} ⋯ a_{0} = a_{n}0^{n−k−1}a_{k} ⋯ a_{0}, where a_{k} > 0. Because a_{n} ⋯ a_{0} is a greedy representation, a_{i} ≥ 0 and ∑_{j=0}^{i} a_{j}(m^{j+1} − 1) < m^{i+2} − 1, for all i ≥ 0. Therefore, a_{k} ⋯ a_{0} satisfies these two conditions as well. The greedy representation of R_{k} = value(a_{k} ⋯ a_{0}) must satisfy these two conditions and, as we argued above, there is only one representation for R_{k} that satisfies these two conditions. Therefore, a_{k} ⋯ a_{0} is the greedy representative for R_{k}. Note that R_{k} = value(a_{n} ⋯ a_{0}) − a_{n}(m^{n+1} − 1) is a smaller multiple of m − 1 than p(m − 1), since value(a_{n} ⋯ a_{0}) = p(m−1) and m^{n+1}−1 is a positive multiple of m−1. By the induction hypothesis, since R_{k} < p(m − 1), the Pm representation a_{k} ⋯ a_{0} is in L_{G}. If we can show that a_{n} < m, then a_{n} ⋯ a_{0} = a_{n}0^{n−k−1}a_{k} ⋯ a_{0} is in L_{G}, too. (If a_{n} = m, then, for the Pm representation a_{n} ⋯ a_{0} to be in L_{G}, we would need a_{i} = 0, for 0 ≤ i < n. Since a_{k} > 0, we must have a_{n} < m.) Since a_{n} ⋯ a_{0} is produced by the greedy algorithm, value(a_{n} ⋯ a_{0}) < m^{n+2} − 1. Since a_{n} and a_{k} may not be the only non-zero digits in the Pm representation a_{n} ⋯ a_{0}, we have a_{n}(m^{n+1} − 1) + a_{k}(m^{k+1} − 1) ≤ value(a_{n} ⋯ a_{0}). If a_{n} ≥ m, then, since a_{k} > 0 and k ≥ 0, we have a_{n}(m^{n+1} − 1) + a_{k}(m^{k+1} − 1) ≥ m(m^{n+1} − 1) + 1(m^{k+1} − 1) ≥ m^{n+2} − 1, a contradiction. Therefore, a_{n} < m. Thus, if a_{n} is not the only non-zero digit, the Pm representation a_{n} ⋯ a_{0} is in L_{G}.

Therefore, a Pm representation produced via the greedy algorithm is in L_{G}.

Now, we show that any Pm representation in L_{G} is produced by the greedy algorithm for the corresponding number. We now show that every Pm representation a_{n} ⋯ a_{0} in L_{G} satisfies a_{i} ≥ 0 and ∑_{j=0}^{i} a_{j}(m^{j+1} − 1) < m^{i+2} − 1, for all i ≥ 0, thus proving, by Proposition 2.1, that every element of L_{G} is a greedy representation. Let a_{n} ⋯ a_{0} be in L_{G}. Clearly, a_{k} ≥ 0, for all k, 0 ≤ k ≤ n. Also, for any k, 0 ≤ k ≤ n, the Pm representation a_{k} ⋯ a_{0} (ignoring leading zeros) is in L_{G}. Now, the value of the Pm representation a_{k} ⋯ a_{0} in L_{G} is bounded from above by value(a_{k} ⋯ a_{0}) ≤ m(m^{k+1} − 1). But m(m^{k+1} − 1) < m^{k+2} − 1, so value(a_{k} ⋯ a_{0}) < m^{k+2} − 1, as required. □

4 The Pm Representations of the Unambiguous Numbers

There are many Pm representations that are not in L_{G}; namely, all those that have a digit equal to m and some other lower-order non-zero digit. Since the value of a Pm representation that is not in L_{G} is also the value of some Pm representation that is in L_{G}, the numbers corresponding to Pm representations that are not in L_{G} are ambiguous. For example, the Pm number m0^{n−2}1, which is not in L_{G}, has value m(m^{n}−1)+(m−1) = m^{n+1}−1 and so does the Pm number 10^{n}, which is in L_{G}. Thus, the number m^{n+1}−1 is ambiguous in the Pm number system. We prove that the set of numbers that are unambiguous in the Pm number system is a regular set.

Definition 4.1 Let L_{U} be the regular language

L_{U} = {1,…, m − 1}^{+}[0m + {1,…, m − 1}{0,…, m} + m0] + {ϵ, 1,…, m0}.

Thus, L_{U} contains all Pm representations that fall, in lexicographic order, between (and including) ϵ and m0, and L_{U} contains all Pm representations a_{n} ⋯ a_{0}, for n ≥ 2, such that the last two digits a_{1}a_{0} fall, in lexicographic order, between (and including) 0m and m0, and 0 < a_{i} < m, for all i, 2 ≤ i ≤ n.

Clearly, L_{U} is a subset of L_{G}; that is, a Pm representation in L_{U} has at most one digit equal to m, and, if it has a digit equal to m, then all lowerorder digits are zero. Furthermore, if a_{n} ⋯ a_{0} is in L_{U}, for some n ≥ 2, then a_{n−1} ⋯ a_{0} is in L_{U}, too.

We will show that the Pm representations in L_{U} are exactly the Pm representations of the unambiguous numbers. To do this, we first show that no two Pm representations in {0, 1,…, mm} have the same value and then we bound the values of the Pm representations in L_{U}.

Lemma 4.1 Let S_{2} be the set of Pm representations with one or two digits; that is, let S_{2} = {ϵ, 1,…, mm}. If x and y are in S_{2} and x ≠ y, then value(x) ≠ value(y).

Proof: For convenience, we treat all Pm numbers in S_{2} as if they have two digits, by adding leading zeros if necessary. Let a_{1}a_{0} and b_{1}b_{0} be in S_{2} and let a_{1}a_{0} ≠ b_{1}b_{0}. There are two cases to consider: either a_{1} ≠ b_{1}, or a_{1} = b_{1} and a_{0} ≠ b_{0}.

If a_{1} ≠ b_{1}, then assume, without loss of generality, that a_{1} < b_{1}. Consider value(a_{1}a_{0}) = a_{1}(m^{2} − 1) + a_{0}(m − 1). Since a_{1} < b_{1} and a_{0} ≤ m, we have value(a_{1}a_{0}) ≤ (b_{1} − 1)(m^{2} − 1) + m(m − 1) = b_{1}(m^{2} − 1) − (m − 1). Since b_{0} ≥ 0, we have value(a_{1}a_{0}) < b_{1}(m^{2} − 1) + b_{0}(m − 1) = value(b_{1}b_{0}).

If a_{1} = b_{1} and a_{0} ≠ b_{0}, assume, without loss of generality, that a_{0} < b_{0}. Then, value(a_{1}a_{0}) ≤ b_{1}(m^{2} − 1) + (b_{0} − 1)(m − 1). Since 0 ≤ a_{0} < b_{0} and m > 1, we have value(a_{1}a_{0}) < b_{1}(m^{2} − 1) + b_{0}(m − 1) = value(b_{1}b_{0}).

In both cases, value(a_{1}a_{0}) ≠ value(b_{1}b_{0}). □

Note that this result does not establish the unambiguity of the numbers with representations in S_{2} because it does not consider Pm representations with more than two digits. Indeed, the numbers corresponding to some two digit Pm representations are ambiguous. For example, the number m(m^{2} − 1) + m − 1 is represented in the Pm number system by m1 and 100.

Lemma 4.2 Let a_{n} ⋯ a_{0} be in L_{U}. If n < 2, then

0 ≤ value(a_{n} ⋯ a_{0}) ≤ m(m^{2} − 1).

Otherwise,

\frac{m^{n+2} − 1}{m − 1} − 2m − n ≤ value(a_{n} ⋯ a_{0}) ≤ m^{n+2} − 1 − n(m − 1).

Proof: The set of Pm representations with zero, one, or two digits is L_{U}(2) = {ϵ, 1,…, m0} and this set consists of all Pm representations that fall, in lexicographic order, between (and including) ϵ and m0. By Lemma 4.1, no two of these representations have the same value. If we list the elements of L_{U}(2) in lexicographic order, their values are strictly increasing. To see this, consider the Pm representation that comes after a_{1}a_{0} (we add leading zeros as necessary to obtain two digits). If a_{0} < m, then the next representation is a_{1}(a_{0} + 1) and

value(a_{1}a_{0}) = a_{1}(m^{2} − 1) + a_{0}(m − 1)
< a_{1}(m^{2} − 1) + (a_{0} + 1)(m − 1)
= value(a_{1}(a_{0} + 1)).

If a_{0} = m, then the next number is (a_{1} + 1)0 and

value(a_{1}a_{0}) = a_{1}(m^{2} − 1) + m(m − 1)
< a_{1}(m^{2} − 1) + (m + 1)(m − 1)
= (a_{1} + 1)(m^{2} − 1)
= value((a_{1} + 1)0).

Therefore, if a_{1}a_{0} ∈ L_{U}, then

value(ϵ) = 0 ≤ value(a_{1}a_{0}) ≤ m(m^{2} − 1) = value(m0).

If a_{n} ⋯ a_{0} ∈ L_{U} and n ≥ 2, then, by similar arguments about the last two digits of this number,

value(a_{n} ⋯ a_{2}0m) ≤ value(a_{n} ⋯ a_{0}) ≤ value(a_{n} ⋯ a_{2}m0).

If some a_{i} > 1, where 2 ≤ i ≤ n, then we can subtract 1 from a_{i} to create a Pm representation in L_{U} with smaller value than value(a_{n} ⋯ a_{0}). Thus, value(1^{n−1}0m) ≤ value(a_{n} ⋯ a_{0}), where 1^{n−1} represents a string of n − 1 ones. Similarly, if some a_{i} < m − 1, where 2 ≤ i ≤ n, then we can add 1 to a_{i} to create another Pm representation in L_{U} with greater value than value(a_{n} ⋯ a_{0}). Thus, value(a_{n} ⋯ a_{0}) ≤ value((m − 1)^{n−1}m0), where (m − 1)^{n−1} represents a string of m − 1’s of length n − 1. □

Theorem 4.3 A number is unambiguous in the Pm number system if and only if it has a representation in L_{U}. Hence, the set of Pm representations of unambiguous numbers is regular.

Proof: We split the proof into two parts. Claim 1: Each Pm representation in L_{U} is the only Pm representation with its value.

Clearly, ϵ is the only Pm representation for 0. Consider the Pm representations a_{n} ⋯ a_{0} in L_{U} with positive values. The proof is by induction on n. Basis: The set L_{U}(2) = {1,…, m0} contains the only Pm representations in L_{U}, for n = 0 and n = 1. Any Pm representation with three or more digits has value at least value(100) = m^{3}−1. The values of the Pm representations m1, m2,…, mm (the only Pm representations with at most two digits that are not in L_{U}(2)) are at least value(m1) = m^{3} −1. By Lemma 4.2, the value of a Pm representation in L_{U}(2) is at most m(m^{2} − 1) < m^{3} − 1, for all m > 1. By Lemma 4.1, no two of the Pm representations in L_{U}(2) have the same value. Therefore, each representation in L_{U}(2) is unambiguous. Induction hypothesis: Assume that each Pm representation a_{k} ⋯ a_{0} in L_{U} is the only Pm representation for value(a_{k} ⋯ a_{0}), for all k < n, for some n > 1. Induction step: Let a_{n} ⋯ a_{0} be a Pm representation in L_{U}. Assume that there exists some other Pm representation b_{k} ⋯ b_{0} (not necessarily in L_{U} or L_{G}) with the same value. There are three possibilities: either k > n, k < n, or k = n.

k > n. We show that value(a_{n} ⋯ a_{0}) < value(b_{k} ⋯ b_{0}); that is, we cannot have a Pm representation b_{k} ⋯ b_{0} with the same value as a_{n} ⋯ a_{0}.

Clearly, we have value(b_{k} ⋯ b_{0}) ≥ value(10^{k}) = m^{k+1} − 1. Since a_{n} ⋯ a_{0} ∈ L_{U}, by Lemma 4.2, value(a_{n} ⋯ a_{0}) ≤ m^{n+2} − 1 − n(m − 1). But, m^{n+2} − 1 − n(m − 1) < m^{n+2} − 1, since m > 1 and n ≥ 2. Since k > n, value(a_{n} ⋯ a_{0}) < m^{n+2} − 1 ≤ m^{k+1} − 1 ≤ value(b_{k} ⋯ b_{0}), a contradiction.

k < n. We show that the difference value(b_{k} ⋯ b_{0}) − value(a_{n−1} ⋯ a_{0}) is different from value(a_{n} ⋯ a_{0}) − value(a_{n−1} ⋯ a_{0}) = a_{n}(m^{n+1} − 1). Thus, the Pm representations a_{n} ⋯ a_{0} and b_{k} ⋯ b_{0} cannot have the same value, a contradiction.

Consider the difference value(b_{k} ⋯ b_{0})−value(a_{n−1} ⋯ a_{0}). This difference should be a_{n}(m^{n+1} − 1), since value(b_{k} ⋯ b_{0}) = value(a_{n} ⋯ a_{0}). Now,

value(b_{k} ⋯ b_{0}) ≤ m (\frac{m^{k+2} − 1}{m − 1} − k − 2) ≤ m (\frac{m^{n+1} − 1}{m − 1} − n − 1) .

Furthermore, since a_{n−1} ⋯ a_{0} ∈ L_{U}, by Lemma 4.2,

\frac{m^{n+1} − 1}{m − 1} − 2m − n + 1 ≤ value(a_{n−1} ⋯ a_{0}).

Therefore,

value(b_{k} ⋯ b_{0}) − value(a_{n−1} ⋯ a_{0})
≤ m (\frac{m^{n+1} − 1}{m − 1} − n − 1) − (\frac{m^{n+1} − 1}{m − 1} − 2m − n + 1)
= m^{n+1} − 1 − (m − 1)(n − 1)
< m^{n+1} − 1,

since m > 1 and n ≥ 2. Thus, value(b_{k} ⋯ b_{0}) − value(a_{n−1} ⋯ a_{0}) ≠ a_{n}(m^{n+1} − 1), a contradiction.

k = n. We know that a_{n} ⋯ a_{0} is in L_{U} ⊆ L_{G}; that is, a_{n} ⋯ a_{0} is produced by the greedy algorithm when it is given value(a_{n} ⋯ a_{0}). Therefore, a_{n} = ⌊value(a_{n} ⋯ a_{0})/(m^{n+1} − 1)⌋. But this implies that b_{n} cannot be larger than a_{n}; that is, b_{n} ≤ a_{n}.

Suppose b_{n} = a_{n}. Then, b_{n−1} ⋯ b_{0} is not equal to a_{n−1} ⋯ a_{0} and value(b_{n−1} ⋯ b_{0}) = value(a_{n−1} ⋯ a_{0}). Now, a_{n−1} ⋯ a_{0} is in L_{U} and, by the induction hypothesis, it is the only Pm representation for value(a_{n−1} ⋯ a_{0}). Therefore, we must have b_{n−1} ⋯ b_{0} = a_{n−1} ⋯ a_{0}, a contradiction.

Now, if b_{n} < a_{n}, then the Pm representations b_{n−1} ⋯ b_{0} and (a_{n}−b_{n})a_{n−1} ⋯ a_{0} are two different Pm representations with the same value. Since a_{n} − b_{n} > 0 and a_{n} ⋯ a_{0} is in L_{U}, the Pm representation (a_{n} − b_{n})a_{n−1} ⋯ a_{0} is also in L_{U}. We have already shown above that we cannot have some Pm representation (a_{n} − b_{n})a_{n} ⋯ a_{0} in L_{U} and some other Pm representation b_{n−1} ⋯ b_{0} such that value(a_{n} ⋯ a_{0}) = value(b_{k} ⋯ b_{0}). Thus, this case is not possible either.

Each possibility leads to a contradiction; therefore, our assumption that there exists some other Pm representation b_{k} ⋯ b_{0} that has the same value as a_{n} ⋯ a_{0} ∈ L_{U} must be false. Thus, each Pm representation in L_{U} is the only Pm representation with the corresponding value.

Claim 2: Each number that does not have a representation in L_{U} is ambiguous.

Suppose the Pm representation a_{n} ⋯ a_{0} is not in L_{U}. We construct another Pm representation for value(a_{n} ⋯ a_{0}) to show that value(a_{n} ⋯ a_{0}) is ambiguous. There are two cases to consider: either a_{n} ⋯ a_{0} is in L_{G} or a_{n} ⋯ a_{0} is not in L_{G}.

If a_{n} ⋯ a_{0} is not in L_{G}, then, by Theorem 3.1, there exists some Pm representation b_{k} ⋯ b_{0} in L_{G} such that value(b_{k} ⋯ b_{0}) = value(a_{n} ⋯ a_{0}). Thus, value(a_{n} ⋯ a_{0}) is ambiguous.

Otherwise, a_{n} ⋯ a_{0} is in L_{G} and we use the equality

m^{k+1} − 1 = m(m^{k} − 1) + (m − 1)

to build another Pm representation with the same value as a_{n} ⋯ a_{0}. There are two subcases to consider: either there are digits a_{j−1} = 0 and a_{j} > 0, for some j, 2 < j ≤ n, or there are not.

Two such digits, a_{j−1} and a_{j}, exist. If a_{0} = m, then, by the definition of L_{G}, since a_{0} is non-zero, a_{1} cannot be m. Consider the Pm representation b_{n} ⋯ b_{0}, where

b_{j} = a_{j} − 1,
b_{j−1} = a_{j−1} + m = m,
b_{1} = a_{1} + 1,
b_{0} = 0, and
b_{i} = a_{i}, otherwise.

Since j > 2, we have not defined digit b_{1} twice, so,

value(b_{n} ⋯ b_{0}) = value(a_{n} ⋯ a_{0}) − (m^{j+1} − 1)
+ m(m^{j} − 1) + m^{2} − 1 − m(m − 1)
= value(a_{n} ⋯ a_{0}).

If a_{0} < m, consider the Pm representation b_{n} ⋯ b_{0}, where

b_{j} = a_{j} − 1,
b_{j−1} = a_{j−1} + m = m,
b_{0} = a_{0} + 1, and
b_{i} = a_{i}, otherwise.

We have

value(b_{n} ⋯ b_{0}) = value(a_{n} ⋯ a_{0}) − (m^{j+1} − 1)
+ m(m^{j} − 1) + m − 1
= value(a_{n} ⋯ a_{0}).

Thus, value(a_{n} ⋯ a_{0}) is ambiguous.

Two such digits, a_{j−1} and a_{j}, do not exist. Then, either n ≤ 2, or n > 2 and a_{j} > 0, for all j, 2 ≤ j ≤ n.

Let us first consider n ≤ 2. (We add leading zeros as required to make all representations under consideration exactly three digits long.) Since a_{2}a_{1}a_{0} is in L_{G}, if any digit is m, then all lower-order digits are zero. Since a_{2}a_{1}a_{0} is not in L_{U}, either a_{2} = m or 0 < a_{2} < m and a_{1}a_{0} is in {00, 01,…, 0(m − 1), m1, m2,…, mm} or a_{2} = 0 and a_{1}a_{0} is in {m1, m2,…, mm}. Combining these two restrictions, we see that if n ≤ 2, then a_{2}a_{1}a_{0} is in {m00}+{1, 2,…, m−1}{00, 01,…, 0(m−1)}. Since a_{2} > 0, a_{1} = 0, and a_{0} < m in each case, the representation (a_{2} − 1)m(a_{0} + 1) is a valid Pm representation and

value((a_{2} − 1)m(a_{0} + 1)) = value(a_{2}a_{1}a_{0}) − (m^{3} − 1)
+ m(m^{2} − 1) + m − 1
= value(a_{2}a_{1}a_{0}).

Now let us consider n > 2 and a_{j} > 0, for all j, 2 ≤ j ≤ n. Since a_{n} ⋯ a_{0} is in L_{G}, if any digit is in m, then all lower-order digits are zero. Thus, since a_{j} > 0, for all 2 ≤ j ≤ n, we have a_{j} ≠ m, for all j, 2 < j ≤ n. Since a_{n} ⋯ a_{0} is not in L_{U}, either a_{2} = m (in which case a_{1}a_{0} = 00, since a_{n} ⋯ a_{0} is in L_{G}), or 0 < a_{2} < m and a_{1}a_{0} ∉ [0m + {1,…, m − 1}{0,…, m} + m0] (in which case a_{1}a_{0} ∈ {00, 01,…, 0(m − 1)}, since a_{n} ⋯ a_{0} is in L_{G}). Since a_{2} > 0, a_{1} = 0, and a_{0} < m in each case, the representation a_{n} ⋯ a_{3}(a_{2} − 1)m(a_{1} + 1) is a valid Pm representation and

value(a_{n} ⋯ a_{3}(a_{2} − 1)m(a_{1} + 1)) = value(a_{n} ⋯ a_{0}) − (m^{3} − 1)
+ m(m^{2} − 1) + m − 1
= value(a_{n} ⋯ a_{0}).

Thus, once again value(a_{n} ⋯ a_{0}) is ambiguous.

Therefore, each number that does not have a Pm representation in L_{U} is ambiguous. □

5 Conclusion

We have characterized the set of Pm representations that are constructed by the greedy algorithm and the set of numbers that are unambiguous in the Pm number system and shown that these are regular sets.

One question that we have not answered is whether we need all the digits 0, 1,…, m. For instance, if we are not allowed to use the digit m, would some integer that had a Pm representation no longer have any Pm representation? We see that L_{U} uses all the digits from {0, 1,…, m} and each number with a representation in L_{U} has only one Pm representation. Thus, we need all the digits 0, 1,…, m, if all nonnegative integers of the form p(m − 1) are to be represented. This observation leaves an open problem: Characterize the integers that have Pm representations if the digit set is restricted to some subset of {0, 1,…, m}.

As noted in the introduction, another more general problem that remains is: Characterize the number systems for which the set of greedy representations and the set of representations of unambiguous numbers are regular.

References

[ABS89] J.-P. Allouche, J. Betrema, and J.O. Shallit. Sur des points fixes de morphismes d’un monoïde libre. Informatique Théorique et Applications / Theoretical Informatics and Applications, 23(3):235–249, 1989.

[Cam91] Helen Cameron. Extremal Cost Binary Trees. PhD thesis, University of Waterloo, 1991.

[CW91] Helen Cameron and Derick Wood. The maximal path length of binary trees. In preparation, 1991.

[Fra85] Aviezri S. Fraenkel. Systems of numeration. The American Mathematical Monthly, 92(2):105–114, 1985.

[Sha91] Jeffrey Shallit. Numeration systems, linear recurrences, and regular sets. Technical Report CS-91-32, University of Waterloo, July