Regreso 17 – Cuestiones sobre los k-casi primos

En el año 2009 presenté los números k-casi primos, que son aquellos que poseen k divisores primos, no necesariamente distintos, así, 48=2⁴*3 es 5-casi primo, y 30=2*3*5, 3-casi primo.

https://hojaynumeros.blogspot.com/2009/12/primos-semiprimos-y-casi-primos-1.html

Casos particulares son los primos, para k=1, los semiprimos, con k=2 y un caso particular para k=3 son los esfénicos, que poseen tres factores primos distintos, como el 42=2*3*7

Es un concepto elemental, por lo que su presencia en Internet no es muy extensa. Una excepción interesante es la página https://mathworld.wolfram.com/AlmostPrime.html

En ella se reproducen fórmulas teóricas que cuentan el número de k-casi primos menores o iguales a un número dado N. Comenzaré con esa cuestión, pero desarrollándola con herramientas informáticas.

Distribución de los k-casi primos

Para identificar los números de este tipo podemos usar la función BIGOMEGA, que cuenta todos los factores primos con repetición. Algunos lenguajes de programación la tienen incorporada, como PARI. En él basta igualar esa función al valor de k:

escasiprimo(n,k)=bigomega(n)==k

Con eso basta.

Con este código encontramos todos los 5-casi primos del 1 al 500:

? escasiprimo(n,k)=bigomega(n)==k

for(a=1,500,if(escasiprimo(a,5), print1(a,", ")))

%3 = (n,k)->bigomega(n)==k

32, 48, 72, 80, 108, 112, 120, 162, 168, 176, 180, 200, 208, 243, 252, 264, 270, 272, 280, 300, 304, 312, 368, 378, 392, 396, 405, 408, 420, 440, 450, 456, 464, 468, 496, 500, …

Están publicados en https://oeis.org/A014614, y su tratamiento es elemental.

Para hojas de cálculo vale esta versión de la función BIGOMEGA:

Function bigomega(n)

Dim f, a, b

Dim vale As Boolean

  

a = n

f = 2: b = 0

While f * f <= a ‘f Es un posible factor primo

vale = False

While a / f = Int(a / f)’ ¿Es divisor?

b = b + 1’ Se cuentan repeticiones

a = a / f

vale = True

Wend

If f = 2 Then f = 3 Else f = f + 2 ‘Siguiente factor

Wend

If a > 1 Then b = b + 1’último factor

bigomega = b

End Function

Con esta función podemos construir ESCASIPRIMO(N,K):

Function escasiprimo(n, k) As Boolean

Dim a

a = bigomega(n)

If a = k Then escasiprimo = True Else escasiprimo = False

End Function

 
De esta forma, basta esta condición para encontrar k-casiprimos. En la imagen podemos observar las primeras soluciones para 5-casiprimos, ya estudiadas en PARI:

 
Cuestión 1: Estadísticas

¿Cuántos casi primos de cada clase son menores o iguales a un número n?

Para encontrar las frecuencias, bastará dimensionar un vector para ellas, por ejemplo, del 1 al 10, y dejar el 11 para “otros mayores de 10”

No es difícil la operación. La siguiente función las calcula y devuelve una lista con comas, para que se pueda convertir el texto en columnas.

Function estad_casi$(n)

Dim v(11)

Dim a, i, j

Dim s$

s$ = ""‘Contenedor de la lista de frecuencias

For i = 1 To 11: v(i) = 0: Next I ‘Frecuencias a cero

For j = 2 To n

a = bigomega(j) ‘Encuentra el tipo de casiprimo

If a > 10 And a > 0 Then v(11) = v(11) + 1 Else v(a) = v(a) + 1

‘Se cargan las frecuencias en el vector

Next j

For i = 1 To 11

s = s + ajusta(v(i)) ‘Se elabora la lista

If i < 11 Then s = s + ","

Next i

estad_casi = s

End Function

 

Por ejemplo, la estadística para n=5000 es la siguiente:

 

669,1365,1273,832,452,224,104,47,22,7,4

 

