# How many significant figures are needed in base 2?

$x \in \mathbb{R}$

$2^{500}<x<2^{501}$

How many significant figures are needed in base 2, to know in high approximation whether $2^x$ is integer?

-
What does it mean to "know in high approximation whether $2^x$ is integer"? Whether $2^x$ is integer is either true or false, and supposing you don't consider "true" to be a high approximation of "false" or vice versa, you need to know exactly. Also, unless you know $x$ exactly (or you know for instance that $x$ is integer), you will never be able to tell for sure that $2^x$ is integer. –  Marc van Leeuwen Apr 18 '12 at 9:48
@MarcvanLeeuwen, I mean that $\exists n \in \mathbb{N}, 2^x - 2^{-500}<n<2^x + 2^{-500}$ –  Must Apr 18 '12 at 10:51
What is the motivation? –  lhf Apr 18 '12 at 13:30
@lhf, To know how many bit I will need to calculate of x. –  Must Apr 18 '12 at 14:57
Question is very close to a cross-post on scicomp.SE. –  Geoff Oxberry Apr 18 '12 at 16:48

Basically you want to estimate the $\delta$ such that $2^{x+\delta} - 2^x = 1$. This means $2^\delta = 1+\dfrac{1}{2^x}$, so that $\delta$ might be estimated as $\dfrac{1}{2^x \times \ln2}$, or, taking the upper bound for $x$, $\delta$ might be estimated as $\dfrac{1}{2^{501} \times \ln2}$.

The number of required significant digits (after the decimal point) is about $-\log_{10}\delta = \log_{10}(2^{501}) + \log_{10}\ln2$, which is about 151, plus-minus a digit. Or, if you're working in base 2, the number of required significant digits is about $-\log_{2}\delta = \log_{2}(2^{501}) + \log_{2}\ln2$, which is about 502.

Given such a number of digits after the decimal point, changing the remaining digits won't change $2^x$ by more than $1$, so that, if $2^x$ is an integer, you can say what integer it is.

However, it is impossible to tell for sure whether $2^x$ is an integer, given only its rounded value, independent of the accuracy, as adding a small value beyond the accuracy limits to $x$ will turn $2^x$ from integer to non-integer and vice versa.

-
$\drfac{x}{y}$ doesn't seem to work... –  penartur Apr 18 '12 at 9:01
Of course that \drfac would not work, but I was hoping that the obvious typo will be obvious to you as well (at least now when I re-read my comment and notice that typo). –  Asaf Karagila Apr 18 '12 at 9:16
You might want to consider using \dfrac instead of \frac because that would make the fraction somewhat more readable. –  Asaf Karagila Apr 18 '12 at 9:17
I'm just not a TeX expert :) –  penartur Apr 18 '12 at 11:56
$\dfrac{1}{2^x \times \ln2} \neq \dfrac{1}{2^{501} \times \ln2}$ –  Must Apr 20 '12 at 11:04

For $2^x$ to be an integer where x has a finite decimal representation, x must also be an integer. Am I missing something here?

-
This is not correct... any positive integer has a logarithm to the base 2, which need not be an integer. –  Ted Apr 18 '12 at 8:53
Yes, but it will in general be an irrational number and you will not be able to distinguish it from a rational number in a finite decimal representation. –  Wonder Apr 18 '12 at 8:56
+1: @Wonder should edit his post to reflect the finite representation problem. –  Bill Barth Apr 18 '12 at 17:00
Ok I edited it accordingly. –  Wonder Apr 18 '12 at 17:48