¿Podemos calcular

11

Estoy buscando un algoritmo eficiente para el problema:

Entrada : El entero positivo (almacenado como bits) para algún entero . $3^n$ $n \geq 0$

Salida : el número . $n$

Pregunta : ¿Podemos calcular partir de los bits de en el tiempo ? $n$ $3^n$ $O(n)$

Esta es una pregunta teórica motivada por mi respuesta a una pregunta matemática. ¿ Cómo encontrar una fórmula para esta biyección? . En esta pregunta, el autor quería encontrar una biyección de y los números naturales . Propuse

{2^{n} 3^{m} : n \geq 0 and m \geq 0}

$\{2^n 3^m: n \geq 0 \text{ and } m \geq 0\}$

N = {1, 2, \dots}

$\mathbb{N}=\{1,2,\ldots\}$

2^{m} 3^{n} \mapsto 2^{m} (2 n + 1)

$2^m 3^n \mapsto 2^m(2n+1)$ como solución Otra respuesta afirmaba "no hay una fórmula simple", lo que me hace preguntarme qué tan simple (computacionalmente) es mi solución propuesta.

Con mi solución propuesta, si conocemos y , podemos calcular fácilmente (escribir los dígitos binarios de seguido de seguido de ceros). Esto lleva tiempo . $n$ $m$ $2^m(2n+1)$ $n$ $1$ $m$ $O(n+m)$

$m$ $2^m 3^n$ $3^n$ $O(m)$

$n$ $n$ $3$ $n$ $O(n)$ $O(n^2)$ $O(n^2)$

$3$

ds.algorithms time-complexity Rebecca J. Stones
fuente

2

O (1)

$O(1)$

\log_{2} 3

$\log_2 3$

3

¿El votante puede explicar el voto negativo? No parece una pregunta trivial en absoluto. ¿Cuál es el mejor tiempo de ejecución bajo un modelo de cálculo razonable?

Yuval Filmus

1

O (1)

$O(1)$

Podría estar relacionado de alguna manera con esta pregunta

J.-E.

Ω (n)

$\Omega(n)$

9

El enfoque obvio es:

$\log_2(3^n)$ $\epsilon$ $O(\log\frac{1}{\epsilon})$ $\epsilon$ $1/2$

$\log_2(3)$ $O(\log n)$

(3) Divida la respuesta a (1) por la respuesta a (2) y redondee al número entero más cercano.

Por lo tanto, el primer paso lleva tiempo lineal (en la mayoría de los modelos de cómputo, aunque tal vez no para algunos de baja potencia, como las máquinas de Turing de una sola cabeza ) y los pasos restantes deben ser polilogarítmicos.

David Eppstein
fuente

3

\log_{2} (3)

$\log_2(3)$

t

$t$

O (M (t) \log t)

$O(M(t) \log t)$

M (t) \leq O (t \log t 2^{\log^{*} t})

$M(t) \leq O(t \log t 2^{\log^* t})$

t

$t$

Gracias por la referencia y disculpas por ser demasiado vago para buscarlo yo mismo.

David Eppstein

9

$n>0$ $3^n$ $L = \lceil \log_2(3^n)+1\rceil$

\frac{L - 2}{\log_{2} 3} \leq n \leq \frac{L - 1}{\log_{2} 3} .

$\frac{L-2}{\log_2 3} \le n \le \frac{L-1}{\log_2 3}.$

L \geq 1

$L\ge 1$

3

$3$

L

$L$

n = ⌊ \frac{L - 1}{\log_{2} 3} ⌋ .

$n = \left\lfloor\frac{L-1}{\log_2 3}\right\rfloor.$

Jeffε
fuente

4

$k$ $3^n$ $3^n \bmod 10^k$ $3^n \bmod 5^k$ $3$ $5^k$ $3$ $\varphi(5^k)=5^{k-1} \times 4$

Por lo tanto, al usar el registro discreto y el levantamiento de Hensel, creo que debería poder calcular partir de los dígitos bajos de muy eficiente. En otras palabras, comienza calculando partir del dígito bajo de , tomando el registro discreto de a la base , módulo ; esto revela , y se puede hacer en tiempo. Luego, encuentra el registro discreto de en la base , módulo ; esto revela , y se puede hacer en $n \bmod \varphi(5^k)$ $k$ $3^n$ $n \bmod 4$ $3^n$ $3^n \bmod 5$ $3$ $5$ $n \bmod 4$ $O(1)$ $3^n \bmod 25$ $e$ $25$ $n \bmod 20$ $O(1)$ tiempo (aprovechando el conocimiento de , solo hay posibilidades que tienes que probar). Iterar. En cada paso, utiliza el conocimiento de para ayudarlo a calcular eficientemente el registro discreto de , haciendo uso del hecho de que solo hay valores posibles para . $n \bmod 4$ $5$ $n \bmod \varphi(5^{k-1})$ $3^n \bmod 5^k$ $5$ $n \bmod \varphi(5^k)$

Ahora solo deje que sea lo suficientemente grande, y esto revela . $k$ $n$

Tendrá que determinar si el tiempo de ejecución es , pero me parece que podría ser. Sospecho que es suficiente para dejar que , y sospecho que puede hacer cada iteración en el tiempo , por un total de tiempo . $O(n)$ $k=O(n)$ $O(1)$ $O(n)$

DW
fuente

¿Podemos calcular

Respuestas: