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$
3
  • 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
    Commented Jan 31, 2018 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$ Commented Jan 31, 2018 at 14:13
  • $\begingroup$ If the first digit is $2$, then $\lfloor \log_3(x/2)\rfloor = \lfloor \log_3(x)\rfloor.$ $\endgroup$ Commented Jan 31, 2018 at 14:28

2 Answers 2

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$
2
  • $\begingroup$ Isn't it 3^n <= x < 3^(n+1) not <=3^(n+1) $\endgroup$ Commented Jan 31, 2018 at 14:23
  • $\begingroup$ @MureyTasroc Yes, that was a typo. $\endgroup$
    – 5xum
    Commented Jan 31, 2018 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .