Brief Investigation on Square Root of a Node of T₃ Tree

Guihong Chen^1,2, Jianhui Li^1,3

¹Department of Computer Science and Technology, Neusoft Institute Guangdong, Foshan, China.
²School of Electronics and Information Technology, Sun Yat-sen University, Guangzhou, China.
³State Key Laboratory of Mathematical Engineering and Advanced Computing, Wuxi, China.

DOI: 10.4236/apm.2018.87039                

Abstract

The article investigates some properties of square root of T₃ tree’s nodes. It first proves several inequalities that are helpful to estimate the square root of a node, and then proves several theorems to describe the distribution of the square root of the nodes on T₃ tree.

Keywords

Square Root, Node, Valuated Binary Tree, Inequality

1. Introduction

Article [1] introduced the T₃ tree and showed a number of properties of tree, including divisibility, multiples and divisors and multiplications of the nodes. Looking through the other papers that are related with the article [1] , such as articles [2] - [7] , one can see that the T₃ tree is really a new attempt to study integers. However, one can also see that, there has not been an article that concerns the square root of a node in the T₃ tree. As is known, a divisor of integer N must be no bigger than $\sqrt{N}$ . Hence the location where $\sqrt{N}$ lies in the T₃ tree is important for finding N’s divisor. Accordingly, this article makes an investigation on the issue and presents the results.

2. Preliminaries

2.1. Symbols and Notations

Symbol T₃ is the T₃ tree that was introduced in [1] and [2] and symbol $N_{\left(k,j\right)}$ is by default the node at position j on level k of T₃, where $k\ge 0$ and $0\le j\le 2^k-1$ . An integer X is said to be clamped on level k of T₃ if and symbol $X\stackrel{\wedge}{=}k$ indicates X is clamped on level k. An odd interval $\left[a,b\right]$ is a set of consecutive odd numbers that take a as lower bound and b as upper bound, for example, $\left[3,11\right]=\left\{3,5,7,9,11\right\}$ . Intervals in this whole article are by default the odd ones unless particularly mentioned. Symbol $\lfloor x\rfloor$ is the floor function, an integer function of real number x that satisfies inequality $x-1<\lfloor x\rfloor \le x$ , or equivalently. Symbol $A\Rightarrow B$ means conclusion B can be derived from condition A.

2.2. Lemmas

Lemma 1 (See in [1] ). Let $N_{\left(k,j\right)}$ be the node at the j^th position on the k^th level of T₃ with $k\ge 0$ and $0\le j\le 2^k-1$ ; then $2^{k+1}+1\le N_{\left(k,j\right)}\le 2^{k+2}-1$ .

Lemma 2 (See in [8] ). For real numbers x and y, it holds

(P2)

(P8) $n\lfloor x\rfloor \le \lfloor nx\rfloor$ with n being a positive integer

(P13)

(P17), $\lfloor \frac{x}{2}\rfloor +\lfloor \frac{x+1}{2}\rfloor =\lfloor x\rfloor$

3. Main Results and Proofs

Theorem 1. Let $a>1$ be an integer and $x>0$ be a real number; then it holds

(1)

and

(2)

Proof. Since $a>1$ , the definition immediately yields

$a^{\lfloor x\rfloor -1}<a^{\lfloor x\rfloor }\le a^x<a^{\lfloor x\rfloor +1}$

Since a and are integers, it yields by Lemma 2 (P13)

$a^{\lfloor x\rfloor }\le \lfloor a^x\rfloor \le a^{\lfloor x\rfloor +1}$

Considering, it knows $a^{\lfloor x\rfloor -1}<a^{\lfloor x\rfloor }$ ; consequently

$a^{\lfloor x\rfloor -1}<a^{\lfloor x\rfloor }\le \lfloor a^x\rfloor \le a^{\lfloor x\rfloor +1}$

Theorem 1. Let n be a positive integer and

$b_0=n^2,b_1=n^2+1,\cdots ,b_i=n^2+i,\cdots ,b_{2n}=n^2+2n,b_{2n+1}=n^2+2n+1$

then

${\lfloor \sqrt{b_i}\rfloor }_{\left(i=1,\cdots ,2n\right)}=\lfloor \sqrt{b_0}\rfloor =n$ , $\lfloor \sqrt{b_{2n+1}}\rfloor =n+1$ (3)

Proof. and $\lfloor \sqrt{b_{2n+1}}\rfloor =n+1$ obviously hold. Now consider that, for $i=1,2,\cdots ,2n$ , it holds

$n=\sqrt{b_0}<\sqrt{b_i}=n\sqrt{1+\frac{i}{n^2}}<\sqrt{b_{2n+1}}=n+1$

This is to say that,; since n is an integer, it is sure by definition of the floor function

${\lfloor \sqrt{b_i}\rfloor }_{\left(i=1,\cdots ,2n\right)}=n$

Corollary 1. Let n and $\alpha$ be a positive integers and

$b_0=n^{2\alpha },b_1=n^{2\alpha }+1,\cdots ,b_i=n^{2\alpha }+i,\cdots ,b_{2n^{\alpha }}=n^{2\alpha }+2n^{\alpha },b_{2n^{\alpha }+1}=n^{2\alpha }+2n^{\alpha }+1$

then

(4)

Proof. (Omitted)

Example 1. Take $b_0=2^8,b_1=2^8+1=257,\cdots ,b_{2\times 2^4}=2^8+2\times 2^4=288$ , $b_{2\times 2^4+1}=2^8+2\times 2^4+1=289$ ; then $\lfloor \sqrt{b_0}\rfloor =2^4,\lfloor \sqrt{b_1}\rfloor =16,\cdots ,\lfloor \sqrt{b_{2\times 2^4}}\rfloor =16,\lfloor \sqrt{b_{2\times 2^4+1}}\rfloor =17$ .

Theorem 2. Let n and $\alpha$ be a positive integers and

$\begin{array}{l}{b}_0=n^{2\alpha +1},b_1=n^{2\alpha +1}+1,\cdots ,b_i=n^{2\alpha +1}+i,\cdots ,b_{2n^{\alpha }}=n^{2\alpha +1}+2n^{\alpha }\sqrt{n},\\ b_{2n^{\alpha }+1}=n^{2\alpha +1}+2n^{\alpha }\sqrt{n}+1\end{array}$

then

$\lfloor n^{\alpha }\sqrt{n}\rfloor \le {\lfloor \sqrt{b_i}\rfloor |}_{\left(i=0,1,2,\cdots ,2n^{\alpha }+1\right)}\le \lfloor n^{\alpha }\sqrt{n}\rfloor +1$

Proof. See the following deductions.

1)

2) By Lemma 2(P13)

$\begin{array}{l}{n}^{2\alpha +1}=b_0<b_1=n^{2\alpha +1}+1<\cdots <b_{2n^{\alpha }}=n^{2\alpha +1}+2n^{\alpha }\sqrt{n}<b_{2n^{\alpha }+1}={\left(n^{\alpha }\sqrt{n}+1\right)}^2\\ \Rightarrow n^{\alpha }\sqrt{n}=\sqrt{b_0}<{\sqrt{b_i}|}_{\left(i=1,2,\cdots ,2n^{\alpha }\right)}<n^{\alpha }\sqrt{n}+1\\ \Rightarrow \lfloor n^{\alpha }\sqrt{n}\rfloor =\sqrt{b_0}\le {\sqrt{b_i}|}_{\left(i=1,2,\cdots ,2n^{\alpha }\right)}\le \lfloor n^{\alpha }\sqrt{n}\rfloor +1\end{array}$

Example 2. Take and $b_{2n^{\alpha }+1}$ by

, $b_{2^5}=2^9+2^5=544$ , $b_{2^5+1}=2^9+2^5+1=545$ then

$\begin{array}{l}\lfloor \sqrt{b_{2^4+1}}\rfloor =\lfloor \sqrt{2^9+17}\rfloor =\lfloor \sqrt{529}\rfloor =23,\\ \cdots ,\\ \lfloor \sqrt{b_{2\times 2^4-1}}\rfloor =\lfloor \sqrt{543}\rfloor =23,\\ \lfloor \sqrt{b_{2\times 2^4}}\rfloor =\lfloor \sqrt{544}\rfloor =23,\\ \lfloor \sqrt{b_{2\times 2^4+1}}\rfloor =\lfloor \sqrt{545}\rfloor =23\end{array}$

Theorem 4 Suppose integer k satisfies $k>2$ and $N_{\left(k,0\right)}$ be the leftmost node on level k of T₃; then is even if k is odd, whereas, it can be either odd or even if k is even.

