Dado $N$, encontramos a $ab = N$ $a$ $b$ tan cerca como sea posible

Question

Dado un número $N$ me gustaría factor como $N=ab$ donde $a$ $b$ están tan cerca como sea posible; decir al $|b-a|$ es mínima. Por cierto $N$ esto es trivial: cuando $N$ es primo, un producto de dos primos, un cuadrado perfecto, o uno menos que un cuadrado perfecto, por ejemplo.

Pero en general parece complicado. Un montón de evidente primeros pasos no funcionan. Por ejemplo, es tentador suponer que al $N=k^2M$, podemos encontrar $a_M\cdot b_M = M$, y la solución óptima para$N$$ka_M\cdot kb_M$. Pero este es bastante malo; un contraejemplo es $N=20$. Hay divide y vencerás tácticas de este tipo que hacen el trabajo?

Una obvia algoritmo para encontrar el óptimo $a$ $b$ podría empezar por calcular el $s=\left\lfloor\sqrt N\right\rfloor$, lo que se puede hacer de manera eficiente y, a continuación, trabajando su camino hacia abajo de $s$ buscando un factor de $N$ por la prueba de la división, que es lento. Hay un algoritmo más eficiente?

A mí me parece que, incluso si la factorización completa de $N$ es conocido, la partición de los factores en dos conjuntos cuyos productos están tan cerca como sea posible será del tipo NP-completo; es similar a el subconjunto de suma problema, por ejemplo.

Answer 1

Tienes razón es el problema de la mochila. Si el factor de $N=\prod_i p_i^{a_i}$ y llevará el registro, consiga $\log N = \sum_i a_i \log p_i$. Ahora usted está buscando para llenar una mochila de tamaño $\frac 12 \log N$ tan completa como sea posible con las cosas de tamaño $\log p_i$ (y un límite de la cantidad de cada uno), pero sin pasarse.

Answer 2

Hay algunas mejoras modestas uno puede hacer a través de la división de juicios, al menos cuando se $N$ es impar. Ciertamente no es suficiente para hacer de este competitivo con los modernos métodos de factorización y la mochila de los algoritmos en la mayoría de los casos, pero aún mejor que la prueba de la división.

Consulte las secciones "de Fermat y el juicio de la división" y "Tamiz de mejora" en el artículo de la Wikipedia sobre la factorización de Fermat; en el caso de los impares $N$, $N = ab$ con $a$ $b$ juntos es equivalente a $N=A^2 -B^2$ $B$ tan pequeño como sea posible.

Answer 3

Este es un problema difícil en general, ya que el factoring es ya un problema difícil. Aunque tal vez usted está asumiendo que $N$'s de la factorización de la que ya se conoce? Parece que no, ya que das un algoritmo que no haga uso de su factorización.

Dado $N=p_1^{a_1}p_2^{a^2}\cdots p_k^{a^k}$ cuando la $p_i$ es de los primeros, que desea particionar este conjunto múltiple en multisets $S$ $T$ de manera tal que sus respectivos productos están tan cerca como sea posible. Voy a suponer que este es NP-Duro, ya que es bastante similar al de la mochila problema (http://en.wikipedia.org/wiki/Knapsack_problem)