Given the number $n$. Why does it take maximum of $\frac{n}{\log n}$ digits to represent the number $2^n - 1$ in base of $n$?
Why does it take maximum of $n/\log n$ digits to represent the number $2^n - 1$ in base of $n$?
1
$\begingroup$
elementary-number-theory
computational-complexity
-
0Changed the tag :) – 2012-12-13
1 Answers
0
Hint: to express any number $m$ in base $n$ takes $\lfloor \log_n m \rfloor +1$ digits. To see this, think about base $10$. With one digit you can express any number up to $9$, for which the floor of the log is $0$. With three digits you can express numbers up to $999$, for which the floor is $2$. What base of logs were you planning to use?
-
0Helped a lot! Thanks Ross! – 2012-12-13