<p>The obvious approach is:</p>

<p>(1) Compute an approximation to $\log_2(3^n)$. You can approximate it to within an additive error of 1 by counting the number of bits in the given binary representation, and to within an additive error of $\epsilon$ by additionally looking at the top $O(\log\frac{1}{\epsilon})$ bits of the input. It should suffice to choose a constant value of $\epsilon$, so that (after combining with the error in step (2)) the final result ends up within an additive error of $1/2$ of correct.</p>

<p>(2) Compute an approximation to $\log_2(3)$. I'm not familiar with the algorithms for this but I expect they take time polynomial in the number of bits of precision you need, and you only need $O(\log n)$ bits of precision.</p>

<p>(3) Divide the answer to (1) by the answer to (2), and round to the nearest integer.</p>

<p>So the first step takes linear time (in most models of computation although maybe not for some underpowered ones like <a href="https://cstheory.stackexchange.com/questions/18980/computing-input-length-on-a-one-tape-turing-machine">single-head Turing machines</a>) and the remaining steps should be polylogarithmic.</p>

CC BY-SA 3.0
2013-09-18T01:20:43.080Z
I believe that computing $\log_2(3)$ to $t$ bits of precision takes time $O(M(t) \log t)$, where $M(t) \leq O(t \log t 2^{\log^* t})$ is the time to multiply $t$-bit numbers.  See Brent--Zimmermann, http://www.loria.fr/~zimmerma/mca/pub226.html
Ryan O'Donnell
CC BY-SA 3.0
2013-09-18T05:41:48.997Z
Thanks for the reference, and apologies for being too lazy to look it up myself.
David Eppstein
CC BY-SA 3.0
2013-09-13T21:08:19.653Z
2013-09-13T22:17:33.807Z
2017-04-13T12:32:28.167Z
David Eppstein
<p>For any integer $n&gt;0$, writing $3^n$ in binary requires exactly $L = \lceil \log_2(3^n)+1\rceil$ bits.  Some elementary algebra implies that
$$
\frac{L-2}{\log_2 3} \le n \le \frac{L-1}{\log_2 3}.
$$
For any bit length $L\ge 1$, there is at most one integer in this range.  Thus, given an integral power of $3$ that is $L$ bits long, the exponent must be the integer
$$
n = \left\lfloor\frac{L-1}{\log_2 3}\right\rfloor.
$$</p>

CC BY-SA 3.0
2013-09-13T22:42:20.327Z
2013-09-13T22:42:20.327Z
Jeffε
<p>Here is another approach.  Given the low $k$ digits of $3^n$, you can learn $3^n \bmod 10^k$ and thus $3^n \bmod 5^k$.  It looks like $3$ is a generator modulo $5^k$ (i.e., $3$ has order $\varphi(5^k)=5^{k-1} \times 4$).</p>

<p>Therefore, by using discrete log and Hensel lifting, I think you should be able to compute $n \bmod \varphi(5^k)$ from the low $k$ digits of $3^n$ very efficiently.  In other words, you start by computing $n \bmod 4$ from the low digit of $3^n$, by taking the discrete log of $3^n \bmod 5$ to the base $3$, modulo $5$; this reveals $n \bmod 4$, and can be done in $O(1)$ time.  Then, you find the discrete log of $3^n \bmod 25$ to the base $e$, modulo $25$; this reveals $n \bmod 20$, and can be done in $O(1)$ time (taking advantage of the knowledge of $n \bmod 4$, there are only $5$ possibilities you have to try).  Iterate.  At each step, you use the knowledge of $n \bmod \varphi(5^{k-1})$ to help you efficiently compute the discrete log of $3^n \bmod 5^k$, making use of the fact that there are only $5$ possible values for $n \bmod \varphi(5^k)$.</p>

<p>Now just let $k$ be large enough, and this reveals $n$.</p>

<p>You'll need to work out whether the running time is $O(n)$, but it looks to me like it might be.  I suspect it's enough to let $k=O(n)$, and I suspect you can do each iteration in $O(1)$ time, for a total of $O(n)$ time.</p>

CC BY-SA 3.0
2013-09-13T23:11:27.703Z
2013-09-13T23:11:27.703Z
D.W.
<p>I'm seeking an efficient algorithm for the problem:</p>
<blockquote>
<p><em>Input</em>: The positive integer <span class="math-container">$3^n$</span> (stored as bits) for some integer <span class="math-container">$n \geq 0$</span>.</p>
<p><em>Output</em>: The number <span class="math-container">$n$</span>.</p>
</blockquote>
<p><em>Question</em>: Can we compute <span class="math-container">$n$</span> from the bits of <span class="math-container">$3^n$</span> in <span class="math-container">$O(n)$</span> time?</p>
<hr />
<p>This is a theoretical question motivated by <a href="https://math.stackexchange.com/a/492655/91818">my answer</a> to a math.SE question <a href="https://math.stackexchange.com/q/492616/91818">How to find a formula for this bijection?</a>.  In this question, the author wanted to find a bijection from <span class="math-container">$$\{2^n 3^m: n \geq 0 \text{ and } m \geq 0\}$$</span> and the natural numbers <span class="math-container">$\mathbb{N}=\{1,2,\ldots\}$</span>.  I proposed <span class="math-container">$$2^m 3^n \mapsto 2^m(2n+1)$$</span> as a solution.  Another answer there asserted &quot;there is no simple formula&quot;, which makes me wonder how (computationally) simple my proposed solution is.</p>
<p>With my proposed solution, if we know <span class="math-container">$n$</span> and <span class="math-container">$m$</span>, we can easily compute <span class="math-container">$2^m(2n+1)$</span> (write the binary digits of <span class="math-container">$n$</span> followed by <span class="math-container">$1$</span> followed by <span class="math-container">$m$</span> zeroes).  This takes <span class="math-container">$O(n+m)$</span> time.</p>
<p>Finding <span class="math-container">$m$</span> from the bits of <span class="math-container">$2^m 3^n$</span> amounts to finding the least significant bit (which can be computed by counting right bit shifts, leaving <span class="math-container">$3^n$</span> in memory).  This takes <span class="math-container">$O(m)$</span> time.</p>
<p>However, we also need to find <span class="math-container">$n$</span>, which might be more difficult.  It would be possible to find <span class="math-container">$n$</span> by repeatedly dividing by <span class="math-container">$3$</span>, but this seems wasteful.  It requires <span class="math-container">$n$</span> division operations, each of which will take <span class="math-container">$O(n)$</span> time, so this is <span class="math-container">$O(n^2)$</span> time in total.  [Actually, the after each iteration, the number of digits will decrease linearly, but this still results in <span class="math-container">$O(n^2)$</span> time.]</p>
<p>It seems like we should be able to exploit knowing the input is a power of <span class="math-container">$3$</span>.</p>

CC BY-SA 3.0
2013-09-13T17:37:00.737Z
What is your exact model of computations? What operations are allowed in $O(1)$ time? (If we could do arithmetic with numbers such as $\log_2 3$ it would be quite useful...)
Yuval Filmus
CC BY-SA 3.0
2013-09-13T17:40:28.283Z
Can the downvoter explain the downvote? It doesn't seem like a trivial question at all. What is the best running time under some reasonable computation model?
Yuval Filmus
CC BY-SA 3.0
2013-09-13T17:56:34.890Z
I'm imagining tapes with 0's, 1's and empty cells (with an infinite number of tapes).  I want single bit toggling and left/right shifting operations to run in $O(1)$ time.  (If we have a marker the 0-th bit on an infinite tape, then left/right shifting is achieved by shifting the marker).  Unlike a Turing machine, I don't want it to take any time to move a pointer.  So "toggle the 0-th bit" takes the same time as "toggle the 124126-th bit".
Rebecca J. Stones
CC BY-SA 3.0
2013-09-13T20:45:58.293Z
It might be somehow related to this [question](http://math.stackexchange.com/questions/61209/what-algorithm-is-used-by-computers-to-calculate-logarithms)
J.-E. Pin
CC BY-SA 3.0
2013-09-13T23:07:38.763Z
Is the lower bound of $\Omega(n)$ obvious?
Boris Bukh
<ds.algorithms><time-complexity>
Can we compute $n$ from the bits of $3^n$ in $O(n)$ time?
Rebecca J. Stones
# Can we compute $n$ from the bits of $3^n$ in $O(n)$ time?

(Asked by: username_0 on 2013-09-13)

I'm seeking an efficient algorithm for the problem:

> *Input*: The positive integer $3^n$ (stored as bits) for some integer $n \geq 0$.
>
> *Output*: The number $n$.

*Question*: Can we compute $n$ from the bits of $3^n$ in $O(n)$ time?

---

This is a theoretical question motivated by [my answer](https://math.stackexchange.com/a/492655/91818) to a math.SE question [How to find a formula for this bijection?](https://math.stackexchange.com/q/492616/91818). In this question, the author wanted to find a bijection from $$\{2^n 3^m: n \geq 0 \text{ and } m \geq 0\}$$ and the natural numbers $\mathbb{N}=\{1,2,\ldots\}$. I proposed $$2^m 3^n \mapsto 2^m(2n+1)$$ as a solution. Another answer there asserted "there is no simple formula", which makes me wonder how (computationally) simple my proposed solution is.

With my proposed solution, if we know $n$ and $m$, we can easily compute $2^m(2n+1)$ (write the binary digits of $n$ followed by $1$ followed by $m$ zeroes). This takes $O(n+m)$ time.

Finding $m$ from the bits of $2^m 3^n$ amounts to finding the least significant bit (which can be computed by counting right bit shifts, leaving $3^n$ in memory). This takes $O(m)$ time.

However, we also need to find $n$, which might be more difficult. It would be possible to find $n$ by repeatedly dividing by $3$, but this seems wasteful. It requires $n$ division operations, each of which will take $O(n)$ time, so this is $O(n^2)$ time in total. [Actually, the after each iteration, the number of digits will decrease linearly, but this still results in $O(n^2)$ time.]

It seems like we should be able to exploit knowing the input is a power of $3$.

**Tags:** ds.algorithms, time-complexity

> **Comments:**
> **username_1**: What is your exact model of computations? What operations are allowed in $O(1)$ time? (If we could do arithmetic with numbers such as $\log_2 3$ it would be quite useful...)  
> **username_1**: Can the downvoter explain the downvote? It doesn't seem like a trivial question at all. What is the best running time under some reasonable computation model?  
> **username_0**: I'm imagining tapes with 0's, 1's and empty cells (with an infinite number of tapes).  I want single bit toggling and left/right shifting operations to run in $O(1)$ time.  (If we have a marker the 0-th bit on an infinite tape, then left/right shifting is achieved by shifting the marker).  Unlike a Turing machine, I don't want it to take any time to move a pointer.  So "toggle the 0-th bit" takes the same time as "toggle the 124126-th bit".  
> **username_2**: It might be somehow related to this [question](http://math.stackexchange.com/questions/61209/what-algorithm-is-used-by-computers-to-calculate-logarithms)  
> **username_3**: Is the lower bound of $\Omega(n)$ obvious?  

---

## 3 answers

### Answer by username_4 on 2013-09-13. Score: 13

The obvious approach is:

(1) Compute an approximation to $\log\_2(3^n)$. You can approximate it to within an additive error of 1 by counting the number of bits in the given binary representation, and to within an additive error of $\epsilon$ by additionally looking at the top $O(\log\frac{1}{\epsilon})$ bits of the input. It should suffice to choose a constant value of $\epsilon$, so that (after combining with the error in step (2)) the final result ends up within an additive error of $1/2$ of correct.

(2) Compute an approximation to $\log\_2(3)$. I'm not familiar with the algorithms for this but I expect they take time polynomial in the number of bits of precision you need, and you only need $O(\log n)$ bits of precision.

(3) Divide the answer to (1) by the answer to (2), and round to the nearest integer.

So the first step takes linear time (in most models of computation although maybe not for some underpowered ones like [single-head Turing machines](https://cstheory.stackexchange.com/questions/18980/computing-input-length-on-a-one-tape-turing-machine)) and the remaining steps should be polylogarithmic.

> **Comments:**
> **username_5**: I believe that computing $\log_2(3)$ to $t$ bits of precision takes time $O(M(t) \log t)$, where $M(t) \leq O(t \log t 2^{\log^* t})$ is the time to multiply $t$-bit numbers.  See Brent--Zimmermann, http://www.loria.fr/~zimmerma/mca/pub226.html  
> **username_4**: Thanks for the reference, and apologies for being too lazy to look it up myself.  

---

### Answer by username_6 on 2013-09-13. Score: 12

For any integer $n>0$, writing $3^n$ in binary requires exactly $L = \lceil \log\_2(3^n)+1\rceil$ bits. Some elementary algebra implies that
$$
\frac{L-2}{\log\_2 3} \le n \le \frac{L-1}{\log\_2 3}.
$$
For any bit length $L\ge 1$, there is at most one integer in this range. Thus, given an integral power of $3$ that is $L$ bits long, the exponent must be the integer
$$
n = \left\lfloor\frac{L-1}{\log\_2 3}\right\rfloor.
$$


---

### Answer by username_7 on 2013-09-13. Score: 8

Here is another approach. Given the low $k$ digits of $3^n$, you can learn $3^n \bmod 10^k$ and thus $3^n \bmod 5^k$. It looks like $3$ is a generator modulo $5^k$ (i.e., $3$ has order $\varphi(5^k)=5^{k-1} \times 4$).

Therefore, by using discrete log and Hensel lifting, I think you should be able to compute $n \bmod \varphi(5^k)$ from the low $k$ digits of $3^n$ very efficiently. In other words, you start by computing $n \bmod 4$ from the low digit of $3^n$, by taking the discrete log of $3^n \bmod 5$ to the base $3$, modulo $5$; this reveals $n \bmod 4$, and can be done in $O(1)$ time. Then, you find the discrete log of $3^n \bmod 25$ to the base $e$, modulo $25$; this reveals $n \bmod 20$, and can be done in $O(1)$ time (taking advantage of the knowledge of $n \bmod 4$, there are only $5$ possibilities you have to try). Iterate. At each step, you use the knowledge of $n \bmod \varphi(5^{k-1})$ to help you efficiently compute the discrete log of $3^n \bmod 5^k$, making use of the fact that there are only $5$ possible values for $n \bmod \varphi(5^k)$.

Now just let $k$ be large enough, and this reveals $n$.

You'll need to work out whether the running time is $O(n)$, but it looks to me like it might be. I suspect it's enough to let $k=O(n)$, and I suspect you can do each iteration in $O(1)$ time, for a total of $O(n)$ time.


---

