2
$\begingroup$

How do I get the leading digits for a large power of 2 (say $2^{123456789}$, although I want a general method)? I was thinking about repeatedly dividing it by ten, but I don't know how to do that efficiently without calculating the number itself, and I was also thinking $\log(a) < 123456789\log(2) < b$ would imply that it would be the first three digits of $a$, but I don't know how I would find $a$ and $b$ in the first place.

$\endgroup$
  • $\begingroup$ I sincerely doubt that there is any efficient way to do it (more efficient than calculating the decimal representation of the number). $\endgroup$ – barak manos Nov 9 '16 at 5:21
6
$\begingroup$

Figured it out! We first need to find the number of digits of $2^n$, which can be done using logarithms: we need to solve (approximately) $2^n = 10^d$. In the end, the formula for the number of digits $d$ is $d = 1+\left\lfloor n\,\log_{10}2\right\rfloor$. Then, once we have $d$, then we see that if we can solve for $10^{d-k} \cdot t < 2^n < 10^{d-k} \cdot (t + 1)$ (where $k$ is the number of leading digits we want), then $t$ is the number we want. In this specific example, we find that the first three digits are $\lfloor 10 ^ {n \log2 - d + 3}\rfloor = 454$, where $n = 123456789$ and $d$ is calculated as above.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 1. I hope you're aware of the fact that $d$ is not integer. 2. What is $a$? 3. How exactly does that get you the leading digits (and how many of them does it get you)??? $\endgroup$ – barak manos Nov 9 '16 at 5:37
  • $\begingroup$ I was in the process of editing the answer, it is still "under construction" $\endgroup$ – b_pcakes Nov 9 '16 at 5:38
  • $\begingroup$ @barakmanos I edited the answer to be more clear. I hope it is clear why we use that inequality (since we only care about the first $k$ digits). $\endgroup$ – b_pcakes Nov 9 '16 at 5:51
  • $\begingroup$ Sounds to me like you still need to calculate $2^n$ in order to make that comparison. $\endgroup$ – barak manos Nov 9 '16 at 6:00
  • 2
    $\begingroup$ OK, I've verified this with a Python script, very nice!!! I think that you just need to write it down explicitly as $\lfloor{10^{n\log2-\lfloor{n\log2}\rfloor+k-1}}\rfloor$, then accept your own answer. +1 from me, of course... $\endgroup$ – barak manos Nov 9 '16 at 6:49
2
$\begingroup$

$123456789\log_{10} 2=37164196.65735903...$, so $2^{123456789}=10^ {.65735903}\times10^{37164196}$. Looking at $log_{10}d$ for single digit integers $d$, it turns out that $log_{10}4 < .65735903... < \log_{10}5$, so the first digit is $4$. To find more digits, narrow things down further or compute $10^.65735903...$ to as many digits as you need.

| cite | improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.