Números altamente compuestos (1)

Estos números fueron estudiados por Ramanujan, que ya tenía ideas sobre ellos antes de su colaboración con Hardy. Su definición es muy sencilla:

Un número altamente compuesto es un entero positivo con más divisores que cualquier número entero positivo menor que él mismo.

Así, el 12 tiene 6 divisores, mientras que todos los números menores que él tienen (del 1 al 11) 1, 2, 2, 3, 2, 4, 2, 4, 3, 4 y 2 respectivamente, luego 12 es altamente compuesto (lo expresaremos como NAC)

Los primeros son:

1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, ... 

(http://oeis.org/A002182)

La sucesión contiene infinitos términos, porque si N es NAC, el número 2N tiene los mismos factores que N y uno más, luego al menos existe un número con más divisores que N y recorriendo N+1, N+2, N+3,…N+N=2N bastará quedarse con el primer número que presente un máximo de divisores respecto a los anteriores (puede ser el mismo 2N).

Podemos expresarlo mediante la función divisor o sigma0, que cuenta los divisores de un número. En los NAC esta función presenta un valor superior al de cualquier otro número entero menor que él.
Pero si recordamos que la expresión de la función divisor es

siendo  a_i los exponentes en su descomposición en factores primos

comprenderemos  que lo que debemos estudiar son los máximos de esta expresión, que sólo dependen de la signatura prima de N (esto es, el conjunto de los exponentes en la factorización. Esto es importante: si sustituimos uno de los números primos de la factorización por otro, el valor de la función divisor no se altera. Esta idea tan simple nos lleva a la primera propiedad de los NAC:

Todo número altamente compuesto tiene como factores primos los primeros de la lista, de forma consecutiva: 2, 3, 5, 7, 11, …

Es sencillo demostrarlo. Imagina que en su desarrollo no figuraran todos los primeros números primos. Por ejemplo, que figurara el 11 y no el 7. Entonces, si sustituyéramos el 11 por un 7, el valor de N disminuiría, pero el de su función divisor, tal como vimos en el párrafo anterior, se mantendría igual, lo que contradice lo afirmado de que N presenta más divisores que cualquier otro número menor.

Esto recuerda a los primoriales. Puedes repasarlos, que los usaremos más adelante. Los tienes en http://hojaynumeros.blogspot.com.es/2012/02/el-primorial.html

No sólo han de figurar los primeros primos, sino que sus exponentes deberán ser no crecientes si ordenamos las potencias mediante bases crecientes: e1 ³ e2 ³ e3 ³ e4 ³ e5 ³…

También es fácil demostrarlo: si un par de exponentes se presentaran en orden inverso, intercambiando sus bases obtendríamos un número menor que N con sus mismos divisores, luego N no es NAC.

Por último, salvo en los casos de N=4=22 y N=36=22*32, el último de los exponentes debe ser 1. No he encontrado demostración de este hecho.

Obtención con hoja de cálculo

Debes disponer de la función divisor. Puedes definirla con esta versión muy simple

Public Function divisor(n)
Dim i, s

s = 1
For i = 1 To n / 2
If n / i = n \ i Then s = s + 1
Next i
divisor = s
End Function

Para implementarla en la hoja de cálculo puedes seguir las instrucciones contenidas en http://hojamat.es/guias/descubrir/htm/macros.htm

Comprueba que funciona bien y escribe en columna los primeros números naturales y junto a ellos el valor de divisor(n)

Una tercera columna la rellenaremos con los máximos consecutivos que se produzcan en la segunda. En la siguiente imagen te damos una idea del método para conseguirlo. Lee la fórmula en la línea de entrada.

Por último, en los saltos que se produzcan en ese máximo, allí estarán los NAC. Te dejamos en la imagen la fórmula usada

Con estas cuatro columnas te irán apareciendo los números altamente compuestos, para lo que basta que rellenes las fórmulas hacia abajo hasta donde quieras.

Más adelante volveremos a la generación ordenada de los NAC.

Relación con los primoriales

Si has visitado http://hojaynumeros.blogspot.com.es/2012/02/el-primorial.html sabrás ya que un número primorial el que equivale al producto de los primeros números primos sin saltar ninguno, es decir, son primoriales 1, 2, 6, 30, 210, 2310, 30030, 510510

Pues bien, es fácil demostrar que todo número altamente compuesto es un producto de primoriales.
La clave está en que los exponentes son no crecientes. De esa forma extraemos del NAC un primer primorial con todos los factores primos usados. Al cociente que nos resulte le hacemos lo mismo, dividirlo entre los primos que hayan quedado, y así sucesivamente. Al ser los exponentes no crecientes, siempre quedarán primos consecutivos que comenzarán en 2. Es mejor verlo con un ejemplo:

2520 es un NAC y se descompone como 2520=2⁵*3³*5*7= (2*3*5*7)*(2*3)*(2*3)*2*2 = P(5)*P(3)*P(3)*P(2)*P(2), si representamos por P(k) el k-ésimo primorial.

Se ve que se pueden repetir primoriales  y que no tienen que estar todos lo posibles. El recíproco no es cierto: no todo producto de primoriales es un NAC. Por ejemplo, en el caso de P(2)*P(2)*P(2)*P(3)*P(4)=2*2*2*6*30=1440 no resulta un NAC.

Otra propiedad: A partir del 6, todos los elementos de la sucesión son múltiplo de 6 y abundantes.

En la siguiente entrada generaremos todos los NAC de forma ordenada en filas consecutivas de una hoja de cálculo.