APM  Vol.8 No.5 , May 2018
T3 Tree and Its Traits in Understanding Integers
Author(s) Xingbo Wang1,2
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.

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 2 N 1 and 2 N + 1 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 N = 3 . The root of the T3 is assigned a right attributive. For convenience, symbol N ( k , j ) is by default the node at the jth position on the k t h level of T3, where k 0 and 0 j 2 k 1 ; symbol T N ( k , j ) denotes a subtree whose root is N ( k , j ) and symbol N ( i , ω ) N ( k , j ) denotes the node at the ωth position on the i th level of T N ( k , j ) . Level m is said to be higher than level n if m < n and it is said to be lower than level n if m > n . Symbol P ( A , B ) 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 N ( N ( m , a ) χ ) is the node where N ( m , α ) slides down χ levels along the leftmost path of subtree

T N ( m , α ) and symbol N ( N ( m , a ) χ ) is that N ( m , α ) slides down χ levels along the

rightmost path of subtree T N ( m , α ) .

An odd interval [ a , b ] is a set of consecutive odd numbers that take a as lower bound and b as upper bound, for example, [ 3,11 ] = { 3,5,7,9,11 } . Intervals in this whole article are by default the odd ones unless particularly mentioned. Symbol x is the floor function, an integer function of real number χ that satisfies inequality x 1 < x x , or equivalently x x < x + 1 .

2.2. Lemmas

Lemma 1 (Subtree Transition Law, See in [2] ) Let T N ( m , s ) and T N ( k , j ) ( m k ) be two subtrees of T; then it holds

N ( i , ω ) N ( m , s ) = 2 i ( N ( m , s ) N ( k , j ) ) + N ( i , ω ) N ( k , j ) , i = 1 , 2 , ; ω = 0 , 1 , , 2 i 1

Lemma 2 (See in [4] ) Let N ( 0,0 ) be an odd integer bigger than 1 and T N ( 0,0 ) be the N ( 0,0 ) -rooted valuated binary tree; then the following statements hold

1) There are 2 k nodes on the k t h level with k = 0,1,2, ;

2) Node N ( k , j ) N ( 0,0 ) is computed by

N ( k , j ) N ( 0 , 0 ) = 2 k N ( 0 , 0 ) 2 k + 2 j + 1 k = 0 , 1 , 2 , ; j = 0 , 1 , , 2 k 1

3) Two position-symmetric nodes, N ( i , ω ) N ( 0 , 0 ) and N ( i ,2 i 1 ω ) N ( 0 , 0 ) , satisfy

N ( i , ω ) N ( 0 , 0 ) + N ( i ,2 i 1 ω ) N ( 0 , 0 ) = 2 i + 1 N ( 0 , 0 )

4) Level i ( i 0 )of subtree T N ( k , j ) N ( 0,0 ) ( k 0 ) is the level ( k + i ) of T N ( 0 , 0 ) and it contains 2 i nodes. Node N ( i , ω ) N ( k , j ) N ( 0,0 ) of T N ( k , j ) N ( 0,0 ) ( 0 ω 2 i 1 ) is corresponding to node N ( k + i , 2 i j + ω ) N ( 0 , 0 ) of T N ( 0 , 0 ) by

N ( i , ω ) N ( k , j ) N ( 0 , 0 ) = N ( k + i , 2 i j + ω ) N ( 0 , 0 ) = 2 i N ( k , j ) N ( 0 , 0 ) 2 i + 2 ω + 1 j = 0 , 1 , , 2 k 1 ; i = 0 , 1 , ; ω = 0 , 1 , , 2 i 1

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 ( n 1 ) q + 1 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 k > 0, the odd integer of the form 4 k +1 is a left node while the odd integer of the form 4 k +3 is a right node.

(P1) On the k t h level with k = 0,1, , there are 2 k nodes starting by 2 k + 1 + 1 and ending by 2 k + 2 1 , namely, N ( k , j ) [ 2 k + 1 + 1,2 k + 2 1 ] with j = 0 , 1 , , 2 k 1 .

(P2) N ( k , j ) is calculated by

N ( k , j ) = 2 k + 1 + 1 + 2 j , j = 0 , 1 , , 2 k 1

(P3) Nodes N ( k + 1,2 j ) and N ( k + 1,2 j + 1 ) on the ( k + 1 ) t h level are respectively the left son and the right son of node N ( k , j ) on the k t h level. The descendants of N ( k , j ) on the ( k + i ) t h level are N ( k + i ,2 i j + ω ) ( 0 ω 2 i 1 ), which are

N ( k + i , 2 i j ) , N ( k + i , 2 i j + 1 ) , N ( k + i , 2 i j + 2 ) , , N ( k + i , 2 i j + 2 i 1 )

Particularly,

N ( N ( m , a ) χ ) = 2 χ ( N ( m , α ) 1 ) + 1

and

N ( N ( m , a ) χ ) = 2 χ ( N ( m , α ) + 1 ) 1

(P4) The biggest node on the k t h level of the left branch is 2 k + 1 + 2 k 1 whose position is j = 2 k 1 1 , and the smallest node on the k t h level of the right branch is 2 k + 1 + 2 k + 1 whose position is j = 2 k 1 .

(P5) Node N ( i , ω ) and node N ( i ,2 i 1 ω ) are at the symmetric positions on the i th level and it holds

N ( i , ω ) + N ( i , 2 i 1 ω ) = 2 i + 1 × 3

(P6) Multiplication of arbitrary two nodes of T3, say N ( m , α ) and N ( n , β ) , is a third node of T3. That is,

N ( m , α ) × N ( n , β ) = ( 2 m + 1 + 1 + 2 α ) × ( 2 n + 1 + 1 + 2 β ) T 3

(P7) The binary representation of node N ( k , j ) takes k + 2 bits with the least significant bit and the most significant bit being 1, that is

N ( k , j ) = ( 1 n k n k 1 n 1 k + 2 1 ) 2

(P8) Odd integer N with N > 1 lies on level l o g 2 N 1 .

Proof. Omit the proofs for (P0) to (P6). (P7) can be proved by mathematical induction. Here only prove (P8). By (P1) it yields k + 1 log 2 N ( k , j ) < k + 2 , that is

l o g 2 N ( k , j ) 2 < k l o g 2 N ( k , j ) 1

By definition of the floor function, it knows k = log 2 N ( k , j ) 1 .

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 n > 1 a subtree of T3 must contain a multiple of 2 n 1 on level n counted from the subtree’s root that stands on level 0.

3) For integer k 1 , a node of T3 on level k must have at least 2 k 1 multiples on level 2 k + 1 of T3; for integer k 0 , a node of T3 on level k must have at least 2 2 k multiples on level 2 ( k + 1 ) of T3.

Proof. The first claim is seen in [1] . Here only prove (2) and (3). The n level of an arbitrary subtree contains 2 n consecutive odd numbers. Since an arbitrary integer n > 1 yields 2 n > 2 n 1 , by Lemma 3 it knows that the claim (2) holds. Note that a node N ( k , j ) on level k of T3 satisfies 2 k + 1 + 1 N ( k , j ) 2 k + 2 1 and there are respectively 2 2 k + 1 nodes and 2 2 ( k + 1 ) nodes on level 2 k + 1 and level 2 ( k + 1 ) . Now consider the case k 1 . Since 2 2 k + 1 = 2 k 1 ( 2 k + 2 1 ) + 2 k 1 , it can see that on level 2 k + 1 , there are at least 2 k 1 consecutive sections each of which contain 2 k + 2 1 odd integers. By Lemma 3 it knows that there are at least 2 k 1 multiples of N ( k , j ) on level 2 k + 1 . Similarly, when k 0 it holds 2 2 ( k + 1 ) = 2 k ( 2 k + 2 1 ) + 2 k , it knows that the level 2 ( k + 1 ) contains at least 2 k multiples of N ( k , j ) .

Theorem 3. Among all nodes that lie on level k or a higher level in subtree T N ( k , j ) with k 0 , there is not a node that is a multiple of N ( k , j ) . Or node N ( k , j ) of T3 cannot divide its direct descendants that lie on level 2 k or a higher level in terms of T3.

Proof. Use proof by contradiction. Without loss of generality, assume N ( k , j ) can divide N ( m , s ) N ( k , j ) with 0 < m k and 0 s 2 m 1 , namely, N ( m , s ) N ( k , j ) = α N ( k , j ) with α being an odd integer; then by N ( m , s ) N ( k , j ) = α N ( k , j ) and

N ( m , s ) N ( k , j ) = 2 m N ( k , j ) 2 m + 2 s + 1

it leads to

α N ( k , j ) = 2 m N ( k , j ) 2 m + 2 s + 1

namely

( 2 m α ) N ( k , j ) = 2 m 2 s 1

which indicates N ( k , j ) can divide ϑ = 2 m 2 s 1 or N ( k , j ) = ϑ = 2 m 2 s 1 in the case 2 m α = 1 . Since the minimal value of s is 0 , it yields

ϑ 2 m 1

which shows that, due to 0 < m k , ϑ 2 m 1 < 2 k + 1 + 1 N ( k , j ) . This means that ϑ is impossible to be divisible by N ( k , j ) and neither holds N ( k , j ) = 2 m 2 s 1 . 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 N ( k , j ) .

Theorem 4. If node N ( k , j ) of T3 tree is composite, it must have a divisor that

lies on level k 2 or a higher level.

Proof. Use proof by contradiction. Assume p 1 and p 2 are two divisors of

Figure 1. Inbreeding avoidance.

N ( k , j ) and each of the two lies on level k 2 + 1 or lower levels; then p 1 2 2 + k 2 + 1 and p 2 2 2 + k 2 + 1 ; thus

p 1 p 2 ( 2 2 + k 2 + 1 ) 2 = 2 4 + 2 k 2 + 2 3 + k 2 + 1

Referring to (P31) in [6] , it knows 2 + 2 k 2 k + 1 for an arbitrary integer

k 0 ; hence

p 1 p 2 > 2 2 + k + 1 + 1 > 2 k + 3 + 1

which is contradictory to the fact that N ( k , j ) lies on level k .

Corollary 1* If a node N ( k , j ) ( k > 0 ) of T3 is a composite number and it has

a divisor d on level k 2 ; then another factor N ( k , j ) d must lie on level k 2 or level k 2 1 or level k 2 2 .

Proof. Considering N ( k 2 ,0 ) 2 and N ( k 2 ,2 k 2 1 ) 2 , the square of the smallest and the largest nodes on level k 2 respectively, and N ( k 2 , 0 ) × N ( k 2 + 1 , 0 ) , multiplication of the two smallest nodes on level k 2 and k 2 + 1

respectively, it yields

2 k + 1 + 1 < N ( k 2 , 0 ) 2 = ( 2 k 2 + 1 + 1 ) 2 < 2 k + 3 1

and

2 k + 2 + 1 < N ( k 2 , 2 k 2 1 ) 2 = ( 2 k 2 + 2 1 ) 2 < 2 k + 4 1

Similarly, it holds

2 k + 2 + 1 < N ( k 2 , 0 ) × N ( k 2 + 1 , 0 ) < 2 k + 4 1

These inequalities show that, multiplication of any two small nodes on level

k 2 lies on level k or level k + 1 or even level k + 2 and even the two smallest nodes one level k 2 and k 2 + 1 respectively cannot have a

multiplication that lies on level k since the multiplication lies on level k + 1 or level k + 2 .

Corollary 1. A node N ( k , j ) of T3 on level k is not divisible by every node on

level k 2 and higher levels is a prime number. Furthermore, N ( k , j ) of T3 on level k is not divisible by each prime-node on level k 2 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 m 0 and n 0 ; then product N ( m , α ) × N ( n , β ) ( α = 0 , 1 , , 2 m 1 ; β = 0 , 1 , , 2 n 1 ) lies on level m + n + 2 = 2 in the case m = n = 0 ; otherwise, it may lie from the position J 00 = 2 m + 2 n on level m + n + 1 to the position J m n = 2 m + n + 2 2 m + 1 2 n + 1 on level m + n + 2 , totally 2 m + n + 2 2 m + 1 2 n + 1 2 m 2 n possible positions.

Proof.

