Números 3-friables

Estudiaremos en esta entrada y la siguiente los números que sólo poseen como factores primos el 2 y el 3. De nuevo nos inspiramos en una sucesión de OEIS. Esta vez en la A003586 (http://oeis.org/A003586), que presenta los que llama “3-smooth numbers”, que se puede traducir como “liso o alisado (o regular) de grado 3”. En francés se les denomina 3-friables, y en nuestro idioma “friable” equivale a “fácilmente desmenuzable”. Si alguien conoce otra  denominación española puede comunicármelo. Mientras tanto, utilizaré una denominación similar a la francesa. Hendrik Lenstra les llama armónicos, en recuerdo de un texto de Phillipe de Vitry, obispo de Meaux, compositor del siglo XIV.

Me quedaré con la nomenclatura francesa: Un número es B-friable si todos sus factores primos son menores o iguales a B. En nuestro caso los números que estudiaremos son 3-friables. En este blog no nos son desconocidos, porque vimos en una entrada de hace unas semanas que los máximos productos de sumandos en las particiones de un número eran de este tipo (ver http://hojaynumeros.blogspot.com.es/2016/11/maximo-producto-en-la-particion-de-un_23.html)

Simplemente son números cuyos únicos factores primos son el 2 o el 3 (o ambos), es decir, que tienen la forma N=2^i*3^j con i,j³0.

Los primeros son estos:

1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96, 108, 128, 144, 162, 192, 216, 243, 256, 288, 324, 384, 432, 486,…

Es fácil ver que desde el 1=2^0*3^0 hasta el final, todos tienen como únicos factores primos el 2 y/o el 3.

Existe una prueba muy sencilla para averiguar si un número es de este tipo. Consiste en dividir entre 2 y entre 3 mientras sea posible, es decir, mientras el número y los cocientes sucesivos sean múltiplos de uno de los dos. Si al final del proceso nos queda un 1, es que los únicos factores son 2 y 3, como se pide. Lo podemos concretar mediante la función solo23, que devuelve VERDADERO o FALSO. Adjuntamos la versión para el Basic de hojas de cálculo:

Public Function solo23(n) As Boolean
Dim m
m = n ‘m representa los cocientes sucesivos
While m Mod 2 = 0: m = m / 2: Wend ‘Divide entre 2 mientras se pueda
While m Mod 3 = 0: m = m / 3: Wend ‘Hace lo mismo con el 3
If m = 1 Then solo23 = True Else solo23 = False ‘Si al final queda un 1, es de ese tipo
End Function

La siguiente tabla aparece en la hoja con bastante rapidez:

La versión en PARI puede ser esta:

m23(n)={local(m,v);m=n;while(m/2==m\2,m=m/2);while(m/3==m\3,m=m/3);if(m==1,v=1,v=0);v}
for(i=1,300,a=m23(i);if(a,print1(i,", ")))

Es idéntica a la anterior, pero con otras reglas de sintaxis.

Esta misma idea puede servir para descomponer un número 3-friable en sus dos componentes 2^p y 3^q. Insertamos las funciones COMP2 Y COMP3 que no necesitan explicación:

Public Function comp2(n)
Dim m
m = n
While m Mod 3 = 0: m = m / 3: Wend 'Divide entre 3 mientras se pueda
comp2 = m
End Function

Public Function comp3(n)
Dim m
m = n
While m Mod 2 = 0: m = m / 2: Wend 'Divide entre 2 mientras se pueda
comp3 = m
End Function

En la siguiente tabla se han descompuesto los primeros números 3-friables:

Generación recursiva

Es tentador generar nuevos términos si se conocen los anteriores. Se puede lograr siguiendo algunas ideas sugeridas en la sucesión A003586 ( Hai He y Gilbert Traub, Dec 28 2004 ). El procedimiento se basa en que las potencias de 2 aparecen con más frecuencia que las de 3. Usamos estas potencias 3^q como indicadores del progreso de creación: mientras se pueda, se añaden factores 2 a los términos anteriores, y cuando ya sea imposible, se aumenta el exponente del 3 y se toma como nuevo término.

Dada una potencia de 3 cualquiera, 3^q, que sea término de la sucesión:

(1) Se prueba a multiplicar por 2 todos los términos anteriores que den lugar así a términos nuevos
(2) Si se agotan las multiplicaciones por 2 (al sobrepasar 3^q), se pasa a 3^(q+1) y se vuelve al paso 1.


 El problema de este procedimiento es que para multiplicar por 2 quizás debamos retroceder bastante en la sucesión, con lo que habría que definir variables locales que almacenaran los términos, con ocupación de memoria y la ignorancia previa de qué dimensión darles. Para resolverlo usaremos la primera columna de una hoja de cálculo. Definiremos como u(k) el valor de la celda k de la primera columna, y usaremos una subrutina es_u(k,v) para escribir el valor v en esa celda k. Lo escribimos para Excel:

Public Function u(i)
u = ActiveWorkbook.Sheets(1).Cells(i, 1).Value ‘la variable u(i) representa la celda i
End Function

Sub es_u(i, a)
ActiveWorkbook.Sheets(1).Cells(i, 1).Value = a ‘esta rutina lee el valor de la celda i
End Sub

Con la ayuda de estas dos rutinas, podemos ya presentar el algoritmo completo:

Sub engendram23()
Dim k, j, n

Call es_u(1, 1) ‘rellena con un 1 la primera celda de la columna 1
k = 1 ‘la variable k lleva la cuenta de los términos engendrados
j = 1 ‘la variable j lleva la cuenta de los exponentes del 3
For n = 1 To 100 ‘así se generan 100 términos. Lo podemos cambiar.
k = k + 1 ‘se busca un nuevo elemento
If 2 * u(k - j) < 3 ^ j Then ‘se retrocede para multiplicar por 2
Call es_u(k, 2 * u(k - j)) ‘si no se llega a la potencia 3^j, se almacena un nuevo término
Else
Call es_u(k, 3 ^ j): j = j + 1 ‘si ya no es posible multiplicar por 2, se almacena 3^j y se incrementa
End if
Next n
End Sub

Aquí tienes el resultado de los primeros, ordenado por filas:

¿Por qué no un producto cartesiano?

Los anteriores cálculos se han introducido para que los números 3-friables aparezcan ordenados, pero si renunciamos a ese detalle, se pueden generar sencillamente con un producto cartesiano entre el conjunto de las potencias de 2 y el de 3. Si trabajamos con hoja de cálculo podemos posteriormente ordenar la columna que los contiene.

Así hemos procedido acudiendo a nuestra hoja Cartesius, de pronta publicación. Hemos definido dos conjuntos de potencias (2 y 3) que hemos combinado formando un producto cartesiano, indicando a la hoja que nos presente el producto de cada par. Las instrucciones han sido estas:

Se adivina que se han definido dos conjuntos, uno de potencias de 2 a partir de 1 (de ahí el n-1) y otro de potencias de 3. A los pares que resultan se les ha convertido en producto, creando así una columna desordenada de números del tipo 2^p*3^q. Después sólo queda copiar esa columna en otra hoja y proceder a ordenarla. De esa forma dispondremos de (en este caso 1000) los números 3-friables hasta donde deseemos.

En esta captura de pantalla puedes ver algunos de ocho cifras: