Determining Smallest Path Size of Multiplication
Transducers Without a Restricted Digit Set
Aditya Mittal and Karthik Mittal
February 19, 2021
Abstract
Directed multiplication transducers are a tool for performing non-
decimal base multiplication without an additional conversion to base 10.
This allows for faster computation and provides easier visualization de-
pending on the problem at hand. By building these multiplication trans-
ducers computationally, new patterns can be identified as these trans-
ducers can be built with much larger bases and multipliers. Through
a Python-based recursive approach, we created artificial multiplication
transducers, allowing for the formation of several unique conjectures specif-
ically focused on the smallest closed loop around a multiplication trans-
ducer starting and ending at zero. We show a general recursive pattern
for this loop; through this recurrence relation, the length of the smallest
closed loop for a particular transducer base b along with the range of mul-
tipliers having this particular length for multiplier m was also identified.
This research is expected to be explored further by testing reductions of
the digit set and determining whether similar properties will hold.
1 Introduction
Directed multiplication transducers are tools to multiply a number by base
b without the need for conversion into an intermediary base such as base 10.
These transducers can run at computationally faster speeds due to this property.
Finding patterns in these transducers (e.g. recursive formulas and minimum
path lengths for specific base and multiplier transducers) can introduce faster
methods for finding bases and create new breakthroughs in the field of quotient
sets.
This paper analyzes multiplication transducers with no excluded digits and
determines patterns in paths (where all states in the path are distinct) within
the multiplication transducer starting and ending with zero as a state. For all
1
bases b and multipliers m, a generalized conclusion can be made on the length
and values of states within the shortest path.
This paper presents a formula for the length of the shortest possible quotient
set given base b and multiplier m and provides a recursive solution for finding
this using depth first search and Python libraries. This newfound method of
identifying these paths can lead to faster computational analysis regarding the
multiplication of numbers in different bases; research will be performed in the
future to find this formula for restricted digits.
The applications of multiplication transducers are varied, but they can be
seen mostly in number theory and automata. By recognizing these paths, faster
computations can be made, and shortcuts can be found to emerging problems
within the field.
1.1 Overview of Multiplication Transducers
Multiplication transducers can consolidate the information stored in base
multiplication into an easily explainable diagram [1] [3]. Base multiplication
has five essential components when in step i: the carry-in value c
i
, the read
value r
i
, the total value t
i
, the write value w
i
and the carry over value c
i+1
.
Elementary one-digit base ten multiplication (which has only one step) can be
discussed in order to understand these characteristics.
Example: Let’s take a base ten example where we are multiplying 5 by 6. In
variables, this means m = 6, b = 10, and r = 5. We know this can be done with
multiplication, but this can also be completed using multiplication transducers.
Some notes can be taken:
• The carry-over value for the first step is 0, because we aren’t carrying over
anything. This means that c
0
= 0.
• The read value for the first step is 5, which means r
0
= 5. Note that if
the read value was 15 for instance, then r
0
= 5 and r
1
= 1.
Step 1 (i = 0): c
0
= 0 (our initial state) and r
0
= 5. The following is
determined:
• We first compute the total. This can be done by multiplying our current
read by our multiplier, and then adding over any carry values from earlier.
This gives us a total of (5 ∗ 6) + 0 = 30.
• Next, we have to calculate the carry value. Since 30 consists of 3 10’s, this
means that the carry value or c
1
= b
30
10
c = 3.
• Lastly, we have to calculate the write value or the value that we will write
down from our first step. This is calculated by finding the remainder when
dividing the total from the base. This means that the first write value or
w
0
= 30 (mod 10) = 0.
2
Some things to note before the next step:
• The carry-over value for the second step is 3, which means that c
1
= 3.
• The read value for the second step is 0 because our read was only one
digit. This means that r
1
= 0.
Step 2 (i = 1): c
1
= 3 and r
0
= 0. The following is determined:
• We first compute the total. This can be done by multiplying our current
read by our multiplier, and then adding over any carry values from earlier.
This gives us a total of (6 ∗ 0) + 3 = 3.
• Next, we have to calculate the carry value. Since 3 consists of 0 10’s, this
means that the carry value or c
1
= b
3
10
c = 0.
• Lastly, we have to calculate the write value or the value that we will write
down from our first step. This is calculated by finding the remainder when
dividing the total from the base. This means that the first write value or
w
0
= 3 (mod 10) = 3.
Note that both our read value and carry value for the third step are zero.
This means that our total will be zero, which means that the write value will
be zero. Therefore, we are done with our calculations. We have w
0
= 0 and
w
1
= 3, so our final answer is w = 30.
This can now be expressed with variables. For a one-digit r by m base ten
multiplication operation, c
0
= 0 since there is no underlying carry value from a
previous multiplication. r is the read value while m is the multiplier. The total
can be represented as:
t
0
= r
0
m + c
0
= rm + c
0
= 10c
1
+ w
0
(1)
The equation above is justified since the carry value c
i+1
is always written
when the write value is too large to be expressed, like in base ten multiplication
operations. In this case, c
1
would be w
1
since r
1
= 0 and r
1
m = 0 (assuming
that r and m are both one digit). However, when dealing with larger numbers,
this number will be carried over to the next multiplication, until the operation
is solved, so that the carry over value c
i+1
becomes the carry in value.
We can expand this concept to any r by m multiplication operation in base
b. Let l
w
be the length of the final write value w in base b and l
r
be the length
of the read value in base b. Then, for r and w in base ten,
w =
l
w
−1
X
i=0
w
i
b
i
, r =
l
r
−1
X
i=0
r
i
b
i
(2)
For r and w in base b, r = [r
l
r
−1
r
l
r
−2
...r
0
]
b
and w = [w
l
w
−1
w
l
w
−1
...w
0
]
b
. The
read value r
i
for multi-digit operations will be the last value index of r for the
3
Figure 1: Representation of the multiplication transducer T
4,3
.
first operation (i = 0), the penultimate value index for the second (i = 1), and
so on. Therefore, the generalized total for step i in a base b multiplication
operation can be written as:
t
i
= r
i
m + c
i
= bc
i+1
+ w
i
(3)
The write value w
i
and the carry over value c
i+1
are found with:
c
i+1
=
t
i
b
; w
i
= t
i
(mod b) (4)
A multiplication transducer represents all the distinct combinations of this
base multiplication for a predefined multiplier m and base b, iterating through
the different possible combinations between the read value r and the carry in
value c
i+1
. In multiplication transducers, carry in values are often represented
by states (denoted by circles). As shown in Figure 4, the corresponding read
value r
i
and write value w
i
is written adjacent to the arrow pointing from state
c
i
to c
j
, in the notation (r
i
, w
i
). The total is calculated using a different
interpretation of the equation above:
t
i
= r
i
m + c
i
= bc
j
+ w
i
(5)
The carry value c
i
= {0, 1, ..., m − 1} and read value r
i
= {0, 1, ..., b −
1} represent the total of b
2
combinations in the multiplication transducer of
designated base b and multiplier m or T
m,b
.
1.2 Base 3 Example
Let’s take an example of m = 4 and b = 3. Let r = [20]
10
= [202]
3
. We
can use multiplication transducers to determine [202]
3
∗ 4 without converting to
4
base 10.
Step 1 (i = 0): c
0
= 0 (our initial state) and r
0
= 2. The following is
determined:
• t
0
= r
0
m + c
0
= 2 ∗ 4 + 0 = 8
• c
1
= b
t
0
b
c = b
8
3
c = 2
• w
0
= t
0
(mod b) = 8 (mod 3) = 2
• c
0
to c
1
: The state in Figure 4 changes from 0 to 2 with a read value of 2
and a write value of 2. This corresponds with our calculations in Step 1,
as r
0
= 2 and w
0
= 2.
Step 2 (i = 1): c
1
= 2 and r
1
= 0. The following is determined:
• t
1
= r
1
m + c
1
= 0 ∗ 4 + 2 = 2
• c
2
= b
t
1
b
c = b
2
3
c = 0
• w
1
= t
1
(mod b) = 2 (mod 3) = 2
• c
1
to c
2
: The state in Figure 4 changes from 2 to 0 with a read value of 0
and a write value of 2. This corresponds with our calculations in Step 2,
as r
1
= 0 and w
1
= 2.
Step 3 (i = 2): c
2
= 0 and r
2
= 2. The following is determined:
• t
2
= r
2
m + c
2
= 2 ∗ 4 + 0 = 8
• c
3
= b
t
2
b
c = b
8
3
c = 2
• w
2
= t
2
(mod b) = 8 (mod 3) = 2
• c
2
to c
3
: The state in Figure 4 changes from 0 to 2 with a read value of 2
and a write value of 2. This corresponds with our calculations in Step 3,
as r
2
= 2 and w
2
= 2.
Step 4 (i = 3): c
3
= 2 and r
3
= 0 (because [0202]
3
= [202]
3
). The following is
determined:
• t
3
= r
3
m + c
3
= 0 ∗ 4 + 2 = 2
• c
4
= b
t
3
b
c = b
2
3
c = 0
• w
3
= t
3
(mod b) = 2 (mod 3) = 2
5
• c
3
to c
4
: The state in Figure 4 changes from 2 to 0 with a read value of 0
and a write value of 2. This corresponds with our calculations in Step 4,
as r
3
= 0 and w
3
= 2.
The iteration is terminated when there are no more read values (i > l
r
)
and when c
i+1
= 0. Adding all of the write values will give our final value.
We know w in base 3 is [w
3
w
2
w
1
w
0
]
3
= [2222]
3
. Using Equation 2 for w,
w = (2 ∗ 3
0
) + (2 ∗ 3
1
) + (2 ∗ 3
2
) + (2 ∗ 3
3
) = 80. We can see this equates to the
more familiar base 10 multiplication of r ∗ m = 20 ∗ 4 = 80.
2 Methods
The methods below will primarily cover the steps towards finding the minimum
length for a path of c’s starting and ending at zero for T
m,b
. Finding these
minimum lengths (if the length is greater than zero) will allow us to find whether
a quotient set exists for T
m,b
; these quotient sets will form the basis of many
conjectures that will be outlined later in this paper.
2.1 Visualizer
The visualizer works by producing an artificial multiplication transducer
(with values stored in a data structure) and then transforming this structural
representation into a visual one similar to that of Figure 4. A visual representa-
tion of the multiplication transducer was generated using Python libraries like
Matplotlib in order to further prove the logic behind the conjectures outlined
in this paper; however, these visualizers became difficult to read as b and m in-
crease due to the fast growth of combinations between different states. Since the
visualizer proves these conjectures for smaller bases/multipliers, this limitation
does not hinder how the conjectures are proven.
For making the artificial representation of the transducer, every combination
of c
i
and r
i
was iterated through, and the corresponding c
i+1
and w
i
were
calculated from these. Note that Equations 3 and 4 can be used to calculate
these values. Since c
i
has a possible m values while r
i
has l
r
values, the runtime
complexity of this step is O(ml
r
). Note that since there are m carry values, this
means that even if l
r
> m, there are only m calculations that need to be made.
Therefore, the runtime complexity for this is O(m
2
).
Secondly, Matplotlib was used to convert this data into an visual multiplica-
tion transducer. Various functions were used, such as plt.Circle (which created
the structure to house the carry-in values), plt.arrow (which created lines be-
tween the carry-in values), and plt.text (which helped create text on the graph
that made the visualizer easier to view).
6
In addition, different colors and line styles (e.g. blue dashed lines) were used
to represent the write and read values respectively for the arrow between the
carry-in values. Using these processes, a figure similar to Figure 2 was created.
These particular linestyles were chosen due to their distinctness from the
other linestyles that would be represented on the transducer; in order for easier
comprehension of the transducer itself, it was necessary to choose differentiating
characteristics for each of the linestyles so that the reader can understand which
line corresponds a specific read value.
Besides from the simple linestyles provided by Matplotlib (e.g. ’solid’, ’dot-
ted’, and ’dashed’), more complex linestyles were taken to increase the amount
of read values that can be represented on the visualizer; this control was achieved
by providing a dash tuple with the form (offset, (on off seq)). For example, (0,
(2, 7, 1, 14)) represents a 2 pt line, a 7 pt space, a 1 pt line, and a 14 pt space
with no offset.
A similar process was done for the colors with the write values where only
extremely distinct colors were chosen (e.g. red, green, blue, etc.). More nuanced
colors were discarded due to their difficult visibility.
Note that the visual multiplication transducer should only be used for m < 8
and b < 8, because values greater than that will produce a multiplication trans-
ducer that will be difficult to comprehend (see Figure 3). The implementation
behind the visualizer can be referenced here.
2.2 Multiplication Transducer Traversal
To find and validate these conjectures, an artificial multiplication transducer
was formed in Python by iterating through the possible read and carry value
combinations for a particular base b and multiplier m. Since multiplication
transducers for different bases and multipliers can be difficult to compute and
draw non-computationally, a multiplication transducer formed by a computa-
tional algorithm provided the perfect method to scale bases and multipliers
efficiently.
Two different approaches were mainly used to generate the pathways to make
the multiplication transducer itself and to traverse these pathways to find the
minimum length path p that starts and ends at zero: the networkx library and
the depth first search algorithm. Note that these two different methods were
both implemented in order to ensure the validity of the findings outlined in this
paper.
7
Figure 2: Representation of the multiplication transducer T
4,3
using
the visualizer.
Figure 3: Representation of a more complex multiplication trans-
ducer T
10,7
using the visualizer.
8
2.2.1 NetworkX Library
The networkx library is a library that provides a platform for reviewing
graphs and networks using Python. By building and manipulating complex
structures, the networkx library is widely used by computational mathemati-
cians wanting to solve new conjectures in the fields of graph theory. As shown
in Figure 4, multiplication transducers can be seen as these networks that net-
workx manipulates. The states can be interpreted as the vertices of the network
while the corresponding arrow with the read and write values represent the
edges of the network.
These transducers can be formed computationally using the networkx library
through the .add node(), and .add edge() commands. Since the networkx library
has a number of different standard graph algorithms for different niche cases and
provides different measures for analysis, it was the optimal library for building
a multiplication transducer. Specifically, the .DiGraph() command was used as
the multiplication transducer acts as a directed graph since there are arrows
pointing to the next possible state inside the transducer (meaning that it has a
direction).
After the generation of this multiplication transducer, this directed graph
was then traversed using the networkx library to find the shortest possible paths
in the graph that start at state zero and end at state zero (one of the conditions
necessary for a path to be part of the quotient set). The implementation behind
the networkx library can be referenced here. [2]
2.2.2 Depth First Search
The depth first search algorithm (DFS) traverses tree structures by starting
at the root node and travelling down each possible path to minimize a specified
parameter. Although algorithms such as breadth-first search (BFS) have similar
time complexities of O(|V | + |E|) with V being the number of states and E
being the number of arrows between the states, DFS is more suitable due to its
inherent algorithmic structure since the first states explored (e.g. state 0, state
1, etc.) often provide the optimal solution and there are much more solutions
farther away from the source.
The generation of the multiplication transducer uses a similar strategy to
the one seen in Section 2.1 since the networkx library is not being utilized for
graph traversal in this scenario like in Section 2.2.1.
Note that the logic in Section 2.2.1 shown to prove a multiplication trans-
ducer to be a directed graph can be used to allow for DFS to be implemented on
the artificial transducer. Since this algorithm was run in Python, arrays were
used instead of stacks (which follow a last in first out pattern). A recursive
formula was mainly utilized to perform this depth first search; the code used
can be referenced here.
9
Figure 4: Side by side representation of a BFS vs. DFS approach.
These two tree traversals represent the inherent differences behind the BFS and the
DFS approach. The DFS (the graph shown on the right) works better for our project
as it goes through the foremost nodes first before traversing down the rest of the
tree. A DFS implementation was taken since most of the smallest paths will lie in
the first section of the transducer itself.
2.3 Challenges
2.3.1 C++ Implementation
For most programs, C++ is computationally faster at running algorithms com-
pared to Python; this is why it is often the preferred language for time-intensive
operating programs. Therefore, we attempted a C++ implementation for form-
ing the artificial multiplication transducer to reduce the time and space com-
plexity of our operations.
However, the operations done by this algorithm worked slower instead of
faster as allocating space to a vector took a computationally intensive time,
especially for larger bases and multipliers. Therefore, at the end, we took a
Python-based approach to build the transducer. The implementation for build-
ing the transducer using C++ can be seen here.
2.3.2 NetworkX Visualizer
We considered the networkx library when building the visualizer to build
an efficient and visually appealing model compared to the Matplotlib library.
Due to its versatility, we believed that the networkx library could be used to
not only build the artificial multiplication transducer but also create it visually;
this would provide a consolidated approach for building these multiplication
transducers, only involving the use of one library.
However, when creating this visualization, there was no option to produce
different linestyles or colors, which meant that different read and write values
could not be differentiated between. Additionally, the scale of the graph could
not be altered, which meant that the multiplication transducer was becoming
too cluttered even for small bases. After seeing this effect with networkx, we
decided that a manually-made multiplication transducer would be optimal.
10
3 Results
Conjecture 1: For all natural numbers b, m > 1, the path of carry values c
i
’s
that is the smallest closed loop across a multiplication transducer T
m,b
starting
and ending from 0 is:
• c
0
= 0.
• c
1
= b
m
b
c.
• c
i
= b
c
i−1
b
c for i ≥ 2.
Note. The conjecture has been computationally checked until b < 2000 and
m < 2000.
Additionally, note that for the conditions stated in Theorem 1, c
0
= 0, so
t
0
= r
0
m and c
1
= b
r
0
m
b
c. This indicates that r
0
= 1, since c
1
= b
m
b
c as stated
in the theorem. Similarly, since p
i
= b
p
i−1
b
c, c
2
= b
p
1
b
c = b
c
1
b
c = b
t
1
b
c. This
indicates t
1
= c
1
, and since t
1
= r
1
m + c
1
, r
1
m = 0. Since multiplier m ≥ 2,
r
1
= 0. Following this pattern, it can be noted that r
0
= 1 and r
i
= 0 for
all i = 2, ..., l
r
. Therefore, r can be represented as [00...1]
b
= [1]
b
= 1 for all
instances of base b and multiplier m.
Theorem 1: The length for the path of carry values c
i
’s, the smallest closed
loop across a multiplication transducer T
m,b
starting and ending at 0, is bm
1/b
c+
2 for b ≥ 2.
Proof. First, note that the smallest closed loop across a multiplication trans-
ducer T
m,b
must contain a c
i
6= 0. Therefore, in order to arrive at the smallest
closed loop, the path needs to produce a non-zero carry value that will get the
path back to the carry value of zero as quickly as possible. It needs to choose
the smallest carries in order to arrive at this smallest path.
Since the total is calculated as t
0
= r
0
m+c
0
and c
0
= 0, the fastest way to get it
to the smallest state/carry value is by making r
0
= 1. This is because t
0
= r
0
m
and any r
0
> 1 would produce a state that is greater than what is produced
by r
0
= 1 since the next state c
1
= b
t
0
b
c = b
r
0
m
b
c. Notice that this potrays a
similar result to what was seen in the proof discussed in the first theorem.
If r
0
= 1, then t
0
= m. Therefore, the next carry value is b
m
b
c while the read
value is w
i
= t
0
(mod b) = m(mod b). Now that it has left state zero, it now
aims to have the shortest path possible. In our expression of t
i
= r
i
m + c
i
, we
can’t control anything except r
i
since m is predefined and c
i
is dependent on
the previous calculation. The simplest way to get the transducer back to state
zero is to make r
i
= 0.
Therefore, t
i
= (0)(m) + c
i
, so t
i
= c
i
. Note that t
1
= b
m
b
c, and c
2
can be
calculated by taking the integer division of the previous state and the base.
11
To understand this concept in further detail, let’s take an example of base b = 3
and multiplier m = 10:
Step 1 (i = 0): c
0
= 0 (our initial state) and r
0
= 1. Therefore,
• t
0
= r
0
m + c
0
= 1 ∗ 10 + 0 = 10
• c
1
= b
t
0
b
c = b
10
3
c = 3
• w
0
= t
0
(mod b) = 10 (mod 3) = 1
Step 2 (i = 1): c
1
= 3 and r
1
= 0. Therefore,
• t
1
= r
1
m + c
1
= 0 ∗ 10 + 3 = 3
• c
2
= b
t
1
b
c = b
3
3
c = 1
• w
1
= t
1
(mod b) = 3 (mod 3) = 0
Step 3 (i = 2): c
2
= 1 and r
2
= 0. Therefore,
• t
2
= r
2
m + c
2
= 0 ∗ 10 + 1 = 1
• c
3
= b
t
2
b
c = b
1
3
c = 0
• w
2
= t
2
(mod b) = 1 (mod 3) = 1
In this example, notice that the read values follow a pattern similar to that
shown in the proof of the first theorem. Essentially, the read value r = [1]
b
= 1
for all bases. Additionally, an interesting pattern occurs when looking at the
write values produced by the example above. The write value is [101]
3
= [10]
10
.
With a read value of [1]
b
, the write values can always be generalized to have
pattern w = m as evidenced by the example above. Therefore, a general pattern
for the read and write values of the shortest path have been found.
Corollary 1: For the path of carry values c
i
’s that make the smallest closed
loop across a multiplication transducer T
m,b
starting and ending from 0, the
read and write values are:
• r = [1]
b
= 1.
• w = m.
Proof: Note that this combination of read values always produces the shortest
path as it goes to the state that is just far enough to escape zero, and then
it takes the fastest approach to go back to zero afterwards. Knowing this, the
length of the shortest path is bm
1/b
c + 2 for b ≥ 2 by using arithmetic logic.
12
First, note that the addition of two is to account for the zeroes in the beginning
and ending of the shortest path. For the path between these zeroes, bm
1/b
c can
be used to denote the length. Remember that these numbers are c
i
= b
t
i−1
b
c
where t
0
= m and t
i
= c
i
. Knowing this is the case, that means that there is an
integer division between m and b
l
w
−1
at the very last step where l
w
represents
the length of the write value. This is because base m is divided by base b in all
steps of this base division except for the first since t
i
equals c
i
.
Knowing that the integer division needs to produce a zero in order to produce a
closed path, then
m
b
l
w
−1
< 1 or m < b
l
w
−1
. Since l
w
− 1 = l
p
where l
p
represents
the length of the smallest path of base b and multiplier m (excluding the first
and last zeroes), this formula can be rewritten as m < b
l
p
. Doing algebraic
manipulation on this inequality, we can reasonably conclude that the length of
the smallest closed set (excluding the zeroes) or l
p
of base b and multiplier m
is bm
1/b
c. Therefore, we can conclude that the length of the smallest closed set
(including the zeroes) of a particular base b and multiplier m is bm
1/b
c + 2.
Corollary 2: The multipliers that have a length of n + 1 for the shortest
closed loop across a multiplication transducer T
m,b
starting and ending at 0
for a particular b has a range of m ∈ [b
n−1
, b
n
− 1] for all n ≥ 3 and b ≥ 2.
Therefore, the number of multipliers that have a length of n + 1 for a particular
b is b
n−1
(b − 1) for all n ≥ 3 and b ≥ 2.
Proof. We prove this corollary by proving that there are sharp bounds for
multipliers that have a length of n + 1 for the shortest closed loop and that the
length of the shortest closed loop with respect to multipliers is monotonically
increasing.
First, note that Theorem 1 shows that the length of the shortest closed loop
with respect to multipliers in monotonically increasing, since f(m) = bm
1/b
c+2
is monotonically increasing.
We then prove the lower bound of m = b
n−1
is sharp. Let m = b
n−1
.
Then, we try to prove that the length of the shortest closed loop around a
multiplication transducer T
b
n−1
,b
starting and ending at 0 for any b is n + 1.
Note that the first two elements in the path are 0 and b
b
n−1
b
c = bb
n−2
c. The
third element in the path is b
b
n−2
b
c = bb
n−3
c. This means that the ith element is
bb
n−i
c and the nth element is bb
n−n
c = b
0
= 1. Therefore, the (n+1)th element
is b
1
m
c = 0. We can see that the length is n + 1 for m = b
n−1
.
The lower bound can be shown to be m = b
n−1
by showing m = b
n−1
− 1
has a length of n. Note the second element in the path would be b
b
n−1
−1
b
c =
bb
n−2
− 1c. The third element in the path would be b
b
n−2
−1
b
c = bb
n−3
− 1c.This
means that the ith element is bb
n−i
− 1c and the nth element is bb
n−n
− 1c =
b
0
− 1 = 1 − 1 = 0. Therefore, the length is n for m = b
n−1
− 1.
13
Next, the upper bound has to be shown to be m = b
n
− 1. We can do this by
proving that b
n
has a length of n + 2. Note that the proof that the length of
m = b
n−1
is n + 1 can be altered such that the length of m = b
n
is n + 2. We
then show that m = b
n
− 1 has a length of n + 1. Note that the proof for the
length of m = b
n−1
− 1 is n can be altered such that the length of m = b
n
− 1
has a length of n + 1. Therefore, the upper and lower bounds have been proven
to be sharp and the lengths are monotonically increasing with respect to the
multipliers. Thus, the corollary is proven.
4 Conclusion
The theorems shown above provide an overview of multiplication transducers
with no excluded digits and analyze paths through the multiplication transducer
when m = 1. These help prove the basis of multiplication transducers inside
of base multiplications and will help with rapidly calculating bases with small
multipliers.
Further research includes generalizing the theorems to multiplication trans-
ducers with a reduction of the digit set and determining whether some of the
same properties hold. Additionally, Corollary 1 has yet to be analytically
proven, which proves another topic of exploration. Furthermore, pathways with
larger multipliers can be explored, and better ways of visualizing multiplication
transducers with large b’s and m’s have yet to be discovered.
4.1 Exploring Quotient Sets With Restricted Digits
As seen above, with these multiplication transducers, we can calculate an
output w when multiplying m by r in base b. We can now add a further
constraint to limit the number of r values that can be multiplied by m, which
will, in turn, reduce the set of all outputs and reduce the number of states in
the multiplication transducer.
This constraint involves reducing the original digit set {d
1
, d
2
, ..., d
k
}, the set
of digits that can be used to represent r in base b, where k = b. For instance,
for digit set {0, 1} for b = 3, r = {1, 3, 4, 9, ...} = {[1]
3
, [10]
3
, [11]
3
, [100]
3
, ...},
and for digit set {0, 1, 2} (the entire set for base three), r = {1, 2, 3, 4, ...} =
{[1]
3
, [2]
3
, [10]
3
, [11]
3
, ...} = N.
Let S(b; {d
1
, ..., d
k
}) be the set of all r that can be created in base b using
digit set {d
1
, ..., d
k
}. For the previous example, S(3; {0, 1}) = {1, 3, 4, 9, ...}. To
express this mathematically,
S(b; {d
1
, ..., d
k
}) = {s ∈ N; s =
∞
X
i=0
α
i
b
i
with α
i
∈ {d
1
, ..., d
k
} for all i} (6)
14
What we are interested in doing is studying the positive whole numbers that
come from dividing numbers in S(b; {d
1
, ..., d
k
}) or the set of all q for a particular
b. This set is known as a quotient set, and is denoted as Q(b; {d
1
, ..., d
k
}).
Expressed mathematically,
Q(b; {d
1
, ..., d
k
}) = {x ∈ Z : x =
s
s
0
for some s, s
0
∈ S(b; {d
1
, ..., d
k
})} (7)
Note that in Q(b; {d
1
, ..., d
k
}), s
0
6= 0.
We can prove whether a particular number n is in this quotient set if two
conditions are met:
• w = n.
• p
0
= p
l
w
−1
= 0 (or there is a closed loop in the multiplication transducer
starting and ending at 0).
Note that for no restricted digits (containing the original digit sit), Q = N.
References
[1] F. Blanchard, J. M. Dumont, and A. Thomas. “Generic sequences, trans-
ducers and multiplication of normal numbers”. In: Israel Journal of Math-
ematics 80.3 (Oct. 1992), pp. 257–287. doi: 10.1007/bf02808071.
[2] Tom Everitt and Marcus Hutter. “Analytical Results on the BFS vs. DFS
Algorithm Selection Problem. Part I: Tree Search”. In: AI 2015: Advances
in Artificial Intelligence. Springer International Publishing, 2015, pp. 157–
165. doi: 10.1007/978-3-319-26350-2_14. url: https://doi.org/10.
1007/978-3-319-26350-2_14.
[3] Simone Sisneros-Thiry. “Combinatorial Number Theory Through Diagram-
ming And Gesture”. University of Illinois at Urbana-Champaign, 2020.
15
