0
$\begingroup$

number of digits in the square root of a perfect square with n digits is ceil(n/2). We can get convinced of this result by following the division method. My question is, is there analytical proof of this result?

$\endgroup$
  • 2
    $\begingroup$ $log \sqrt n=\frac {1}{2}log n $ $\endgroup$ – N.S.JOHN Aug 7 '16 at 9:24
  • $\begingroup$ simple and nice, I missed it some how. @N.S.JOHN. $\endgroup$ – Seetha Rama Raju Sanapala Aug 7 '16 at 9:31
3
$\begingroup$

An $m$-digit integer is in the interval $[10^{m-1},10^m)$ and has a square in the interval $[10^{2m-2},10^{2m})$ with $2m-1$ or $2m$ digits.

So to reverse, divide the number of digits in the square by two to give $\frac{2m-1}{2}= m-\frac12$ or $\frac{2m}{2}= m$ and round up to give the original integer $m$.

$\endgroup$
2
$\begingroup$

The number of digits of a number $n$ in base $b$ is given by

$$\lfloor\log_b (n)\rfloor + 1$$

Now we have

\begin{align*} \lfloor \log_b(\sqrt{n}) \rfloor + 1 &= \left\lfloor\frac{1}{2} \log_b(n) \right\rfloor + 1 \\ &= \begin{cases} \frac{1}{2}\lfloor\log_b(n)\rfloor +1 & \text{if } \lfloor\log_b(n)\rfloor \text{ is even} \\ \frac{1}{2}\lfloor\log_b(n)\rfloor + \frac{1}{2} & \text{if } \lfloor\log_b(n)\rfloor \text{ is odd} \end{cases} \\ &= \left\lceil \frac{1}{2} \left(\lfloor \log_b(n) \rfloor + 1 \right)\right\rceil. \end{align*}

$\endgroup$
2
$\begingroup$

Claim: For a positive integer $a$, suppose $a$ has $m$ digits and $a^2$ has $n$ digits. Then $m = \left\lceil \frac{n}{2} \right\rceil$.

Proof: We have \begin{align*} 10^{m-1} \le a < 10^m \tag{1} \\ 10^{n-1} \le a^2 < 10^n \tag{2} \end{align*} Squaring (1), we get $$ 10^{2m-2} \le a^2 < 10^{2m} $$ Combining with (2), it follows that $$ 10^{n-1} < 10^{2m} \implies m > \frac{n-1}{2} \implies m \ge \frac{n}{2} $$ and $$ 10^{2m-2} < 10^n \implies m < \frac{n+2}{2} \implies m < \frac{n}{2} + 1. $$ Therefore $m$ is an integer greater than or equal to $\frac{n}{2}$ and less than $\frac{n}{2} + 1$. Thus by definition of the ceiling function, we must have $$ m = \left\lceil \frac{n}{2} \right\rceil. $$

$\endgroup$
  • $\begingroup$ @igael thanks, i fixed it $\endgroup$ – 6005 Aug 7 '16 at 18:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.