1
$\begingroup$

I get that the number of digits in a base $3$ number $x$ is found with $$ \big\lfloor\log_3(x)\big\rfloor + 1 $$

($+1$ for the first digit being a scalar of $3^0$ not $3^1$) That being said, how do you know it's not $$ \Big\lfloor\log_3\Big(\frac{x}{2}\Big)\Big\rfloor + 1 $$

If the first digit of the number is a $2$?

Just from exploration I've found that whenever a base $3$ number starts with $2$, these two expressions are equal. Whenever it starts with one the number of digits is always the first expression (obviously). So the first expression is always a correct approximation of the number of digits. Why is this? I don't get why the first expression is always the same as the second expression when the first digit is a $2$.

$\endgroup$
  • 2
    $\begingroup$ Isn't it clear that if the first digit is a $2$ then half the number has the same number of digits? $\endgroup$ – lulu Jan 31 '18 at 14:12
  • 1
    $\begingroup$ Think about your question in ordinary base $10$ and examine how the answer depends on the value of the first digit. $\endgroup$ – Ethan Bolker Jan 31 '18 at 14:13
  • $\begingroup$ If the first digit is $2$, then $\lfloor \log_3(x/2)\rfloor = \lfloor \log_3(x)\rfloor.$ $\endgroup$ – Thomas Andrews Jan 31 '18 at 14:28
1
$\begingroup$

The expression $$\lfloor\log_3(x)\rfloor + 1$$ is not just, as you say, a correct approximation of the number of digits. It is, in fact, the exact number of digits of $x$.

You can easily prove this fact by writing a $(n+1)\mathrm{-digit}$ number as $$x=\sum_{i=0}^n 3^i a_i$$ where $a_n\neq 0;$ and showing that, since $$3^n\leq x< 3^{n+1},$$ we have $$n\leq\log_3(x)<n+1$$


So, we now already know that $$\lfloor\log_3(x)\rfloor + 1$$ is the number of digits of $x$ in base $3$. Therefore, we also know that $$\lfloor\log_3\frac x2\rfloor + 1$$ must be the number of digits of $\frac x2$, and $\frac{x}2$ has the same number of digits as $x$ if and only if the first digit of $x$ is equal to $2$.

The final statement I wrote is fairly easy to prove, and generalizes to the fact that $x$ has the same number of digits as $\frac x2$ in base $b$ if and only if the first digit of $x$ is greater than $1$.

$\endgroup$
  • $\begingroup$ Isn't it 3^n <= x < 3^(n+1) not <=3^(n+1) $\endgroup$ – Murey Tasroc Jan 31 '18 at 14:23
  • $\begingroup$ @MureyTasroc Yes, that was a typo. $\endgroup$ – 5xum Jan 31 '18 at 14:28
0
$\begingroup$

$\ log_3(100_3)+1 = 3 $

$\ log_3(111_3)+1 = 3.335 $

$\ log_3(122_3)+1 = 3.579 $

$\ log_3(222_3)+1 = 3.966 $

$\ log_3(1000_3)+1 = 4 $

I understand it now. Even if the first digit is 2 the floored base 3 logarithm of that number will not be different because the minimum scalar to add another place would be 3 (which would become a 1 in the next spot). So yes, $\lfloor\log_3(\frac{num}2)\rfloor$ would be the same as $\lfloor\log_3(num)\rfloor$ when the first digit is 2 because halving that number will just make the first place 1 but will not add or subtract digits (ignoring remainders). In other words (thinking about it in our number system) a number will not fall below $3^n$ when halved if the first digit is $2*3^n$ (first digit of 2 in base 3), which would be necessary to change the floored logarithm. When the first digit is 1, however, dividing by 2 will remove a place which is why the two expressions in my question aren't equal when the first digit is one. This is equivalent to asking why $\lfloor log(\frac{999_{10}}{9_{10}})\rfloor$ is equal to $\lfloor log(999_{10})\rfloor$.

$\endgroup$

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.