Números altamente compuestos (3)

Encontrar sin ver

La hoja de cálculo tiene una precisión limitada en el cálculo con enteros, pero para encontrar números altamente compuestos no es necesario ver su desarrollo en el sistema de numeración decimal, pues basta poder dar los exponentes correspondientes de 2, 3, 5, 7, 11, 13,…(ver entradas anteriores) Así podemos estar seguros de haber encontrado un NAC aunque no lo veamos escrito, sólo leyendo los exponentes.

Hemos preparado una herramienta siguiendo las ideas contenidas en el documento http://wwwhomes.uni-bielefeld.de/achim/julianmanuscript3.pdf de D. B. Siano and J. D. Siano - Oct. 7, 1994

La idea consiste en manejar tan sólo las potencias del tipo

Para cada juego de exponentes tendremos en cuenta los siguientes hechos:

(a) El número 2N tiene más divisores que N, luego si tenemos un N altamente compuesto, para encontrar el siguiente partiremos de ese valor 2N hacia abajo, números cada vez más pequeños hasta llegar a N. Uno de ellos será el mínimo que cumpla el tener más divisores que N.

(b) Ramanujan descubrió una desigualdad doble para los exponentes de 2, 3, 5, 7,…en un NAC, que nos da el mínimo y máximo valor que han de tener estos en el desarrollo. Si llamamos aq al exponente con el que figura el número primo q en ese desarrollo, se cumple que

En la desigualdad p representa el último número primo del desarrollo y p+ el siguiente primo después de él.

Podemos recorrer todas las combinaciones posibles  entre estas cotas para descubrir el próximo NAC a partir de un juego de exponentes dado. Necesitaremos efectuar cuatro comparaciones:

•  Con 2N y exigir que el número encontrado sea menor o igual
•  Con N y exigir que sea mayor
•  Con el anterior candidato  para ver si es menor 
•  Sus divisores han de compararse con los de N y presentar mayor número

No daremos excesivos detalles, pero la idea es la de comparar los exponentes de cada candidato con los de N y llamar exceso al número formado por aquellas potencias en las que el primero sobrepasa al segundo y defecto a aquellos en los que ocurre lo contrario. Es la única forma de comparar si tener que escribir los números en el sistema decimal.

Si el exceso es mayor que el doble del defecto, se desecha el candidato, porque sobrepasaría a 2N. Si el defecto es mayor que el exceso también, porque sería menor que N. Entre los que quedan analizaremos sus divisores calculados mediante. Además, deberán presentar más divisores que N

(c) Lo anterior presenta un problema, y es que dado un juego de exponentes para N, el siguiente puede tener el mismo número de ellos, uno más e incluso uno menos. Puedes verlo en estos ejemplos de la lista de NAC:

Los mismos primos:

20160 2* 2* 2* 2* 2* 2* 3* 3* 5* 7
25200 2* 2* 2* 2* 3* 3* 5* 5* 7

Un primo más

50400 2* 2* 2* 2* 2* 3* 3* 5* 5* 7
55440 2* 2* 2* 2* 3* 3* 5* 7* 11

Un primo menos

27720 2* 2* 2* 3* 3* 5* 7* 11
45360 2* 2* 2* 2* 3* 3* 3* 3* 5* 7

Así que el algoritmo que intentemos deberá ser triple, uno para cada caso. Como dijimos, no damos más detalles, que podrían ser largos y pesados.

Herramienta

Hemos preparado una herramienta que sacrifica la velocidad para que se vean bien los cambios de exponentes, el exceso y defecto y el resultado final

En la fila 6 escribimos los exponentes de un NAC conocido, en este caso 21621600, cuyo juego es 5, 3, 2, 1, 1 y 1 (en el resto, para que estén en blanco, usa la tecla Supr). En la 9 se irán formado todas las combinaciones posibles dentro de las cotas de Ramanujan (algo ampliadas) y en las 12 y 13 se calculan los excesos y defectos, para garantizar que se mueven entre 2N y N.

También se calcula el número de divisores del inicial y el candidato, así como sus valores, aunque estos no son representativos y pueden presentar desbordamiento.

Si usas el botón “Buscar el próximo NAC” verás que van cambiando los valores de las filas 9 a 19, pero que en esta última se puede ir estabilizando el mejor candidato, hasta que termina el proceso y se convierte en el definitivo. En nuestro ejemplo se obtiene el siguiente  32432400.

A la derecha tienes la posibilidad de obtener varios NAC consecutivos a partir del escrito en la fila 6. No abuses de números grandes, que lo que obtendrás será un gran bloqueo en los cálculos. Si te metes en ese terreno, intenta salir con la tecla ESC.

En este caso aparecen los valores, pero si avanzáramos más llegaría un momento en el que sólo podríamos leer los exponentes. Por eso usábamos la expresión “encontrar sin ver”

En la anterior entrada ya dimos la dirección para que descargues la herramienta. Sólo la hemos implementado en Excel, pues su complejidad nos ha llevado bastante tiempo.

http://hojamat.es/blog/nac.xlsm

Puedes intentar exprimirla y comparar con la lista publicada en http://wwwhomes.uni-bielefeld.de/achim/highly.txt. Y también puedes mejorar el algoritmo…con paciencia.