In Project Euler problem 16, you have to sum up the digits of $2^{1000}$. A non-brute force solution had the prerequisite to know the length of the result beforehand and the following formula gave the result: $1000\log_{10}(2)+1$. Could someone explain where this came from? And add a generalization (and resources on the background of the topic).

  • $\begingroup$ Can you clarify the question? Are you asking how to arrive at the given formula for the number of digits in a large power of $2$? $\endgroup$ – Sammy Black Oct 3 '13 at 9:51
  • 2
    $\begingroup$ In general, every integer $n$ is between $10^{r-1}$ and $10^r$ for some $r$, and such an integer has $r$ digits (can you see why?). And the base-10 log of $n$ is between $r-1$ and $r$. So, the number of digits is one more than the integer part of the base-10 log. Now: generalize this to base $b$ for arbitrary (integer) $b$ (greater than 1). $\endgroup$ – Gerry Myerson Oct 3 '13 at 9:52
  • $\begingroup$ @SammyBlack: more generally, how to predict the number of digits in the result of an operation. Gerry Myerson: I'll try to understand about your explanation. $\endgroup$ – zeller Oct 3 '13 at 10:06
  • $\begingroup$ @GerryMyerson I understand now, thanks. Though I can only empirically prove your first "lemma"... $\endgroup$ – zeller Oct 3 '13 at 10:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.