Given large $x \in \mathbb{R}$, I want to know whether or not $2^x$ is an integer. Is there any fast way to answer the question for $x>2^{500}$?

I have also asked a slightly different form of this question on math.se: How many significant figures are needed in base 2?

  • $\begingroup$ What are you assuming about the range of x? $\endgroup$
    – hardmath
    Apr 17, 2012 at 17:58
  • $\begingroup$ @hardmath, Which type of assumptions? $\endgroup$
    – Must
    Apr 17, 2012 at 18:34
  • $\begingroup$ Does "500 bits" represent the integer part of $x$? The fractional part? Both parts combined? Is the value of $x$ only known to this precision, or are you asking about a value of $x$ which is either known exactly or to such arbitrary precision as an algorithm may require? $\endgroup$
    – hardmath
    Apr 17, 2012 at 19:29
  • $\begingroup$ Are you looking for a way to know whether $2^x$ is integer without actually evaluating $2^x$? $\endgroup$
    – Paul
    Apr 17, 2012 at 19:32
  • 2
    $\begingroup$ If $x \in \mathbb{R}$, how do you plan to represent it on a computer? I think that tel's question about whether $x$ is rational is telling. If it's really true that $x \in \mathbb{R}$ then you must be contemplating a computer algebra system of some sort, otherwise you must know enough to know whether $x$ itself is an integer or not. Can you say more about where $x$ comes from so that we can understand why you don't know instantly whether it is computable that $2^x \in \mathbb{N}$? $\endgroup$
    – Bill Barth
    Apr 18, 2012 at 2:30

3 Answers 3


(This is a partial response to OP's question that covers the case where $x$ is rational and is not being used to approximate an irrational number)

If $x\in\mathbb{Q}$, testing whether $2^x$ is an integer is equivalent to testing whether $x$ is a non-negative integer.


proposition 1

Given $Log_2(y)=x$ where $x\in\mathbb{Q}$, if $y$ is a positive integer there must be some $c$ such that $2^m=y^n=c$ and $x=\frac{m}{n}$ where $m,n\in\mathbb{N}$.

(see comments of this answer for the proof)

proposition 2

If $y>2$, and $m,n, y\in\mathbb{N}$, if $2^m=y^n$ then $m$ must equal $ni$ where $i$ is some integer.

Consider the set of prime factors of $2^m$. In order for $2^m$ to have an integer $n^{th}$ root, the set of prime factors must be able to be split into $n$ identical subsets. Since the prime factors are a set of $m$ twos, this condition can only be fulfilled if $m=ni$ where $i\in\mathbb{N}$.

putting it together

Taken together, propositions 1 and 2 imply that if $2^x\in\mathbb{N}$ then $x=\frac{m}{n}=\frac{ni}{n}=\{i|i\in\mathbb{N}\}$. It is taken as obvious that if $x\in\mathbb{N}$ then $2^x\in\mathbb{N}$. Therefore, $2^x\in\mathbb{N}\Longleftrightarrow x\in\mathbb{N}$.

In theory this would mean that all you need to do is test whether the fractional part of $x=0$. Of course, OP's application skirts this proof by virtue of the fact that his test is not that $2^x\in\mathbb{N}$ but rather that $2^x$ should be arbitrarily close to some positive integer.

  • $\begingroup$ I'm no mathematician, so it's likely that my proof is full of holes. If anyone spots something, put it in the comments and I'll fix it. $\endgroup$
    – tel
    Apr 18, 2012 at 22:09
  • $\begingroup$ "is equivalent to testing whether x is an integer": Correct this to be "non-negative integer" $\endgroup$ Apr 20, 2012 at 20:07
  • $\begingroup$ @trinithis I changed it $\endgroup$
    – tel
    Apr 21, 2012 at 19:08

You can determine if $2^x$ is integer by checking how close $x$ is to the log of an integer. If $|x-log_2(N)|<\epsilon$ for some small $\epsilon$ for some integer N, then we can say that $2^x$ is approximately an integer. You can use a taylor expansion of $log_2(x)$ to evaluate it.

The tricky part is knowing which integer N has a log closest to x.

  • $\begingroup$ Hi, I am a little bit confused. Did you wrote $x$ instead of $N$? $\endgroup$
    – Must
    Apr 17, 2012 at 18:38
  • $\begingroup$ Hi Must. I just rephrased my answer for a little more clarity... sorry for the confusion :) $\endgroup$
    – Paul
    Apr 17, 2012 at 19:00
  • 2
    $\begingroup$ The problem will be that $N$ is around $2^{2^{500}}$. $\endgroup$
    – Must
    Apr 17, 2012 at 19:59

