7

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?

Community
  • 1
Must
  • 73
  • 5
  • 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
  • @hardmath,I assumed that $x>2^{500}$ and that the fractional part will be calculated to the minimum needed precision. I will correct my question. – Must Apr 17 '12 at 19:42
  • @Paul, yes. This is what I need. – Must Apr 17 '12 at 19:46
  • @Must Is $x$ always rational? Relatedly, is Paul's condition, that $2^x$ be within $\epsilon$ of some integer sufficient for your needs, or do you need to know if $2^x$ is exactly an integer? – tel Apr 17 '12 at 23:12
  • 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 02:30
  • @BillBarth, I may use floating-point variable in the GNU MPFR Library. $x$ is not an integer. $x$ is the result of computing $\log_2{(\gamma(n))} - k*\log_2{(m)}$ where $n,k,m \in \mathbf{N}$. – Must Apr 18 '12 at 06:32
  • @tel, I don't need to know that $2^x$ is exactly an integer. – Must Apr 18 '12 at 06:38
  • @Must If $x=log_2(γ(n))−k∗log_2(m)$, this would imply that $2^x=m^{-k}\gamma(n)$. How large is $k$ compared to $x$? Also, is $\gamma$ the gamma function? – tel Apr 18 '12 at 09:25
  • @tel, $k$ is small compared with $x$. Yes, its gamma function. – Must Apr 18 '12 at 11:57
  • What is the motivation? – lhf Apr 18 '12 at 13:29
  • @lhf, To check if $\gamma(n) \bmod m^k = 0$ – Must Apr 18 '12 at 14:11
  • @Paul: As a heads up, the question has now been cross-posted at math.SE. (The link in the question also points to math.SE.) The cross-post isn't quite verbatim; they ask slightly different things, but I wanted to give you a heads up. – Geoff Oxberry Apr 18 '12 at 16:46
  • @Must: Can you give the sizes of $n$, $m$, and $k$? Your most recent comment makes this an entirely different question. Also, is $m$ prime? – Bill Barth Apr 18 '12 at 17:01
  • @BillBarth: In the needed case $m=n$, $k<n^{1/2}$ and $m$ is not a prime. – Must Apr 18 '12 at 17:12
  • Wait, if $m=n$ and $\gamma() = \Gamma()$ is the gamma function, then you want to know whether $n! \equiv 0 \mod n^k$, right? This basically means that you need to prime factor $n$ and $n!$. However, for $n$ with about 500 digits, this probably isn't easy unless you know $n$'s prime factorization in advance. – Bill Barth Apr 18 '12 at 18:29
  • @BillBarth, I don't know the prime factorization of $n$. – Must Apr 19 '12 at 07:34
  • I'm no computational number theorist, but given that you don't know very much about $n$, I doubt there's a fast way to answer your true question. What you want seems to require factoring large numbers (there are fast-ish ways to factor $n!$ if you know the prime factors of $n$), and factoring is not possible in polynomial time. CADO-NFS (one GNFS factoring program I found via Google) suggests several months time on one computer to factor a 500-bit number. Is there more you can say about why you want to know whether $n! \equiv 0 \mod n^k$ that might help us find other attacks on the problem? – Bill Barth Apr 19 '12 at 15:06
  • @BillBarth the problem was getting the largest prime factor of $n$, when $n$ has a prime number $p>n^{1/2}$ – Must Apr 19 '12 at 16:02
  • @Must: Yeah, I'm pretty sure that's a computationally hard problem. There is no "fast" way to do it that I know of. – Bill Barth Apr 19 '12 at 19:13

3 Answers3

4

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

Community
  • 1
tel
  • 1,380
  • 12
  • 23
-1

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.

Paul
  • 12,045
  • 7
  • 56
  • 129
-1

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

Thomas Eding
  • 101
  • 3
  • 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 00:32