Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

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?

share|improve this question
    
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
2  
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
show 17 more comments

3 Answers 3

up vote 4 down vote accepted

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

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
2  
The problem will be that $N$ is around $2^{2^{500}}$. –  Must Apr 17 '12 at 19:59
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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