# Given large $x \in \mathbb{R}$, How to determine if $2^x$ is an integer?

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?

• What are you assuming about the range of x? – hardmath Apr 17 '12 at 17:58
• @hardmath, Which type of assumptions? – Must Apr 17 '12 at 18:34
• 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? – hardmath Apr 17 '12 at 19:29
• Are you looking for a way to know whether $2^x$ is integer without actually evaluating $2^x$? – Paul Apr 17 '12 at 19:32
• 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}$? – Bill Barth Apr 18 '12 at 2:30

(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.

# Proof

## 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}$.

## 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.

• 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. – tel Apr 18 '12 at 22:09
• "is equivalent to testing whether x is an integer": Correct this to be "non-negative integer" – Thomas Eding Apr 20 '12 at 20:07
• @trinithis I changed it – tel Apr 21 '12 at 19:08

Edit
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.

• Hi, I am a little bit confused. Did you wrote $x$ instead of $N$? – Must Apr 17 '12 at 18:38
• Hi Must. I just rephrased my answer for a little more clarity... sorry for the confusion :) – Paul Apr 17 '12 at 19:00
• The problem will be that $N$ is around $2^{2^{500}}$. – Must Apr 17 '12 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}$.

Proof:

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}}.$

• Uh, 2**1.5849625007211563 == 3.0000000000000004. – Andreas Klöckner Apr 20 '12 at 22:50
• @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. – Thomas Eding Apr 21 '12 at 0:32