You just need to check that $x \in \mathbb Z_{\ge 0}$ given $x \in \mathbb{Q}$.

In the following, let

  • $\mathbb{I} = \mathbb{R}\setminus\mathbb{Q}$
  • $E(n) \iff n$ is even

Lemma 1: $n \in \mathbb{Z_{\ge 2}} \implies 2^{1/n} \in \mathbb{I}$.


Case $n = 2$: $\sqrt{2} \in \mathbb{I}$ is a well-known fact.

Case $n \gt 2$: Proof is similar to the $\sqrt{2} \in \mathbb{I}$ found in Euclid's Elements. Suppose for a contradiction that $2^{1/n} \in \mathbb{Q}$. Then by definition, $2^{1/n} = a/b$, where $a$ and $b$ are coprime. Then $2 = (a/b)^n = a^n/b^n \implies 2b^n = a^n \implies E(a^n) \implies E(a) \implies a = 2k, k \in \mathbb{Z} \implies 2b^n = (2k)^n = 2^nk^n \implies b^n = 2^{n-1}k^n \implies E(b^n) \because 2 \mid 2^{n-1} \because n \ge 2 \implies E(b) \implies b = 2l, l \in \mathbb{Z}$. But since $2 \mid a$ and $2 \mid b$, $a$ and $b$ are not coprime $\implies$ contradiction.

Lemma 2: If $x \in \mathbb{Q} \cap (0,1)$ then $2^x \in \mathbb{I}.$

Proof: Note that $2^0=1$ and $2^1 = 2$. Since $f(x) = 2^x$ is strictly monotonic, it follows that $0<x<1 \implies f(0) < f(x) < f(1)$. But this is the same as saying $1 < f(x) < 2$. Thus $f(x) \notin \mathbb{Z}$ because there are no integers between $1$ and $2$. Since $x \in \mathbb{Q}, x = a/b$, where $a \in \mathbb{z}$ and $b \in \mathbb{Z}$. But $b > 1 \because f(x) \notin \mathbb{Z}$. Thus $2^x = 2^{a/b} = 2^{a(1/b)} = 2^{(1/b)a} = (2^{1/b})^a = w^a, w \in \mathbb{I}$ by lemma 1. Since $a < b \because x \in (0,1), w^a \in \mathbb{I} \because $ [fuck it, i'm stuck w/e'vs].

Theorem: If $x \in \mathbb{Q}$ then $2^x \in \mathbb{Z} \iff x \in \mathbb{Z_{\ge 0}}.$

Proof: Let $x \in \mathbb{Q}$.

Case $x < 0$: $2^x \notin \mathbb{Z}$ because $0 < 2^x < 1$ by exponential properties.

Case $x \ge 0$: By rules of exponentiation, $2^x = 2^{n + \epsilon} = 2^n2^\epsilon, n \in \mathbb{Z_{\ge 0}}$ and $ \epsilon \in [0, 1).$ By lemma 2 and $2^0 = 1$, $2^\epsilon \in \mathbb{Z} \iff \epsilon = 0.$ Hence $2^n2^\epsilon \in \mathbb{Z} \iff \epsilon = 0$ because $2^n \in \mathbb{Z}$ and $2^0 = 1$. Since $x = n+\epsilon$ by definition, it follows that $2^x \in \mathbb{Z} \iff x \in \mathbb{Z_{\ge 0}}.$

  • $\begingroup$ Uh, 2**1.5849625007211563 == 3.0000000000000004. $\endgroup$ Apr 20, 2012 at 22:50
  • $\begingroup$ @Andreas: Oh, right, $2^\epsilon$ can be in $\mathbb {Q}$. I changed my hypothesis and altered my proof. Now it states the same as tel's answer does, but it proves it in a different way. If anyone see's flaws in my proof, let me know. $\endgroup$ Apr 21, 2012 at 0:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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