Si usamos la prestación de “Texto a columnas” podemos construir tablas de frecuencias y gráficos en hoja de cálculo:

Los resultados son lógicos. El máximo se presenta en los semiprimos. Los cuatro que poseen bigomega mayor que 10 son:

Sería interesante un ajuste a algún tipo de distribución, como la del modelo logístico de las epidemias. Ahí dejo el reto.

Cuestión 2: Descomposición de 2k-casiprimos en dos k-casiprimos

Un ejercicio sencillo es el de obtener la descomposición de un 2k-casiprimo en dos k-casiprimos. Nos permitirá desarrollar algunas técnicas.

Con una función

900=2²*3²*5² se puede descomponer en los 3-casiprimos 12=2*2*3 y 75=3*5*5. ¿En cuantos productos más? Con esta función se pueden encontrar todos. Como es tan solo una demostración, no se ha previsto que n no sea 2k-casiprimo, y se ha adaptado al ejemplo, suponiendo k=3. Para otro ejemplo, basta corregir.

Function dosfact$(n)

s = ""

For i = 2 To Sqr(n)

If n / i = n \ i Then’ Es divisor

If bigomega(i) = 3 Then’ Es 3-casiprimo

j = n / i: s = s + ajusta(i) + "×" + ajusta(j) + "  "

End If

End If

Next i

dosfact = s

End Function

 

Nos resultan cuatro descomposiciones:

12×75, 18×50, 20×45, 30×30 

Con Cartesius

Con esta herramienta también se puede intentar

