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
logbN+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 Na to N10 (its decimal representation)?







What I have tried:



If we have a case like, for example, where we have 12345678 and b=2, then we can solve 2x=8x=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×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 Na, we can count how many digits it has.
Also, I need to "cheat" a bit by evaluating only the last digit of the number Na.



If n is the number of digits of Na and d is the last digit, then Nb has digits: (n1)[logba]+logbd+1



([x] rounds the number to the nearest integer, and x 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 logbN+1.



If N is a concrete number written in base a with n digits, its value lies in [an1,an1] and the number of base-b digits is in



[logban1+1,logb(an1)+1] which is most of the time




[(n1)logba+1,nlogba+1].


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f:AB and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...