2
$\begingroup$

$x \in \mathbb{R}$

$2^{500}

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

  • 0
    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.2012-04-18
  • 0
    @MarcvanLeeuwen, I mean that $\exists n \in \mathbb{N}, 2^x - 2^{-500}2012-04-18
  • 0
    What is the motivation?2012-04-18
  • 0
    @lhf, To know how many bit I will need to calculate of x.2012-04-18
  • 1
    Question is very close to a cross-post on [scicomp.SE](http://scicomp.stackexchange.com/q/1950/276).2012-04-18
  • 0
    @GeoffOxberry, do I have to delete one of the questions?2012-04-18
  • 0
    @Must: I don't know yet. Let me consult with the math mods.2012-04-18
  • 0
    @Geoff: the questions are very similar, but I think we have the better answer here right now. I am not sure if we need to migrate. But if you feel the need, I would prefer if you migrate it if this one is the main one.2012-04-25

2 Answers 2

5

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.

  • 0
    $\drfac{x}{y}$ doesn't seem to work...2012-04-18
  • 0
    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).2012-04-18
  • 0
    You might want to consider using `\dfrac` instead of `\frac` because that would make the fraction somewhat more readable.2012-04-18
  • 0
    I'm just not a TeX expert :)2012-04-18
  • 0
    $\dfrac{1}{2^x \times \ln2} \neq \dfrac{1}{2^{501} \times \ln2}$2012-04-20
  • 0
    $2^{500}2012-04-20
  • 0
    @Must The task is to estimate the number of digits. $\dfrac{1}{2^{501}\times\ln 2} \leq \dfrac{1}{2^x\times\ln 2}$.2012-04-20
  • 0
    @penartur: the upper bound for $x$ should equal $2^{501}$, not $501$2012-04-21
-1

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?

  • 3
    This is not correct... any positive integer has a logarithm to the base 2, which need not be an integer.2012-04-18
  • 0
    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.2012-04-18
  • 0
    +1: @Wonder should edit his post to reflect the finite representation problem.2012-04-18
  • 0
    Ok I edited it accordingly.2012-04-18