(https://www.hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#cartesius)

Usamos las condiciones:

xtotal=3

xt=2,3,5

contar(2)<3

contar(3)<3

contar(5)<3

creciente

Piden combinar los tres números primos de 900 de forma que ninguno se repita más de dos veces. Así resultarán 3-casiprimos divisores de 90.

 

Sus desarrollos en factores resultan ser:

 

Y sus productos:

Obtenemos los mismos factores casiprimos. Al emparejarlos resultan los cuatro productos.

Razonamos

No son necesarias las herramientas informáticas en este caso. Si cada factor ha de poseer tres factores primos, sólo uno de ellos se podrá repetir, porque 900 no posee factores elevados a un exponente mayor que 2, luego tenemos: un factor sin repetición, 2*3*5 y seis factores con un elemento repetido. Como hay tres factores distintos en 900, y solo uno se repite, ese dará lugar a dos casos, y seis en total. Sumamos y nos resultarán siete factores posibles.

El principio de inclusión y exclusión nos ayuda a generalizar a más factores:

Card(AÈBÈC) =Card(A) + Card(B) + Card(C) - Card(AÇB) - Card(AÇC) - Card(BÇC) +  Card(AÇBÇC)

En este caso, podemos encontrar el número máximo combinaciones con repetición de los factores de 900 y restarle los arreglos no permitidos porque supongan repeticiones de tres o cuatro veces:

Sería:

Se deja así para quienes quieran seguir razonando.

Para casos más complejos podemos acudir a unas entradas recientes de este blog, que tratan el tema de los submulticonjuntos.

Cuestión 3: Además de casiprimos, ¿de qué otro tipo son?

Triangulares

Si pensamos en k-casiprimos triangulares, la primera idea es acudir a los semiprimos. Si N=n(n+1)/2 por ser triangular, uno de los factores de N deberá ser par, sea por ejemplo, n, y en ese caso n/2 y n+1 deberán ser primos. Si el factor par es n+1, lo serán (n+1)/2 y n. En ambos casos, el semiprimo deberá ser producto de un primo p en el que p+1 o p-1 sea doble de un primo. Los primeros ejemplos son: 6=3*4/2=3*2, 10=4*5/2=2*5, 15=5*6/2=5*3, …Todos ellos son triangulares y también semiprimos.

Con estas líneas los identificamos en PARI

a(n)=bigomega(n)==3&&omega==3&&(8*n+1)
for(k=4,5000,if(a(k)>0,print1(k,", ")))

La expresión 8*n+1 viene de que es cuadrada en los triangulares.

6, 10, 15, 21, 55, 91, 253, 703, 1081, 1711, 1891, 2701, 3403, …

Están publicados en https://oeis.org/A068443

Para los demás k-casiprimos, basta igualar bigomega a k en el anterior código PARI. Por ejemplo, los primeros triangulares 5-casiprimos son:

120, 300, 378, 496, 630, 780, 990, 1128, 1485, 1540, 1596, 2556, 2628, 2850, 3160, 3321, 3570, 3828, 4095, 4851, …

Están publicados muchos casos.

Oblongos

Los oblongos poseen la fórmula N=k(k+1), luego salvo 6=2*3, no podrán ser semiprimos. Los primeros 3-casiprimos lo serán si son doble de los triangulares semiprimos estudiados en el apartado anterior:

12, 20, 30, 42, 110, 182, 506, 1406, 2162, 3422, 3782, …

Han de tener un factor primo igual a 2, y de ahí que resulten muchos dobles de los anteriores. Pueden ser múltiplos de 4,  y así obtenemos el 12 y el 20 de nuevo. No hay más posibilidades.

Si buscamos ejemplos con k mayor que 3, se multiplican las soluciones, como 56=7*8 con k=4, 72=8*9 con k=5, y así con valores mayores. Su abundancia les quita interés.

Cuadrados o cubos

Dependerá del valor de k. Es fácil razonar que si es múltiplo de 2, podrán aparecer cuadrados, como 4=2*2, semiprimo, 36=2*2*3*3, con k=4, y cubos, con k múltiplo de 3. No tienen más misterio.

Números de Fibonacci

En este blog se ha usado la función esfibo:

Function esfibo(n) As Boolean 'devuelve verdadero si N es de Fibonacci

Dim f As Boolean

Dim a

f = False
a = 5 * n * n + 4
If escuad(a) Then f = True
a = 5 * n * n - 4
If  f = True
esfibo = f

End Function

Con ella y bigomega se pueden encontrar. Si los traducimos a PARI se obtienen los primeros:

Para semiprimos usamos

a(n)=bigomega(n)==3&&(issquare(5*n*n+4) || issquare(5*n*n-4))
for(k=4,5000,if(a(k)>0,print1(k,", ")))

Resultan estos primeros ejemplos:

21, 34, 55, 377, 4181, 17711, 121393, …

Están publicados en https://oeis.org/A053409

Con k=3 sólo han sido publicados los casos de esfénicos, más general es

8, 610, 987, 10946, 75025, …

Es un camino a seguir para buscar más casos.

 

 

 

La hoja de cálculo y los números de Catalan

Últimamente estoy volviendo a la Combinatoria, que tenía algo abandonada. Hoy es el turno de dar un repaso a los números de Catalan (Obtienen su nombre del matemático Eugène Charles Catalan):

1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, …

(http://oeis.org/A000108)

Estos números se suelen introducir mediante las triangulaciones de polígonos, según puedes comprobar con esta imagen tomada de la Wolfram MathWorld:

 

(Fuente: http://mathworld.wolfram.com/CatalanNumber.html)

A la vista de la figura, y de la definición, se comprende que un triángulo solo se puede triangular de una forma, con lo que C(1)=1. Un cuadrilátero, según vemos, en dos, que son las diagonales, por lo que C(2)=2.

El pentágono se triangula según sus cinco vértices, lo que hace que C(3)=5. También puedes comprobar que C(4)=14 para el hexágono.

Así podríamos seguir.

Estos números son muy conocidos, y aquí sería inútil añadir más teoría. Por eso, nos dedicaremos solo al uso de la hoja de cálculo para calcularlos.

Para conocer mejor estos números puedes consultar:

https://www.youtube.com/watch?v=kjn9hFQK9aQ

(vídeo de Eduardo Sáenz de Cabezón)

https://es.wikipedia.org/wiki/N%C3%BAmeros_de_Catalan

https://www.gaussianos.com/los-numeros-de-catalan/

http://mathworld.wolfram.com/CatalanNumber.html

https://brilliant.org/wiki/catalan-numbers/

http://mathforum.org/advanced/robertd/catalan.html

En ellas y otras similares puedes encontrar propiedades y demostraciones. Como no es cuestión de repetir lo que en otras fuentes se explica mejor, daremos por supuestas las propiedades en lo que sigue y nos dedicaremos a plantear cálculos y cuestiones con Excel solamente, pues el programa Calc de LibreOffice también los lee, incluidas las macros más populares:

Fórmula directa

En esas páginas enlazadas figura la fórmula directa para calcular el enésimo número de Catalan.

En las hojas de cálculo dispones de la función COMBINAT para los números combinatorios C(m,n), FACT para el factorial n! y FACT.DOBLE para el doble factorial n!!

Con ellas podemos comprobar las tres fórmulas directas anteriores. Quedarían así:

=COMBINAT(2*N;N)/(N+1)

=FACT(2*N)/FACT(N+1)/FACT(N)

=2^N*FACT.DOBLE(2*N-1)/FACT(N+1)

Lo comprobamos con tres columnas paralelas en una tabla:

Aprenderás bastante del manejo de las hojas de cálculo con la construcción de esta tabla. Con ella comprobamos la equivalencia de las tres fórmulas. Si sabes añadir funciones a Excel, puedes definir una función con una de estas tres fórmulas. Elegimos la segunda, que solo usa la función FACT. Te sorprenderá su extensión, pero es que contiene tres llamadas a las funciones de Excel:

Function catalan(n)

catalan = Application.WorksheetFunction.Fact(2 * n) / Application.WorksheetFunction.Fact(n) / Application.WorksheetFunction.Fact(n + 1)
End Function

En la entrada de este blog enlazada a continuación puedes recordar el procedimiento para disponer de esta función en el Excel de tu ordenador:

https://hojaynumeros.blogspot.com/2013/09/tus-funciones-disponibles-en-todas-las.html

Así, si escribes =CATALAN(8) te devolverá 1430. Igualmente, puedes escribir operaciones con números de Catalan, como, por ejemplo, la diferencia entre dos consecutivos:

CATALAN(20)-CATALAN(19)=4796857230

Si deseas practicar un poco más con la hoja de cálculo, puedes comprobar o construir la función CATALAN con esta otra expresión:

 

Por ejemplo, 132=COMBINAT(12;6)-COMBINAT(12;5)

Otras expresiones de los números de Catalan

Mediante un producto:

Desde el segundo número de Catalan, siguiendo las propiedades contenidas en http://oeis.org/A000108:

a(n) = Product_{k=2..n} (1 + n/k), if n > 1.

Es fácil traducir este producto al Basic de Excel y Calc:

Function catalan2(n)

Dim k, p

 

p = 1

For k = 2 To n

p = p * (1 + n / k)

Next k

catalan2 = p

End Function

 

En esta captura de pantalla se refleja la comprobación del idéntico resultado para el número 8 en las dos versiones propuestas:

 

Mediante recurrencia

No es difícil demostrar, con cualquiera de las tres fórmulas directas, esta versión recursiva:

Podemos aprovechar las prestaciones de Excel en el uso de funciones recursivas. No es muy potente, pero para números sencillos funciona bien. Consiste en que una función se llama a sí misma.

Tienes una introducción a esta técnica en nuestro documento “Funciones y Macros”, descargable desde

http://www.hojamat.es/guias/descubrir/htm/macros.pdf

Para el caso de los números de Catalan proponemos este código:

 

Function catalan3(n)

Dim c

 

If n = 1 Then c = 1 Else c = catalan3(n - 1) * 2 * (2 * n - 1) / (n + 1)

‘Si n=1 declaramos que c=1 y, en caso contrario, catalan3 se llama sí misma en el valor n-1

catalan3 = c

End Function

 

Es un código muy compacto, pero que puede fallar para números grandes

He incorporado esta otra función en una hoja de cálculo descargable que contiene el material que se va desarrollando en esta serie de entradas

 

http://www.hojamat.es/blog/catalan.xslm

Otra forma de conseguir la recurrencia es mediante dos columnas, una con los índices y otra en la que cada número de Catalan depende del anterior:

Si n=1, a=1
A(n)=a(n-1)*2*(2*n-1)/(n+1)

Dejamos aquí los cálculos sobre los números de Catalan. Nuestro enfoque ha sido operativo, porque es un tema tan extenso y tan bien tratado en otras publicaciones que con una sola herramienta como la hoja de cálculo era algo inútil reproducir conceptos y cálculos.

 

Números poligonales generalizados

Algunos conceptos matemáticos, que se basaron inicialmente en los números naturales, fueron después adaptados a otros tipos de números. Esto ocurrió con los números poligonales, que, al superar su carácter inicial geométrico, se generalizaron a los números enteros, pues ya no era necesario que su orden fuera positivo, al no representar una longitud. Esta decisión les abrió a nuevas posibilidades, por lo que han perdurado.

Todo número poligonal viene dado por esta fórmula muy popular:

Si permitimos que n sea cero o negativo, obtendremos los llamados números poligonales generalizados.

Si n es positivo, resultará un número poligonal clásico, que siempre será entero, ya que en el numerador se restan dos números de la misma paridad. Si generalizamos a un número negativo, sea n=-m, al sustituir en la fórmula obtendremos

Esta expresión da lugar a una nueva clase de poligonales a los que llamaremos segundos poligonales del mismo orden. Con el añadido del cero, los números poligonales generalizados serán la unión de los clásicos con estos otros de segunda naturaleza.

Si imaginamos m=n, ocurrirá que PS_n=P_n+(k-4)n

Comparemos, por ejemplo, las dos clases de hexagonales:

Los clásicos: 0, 1, 6, 15, 28, 45, 66, 91, 120, 153, 190, 231, de fórmula n(2n-1)

https://oeis.org/A000384

Los segundos: 0, 3, 10, 21, 36, 55, 78, 105, 136, 171, 210, de fórmula n(2n+1)

https://oeis.org/A014105

la diferencia entre sus elementos del mismo orden (k-4)n=2n

Así, 3-1=2*1, 10-6=2*2, 21-15=2*3, …

Lo interesante es que ambos conjuntos se pueden unir intercalando sus elementos. Para ello, habrá que demostrar que PS_n<P_n+1

Planteamos la diferencia:

Al ser el resultado positivo, podemos afirmar que P_n  < PS_n< P_n+1, y que, por tanto, se pueden intercalar ambas sucesiones con el título de números poligonales generalizados.

En el caso del hexágono formarían, intercalados, los números hexagonales generalizados:

0, 1, 3, 6, 10,15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136,153,

Nos llevamos la sorpresa de que son los números triangulares clásicos. Ya volveremos sobre ellos.

Casos particulares

Los triangulares se convierten en otros triangulares al cambiar de índice positivo a negativo, y los cuadrados permanecen iguales. Los casos interesantes comienzan con los pentagonales. Veremos los de este tipo y algunos más:

Números pentagonales generalizados

Los pentagonales clásicos, 1, 5, 12, 22, 35, 51, … siguen la fórmula

Es el caso particular de la fórmula general para k=5

Están publicados en https://oeis.org/A000326 y estudiados en mi publicación “Números poligonales” https://www.hojamat.es/publicaciones/poligonales.pdf

Según lo tratado anteriormente, los segundos pentagonales tendrán como fórmula

Son estos:

0, 2, 7, 15, 26, 40, 57, 77, 100, 126, 155, 187, …

Su diferencia con los clásicos del mismo orden es n: 2-1=1, 7-5=2, 15-12=3, …

Están publicados en https://oeis.org/A005449

La unión de las dos sucesiones formará esta otra, la de pentagonales generalizados:

0, 1, 2, 5, 7, 12, 15, 22, 26, 35, 40, 51, 57, 70, 77, 92, 100, 117, 126, 145, 155, 176, 187, 210, 222, 247, 260, … (https://oeis.org/A001318)

Segundos pentagonales

Estudiamos algunos detalles de los segundos pentagonales:

Interpretación combinatoria

En la página de OEIS correspondiente se afirma que representan las cartas necesarias para construir un castillo de naipes. La clave está en el hecho de que PS(n+1)=PS(n)+2n+3:

Para el primer castillo se necesitan 3 cartas, y dado un castillo ya formado, deberemos añadir tres cartas por nivel (dos inclinadas y una horizontal) más la culminación, que serán dos cartas. En la imagen se entiende bien:

Las cartas de perfil azul corresponden a PS(3)=15 y las rojas 3*3+2=11, y al sumar obtenemos PS(4)=26

Recurrencias

Además de la ya tratada de 3n+2, existen varias publicadas en OEIS, pero no la que califico de “muy útil” (https://hojaynumeros.blogspot.com/2026/05/unas-recurrencias-muy-utiles.html) también nos vale, y no recurre al valor de n:

x_n= 3x_n-1-3x_n-2+x_n-3

En la entrada enlazada se explica su fundamento. Aquí basta con una comprobación en forma de tabla:

Números pentagonales generalizados

Al ser la unión de dos sucesiones, podemos unificar sus fórmulas mediante una función. En ella la variable m es útil para alternar los signos más y menos en el numerador.

pg(n)=my(m=truncate((n+1)/2));(3*m^2+(-1)^n*m)/2

for(k=1,20,print1(pg(k),", "))

Resulta:

1, 2, 5, 7, 12, 15, 22, 26, 35, 40, 51, 57, 70, 77, 92, 100, 117, 126, 145, 155, …

Era lo que se pretendía.

En su página de OEIS se incluyen muchas alternativas como fórmulas para esta sucesión.

 

Nuestra recurrencia “útil”

 

Al ser ambas sucesiones componentes generadas por la misma fórmula de recurrencia, bastará definir como elementos iniciales 0, 0, 1, 2, 5, 7 y aplicar

x_n= 3x_n-2-3x_n-4+x_n-6

Así: 3*5-3*1+0=12, 3*7-3*2+0=15, 3*12-3*5+1=22, …

Propiedad de Conway

La tercera parte de un triangular es un pentagonal generalizado si no es del tipo 3n+1

En esta tabla figuran los primeros triangulares y su tercera parte si es válida la para la propiedad:

0 1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 ...

0    1 2        5  7       12 15      22 26       35  40          51 ...

T(3n)/3=3n*(3n+1)/6=(9n²+3n)/6=(3n²+n)/2

T(3n-1)/3=(3n-1)(3n)/6=(3n²-n)/2

En ambos casos resulta un pentagonal generalizado.

 Otra propiedad: 24*a(n)+1 es un cuadrado

24(3n²+2)/2+1=36n²+24n+1=(6n+1)²

E igual con los pentagonales clásicos

Números heptagonales generalizados

Siguiendo los mismos razonamientos que con los pentagonales, esta otra sucesión será la unión de los heptagonales clásicos, de fórmula HP(n)=n(5n-3)/2 y los “segundos”, provenientes de órdenes negativos HPS(n)=n(5n+3)/2.

La sucesión resultante es, en sus primeros términos:

0, 1, 4, 7, 13, 18, 27, 34, 46, 55, 70, 81, 99, 112, 133, 148, 172, 189, 216, 235, 265, 286, 319, 342, 378, 403, 442, 469, 511, 540, 585, …

Está publicada en https://oeis.org/A085787, y los segundos heptagonales en https://oeis.org/A147875

Propiedades

A continuación, se verán algunas propiedades de ambas sucesiones:

Los segundos heptagonales son suma de una progresión geométrica, la b(n)=5*n+4, con primer término b(0)=4. En efecto, la suma será S(n)=(4+5*(n-1)+4)*n/2=n(5n-3)/2

Como todos los números de estos tipos siguen la recurrencia

x_n= 3x_n-1-3x_n-2+x_n-3

27=3*13-3*4+0, 46=3*27-3*13+4, …

Esta recurrencia se extiende a toda la sucesión generalizada de igual forma que en el caso de pentagonales.

De forma similar a los pentagonales, se cumple que 40a(n)+9 es un cuadrado:

40*n*(5n±3)/2+9=100n²±60n+9=(10n±3)²