Números altamente compuestos (2)

Generación ordenada de los NAC (ver entrada anterior)

Ya hemos visto una forma de generar los NAC a base de columnas en una hoja de cálculo, pero este procedimiento tiene el inconveniente de que para números grandes los intervalos de aparición son tan amplios que no se pueden presentar en una columna. Lo ideal sería poderlos tener en filas consecutivas, como vemos en la imagen:

Pero esto no es fácil, porque el orden natural de los números no coincide con el del número de divisores, por lo que deberemos avanzar uno a uno y quedarnos con el máximo.

Veamos qué necesitamos:

Una función POTE(a;p) que nos indique el exponente con el que figura un número p en la descomposición en factores primos de a. Si no figura, el valor de la función será cero.

Otra función ESPRENAC(n) que indique si un número puede ser altamente compuesto o no, dependiendo de si presenta el esquema exigido con exponentes decrecientes.

Deberemos usar la función POTE y con ella verificar que los exponentes son los adecuados.

Un truco muy útil es el siguiente:

Si el número no obedece el esquema previo, la función ESPRENAC devuelve un cero, pero si lo obedece, la salida será el número de divisores. De esta forma podremos comparar este número con los de los anteriores y descubrir cuándo se ha llegado a un NAC.

Función POTE

Dado un número natural a y un primo p (en el algoritmo no se necesita que sea primo), para calcular el exponente con el que figura p en la descomposición de a bastará ir dividiendo a entre p todas las veces posibles siempre que p siga siendo divisor de a. Algo así:

•  Pongo un contador a cero
•  MIENTRAS p sea divisor de a
•  Divido a entre p y vuelvo a probar
•  Aumento el contador por cada división exacta
•  FIN del MIENTRAS

 El contador será el exponente

Su funcionamiento se entiende bien: al principio no sabemos si p es divisor de a, por lo que le asignamos exponente cero (el contador). Después intentamos una división exacta de a entre p. Cada vez que lo logremos aumenta el contador del exponente.

Código en Basic de hoja de cálculo

Public Function pote(a, b)
Dim p, c, d

p = 0: c = a
d = c / b (división con decimales)
While d = c \ b (división entera)
p = p + 1
c = c / b
d = c / b
Wend
pote = p
End Function

Dejamos a nuestros lectores la interpretación de este código.

Función ESPRENAC

Su objetivo es descubrir si un número tiene la estructura adecuada para ser NAC, es decir, que en su descomposición en factores primos sólo figuren los primeros con exponentes no crecientes.

Esta función recorre los primeros números primos 2, 3, 5, 7, … (representados en el código por la variable pr(i)) y va calculando la función POTE para cada uno de ellos. Analiza si ninguno es cero y si forman una sucesión no creciente. De paso, almacena (1+POTE) para al final calcular el número de divisores.

El esquena sería:

•  Inicio una variable SIGUE a uno
•  MIENTRAS el número N sea mayor que 1 y SIGUE>0
•  Recorro los primeros números primos
•  Para cada uno de ellos evalúo la función POTE, con lo N disminuirá
•  Si POTE es nula o mayor que la anterior, hago SIGUE=0
•  En caso contrario multiplico SIGUE por (1+POTE), con lo que preparo el cálculo del número de divisores
•  FIN del mientras

 Por último, ESPRENAC toma el valor de SIGUE. Si es cero, es que el número no puede ser altamente compuesto y si no lo es, devolverá el número de divisores.

Su código puede ser:

Public Function esprenac(n)
Dim p(20)
Dim c, i
Dim sigue

c = n
i = 0
sigue = 1
While c > 1 And sigue > 0
If i < 20 Then
i = i + 1
p(i) = pote(c, pr(i))
If p(i) = 0 Then sigue = 0
c = c / pr(i) ^ p(i)
sigue = sigue * (p(i) + 1)
If i > 1 Then
If p(i) > p(i - 1) Then sigue = 0
End If
Else
sigue = 0
End If
Wend
esprenac = sigue
End Function

Búsqueda ordenada

Con estas dos funciones podemos generar fácilmente la lista de NAC. Es un algoritmo “ingenuo” porque recorre todos los números entre cada dos posibles NAC, con el consiguiente gasto de trabajo y tiempo, pero para números no muy grandes va bastante bien.

Consistiría en

•  Iniciamos la lista con el 1. Llamamos ANTERIOR al mismo y DANTERIOR  a su número de divisores (también 1)
•  DESDE el valor 2 hasta el tope que marquemos
•  Analizamos cada número consecutivo para ver si puede ser NAC. Le calculamos su número de divisores y lo comparamos con DANTERIOR. 
•  Si el resultado de la comparación es que es mayor, ya hemos encontrado el siguiente NAC. Lo almacenamos en ANTERIOR y su número de divisores en DANTERIOR
•  FIN del DESDE
• De esta forma iremos comparando los divisores de los candidatos y cuando encontremos un NAC lo consideramos como ANTERIOR y vuelta a empezar.

El código de esta búsqueda contiene elementos propios cada hoja de cálculo concreta, por lo que es preferible que los descargues desde

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

¿Y qué ocurre si llegamos a números tan grandes que las hojas de cálculo no pueden ya representar sus cifras? Pues o bien nos pasamos a programas más potentes o intentamos buscar NAC sin verlos. Eso es lo que haremos en la siguiente entrada.