Thursday, March 17, 2016

recreational mathematics - Find number of digits of N in base b



Given an integer $N$, we can find that it has
$ \lfloor\log_bN\rfloor+1$
digits in base $b$.

But what if $N$ is not in base $10$, but is in base $a$?





Can we calculate the number of digits $N$ written in base $a$ has in base $b$, but without converting $N_a$ to $N_{10}$ (its decimal representation)?







What I have tried:



If we have a case like, for example, where we have $1234567_8$ and $b=2$, then we can solve $2^x=8 \to x=3$ and know that each digit of base $8$ will take three digits to write in base $2$ (including trailing zeroes). But the last one should not have trailing zeroes, so we need to evaluate the last digit by itself, which is $1$, and see it takes only one digit in base $2$ as well. Thus, our number written in octal will have $3\times 6 +1=19$ digits in binary. But what if $x$ is not an integer?



I've thus tried to round the values to the nearest integer and put this method into a formula. In general, we follow this approach:






Since we can't evaluate (convert to base $10$) the $N_a$, we can count how many digits it has.
Also, I need to "cheat" a bit by evaluating only the last digit of the number $N_a$.



If $n$ is the number of digits of $N_a$ and $d$ is the last digit, then $N_b$ has digits: $$(n-1)[\log_ba]+\lfloor\log_bd\rfloor+1$$



($[x]$ rounds the number to the nearest integer, and $\lfloor x\rfloor$ is the floor function.)





How can we check/prove whether this expression is always exactly correct or not? I've tried only handful of examples and not sure how to fully check this. (it is correct if $x$ is an integer, the rounding is the only thing that bothers me)



Is there a better way to calculate/write solution to this problem?



Answer



When the number $N$ is a variable with an arbitrary value, the number of base-$b$ digits is indeed $\lfloor \log_b N\rfloor+1$.



If $N$ is a concrete number written in base $a$ with $n$ digits, its value lies in $[a^{n-1},a^n-1]$ and the number of base-$b$ digits is in



$$\big[\lfloor \log_b a^{n-1}\rfloor+1,\lfloor \log_b(a^n-1)\rfloor+1\big]$$ which is most of the time




$$\big[\lfloor (n-1)\log_ba\rfloor+1,\lfloor n\log_ba\rfloor+1\big].$$


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...