Proof. Since $N_{\left(k,0\right)}=2^{k+1}+1$ , it knows by Corollary 1 for an odd k. If k is even, let it be $k=2\alpha +1$ ; then by Theorem 2 $\lfloor \sqrt{N_{\left(k,0\right)}}\rfloor =\lfloor 2^{\alpha }\sqrt{2}\rfloor$ or $\lfloor \sqrt{N_{\left(k,0\right)}}\rfloor =\lfloor 2^{\alpha }\sqrt{2}\rfloor +1$ , which indicates $\lfloor \sqrt{N_{\left(k,0\right)}}\rfloor$ can be either odd or even.

Example 3. Taking $N_{\left(7,0\right)},N_{\left(11,0\right)},N_{\left(19,0\right)},N_{\left(8,0\right)},N_{\left(10,0\right)}$ and $N_{\left(16,0\right)}$ as examples results in the following results.

$\begin{array}{l}{N}_{\left(7,0\right)}=2^{7+1}+1=257\Rightarrow \lfloor \sqrt{N_{\left(7,0\right)}}\rfloor =16\\ N_{\left(11,0\right)}=2^{11+1}+1=4097\Rightarrow \lfloor \sqrt{N_{\left(11,0\right)}}\rfloor =64\\ N_{\left(19,0\right)}=2^{19+1}+1=\text{1048577}\Rightarrow \lfloor \sqrt{N_{\left(19,0\right)}}\rfloor =1024\end{array}$

$\begin{array}{l}{N}_{\left(8,0\right)}=2^{8+1}+1=513\Rightarrow \lfloor \sqrt{N_{\left(8,0\right)}}\rfloor =22\\ N_{\left(10,0\right)}=2^{10+1}+1=1025\Rightarrow \lfloor \sqrt{N_{\left(10,0\right)}}\rfloor =45\\ N_{\left(16,0\right)}=2^{16+1}+1=\text{131073}\Rightarrow \lfloor \sqrt{N_{\left(16,0\right)}}\rfloor =362\end{array}$

Theorem 5. Suppose integers k and j satisfy $k>2$ and $0\le j\le 2^k-1$ ; let $N_{\left(k,j\right)}$ be the node at position j on level k of T₃; then it holds

(5)

Proof. Since $2^{k+1}+1\le N_{\left(k,j\right)}\le 2^{k+2}-1$ , it yields $2^{k+1}<N_{\left(k,j\right)}<2^{k+2}$ ; hence it holds

$2^{\frac{k+1}{2}}<\sqrt{N_{\left(k,j\right)}}<2^{\frac{k}{2}+1}$

By Lemma 2 (P13), it yields

$\lfloor 2^{\frac{k+1}{2}}\rfloor \le \lfloor \sqrt{N_{\left(k,j\right)}}\rfloor \le \lfloor 2^{\frac{k}{2}+1}\rfloor$ (6)

By Theorem 1, it holds

$2^{\lfloor \frac{k+1}{2}\rfloor }\le 2^{\frac{k+1}{2}}$

and

$2^{\frac{k}{2}+1}<2^{\lfloor \frac{k}{2}\rfloor +2}$

Hence it results in

$2^{\lfloor \frac{k+1}{2}\rfloor }=\lfloor 2^{\lfloor \frac{k+1}{2}\rfloor }\rfloor \le \lfloor 2^{\frac{k+1}{2}}\rfloor \le \lfloor \sqrt{N_{\left(k,j\right)}}\rfloor \le \lfloor 2^{\frac{k}{2}+1}\rfloor \le \lfloor 2^{\lfloor \frac{k}{2}\rfloor +2}\rfloor =2^{\lfloor \frac{k}{2}\rfloor +2}$

That is

$2^{\lfloor \frac{k+1}{2}\rfloor }\le \lfloor \sqrt{N_{\left(k,j\right)}}\rfloor \le 2^{\lfloor \frac{k}{2}\rfloor +2}$ (7)

or equivalently

$2^{\lfloor \frac{k+1}{2}\rfloor }-1<\lfloor \sqrt{N_{\left(k,j\right)}}\rfloor <2^{\lfloor \frac{k}{2}\rfloor +2}+1$ (8)

Corollary 2. $\lfloor \sqrt{N_{\left(k,j\right)}}\rfloor$ is clamped in T₃ on level $\lfloor \frac{k+1}{2}\rfloor -1$ and or level $\lfloor \frac{k}{2}\rfloor$ .

Proof. Since $2^{\lfloor \frac{k+1}{2}\rfloor }-1$ the biggest node on level $\lfloor \frac{k+1}{2}\rfloor -2$ and $2^{\lfloor \frac{k}{2}\rfloor +2}+1$ is the smallest node on level $\lfloor \frac{k}{2}\rfloor +1$ , it knows by (8) $\lfloor \sqrt{N_{\left(k,j\right)}}\rfloor$ may be clamped on levels from $\lfloor \frac{k+1}{2}\rfloor -1$ to $\lfloor \frac{k}{2}\rfloor$ , totally $\lfloor \frac{k}{2}\rfloor -\left(\lfloor \frac{k+1}{2}\rfloor -1\right)+1$ levels.

By Lemma 2 (P2) $\lfloor \frac{k}{2}\rfloor -\left(\lfloor \frac{k+1}{2}\rfloor -1\right)+1\ge 2+\lfloor \frac{k}{2}-\frac{k+1}{2}\rfloor =2-1=1$

By Lemma 2 (P17 & P8) $\lfloor \frac{k}{2}\rfloor -\left(\lfloor \frac{k+1}{2}\rfloor -1\right)+1=2+\lfloor \frac{k}{2}\rfloor -\left(\lfloor k\rfloor -\lfloor \frac{k}{2}\rfloor \right)=2+2\lfloor \frac{k}{2}\rfloor -\lfloor k\rfloor \le 2$

Hence the corollary holds

Example 4. Taking the smallest nodes and the biggest nodes on level 7 and level 10 respectively, it can see that $\lfloor \sqrt{N_{\left(7,*\right)}}\rfloor$ is clamped on 2 levels, whereas $\lfloor \sqrt{N_{\left(10,*\right)}}\rfloor$ is clamped on 1 level.

$\begin{array}{l}{N}_{\left(7,0\right)}=2^{7+1}+1=257\Rightarrow \lfloor \sqrt{N_{\left(7,0\right)}}\rfloor =16\stackrel{\wedge}{=}2\\ N_{\left(7,2^7-1\right)}=2^{7+2}-1=511\Rightarrow \lfloor \sqrt{N_{\left(7,2^7-1\right)}}\rfloor =22\stackrel{\wedge}{=}3\\ N_{\left(10,0\right)}=2^{11}+1=2047\Rightarrow \lfloor \sqrt{N_{\left(10,0\right)}}\rfloor =45\stackrel{\wedge}{=}4\\ N_{\left(10,2^{10}-1\right)}=2^{12}-1=4095\Rightarrow \lfloor \sqrt{N_{\left(10,2^{10}-1\right)}}\rfloor =63\stackrel{\wedge}{=}4\end{array}$

4. Conclusion

Elementary number theory shows that an integer must have a divisor smaller than the square root of the integer itself. Hence the square root is undoubtedly an important issue of an integer. Since T₃ tree is considered to be a new tool to study integers, the square root of a node is certainly helpful to know the distribution of the node’s divisors. The properties proved in this article are sure to provide a know-about the square root of the nodes. We hope it will be useful in the future.

Acknowledgements

The research work is supported by the State Key Laboratory of Mathematical Engineering and Advanced Computing under Open Project Program No. 2017A01, the Youth Innovative Talents Project (Natural Science) of Education Department of Guangdong Province under grant 2016KQNCX192, 2017KQNCX230. The authors sincerely present thanks to them all.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	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
[2]	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.
[3]	Wang, X.B. (2016) Amusing Properties of Odd Numbers Derived From Valuated Binary Tree. IOSR Journal of Mathematics, 12, 53-57.
[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]	Wang, X.B. (2017) Strategy for Algorithm Design in Factoring RSA Numbers. IOSR Journal of Computer Engineering, 19, 1-7.
[6]	Wang, X.B. (2017) Two More Symmetric Properties of Odd Numbers. IOSR Journal of Mathematics, 13, 37-40.
[7]	Wang, X.B. (2018) Influence of Divisor-ratio to Distribution of Semiprime’s Divisor. Journal of Mathematics Research, 10, 54-61. https://doi.org/10.5539/jmr.v10n4p54
[8]	Wang, X.B. (2017) Brief Summary of Frequently-Used Properties of the Floor Function. IOSR Journal of Mathematics, 13, 46-48.