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
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
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.