N ( m , α ) × N ( n , β ) = ( 2 m + 1 + 1 + 2 α ) × ( 2 n + 1 + 1 + 2 β ) = 2 m + n + 2 + 2 m + 1 ( 1 + 2 β ) + 2 n + 1 ( 1 + 2 α ) + 4 α β + 2 α + 2 β + 1 = 2 m + n + 2 + 1 + 2 ( 2 m ( 1 + 2 β ) + 2 n ( 1 + 2 α ) + 2 α β + α + β )

Let J = 2 m ( 1 + 2 β ) + 2 n ( 1 + 2 α ) + 2 α β + α + β ; then

N ( m , α ) × N ( n , β ) = 2 m + n + 2 + 1 + 2 J

Hence when 0 J 2 m + n + 1 1 , N ( m , α ) × N ( n , β ) = N ( m + n , J ) lies on level m + n + 1 of T3 and when J > 2 m + n + 1 1 , N ( m + n , J ) lies on level m + n + 2 or some lower level. Now consider the following cases.

Case (i) m = n = 0 . This time α = β = 0 and thus J = ( 1 + 2 β ) + ( 1 + 2 α ) + 2 α β + α + β = 2 > 1 . Since on level m + n + 1 = 1 , the maximal number of position is 1, it knows N ( m , α ) × N ( n , β ) = 2 m + n + 2 + 1 + 2 J lies on level 2, which is level m + n + 2 .

Case (ii) m = 0 plus n > 0 , or m > 0 plus n = 0 . Since J is a symmetric expression of m , n , α , and β , here only consider m = 0 plus n > 0 . This time, α = 2 m 1 = 0 thus J = ( 1 + 2 β ) + 2 n + β takes its minimal value at β = 0 and maximal value at β = 2 n 1 . Let the minimal value and the maximal value be respectively J 00 and J m n ; direct calculation shows

J 00 = 2 n + 1 , J m n = 2 n + 2 2

Since J 00 2 m + n + 1 1 (the equality holds only if n = 1 ), the minimal value of N ( m , α ) × N ( n , β ) , which is 2 m + n + 2 + 1 + 2 J 00 , lies on level m + n + 1 .

Meanwhile, by J m n = 2 n + 2 2 and m = 0 it knows

J m n = 2 n + 2 2 = 2 ( 2 n + 1 1 ) > 2 n + 1 1 = 2 m + n + 1 1

and

J m n = 2 n + 2 2 < 2 m + n + 2 1

That is to say, N ( m , α ) × N ( n , β ) = 2 m + n + 1 + 2 J m n lies on level m + n + 2 .

Case (iii) m > 0 and n > 0 . This time, J = 2 m ( 1 + 2 β ) + 2 n ( 1 + 2 α ) + 2 α β + α + β takes its minimal value at α = β = 0 and maximal value at α = 2 m 1 , β = 2 n 1 . Direct calculation shows

J 00 = 2 m + 2 n , J m n = 2 m + n + 2 + 2 m + n + 1 2 m + 1 2 n + 1

Note that, m > 0 and n > 0 yield J 00 2 m + n + 1 = 1 2 m + 1 + 1 2 n + 1 < 1 , namely,

4 J 00 = 2 m + 2 n 2 m + n + 1 1 < 2 m + n + 1 ; hence N ( m , α ) × N ( n , β ) = 2 m + n + 2 + 1 + 2 J 00 lies on level m + n + 1 .

On the other hand, by J m n = 2 m + n + 2 + 2 m + n + 1 2 m + 1 2 n + 1 , it holds

2 m + n + 2 + 1 + 2 J m n = 2 m + n + 2 + 1 + 2 × 2 m + n + 2 + 2 m + n + 2 2 m + 2 2 n + 2 = 2 m + n + 3 + 1 + 2 ( 2 m + n + 2 2 m + 1 2 n + 1 )

hence when m 1 and n 1 , 0 2 m + n + 2 2 m + 1 2 n + 1 2 m + n + 2 = 1 1 2 m + 1 1 2 n + 1 < 1

and thus

0 2 m + n + 2 2 m + 1 2 n + 1 2 m + n + 2 1

Consequently,

2 m + n + 3 + 1 N ( m , α ) × N ( n , β ) = 2 m + n + 2 + 1 + 2 J m n = 2 m + n + 3 + 1 + 2 ( 2 m + n + 2 2 m + 1 2 n + 1 ) < 2 m + n + 3 + 1 + 2 ( 2 m + n + 2 1 )

which shows that N ( m , α ) × N ( n , β ) = 2 m + n + 2 + 1 + 2 J m n lies on level m + n + 2 .

Now it can summarize that the smallest possible value of N ( m , α ) × N ( n , β ) is N ( m , α ) × N ( n , β ) = 2 m + n + 2 + 1 + 2 J 00 , which lies on level m + n + 1 at position J 00 = 2 m + 2 n ,and its maximal possible value is N ( m , α ) × N ( n , β ) = 2 m + n + 2 + 1 + 2 J m n ,which lies on level m + n + 2 at position J m n = 2 m + n + 2 2 m + 1 2 n + 1 . Since there are totally 2 m + n + 1 nodes on level m + n + 1 , it knows that there are 2 m + n + 1 1 2 m 2 n = 2 m + n + 1 2 m 2 n 1 nodes from position J 00 to position 2 m + n + 1 1 . Similarly, there are on level m + n + 2 totally 2 m + n + 2 2 m + 1 2 n + 1 + 1 nodes from position 0 to position J m n . It knows that, N ( m , α ) × N ( n , β ) has 2 m + n + 2 2 m + 1 2 n + 1 + 1 + 2 m + n + 1 2 m 2 n 1 = 2 m + n + 2 2 m + 1 2 n + 1 2 m 2 n possible positions.

Corollary 2. Suppose m 0 and n 0 ; then the product N ( m , α ) × N ( n , β ) = 2 m + n + 2 + 1 + 2 J with J = 2 m ( 1 + 2 β ) + 2 n ( 1 + 2 α ) + 2 α β + α + β and 0 α 2 m 1 plus 0 β 2 n 1 lies on level m + n + 1 and fits N ( m , α ) × N ( n , β ) = N ( m + n + 1 , J ) when J < 2 m + n + 1 , whereas it lies on level m + n + 2 and satisfies N ( m , α ) × N ( n , β ) = N ( m + n + 2, χ ) with χ = J 2 m + n + 1 when J 2 m + n + 1 .

Proof. The case J < 2 m + n + 1 has already been proved in the proof of Theorem 6. Now consider the case J 2 m + n + 1 . Note that there are in all N ( m , α ) × N ( n , β ) 1 integers from 2 to N ( m , α ) × N ( n , β ) . Eliminating all the even integers remains ( N ( m , α ) × N ( n , β ) 1 ) / 2 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 m + n + 1 levels contain 2 m + n + 2 1 ones and the left ( N ( m , α ) × N ( n , β ) 1 ) / 2 ( 2 m + n + 2 1 ) ones will be placed on the level m + n + 2 . Counting from position 0 to the position χ yields χ = ( N ( m , α ) × N ( n , β ) 1 ) / 2 ( 2 m + n + 2 1 ) 1 = ( N ( m , α ) × N ( n , β ) 1 ) / 2 2 m + n + 2 . Substituting N ( m , α ) × N ( n , β ) by 2 m + n + 2 + 1 + 2 J yields

χ = ( 2 m + n + 2 + 1 + 2 J 1 ) / 2 2 m + n + 2 = 2 m + n + 1 + J 2 m + n + 2 + 2 = J 2 m + n + 1

Corollary 3. For positive integer m and n , the node of T3 at position J 00 = 2 m + 2 n on level m + n + 1 is in left branch of T3 but it cannot a leftmost node; the node at position J m n 2 m + n + 1 on level m + n + 2 is in right branch but it cannot be a rightmost node.

Proof. The maximal node on level m + n + 1 in the left branch of T3 is 2 m + n + 2 + 1 + 2 ( 2 m + n 1 ) with position ϑ ( m + n + 1 , max ) l = 2 m + n 1 . Note that

J 00 ϑ ( m + n + 1 , max ) l = 2 m + 2 n 2 m + n + 1 = 2 m + n ( 1 2 m + 1 2 n 1 ) + 1

it knows that, m n = 1 yields J 00 ϑ ( m + n + 1 , max ) l = 1 and m n > 1 yields J 00 ϑ ( m + n + 1 , max ) l < 0 , which says that the position J 00 = 2 m + 2 n is on level m + n + 1 in the left branch of T3. Since the leftmost node is at position 0 whereas J 00 = 2 m + 2 n > 0 , the position J 00 = 2 m + 2 n is surely not a leftmost one.

To prove the second conclusion, let ϑ = J m n 2 m + n + 1 . Since the smallest node on level m + n + 2 in the right branch of T3 is 2 m + n + 3 + 1 + 2 × 2 m + n + 1 , it merely needs to prove 2 m + n + 1 ϑ < 2 m + n + 2 1 . In fact,

ϑ 2 m + n + 1 = J m n 2 m + n + 2 = 2 m + n + 1 2 m + 1 2 n + 1 = 2 m + n + 1 ( 1 1 2 m 1 2 n ) 0

and

ϑ ( 2 m + n + 2 1 ) = J m n 2 m + n + 1 2 m + n + 2 + 1 = 2 m + n + 2 + 2 m + n + 1 2 m + 1 2 n + 1 2 m + n + 1 2 m + n + 2 + 1 = 2 m + 1 2 n + 1 + 1 < 0

By Corollary 2 and Corollary 3, the product N ( m , α ) × N ( n , β ) can be intuitionally depicted with Figure 2.

Corollary 4. Let N ( m , α ) and N ( n , β ) be two nodes of T3 with 0 m n ; then the product N ( m , α ) × N ( n , β ) cannot fall in T N ( n , β ) on level m + 1 or a higher level.

Proof. Let N ( m , α ) = 2 m + 1 + 1 + 2 α and N ( n , β ) = 2 n + 1 + 1 + 2 β with α = 0 , 1 , , 2 m 1 and β = 0 , 1 , , 2 n 1 . Since the maximal node on level m + 1 of T N ( n , β ) is 2 m + 1 ( N ( n , β ) + 1 ) 1 , direct calculation yields

N ( m , α ) × N ( n , β ) = ( 2 m + 1 + 1 + 2 α ) × N ( n , β ) = 2 m + 1 × N ( n , β ) 2 m + 1 + 2 m + 1 + ( 1 + 2 α ) N ( n , β ) = 2 m + 1 ( N ( n , β ) + 1 ) 1 N ( n , β ) ( m + 1 ) 2 m + 1 + 1 + ( 1 + 2 α ) N ( n , β )

Note that

2 m + 1 + 1 + ( 1 + 2 α ) N ( n , β ) = 2 m + 1 + 1 + ( 1 + 2 α ) ( 2 n + 1 + 1 + 2 β ) 2 m + 1 + 1 + 2 n + 1 + 1 + 2 β > 0

hence N ( m , α ) × N ( n , β ) > 2 m + 1 ( N ( n , β ) + 1 ) 1 , which says N ( m , α ) × N ( n , β ) cannot fall on level m + 1 or a higher level of T N ( n , β ) .

Corollary 4 can be equivalently stated as that, if N ( m , α ) and N ( n , β ) are two nodes of T3 with m n , then the product N ( m , α ) × N ( n , β ) can only fall in the shadow area in Figure 3.

Corollary 5. Let N ( m , α ) and N ( m , β ) be two nodes of T3 with α < β ; then the product N ( m , α ) × N ( m , β ) cannot lie in T N ( m , α ) or T N ( m , β ) on level m + 1 or a higher level.

Figure 2. Possible positions of product N ( m , α ) × N ( n , β ) .

Figure 3. N ( m , α ) × N ( n , β ) can merely lie in area of shadow.

Proof. (Omitted)

Corollary 5 can be equivalently stated as that, if N ( m , α ) and N ( m , β ) are two nodes of T3 with α < β , then the product N ( m , α ) × N ( m , β ) can only fall in shadow area in Figure 4.

5.2. Square of A Node

Theorem 7. Product N ( m , α ) × N ( m , α ) = N ( m , α ) 2 is a left node of T3, it lies in T3 on level 2 m + 1 or 2 m + 2 and there are 2 ( 2 m + 1 ) α + 2 α 2 nodes from N ( m , α ) 2 to N ( N ( m , α ) ( m + 1 ) ) .

Proof. Direct calculation shows

N ( m , α ) 2 = ( 2 m + 1 + 1 + 2 α ) N ( m , α ) = 2 m + 1 ( N ( m , α ) + 1 ) 1 N ( m , α ) ( m + 1 ) 2 m + 1 + 1 + ( 1 + 2 α ) N ( m , α )

Let ξ = 2 m + 1 + 1 + ( 1 + 2 α ) N ( m , α ) ; then

ξ = 2 m + 1 + 1 + ( 1 + 2 α ) ( 1 + 2 α + 2 m + 1 ) = 2 m + 1 + 1 + 1 + 2 α + 2 m + 1 + 2 α + 4 α 2 + 2 m + 2 α = 2 ( 1 + 2 α + 2 α 2 + 2 m + 1 α )

and Δ = 2 α + 2 α 2 + 2 m + 1 α is the number of nodes from N ( m , α ) 2 to N ( N ( m , α ) ( m + 1 ) ) .

Corollary 6. For arbitrary integer m 0 , it holds N ( m , 2 m 1 ) × N ( m , 2 m 1 ) = N ( N ( m , 2 m 1 ) ( m + 2 ) ) and N ( m , 0 ) × N ( m , 0 ) = N ( N ( m , 1 ) ( m + 1 ) ) .

Proof. By (P4), it yields

N ( N ( m , α ) ( m + 2 ) ) = 2 m + 2 ( N ( m , α ) 1 ) + 1 = 2 m + 2 ( 2 m + 1 + 1 + 2 α 1 ) + 1 = 2 m + 2 ( 2 m + 1 + 2 α ) + 1 = 2 2 m + 3 + 2 m + 3 α + 1

Note that

Figure 4. N ( m , α ) × N ( n , β ) can merely lie in area of shadow.

N ( m , α ) 2 = ( 2 m + 1 + 1 + 2 α ) ( 2 m + 1 + 1 + 2 α ) = 2 2 m + 2 + 2 m + 1 + 2 m + 2 α + 2 m + 1 + 1 + 2 α + 2 m + 2 α + 2 α + 4 α 2 = 2 2 m + 2 + 2 m + 2 + 2 m + 3 α + 4 α + 4 α 2 + 1

Hence

N ( N ( m , α ) ( m + 2 ) ) N ( m , α ) 2 = 2 2 m + 2 2 m + 2 4 α 4 α 2

Taking α = 2 m 1 results in

N ( N ( m , α ) ( m + 2 ) ) N ( m , α ) 2 = 2 2 m + 2 2 m + 2 4 ( 2 m 1 ) 4 ( 2 m 1 ) 2 = 2 2 m + 2 2 m + 2 2 m + 2 + 4 2 2 ( 2 2 m 2 m + 1 + 1 ) = 2 2 m + 2 2 m + 2 2 m + 2 + 4 2 2 m + 2 + 2 m + 3 4 = 2 m + 2 2 m + 2 + 2 m + 3 = 0

Thus N ( m , α ) × N ( m , α ) = N ( N ( m , α ) ( m + 2 ) ) .

Now directly calculating N ( N ( m ,1 ) ( m + 1 ) ) and N ( m ,0 ) × N ( m ,0 ) yields

N ( m , 0 ) 2 = ( 2 m + 1 + 1 ) 2 = 2 2 m + 2 + 2 m + 2 + 1

and

N ( N ( m , 1 ) ( m + 1 ) ) = 2 m + 1 ( N ( m , 1 ) 1 ) + 1 = 2 m + 1 ( 2 m + 1 + 1 + 2 1 ) + 1 = 2 m + 1 ( 2 m + 1 + 2 ) + 1 = 2 2 m + 2 + 2 m + 2 + 1

which says N ( m , 0 ) × N ( m , 0 ) = N ( N ( m , 1 ) ( m + 1 ) ) .

Corollary 7 For arbitrary integer m 0 , N ( m ,2 m 1 ) 2 lies in T N ( m ,2 m 1 ) whereas N ( m ,0 ) 2 lies in T N ( m ,1 ) .

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 m 0 and 0 α < 2 m 1 , then N ( m , α ) 2 does not lie in T N ( m , α ) . Or equivalently, N ( m , α ) 2 does not lie in T N ( m , α ) unless m = 0 or m > 0 plus α = 2 m 1 .

Proof. By Theorem 7, N ( m , α ) 2 lie in T3 on level 2 m + 1 or 2 m + 2 . Since by Lemma 2 the level m + 1 of T N ( m , α ) is the level 2 m + 1 of T3, N ( m , α ) 2 can never lie in T N ( m , α ) on a level lower than m + 2 . By Corollary 5, N ( m , α ) 2 cannot lie in T N ( m , α ) on level m + 1 or a higher level. Now it needs to prove that it cannot either lie in T N ( m , α ) on level m + 2 . In fact, the smallest node of T N ( m , α ) on level m + 2 is N ( N ( m , α ) ( m + 2 ) ) . By Theorem 7 and Corollary 6 it knows that when α = 2 m 1 , N ( m , α ) 2 reaches it maximal value that is also the minimal node of T N ( m , α ) on level m + 2 . Hence it cannot lie in T N ( m , α ) under the condition m 0 and 0 α < 2 m 1 .

5.3. Path Connecting Multiple to Divisor

Theorem 8. Let N ( m , α ) and N ( n , β ) be two nodes of T3 with 0 m n ; then there is a path connecting N ( m , α ) × N ( n , β ) to N ( m , α ) and the length of the path is less than 2 m + n + 2 ; there is also a path connecting N ( m , α ) × N ( n , β ) to N ( n , β ) and the length of the path is less than m + 2 n + 2 .

Proof. By Theorem 6 and Corollary 7 and Corollary 8, it knows that N ( m , α ) × N ( n , β ) must lie in T N ( m , α ) , T N ( n , β ) or some other subtree of T3. First consider the case that N ( m , α ) × N ( n , β ) lies in T N ( n , β ) . By Corollary 2 and Lemma 2 it knows P ( N ( m , α ) × N ( n , β ) , N ( n , β ) ) m + 1 < m + n + 2 . Likewise, if N ( m , α ) × N ( n , β ) lies in T N ( m , α ) it holds P ( N ( m , α ) × N ( m , α ) , N ( m , α ) ) n + 1 < m + n + 2 .

Now consider the case that N ( m , α ) × N ( n , β ) lies in neither T N ( m , α ) nor T N ( n , β ) ; then there must be a γ and a λ with 0 γ 2 m 1 plus γ α and 0 λ 2 n 1 plus λ β such that N ( m , α ) × N ( n , β ) lies in T N ( m , γ ) or T N ( n , λ ) . Assume it lies in T N ( m , γ ) ; then by the subtree transition law,

N ( i , ω ) N ( m , γ ) = 2 i ( N ( m , γ ) N ( m , α ) ) + N ( i , ω ) N ( m , α ) i = 1 , 2 , ; ω = 0 , 1 , , 2 i 1

Let N ( l , s ) be the lowest common ancestor (LCA) of N ( m , α ) and N ( m , γ ) ; then by properties of LCA, as introduced in [7] [8] and [9] , N ( m , α ) × N ( n , β ) can be connected to along path P ( N ( m , α ) × N ( n , β ) , N ( m , γ ) ) P ( N ( m , γ ) , N ( l , s ) ) P ( N ( l , s ) , N ( m , α ) ) . Since the length of P ( N ( m , α ) × N ( n , β ) , N ( m , γ ) ) is less than m + n + 2 m = n + 2 , the length of P ( N ( m , γ ) , N ( l , s ) ) is m l and the length of P ( N ( l , s ) , N ( m , α ) ) is m l , it knows that the total length of the path is less than 2 m + n + 2 2 l 2 m + n + 2 . 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.

Cite this paper
Wang, X. (2018) T3 Tree and Its Traits in Understanding Integers. Advances in Pure Mathematics, 8, 494-507. doi: 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.

 
 
Top