Encontrar 1000 5-lisa número

Question

Suave números son números naturales que son sólo los pequeños productos de números primos. Tienen algunas aplicaciones en criptografía.

Un número es 5-suave si sus únicos factores primos se $2,3$ o $5$.

Ejemplo:

$$1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, \dots$$

Cosa interesante es que a medida que se hacen más grandes y más grandes, son más escaso y más escaso, con respecto a todos los números naturales...

Tengo 2 problemas estoy luchando con:

1. Encontrar un algoritmo para la búsqueda de $n$-th 5-lisa número. (si es posible, en menos de $\mathcal{O}(n)$)

2. ¿Qué es 1000 5-lisa número?

Agradezco cualquier idea y/o la penetración.

Answer 1

Deje $u_n\ne1$ $n$- th 5-lisa número. Al menos uno de $$ \frac32\,u_n, \frac43\,u_n, \frac65\,u_n $$ es un 5-lisa número mayor que $u_n$. Deje $U_n$ ser el más pequeño de ellos. Entonces $$ u_n<u_{n+1}\le U_n. $$ Compruebe los números de $u_n+1,u_n+2,\dots$ hasta un 5-lisa número. El algoritmo puede hacerse más rápido con los siguientes trucos:

1. Obtener un menor $U_n$, definiéndolo como el más pequeño de 5-lisa número entre $$ \frac32\,u_n, \frac43\,u_n, \frac54\,u_n, \frac65\,u_n, \frac98\,u_n,\frac{16}{15}\,u_n,\frac{25}{24}\,u_n,\frac{27}{25}\,u_n,\frac{81}{80}\,u_n,\dots $$ Cada fracción es el cociente de dos coprime consecutivos 5-suave números.
2. Para comprobar si un número es 5-lisa, no factorizar. Compruebe si sus únicos factores primos son $2$, $3$ y $5$. Esto se puede hacer de manera eficiente por la repetida división.

Yo he programado esta en Mathematica y tengo que $$ u_{1000}=51200000=2^{14}5^5. $$

Answer 2

A menos que me haya perdido algo, Julián algoritmo simplemente comprobar todos los números del 1, 2, 3, ... hasta que encuentra el 1000 5-lisa número. Esto significa que se requiere de $O(u_n)$ del tiempo.

Un algoritmo más eficiente es la siguiente. Deje $N$ ser grande, y definir $S_2$, $S_3$ y $S_5$ s de la siguiente manera.

$S_2 = \cup_{i=0}^{\infty} \{2^i\} \cap \{1, 2, \ldots, N\}$

$S_3 = \cup_{i=0}^{\infty} \{3^i s | s \in S_2\} \cap \{1, 2, \ldots, N\}$

$S_5 = \cup_{i=0}^{\infty} \{5^i s | s \in S_3\} \cap \{1, 2, \ldots, N\}$

Si $N$ elegido es lo suficientemente grande como para que $|S_5|>1000$, entonces podemos fácilmente encontrar $u_{1000}$. Creo (no de prueba) que $|S_2| = O(\log{N})$ ,$|S_3|=O(\log^2 N)$, y $|S_5|=O(\log^3 N)$, lo que conduce a un polinomio de tiempo del algoritmo para el problema, siempre y cuando elijamos $N$ lo suficientemente grande. También creo que podemos optar $N \approx e^{n^\frac{1}{3}}$ con el fin de obtener $|S_5|>n$, pero no he probado todavía...

Answer 3

Cada $5$-lisa número es de la forma $2^x3^y5^z$. Vamos a llamar a la $1000$th uno $M$. Eso significa que hay un $1000$ número entero no negativo soluciones a $$2^x3^y5^z<M$$ This is the same as having $1000$ nonnegative integer solutions to $$\log(2)x+\log(3)y+\log(5)z<\log(M)$$

There are approximately as many nonnegative integer solutions as the volume of the tetrahedron that this linear inequality defines: $\frac{1}{6}\frac{(\log(M))^3}{\log(2)\log(3)\log(5)}$. So we can immediately zoom in on the order of magnitude of $M$ by solving $$\begin{align} \frac{1}{6}\frac{(\log(M))^3}{\log(2)\log(3)\log(5)} &\approx1000\\ \implies M &\approx \exp\left(\sqrt[3]{6000\log(2)\log(3)\log(5)}\right)\approx 278817463=:\tilde{M} \end{align}$$

Now define $S_0=\{1\}$. Since each $5$-smooth number will yield three more through multiplication by $2$, $3$, and $5$, generate more $5$-suave números de esta manera. Tenemos $S_1=\{2,3,5\}$. Y, a continuación,$S_2=\{4,6,10,6,9,15,10,15,25\}$, lo que nos apartan hacia abajo a $\{4,6,10,9,15,25\}$.

Mantener la creación de estos $S_i$, sacrificio de animales fuera de los duplicados y también sacrificio de distancia de cualquier resultado que se llevará demasiado lejos más allá de nuestro estadio para $\tilde{M}$. Por ejemplo, si usted llega a $2\tilde{M}$, arrojan que el número.

Finalmente, se le han agotado sus opciones (después de $\log_2(2\tilde{M})\approx28$ iteraciones). Esto te dejará con una colección de $S=S_0\cup S_1\cup \cdots S_n$ de todas las $5$-suave números de menos de $2\tilde{M}$, de la cual no debería ser $K>1000$. Aplicar un algoritmo de ordenación (en el peor de los ${\cal O}(K\log(K))$, pero probablemente la más rápida, ya que hay algunos naturales pedido ya a partir de este proceso) y usted puede elegir el $1000$th plazo.

Nota: podría ser más rápido para conseguir $S$ sólo para iterar a través de él como

for i = 0..log_2(2M)
  for j = 0..log_3(2M/2^i)
    for k = 0..log_5(2M/2^i/3^j)
       append 2^i*3^j*5^k to S