On the Number of Distinct Binary Factor Trees That Display the Prime Factors of an Integer
GARY ADAMS
ABSTRACT. This paper addresses the correlation between the number of prime factors for any given positive integer nand the number of distinct binomial factor trees for that n. After much observation, an equation for determining the number of distinct binomial factor trees has been discovered.
1. INTRODUCTION
In 1736, the study of graph theory was begun by Leonhard Euler. He was trying to establish whether or not it was possible to walk across all seven of the bridges in the city of Königsberg, Russiaexactly once and end where you started. This was known as the KönigsbergBridge Problem. Since his publication of this problem the study of graph theory has been widely studied by mathematicians such as Thomas Kirkman and William Hamilton. In Euler’s original problem, he configured his drawing of the city and its bridges into a graph. He labeled the bridges as edges and various separated sections of the city as vertices. [4], [6]
An early success of graph theory (and the general problem of counting all different graphs of a fixed type) was to identify the isomorphs of the hydrocarbon pentane with the set of different graphs which could represent or model different molecular arrangement of the 5 carbon atoms and 12 hydrogen atoms. The problem undertaken in this paper is to count for each small positive integer, the number of different factor trees that exist. Hopefully, one might determine features in the structural patterns allowing a prediction for any large n, the total number of factor trees for that n. IN fact, we solve this problem, and Section 3 gives a presentation of the solution.
- PRELIMINARY INFORMATION
In order to have a better understanding of the information presented in the paper, we must first give some terminology. For terms left undefined, the reader should see [5].
Definition 1. A graphG = (V, E) is a finite nonempty set V of elements called vertices, together with a set E of unordered pairs of elements of V called edges.[5]
FIGURE 1. An example of a graph
Definition 2. A path in a graph is a sequence (v1, {v1,v2}, v2, {v2,v3}, … , {vt-1,vt}). A path begins with a vertex v1, moves along the edge {v1,v2} to vertex v2, and so on until vertex vt is reached, and the path ends. A closed path is one that ends where it started (with v1=vt). A path is simple if no vertex is repeated (except possibly the last one).
Definition 3. A cycleis asimple closed path. If {x, y} is an edge of a graph, the vertex x is said to be incident with the edge and is called an endpoint of the edge. The degree of a vertex is the number of edges for which the vertex is an endpoint. [6] Every vertex in FIGURE 1 has degree 2 or 3.
FIGURE 2. Examples of circuits or loops.
Definition 4. A graph is connected if there is a path from vertex x to vertex y for every pair x, y.
Definition 5. A tree is anundirected connected graph with no cycles. [6]
FIGURE 3. An example of a tree
Definition 6. A tree is a rootedtreeif one vertex has been designated the root, in which case all of the edges have a natural orientation, towards or away from the root. Rooted trees, often with additional structure such as ordering of the neighbors at each vertex, are a key data structure in computer science. [6]
NOTE. In this paper, we orient edges so that the edges become ordered pairs (v1,v2) and our graphs become directed graphs (digraphs).
FIGURE 4. An example of a rooted tree with root at the top
Definition 7. A data structure is a way of storing data in a computer and the associated methods for retrieving that data. [2]
NOTE. The number of ordered edges leading into a vertex is its in-degree. The number of edges leaving a vertex is its out-degree. In Figure 5,the root has in-degree 0 and out-degree 2.
FIGURE 5. This binary tree is an example of a simple data structure used in computer science. [2]
Definition 8. A binary tree is a type of tree that contains zero or two edges incident with every vertex. [5] Equivalently, every vertex has out-degree 0 or 2 except for endpoints.
NOTE. Our diagrams will omit arrows since we take the orientation down-ward and the top-most vertex is always the root.
FIGURE 6. Three examples of binary trees.
Definition 9. A factor tree is simply a graphical representation using a binary treethat shows the factors of a particular number.
NOTE. Observe that we do not label the vertices as u, v, w,…etc but just put whole numbers on the tree (in lieu of a vertex) so that the product of the two numbers just below any vertex is always equal to the node above.
FIGURE 7. Examples of two distinct factor trees for the integer 16.
Definition 10. The levels of trees are labeled as follows: The root of the tree is at level 0; the nodes just below the root are at level 1; the nodes just below the nodes at level 1 are at level 2; and so on.
Definition 11. Equivalent binary factor trees are binary factor trees that can be arranged to appear the same in shape by switching a node with another at the same level and taking all of its subsequent nodes with it.
NOTE. Notice that the first and last trees in Figure 8 have seemed to have transformed by switching 2 and 8 at the first level. Also, notice that the first and last trees could also be transformed by switching the 2 and 4 at the second level, and the middletrees are equivalent to each other even though the numbers assigned to the nodes are different. If a tree can be transformed into another by a sequence of such switches, we will say they are equivalent trees.
NOTE. The project is to determine |Tr| for each r = 1, 2, 3,…, where Tr is the class of distinct factor trees for the positive integer r, and |Tr| refers to the number of distinct binary factor trees for Tr. For convenience, we write {r} to indicate |Tr|.
FIGURE 8. An example of four equivalent binary factor trees.
NOTE. In creating a factor tree for the integer n, the number 1 is never used, and paths from the root always terminate with a prime divisor of n. We will always use m, n, andr to denote some integer and p and q to denote primes with pq.
NOTE. At level n, a factor tree will have at most 2n vertices. In recognizing whether two factor trees are equivalent, we may use the levels in at least two ways. First, if the number of vertices at some level is different, the trees are not equivalent. Further, if at some level the number of vertices with out-degree equal to 0 is different, the trees are not equivalent.
- DEVELOPING THE BINARY FACTOR TREES
In order to establish an algorithm that correlates the number of binary factor trees with the number of prime factors, we must first graph the binary factor trees and make observations.
For r = p, there is only one tree, and it consists of a single node (no edges).
For r =p2or r = pq or r = q2there is only onebinary factor tree, and the trees are equivalent to each other.
FIGURE 9.
Since there are no other factorizations of r, we see in FIGURE 9 that there is only one binary factor tree possible for and we denote the quantity as {p2} = 1.
Theorem 1. If ris the product of two prime numbers, the only binary factor tree possible for r isone similar to the factor tree in FIGURE 9. That is {pq} = 1 = {p2}.
Theorem 2: The number of distinct binary factor trees for some integer pm (denoted {pm}), where p is a prime number, is equal to the number of distinct binary factor trees of some other integer qm(denoted {qm}), where q is a prime number not equal to p.
Proof. Let p, q be prime numbers with pq. Therefore, the numbers {pm} and {qm} would be the same since pm and qm have the same number of prime factors, and they would need to be factored correspondingly. This can be seen by mapping distinct Tp to Tq by replacing p’s with q’s. This clearly is 1-1 and onto.
For r = p3,Tr has the binary factor trees in FIGURE 10. Since there are essentially only 2 ways to factors p3, as p * p2 or p2 * p, the tree in FIGURE 10 are the only trees for r.
FIGURE 10. Factorizations of p3.
However, the two trees are equivalent by switching factors at the first level. This proves the following Theorem 3.
Theorem 3. If r = p3, the only binary factor trees possible are ones similar to those in FIGURE 10, and {p3} = 1.
For r = p4, Tr has onlythe following different binary factor trees:
FIGURE 11. The only two factor trees for r = p4.
Therefore,{p4} = 2.
Theorem 4. For r = p4, the only binary factor trees possible are ones similar to those in FIGURE 11. Thus, {p4} = 2.
Lemma 4.1. Suppose m is even and n = {pm/2}. Then there are [n (n + 1)] / 2 ways to complete a factor tree for r = pm if the first level has nodes with pm/2 and pm/2. (Note that [n (n + 1)] / 2 is exactly.)
Proof. Suppose m is even, and consider trees for pm. The left column of FIGURE 13 represents each distinct factor tree for pm/2. When mapping them to the n distinct factor trees in the right column (i.e., the node paired with Ti on the left), we see that factor tree T1, on the left, can be mapped to factor tree on the right. Factor tree T2 can be mapped to n-1 of the factor trees on the right—T1 is excluded since T1 and T2 have already been paired together. Factor tree T3 can be mapped to n-2 of the factor trees on the right, and so on until Factor tree Tn can only be mapped only to Tn on the right. Notice that one cannot map any tree on the right to any tree on the left without repeating a previous mapping from the left to the right. This observation leads to another elementary counting principle, and the sum is.
FIGURE 12.
Theorem 5. For r = p5, Tr has only the following different binary factor trees:
FIGURE 13. Note that {p} = 1, {p2} = 1, {p3} = 1, and {p4} = 2.
Therefore,[{p} * {p4} + {p2} * {p3}] = (1) (2) + (1) (1) = {p5} = 3.
Lemma 5.1. Suppose a factor tree for pn must begin with paand pb at level 1 with a < b. Then there are {pa}*{pb} distinct such factor trees.
Proof. Let p be a prime number, and let n, a, b, x, and y be some positive integer with a < b and a + b = n. Given that pn is at level 0 of the factor tree and that paand pb are the nodes at level 1, we make the following observations:
FIGURE 14.
Suppose {pa} = x and {pb} = ywhere x < y and that none of the factor trees ofpa are equivalent to any of the factor trees with pb. We must determine how many distinct factor trees can be constructed from this particular factoring of pn. The left column is a representation of the factor trees for pa. The right column is a representation of the factor trees for pb. Notice that every factor tree on the left maps to every factor tree on the right (i.e. T1imaps to T2kwhere k = 1,…, y and i = 1,…, x.)
FIGURE 15.
We see that no factor tree from the right column can map to any factor tree on the left without repeating any prior mapping from left to right. This means that the x number of factor trees on the left maps to the y number of factor trees on the right (i.e. x * y). Therefore, x * y = {pa} * {pb}, which is what was needed.
Theorem 6. Suppose m and p is a prime. Then
{pm}=, where m is odd.
{pm}= , where m is even.
In essence we have for, where n = 25, the following values using Theorem 4:
{p} = 1
{p2} = 1
{p3} = 1
{p4} = 2
{p5} = 3
{p6} = 6
{p7} = 11
{p8} = 23
{p9} = 46
{p10} = 98
{p11} = 207
{p12} = 451
{p13} = 983
{p14} = 2179
{p15} = 4850
{p16} = 10905
{p17} = 24631
{p18} = 56011
{p19} = 127912
{p20} = 293547
{p21} = 676157
{p22} = 1563372
{p23} = 3626149
{p24} = 8436379
{p25} = 19680277
Proof. Suppose m > 5. The theorem is true for m 5. Suppose the theorem is true for all numbers less than m for some m6. We want to show it is true for m.
Case 1. Suppose m is odd, and consider trees for pm. There are (m-1)/2 possible factorizations of pm.At level 1, the 2 nodes are distinct for each pair.
FIGURE 16.
So, there are (m-1)/2 distinct level 1’s to consider. We refer to these as Lt1 for
t = 1,…, (m-1)/2. For each Lt1, the number of distinct ways to continue is the product of the number of ways of continuing each branch, applying an elementary counting principle. Thus the sum is
.
This is exactly what we need for m odd. The numbers in the products used are correct by the induction hypothesis.
Case 2. Suppose m is even, and consider trees for pm. There are m/2 possible factorizations of pm.
FIGURE 17.
Using Case 1, we know that the value for {pm} is equal to
+ the number of distinct factor trees for last factor tree listed
in FIGURE 15.
Using Lemma4.1, we know that the number of distinct factor trees for the last factor tree listed in FIGURE 15 is
.
Therefore, we know that the number of distinct factor trees for pm when m is even is equal to
Theorem 7. Just as {p2} = {pq}, we may say that {qkpj} = {pk +j}.
Proof. As stated in Theorem 1 and shown in FIGURE 9, {pq} = {p2}. Therefore we make the following observations:
According to FIGURE 16, the only nodes in question are the left nodes at level 1. The right nodes in the factor trees are equal to that same node in its corresponding factor tree. Since Theorem 5 states that {qk} = {pk}, and we know that {pj} = {pj}, we can conclude that {qkpj} = {pk +j}.
FIGURE 18.
In conclusion, for any positive integer n with its prime factorization given by the number of distinct binary factor trees for n is {i1+i2+…+is}.