Advances in Pure Mathematics
Vol.08 No.05(2018), Article ID:84966,14 pages
10.4236/apm.2018.85028
T3 Tree and Its Traits in Understanding Integers
Xingbo Wang1,2
1Department of Mechatronics, Foshan University, Foshan City, China
2Guangdong Engineering Center of Information Security for Intelligent Manufacturing System, Foshan City, China
Copyright © 2018 by author and Scientific Research Publishing Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
Received: April 19, 2018; Accepted: May 28, 2018; Published: May 31, 2018
ABSTRACT
Valuated binary tree is emerging its magical characteristics in study of integers. As the father tree of all valuated binary subtrees, T3 tree plays a very important role in studying the odd integers for its owning both the common properties of a general valuated binary tree and its own traits of covering all the odd integers bigger than 1. The article investigates the properties of the T3 tree as well as the multiplications on the tree. It exhibits the distribution of a node's multiples, the distribution of the product of two nodes and the distribution of the square of a node. Some other contents such as fundamental properties of the T3 tree and path connecting a product to its divisor-nodes are also investigated with detail mathematical proofs. The theorems and corollaries proved in the article lay a foundation for future work.
Keywords:
Number Theory, Valuated Binary Tree, Multiplication
1. Introduction
Number theory is an ancient subject in mathematics and it has attracted people’s interests because it has continuously left kinds of amazing problems for human being. Classical approach of studying number theory can be seen to put integers on a line called number axis. It is of course a thinking in one dimensional space. In 2016, article [1] proposed a new approach to study integers by putting odd integers bigger than 1 on a full binary tree from top to bottom and from left to right and called the new approach a valuated binary tree approach. The approach is of course a two-dimensional thinking. Following the article’s study, articles [2] and [3] further investigated and proved some properties of the valuated binary tree and its subtrees, article [4] revealed the genetic properties of odd integers and obtained a new approach to factorize odd integers with the help of the valuated binary tree, and article [5] developed a parallel method to factorize odd integers by applying the new factoring approach on parallel computing systems. Undoubtedly, the approach of the valuated binary tree is emerging its characteristic in study of integers.
The T3 tree, namely, the 3-rooted valuated binary tree, is the father tree of all subtrees. Owning both the common properties of a general valuated binary tree and its own traits of covering all the odd integers bigger than 1, it obviously plays a very important role in understanding the integers. This article introduces fundamental properties of the T3 tree as well as multiplication related properties of the tree so as for people to know more about the valuated binary in study of integers.
2. Preliminaries
2.1. Definitions and Notations
A valuated binary tree T is such a binary tree that each of its nodes is assign a value. An odd-number N-rooted tree, denoted by TN is a recursively constructed valuated binary tree whose root is the odd number N with and being the root’s left and right sons, respectively. The left son is said to have a left attributive and the right son is to have a right attributive. Each son is connected with its father with a path, but there is no path between the two sons. T3 tree, or briefly called T3, is the case . The root of the T3 is assigned a right attributive. For convenience, symbol is by default the node at the jth position on the level of T3, where and ; symbol denotes a subtree whose root is and symbol denotes the node at the ωth position on the th level of . Level is said to be higher than level if and it is said to be lower than level if . Symbol is the path from node A to node B and the length of a path is calculated by the number of total nodes on the path subtracting by 1. Symbol is the node where slides down χ levels along the leftmost path of subtree
and symbol is that slides down χ levels along the
rightmost path of subtree .
An odd interval is a set of consecutive odd numbers that take as lower bound and b as upper bound, for example, . Intervals in this whole article are by default the odd ones unless particularly mentioned. Symbol is the floor function, an integer function of real number χ that satisfies inequality , or equivalently .
2.2. Lemmas
Lemma 1 (Subtree Transition Law, See in [2] ) Let and ( ) be two subtrees of T; then it holds
Lemma 2 (See in [4] ) Let be an odd integer bigger than 1 and be the -rooted valuated binary tree; then the following statements hold
1) There are nodes on the level with ;
2) Node is computed by
3) Two position-symmetric nodes, and , satisfy
4) Level ( )of subtree ( ) is the level of and it contains nodes. Node of ( ) is corresponding to node of by
Lemma 3 (See in [1] & [6] ) Let p be a positive odd integer; then among p consecutive positive odd integers there exists one and only one that can be divisible by p. Let q be a positive odd number and S be a finite set that is composed of consecutive odd numbers; then S needs at least elements to have n multiples of q.
3. Fundamental Properties of T3
Theorem 1. The T3 Tree has the following fundamental properties.
(P0) Every node is an odd integer and every odd integer bigger than 1 must be a node of the T3 tree. For an arbitrary positive integer > 0, the odd integer of the form 4 +1 is a left node while the odd integer of the form 4 +3 is a right node.
(P1) On the level with , there are nodes starting by and ending by , namely, with .
(P2) is calculated by
(P3) Nodes and on the level are respectively the left son and the right son of node on the level. The descendants of on the level are ( ), which are
Particularly,
and
(P4) The biggest node on the level of the left branch is whose position is , and the smallest node on the level of the right branch is whose position is .
(P5) Node and node are at the symmetric positions on the th level and it holds
(P6) Multiplication of arbitrary two nodes of T3, say and , is a third node of T3. That is,
(P7) The binary representation of node takes bits with the least significant bit and the most significant bit being 1, that is
(P8) Odd integer N with lies on level .
Proof. Omit the proofs for (P0) to (P6). (P7) can be proved by mathematical induction. Here only prove (P8). By (P1) it yields , that is
By definition of the floor function, it knows .
4. Multiples and Divisors on T3
This section presents relationship between a node and its multiples in T3 tree.
Theorem 2. The following claims are true.
1) On the same level of T3, there is not a node that is a multiple of another one.
2) An arbitrary subtree of T3 contains a multiple of 3 on level 2, a multiple of 5 on level 3, a multiple of 7 on level 4 and so on. Or for a given integer a subtree of T3 must contain a multiple of on level counted from the subtree’s root that stands on level 0.
3) For integer , a node of T3 on level must have at least multiples on level of T3; for integer , a node of T3 on level must have at least multiples on level of T3.
Proof. The first claim is seen in [1] . Here only prove (2) and (3). The level of an arbitrary subtree contains consecutive odd numbers. Since an arbitrary integer yields , by Lemma 3 it knows that the claim (2) holds. Note that a node on level of T3 satisfies and there are respectively nodes and nodes on level and level . Now consider the case . Since , it can see that on level , there are at least consecutive sections each of which contain odd integers. By Lemma 3 it knows that there are at least multiples of on level . Similarly, when it holds , it knows that the level contains at least multiples of .
Theorem 3. Among all nodes that lie on level or a higher level in subtree with , there is not a node that is a multiple of . Or node of T3 cannot divide its direct descendants that lie on level 2 or a higher level in terms of T3.
Proof. Use proof by contradiction. Without loss of generality, assume can divide with and , namely, with α being an odd integer; then by and
it leads to
namely
which indicates can divide or in the case . Since the minimal value of s is 0 , it yields
which shows that, due to , . This means that is impossible to be divisible by and neither holds . Hence contradiction occurs and the first part of the theorem holds. The second part surely holds by Lemma 2(4).
Theorem 3 is called a law of inbreeding avoidance and it can be intuitionally described with Figure 1, in which the inbred area has no multiple of .
Theorem 4. If node of T3 tree is composite, it must have a divisor that
lies on level or a higher level.
Proof. Use proof by contradiction. Assume and are two divisors of
Figure 1. Inbreeding avoidance.
and each of the two lies on level or lower levels; then and ; thus
Referring to (P31) in [6] , it knows for an arbitrary integer
; hence
which is contradictory to the fact that lies on level .
Corollary 1* If a node ( ) of T3 is a composite number and it has
a divisor d on level ; then another factor must lie on level or level or level .
Proof. Considering and , the square of the smallest and the largest nodes on level respectively, and , multiplication of the two smallest nodes on level and
respectively, it yields
and
Similarly, it holds
These inequalities show that, multiplication of any two small nodes on level
lies on level or level or even level and even the two smallest nodes one level and respectively cannot have a
multiplication that lies on level since the multiplication lies on level or level .
Corollary 1. A node of T3 on level is not divisible by every node on
level and higher levels is a prime number. Furthermore, of T3 on level is not divisible by each prime-node on level or higher levels is a
prime number.
5. Multiplications on T3 Tree
This section presents basic law of multiplication of two nodes and properties of the square of a node in T3 tree. Path connecting a multiple to its divisors are also investigated in this section.
5.1. Basic Law of Multiplication
Theorem 5. Multiplication of two left nodes or two right nodes results in a left node; multiplying a left node with a right node results in a right node.
Proof. (Omitted)
Theorem 6. Suppose and ; then product ( ; ) lies on level in the case ; otherwise, it may lie from the position on level to the position on level , totally possible positions.
Proof.
Let ; then
Hence when , lies on level of T3 and when , lies on level or some lower level. Now consider the following cases.
Case (i) . This time and thus . Since on level , the maximal number of position is 1, it knows lies on level 2, which is level .
Case (ii) plus , or plus . Since J is a symmetric expression of , and , here only consider plus . This time, thus takes its minimal value at and maximal value at . Let the minimal value and the maximal value be respectively and ; direct calculation shows
,
Since (the equality holds only if ), the minimal value of , which is , lies on level .
Meanwhile, by and it knows
and
That is to say, lies on level .
Case (iii) and . This time, takes its minimal value at and maximal value at . Direct calculation shows
,
Note that, and yield , namely,
; hence lies on level .
On the other hand, by , it holds
hence when and ,
and thus
Consequently,
which shows that lies on level .
Now it can summarize that the smallest possible value of is , which lies on level at position ,and its maximal possible value is ,which lies on level at position . Since there are totally nodes on level , it knows that there are nodes from position to position . Similarly, there are on level totally nodes from position 0 to position . It knows that, has possible positions.
Corollary 2. Suppose and ; then the product with and plus lies on level and fits when , whereas it lies on level and satisfies with when .
Proof. The case has already been proved in the proof of Theorem 6. Now consider the case . Note that there are in all integers from 2 to . Eliminating all the even integers remains odd ones. By property of full binary tree, if putting these odd integers on the nodes of T3 from top to bottom and from the left to the right, the preceding levels contain ones and the left ones will be placed on the level . Counting from position 0 to the position χ yields . Substituting by yields
Corollary 3. For positive integer and , the node of T3 at position on level is in left branch of T3 but it cannot a leftmost node; the node at position on level is in right branch but it cannot be a rightmost node.
Proof. The maximal node on level in the left branch of T3 is with position . Note that
it knows that, yields and yields , which says that the position is on level in the left branch of T3. Since the leftmost node is at position 0 whereas , the position is surely not a leftmost one.
To prove the second conclusion, let . Since the smallest node on level in the right branch of T3 is , it merely needs to prove . In fact,
and
By Corollary 2 and Corollary 3, the product can be intuitionally depicted with Figure 2.
Corollary 4. Let and be two nodes of T3 with ; then the product cannot fall in on level or a higher level.
Proof. Let and with and . Since the maximal node on level of is , direct calculation yields
Note that
hence , which says cannot fall on level or a higher level of .
Corollary 4 can be equivalently stated as that, if and are two nodes of T3 with , then the product can only fall in the shadow area in Figure 3.
Corollary 5. Let and be two nodes of T3 with ; then the product cannot lie in or on level or a higher level.
Figure 2. Possible positions of product .
Figure 3. can merely lie in area of shadow.
Proof. (Omitted)
Corollary 5 can be equivalently stated as that, if and are two nodes of T3 with , then the product can only fall in shadow area in Figure 4.
5.2. Square of A Node
Theorem 7. Product is a left node of T3, it lies in T3 on level or and there are nodes from to .
Proof. Direct calculation shows
Let ; then
and is the number of nodes from to .
Corollary 6. For arbitrary integer , it holds and .
Proof. By (P4), it yields
Note that
Figure 4. can merely lie in area of shadow.
Hence
Taking results in
Thus .
Now directly calculating and yields
and
which says .
Corollary 7 For arbitrary integer , lies in whereas lies in .
Proof. (Omitted)
Corollary 7 can be equivalently and intuitionally stated as that, the square of a rightmost node of T3 is a descendant of the node itself, whereas the square of a leftmost node of T3 is a descendant of the node’s elder brother.
Corollary 8. If and , then does not lie in . Or equivalently, does not lie in unless or plus .
Proof. By Theorem 7, lie in T3 on level or . Since by Lemma 2 the level of is the level of T3, can never lie in on a level lower than . By Corollary 5, cannot lie in on level or a higher level. Now it needs to prove that it cannot either lie in on level . In fact, the smallest node of on level is . By Theorem 7 and Corollary 6 it knows that when , reaches it maximal value that is also the minimal node of on level . Hence it cannot lie in under the condition and .
5.3. Path Connecting Multiple to Divisor
Theorem 8. Let and be two nodes of T3 with ; then there is a path connecting to and the length of the path is less than ; there is also a path connecting to and the length of the path is less than .
Proof. By Theorem 6 and Corollary 7 and Corollary 8, it knows that must lie in , or some other subtree of T3. First consider the case that lies in . By Corollary 2 and Lemma 2 it knows . Likewise, if lies in it holds .
Now consider the case that lies in neither nor ; then there must be a γ and a λ with plus and plus such that lies in or . Assume it lies in ; then by the subtree transition law,
Let be the lowest common ancestor (LCA) of and ; then by properties of LCA, as introduced in [7] [8] and [9] , can be connected to along path . Since the length of is less than , the length of is and the length of is , it knows that the total length of the path is less than . Likewise, the other conclusion can be proved.
6. Conclusion
Putting integers on binary tree can reveals many new properties of the integers, as seen in previous sections and in the references list in bibliography. This paper merely shows some traits related with multiplication of nodes on T3 tree. In fact, there are many other new properties that have not been known till now and are required to make further study. For example, Theorem 8 indicates there exists a very fast approach to factorize an odd integer; in addition, there are evidences that there is a law of distribution of prime number on certain subtrees. Hence there is a lot of work done in the future. Hope that it is concerned by researchers of interests.
Acknowledgements
The research work is supported by the State Key Laboratory of Mathematical Engineering and Advanced Computing under Open Project Program No. 2017A01, Department of Guangdong Science and Technology under project 2015A010104011, Foshan Bureau of Science and Technology under projects 2016AG100311, Project gg040981 from Foshan University. The author sincerely presents thanks to them all.
Cite this paper
Wang, X.B. (2018) T3 Tree and Its Traits in Understanding Integers. Advances in Pure Mathematics, 8, 494-507. https://doi.org/10.4236/apm.2018.85028
References
- 1. Wang, X.B. (2016) Valuated Binary Tree: A New Approach in Study of Integers. International Journal of Scientific and Innovative Mathematical Research, 4, 63-67.
- 2. Wang, X.B. (2016) Amusing Properties of Odd Numbers Derived from Valuated Binary Tree. IOSR Journal of Mathematics, 12, 53-57.
- 3. Wang, X.B. (2017) Two More Symmetric Properties of Odd Numbers. IOSR Journal of Mathematics, 13, 37-40. https://doi.org/10.9790/5728-1303023740
- 4. Wang, X.B. (2017) Genetic Traits of Odd Numbers with Applications in Factorization of Integers. Global Journal of Pure and Applied Mathematics, 13, 493-517.
- 5. Fu, D. (2017) A Parallel Algorithm for Factorization of Big Odd Numbers. IOSR Journal of Computer Engineering, 19, 51-54. https://doi.org/10.9790/0661-1902055154
- 6. Wang, X.B. (2014) New Constructive Approach to Solve Problems of Integers’ Divisibility. Asian Journal of Fuzzy and Applied Mathematics, 2, 74-82.
- 7. Wang, X.B. (2017) Brief Summary of Frequently-Used Properties of the Floor Function. IOSR Journal of Mathematics, 13, 46-48.
- 8. Wang, X.B. (2015) Properties of the Lowest Common Ancestor in a Complete Binary Tree. International Journal of Scientific and Innovative Mathematical Research, 3, 12-17.
- 9. Wang, X.B. (2015) Analytic Formulas for Computing LCA and Path in Complete Binary Trees. International Journal of Scientific and Innovative Mathematical Research, 3, 1-8.