Generación de primos sumando cuadrados y otros (1)

En mis exploraciones por la página OEIS me he encontrado con una sucesión de primos en la que a cada término le sigue el menor primo cuya diferencia con el anterior es un cuadrado (https://oeis.org/A073609). He pensado en ampliar el tema a diferencias de otro tipo, no cuadrados, para descubrir algunas posibles propiedades.

La sucesión es claramente dependiente de su inicio, que en este caso es el 2, pero para cualquier primo con que iniciemos, producirá un siguiente primo único, diferente a estos o coincidente. Los términos publicados son los siguientes, con inicio en 2:

2, 3, 7, 11, 47, 83, 227, 263, 587, 911, 947, 983, 1019, 1163, 1307, 1451, 1487, 1523, 1559, 2459, 3359, 4259, 4583, 5483, 5519, 5843, 5879, 6203, 6779, 7103, 7247, 7283, 7607, 7643, 8219, 8363, 10667, 11243, 11279, 11423, 12323, 12647, 12791, 13367,...

No es difícil, dado un número primo, encontrar otro primo, el menor posible, que se diferencie del primero en un cuadrado. La función en VBA de Excel puede ser la siguiente:

Function primsalto(a) As Long

Dim p, prim,d As Long

Dim sale As Boolean

if not esprimo(a) then primsalto=0:exit function ‘No es primo y se asigna un cero

p = primprox(a): sale = False: prim = 0 ‘Se van buscando los siguientes primos

While Not sale

d=p-a ‘Se calcula la diferencia

if escuad(d) then prim=p:sale=true ‘Si la diferencia es cuadrada, tenemos la solución

p=primprox(p) ‘Se sigue con el siguiente primo

wend

primsalto=prim ‘Se encontró

End Function

Hay que usar las funciones ESCUAD y PRIMPROX, que se pueden buscar en nuestro blog.

Con ella, comenzando, por ejemplo en el 7, se construye fácilmente un conjunto dentro de la sucesión:

Si elegimos un primo que no figure en la sucesión, como el 13, construiremos otra similar, que, en este caso sería:

 

En este caso nos devuelve otra sucesión cuyos primeros términos no coinciden con los anteriores. Podía haber un elemento común, con lo que ambas sucesiones coincidirían totalmente a partir de él. Volveremos a ese tema.

En la sucesión de OEIS citada se organiza la búsqueda con un orden distinto, pues para cada primo se le van sumando cuadrados hasta llegar a otro primo. El código PARI es muy sintético y lo copiamos aquí.

print1(a=2, ", "); for(n=1, 43, k=1; while(!isprime(b=a+k^2), k++); print1(a=b, ", "))

Usa la instrucción print para asignar también valores a las variables. No lo habíamos visto hasta ahora, y es ingenioso.

Cuestiones diversas

Naturaleza de los cuadrados

Para primos mayores que 6, en cada inicio de sucesión, si se llega a un tipo 36k+p, siendo p primo del tipo 6q+5, todos los cuadrados que se añadan en este proceso serán múltiplos de 36, con lo que el tipo inicial 36k+p se mantendrá.

Efectivamente, si le sumo otro cuadrado, deberá ser par, para que la suma siga siendo impar, y también ha de ser  múltiplo de 3, pues, en caso contrario, sería uno de los tipos 6m+2 o 6m+4, y resultaría:

36k+p+(6m+2)² =36(k+m²)+24m+4+p

36k+p+(6m+4)² =36(k+m²)+48m+16+p

Si p=6k+5 no valen estos casos, pues 4+p y 16+p serían múltiplos de 3, con lo que el resultado final no sería primo. Por tanto, el cuadrado ha de ser múltiplo de 36.

Si p=6k+1, puede no ser el salto de 36k, sino otro cualquiera par, como 4, 16, 64 o 100.

Observamos algunos inicios:

Inicio 37

Este primo es del tipo 6k+1, por lo que el cuadrado que se suma no ha de ser múltiplo de 36, pero el siguiente, 41, es del tipo 6k+5, y a partir de él, todos son del mismo tipo. A esta situación se llegará siempre. Es fácil razonarlo.

36k+6q+1+(6m+2)² =36(k+m²)+24m+4+6q+1=6h+5

36k+6q+1+(6m+4)² =36(k+m²)+48m+16+6q+1=6h+5

Lo vemos en la imagen:

 

Todos los restos módulo 6 valen 5, y todas las diferencias múltiplos de 36 a partir del 41.

Inicio 47

Este primo es del tipo 6k+5, luego todos los cuadrados serán múltiplos de 36

 

Primos consecutivos

Hemos visto que el primo 37, con un cuadrado se ha convertido en su consecutivo. En este caso, con cuadrado igual a 4. Esto será frecuente, pero habrá otros ejemplos. En un primer intento, todos los casos hasta el valor de 1000 presentan una diferencia de 4. El siguiente cuadrado par, 16, se alcanza por primera vez en el par 1831, 1847. La siguiente diferencia de 64 no se alcanza para valores inferiores a 25000. Con el siguiente código, adaptado de OEIS, hemos encontrado dos pares de primos consecutivos con diferencia 64.

primosalto(n)={my(k=1,b);while(!isprime(b=n+k^2), k++);b}

forprime(i=2,2000,p=nextprime(i+1) ;q=primosalto(i);if(p==q&&p-i==16,print(i," ",p)))

Son estos: (89689, 89753) y (107377, 107441)

Los primeros casos para cada cuadrado están publicados en https://oeis.org/A138198:

2, 7, 1831, 9551, 89689, 396733, 11981443, 70396393, 1872851947, 10958687879, 47203303159, 767644374817, 8817792098461, 78610833115261, 497687231721157, 2069461000669981, 22790428875364879, 78944802602538877....

Primos comunes a dos sucesiones

Se podría preguntar si estas sucesiones son disjuntas o existen elementos comunes, y la respuesta es que sí los hay. Hemos usado la siguiente función para detectar si un número primo pertenece a la sucesión iniciada con otro primo menor, al que llamaremos antecedente.

function numsaltos$(n)

dim s$

dim i,k

k=0 ‘Contador de soluciones

i=2 ‘Primer inicio primo

while i<=n and k<2

if n=primsalto(i) then k=k+1:s=s+str$(i)+", "’Nueva solución

i=primprox(i)’Siguiente primo posible

wend

if k>=2 then numsaltos=str$(ajusta(k))+". "+s else numsaltos="NO"

end function ‘Devuelve un par de soluciones o un “NO”

Los primeros elementos comunes, seguidos por dos antecedentes son:

41  5,  37

47  11,  31

83  47,  79

89  53,  73

107 71,  103

167 131,  151

173  29,  137

197 181,  193

 Por ejemplo, 167 pertenece a las sucesiones

131, 167, 311, 347, 383

151, 167, 311, 347, 383

Es evidente que, a partir de un elemento común, todos lo son.

Primos sin antecedentes

Si modificamos la función numsaltos para que devuelva sólo el número de antecedentes, obtendremos otras soluciones interesantes:

Estos serían inicio de sucesión pero no pertenecerían a ninguna otra. Basta buscar aquellos primos p en los que numsaltos(p)=0. Los primeros son estos:

2, 5, 13, 19, 29, 31, 37, 43, 61, 67, 73, 79, 103, 109, 127, 139, 151, 157, 163, 179, 181, 191, 193, 199, 211, 223, 229, 241, 271, 277, 283, 313, 331, 337, 349, 359, 367, 373, 379, 397, 409, 421, 431, 433,...

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

Diversos órdenes de la función TAU

Una extensión de la definición de la función TAU, que es la que cuenta los divisores de un número, puede ser la que resuma las descomposiciones en dos factores, N=x*y, o, ya puestos, las de tres factores N=x*y*z, o cuatro. Así podríamos definir TAU_1, TAU_2, TAU_3,…según el número de esos factores.

En este blog hemos aludido alguna vez a la descomposición de un número en tres factores, pero sin tener en cuenta el orden de los mismos, que elegíamos ordenados en orden creciente.

Por ejemplo, se tratan en https://hojaynumeros.blogspot.com/2018/04/productos-de-tres-divisores-13.html y siguientes

En esta entrada dedicaremos una pequeña referencia a TAU_2, que en realidad es la función TAU tradicional, para después dedicarnos a TAU_3 y TAU_4. A partir de ellas no es difícil estudiar las siguientes.

 

Función TAU_2(n)

Si buscamos todos los pares ordenados de divisores de N cuyo producto es N, en realidad estamos contando los divisores simples, porque cada divisor posee un complementario (N/d) respecto a N que también es divisor de N, lo que duplica su presencia en los productos.

En síntesis: TAU_2(N) = TAU(N)

Es lo único que estudiaremos de esta función, muy conocida y también muy usada en este blog.

Según el razonamiento anterior, contar divisores de un número N equivale a contar soluciones ordenadas de la ecuación N=x*y con x e y positivos.

Lo podemos comprender mejor con un ejemplo concreto. Hemos elegido el número 84:

El número de divisores de 84, o TAU(84), se calcula a partir de la descomposición factorial: 84=2²*3*7, aplicando la conocida fórmula del producto de exponentes incrementados en una unidad:

TAU(84)=(1+2)(1+1)(1+1)=12.

Los doce divisores son: 84, 42, 28, 21, 14, 12, 7, 6, 4, 3, 2 y 1

Viene bien recordar que el valor de TAU sólo depende de la signatura prima, que es el conjunto de exponentes, y no de los factores primos.

Por otra parte, las soluciones de 84=x*y se pueden encontrar con nuestra herramienta Cartesius (http://www.hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#cartesius)

Con ella podemos usar el siguiente planteo:

Se sigue fácilmente: Combinar dos números, entre 1 y 84, que sean ambos divisores de 84, y que su producto sea también 84. Resultan las soluciones:

Como cada divisor d posee un único complementario N/d para conseguir el 84, es evidente que resultarán también 12 soluciones, con lo que comprobamos que esta forma de definir TAU es válida.

 

Función TAU_3(n)

Ya se indicó más arriba que la descomposición en tres factores ya se ha abordado en este blog, pero ahora consideraremos todas las ordenaciones posibles de las tres soluciones de la ecuación N=x*y*z. No es difícil razonar cómo encontrar el número de soluciones. Basta considerar que z ha de tomar todos los valores posibles de divisores de N, y que x*y serían entonces todos los productos posibles del complementario de z, N/z. Por tanto, cada valor de z se combinará con las soluciones de N/z=x*y, que vimos más arriba que coinciden con el número de divisores de N/z. Por tanto TAU_3(N) se encuentra sumando los números  de divisores de cada divisor de N.

Lekraj Beedassy lo expresa muy bien en OEIS: “Number of divisors of n's divisors”.

Lo comprobaremos de varias formas con el mismo ejemplo del 84. Comenzaremos con Cartesius:

El mismo plantamiento que con dos factores, adaptándolo a tres. Resultan entonces 54 soluciones.

Ahora lo resolveremos con una función para Excel o Calc:

Public Function tau_3(n)

Dim i, j, s

 

s = 0 ‘Inicio del contador

For i = 1 To n

If n / i = n \ i Then ‘Recorre los divisores de N

For j = 1 To i

If i / j = i \ j Then s = s + 1 ’Aumenta el contador con “divisores de divisores”

Next j

End If

Next i

tau_3 = s

End Function

 

Si lo aplicamos al número 84, se confirma que TAU_3(84)=54

En https://oeis.org/A007425 están publicados los valores para los primeros números:

A007425 d_3(n), or tau_3(n), the number of ordered factorizations of n as n = r s t.

1, 3, 3, 6, 3, 9, 3, 10, 6, 9, 3, 18, 3, 9, 9, 15, 3, 18, 3, 18, 9, 9, 3, 30, 6, 9, 10, 18, 3, 27, 3, 21, 9, 9, 9, 36, 3, 9, 9, 30, 3, 27, 3, 18, 18, 9, 3, 45, 6, 18, 9, 18, 3, 30, 9, 30, 9, 9, 3, 54, 3, 9, 18, 28, 9, 27, 3, 18, 9, 27, 3, 60, 3, 9, 18, 18, 9, 27, 3, 45, 15, 9, 3, 54, 9, 9, 9, 30,…

Puedes comprobar valores con Cartesius o nuestra función.

Los códigos PARI publicados en esta página son tan ingeniosos, que es prferible copiar alguno. Por ejemplo:

a(n)=sumdiv(n, x, sumdiv(x, y, 1 )) \\ Joerg Arndt, Oct 07 2012

Pide sumar, para cada divisor de N, un 1 por cada uno de sus divisores, lo que equivale a contarlos. Lo probamos en la página web de PARI:

 for(i=1, 200, print1(sumdiv(i, x, sumdiv(x, y, 1 )),", "))

Coincide, como era de esperar, con los publicados.

 

Intervienen los números triangulares

Todos los resultados son productos de números triangulares y dependen de la signatura prima de N, y no de los valores de los factores primos.

Introducimos el tema con algunos ejemplos:

N es primo

En ese caso Tau_3(N)=3, porque los productos xyz posibles serían 11p,1p1, y p11, es decir T(1+1)=3, representando por T el triangular correspondiente. También podemos acudir a una partición plana que represente la segunda definición que hemos dado (https://en.wikipedia.org/wiki/Plane_partition)

1  p

1

Es un esquema triangular de lado 2

 

N es semiprimo N=p*q con factores primos diferentes

Los productos xyz serían

N11, 1N1, N11, 1pq, 1qp, qp1, q1p, pq1, p1q son nueve, que coincide con T(1+1)T(1+1)=3*3=9

Como partición plana:

N  p  q  1

p 1

q 1

1

Resulta TAU_3(pq)=9

 

Para un semiprimo cuadrado

Los productos serían 11n,1n1, n11, 1pp, p1p, pp1 son seis: T(2+1)=T(3)=6

En representación de dos dimensiones:

N p 1

p 1

1

TAU_3(p²)=6

 

Para exponentes 2 y 1, como el 12:

Los productos serían 1(12)1, 11(12), (12)11, 143, 134, 413, 431, 314, 341, 223, 232, 322, 126, 162, 216, 261, 612, 621 son 18, T(2+1)T(1+1)=6*3=18

En un esquema de partición plana se organizarían así:

12   6   4   3   2   1

6   3   2   1

4   2   1

3   1

2   1

1

TAU_3(p²q)=18

Los divisores de los divisores resultan ser 18, ordenados.

Aquí nos detenemos. Hemos comprobado que para un factor el TAU_3(N) es un triangular, y para dos factores, un producto de triangulares. Pues bien, ese esquema se conserva, y si un número posee varios factores primos con diferentes exponentes, bastará sustituir en la fórmula de la función TAU los paréntesis por números triangulares

Lo podemos razonar descomponiendo la partición plana en diversas zonas cuando se añade un factor nuevo. Tomaremos el 12 como ejemplo y realizaremos un producto cartesiano entre los datos del 4 con los del 3

Hemos representado en colores distintos las zonas en las que se divide el producto cartesiano de seis filas y tres columnas:

En rojo figuran los elementos de TAU_3(4), los que había antes de incorporar el 3. En la tercera columna figuran los divisores en los que interviene el nuevo factor 3. Las zonas horizontales de distinto color representan los “divisores de divisores”, que son fundamentales en este estudio.

Es fácil comprender que obtendríamos un esquema similar si el nuevo factor estuviera elevado a un exponente mayor que 1. Ahí lo dejamos y nos creemos sin desarrollarlo que también se obtendría un producto de triangulares.

Sólo comprobaremos la fórmula con nuestras funciones. Por ejemplo, 72=2³*3², luego según la fórmula sugerida, tendríamos TAU_3(72)=T(1+3)T(1+2)=10*6=60

Con nuestra función

 

Con el código PARI de Joerg Arndt

print(sumdiv(72, x, sumdiv(x, y, 1 )))

Función TAU_4(n)

El estudio de TAU_3 nos ha abierto caminos y los hemos aprovechado con calma. Ahora sólo resumiremos algunos de ellos en los demás casos.

Si definimos TAU_4(N) como como el número de productos xyzu de cuatro factores (con ordenación) cuyo producto es N, podremos comenzar como en el caso de 3, con nuestra herramienta Cartesius. Sería así en nuestro ejemplo del 84:

Al combinar cuatro factores, el proceso es más lento, pero no excesivamente, y nos da un resultado de 160:

Algunas ideas sobre TAU_3(N) se pueden ampliar a TAU_4(N). La primera es que la frase “divisores de divisores” habrá que cambiarla por “Valores de TAU en divisores”, ya que, al añadir un factor nuevo en el producto xyzv, este no se combina con divisores, sino con productos que vimos al principio que representaban a TAU. Así, el esquema bidimensional no se rellenará con divisores, sino con su número de divisores. Recordemos que en TAU_3 usábamos este esquema

12   6   4   3   2   1

6   3   2   1

4   2   1

3   1

2   1

1

Ahora deberíamos sustituir cada divisor por el valor de TAU (número de divisores) en cada uno. Lo hemos efectuado en Excel relacionando los dos esquemas:

Como podemos observar, TAU_4(12)=40.

Podíamos añadir un bucle a nuestra función en VBasic para TAU_3, pero resultaría algo lenta. Por otra parte, no es difícil la comprobación con Cartesius, cambiando datos en las condiciones que usamos para el 84. Sin embargo, parece más útil comprobar el cálculo recordando la fórmula para TAU_3 que usa números triangulares

En efecto, para TAU_4 se pueden sustituir por tetraedros, pirámides triangulares, ya que las posibilidades dependen de tres dimensiones. Esta idea es correcta y se puede aplicar en este caso. Hay que recordar que la fórmula del tetraedro de orden n es TE(n)=n(n+1)(n+2)/6 (ver nuestra publicación Números piramidales:

 http://www.hojamat.es/publicaciones/piramidal.pdf)

En el caso de 12 quedaría:

12=2²*3

TAU4_(12)=TE(1+2)*TE(1+1)=3*4*5/6*2*3*4/6=10*4=40

Con ello queda comprobada esta técnica, que se amplía a TAU_5, TAU_6,…aumentando dimensiones a las pirámides.

Puedes repasar todo en la sucesión https://oeis.org/A007426, en la que están publicados los primeros valores de TAU(N):

1, 4, 4, 10, 4, 16, 4, 20, 10, 16, 4, 40, 4, 16, 16, 35, 4, 40, 4, 40, 16, 16, 4, 80, 10, 16, 20, 40, 4, 64, 4, 56, 16, 16, 16, 100, 4, 16, 16, 80, 4,…

Con esto, podemos seguir ampliando productos, pero con lo que tenemos ya se comprende la esencia de estas funciones TAU.

Menor múltiplo oblongo

Para su uso en los cálculos diarios que publico en Twitter, visito casi a diario la página The On-Line Encyclopedia of Integer Sequences!, (OEIS), http://oeis.org, fundada por N. J. A. Sloane. En la primavera de 2022 me llevé la sorpresa de ver una sucesión suya, del año 2021, referente a divisores de números oblongos. El tema de estos números no es muy popular en OEIS, y por eso me sorprendió verlos tratados por el mismo fundador de la página. Esto me ha llevado a tratar el tema con la mayor amplitud posible, según las sucesiones A345988 y A344005.

Lo que plantea N. J. A. Sloane en sus sucesiones es encontrar el oblongo más pequeño que es divisible entre un número dado. Si llamamos n a ese número, es claro que tiene dos múltiplos oblongos con seguridad, n(n+1) y (n-1)n. Por eso, se puede plantear una búsqueda infinita, como figura en OEIS, con la certeza  de que se detendrá:

(PARI) a(n) = for(m=1, oo, if((m*(m+1))%n==0, return(m))) \\ Felix Fröhlich, Jun 04 2021

Lo planteamos para hoja de cálculo en VBASIC. Como no podemos usar el símbolo de infinito, nos serviremos de un bucle WHILE sin fin:

Function menoroblongo(n)

Dim m, o

m = 1 ‘Comenzamos la búsqueda con 1

o = m * (m + 1) ‘Creamos el oblongo

While o Mod n <> 0 ‘Mientras no sea divisible, avanzamos el WHILE

m = m + 1

o = m * (m + 1)

Wend

menoroblongo = o

End Function

Se podía plantear con más eficiencia, pero funciona con rapidez y la hemos dejado así. Con esta función podemos encontrar las mismas soluciones de Sloane:

Uso del Buscador de Naturales

Nuestra herramienta de búsqueda de números naturales permite encontrar el menor oblongo múltiplo de un número dado. Lo que no puede construir es un listado como el de la tabla anterior, pero para explicar el concepto, a nivel elemental, nos vale.

Se puede descargar desde (http://www.hojamat.es/sindecimales/divisibilidad/herramientas/herrdiv.htm#buscador)

En la captura de pantalla siguiente figura la búsqueda en el caso de 80. Hemos buscado entre 80 y 6480=80*81, con las condiciones de ser oblongo y múltiplo de 80. Vemos que la solución es 240 como mínimo oblongo:

Casos particulares

Potencia de un primo

Si n es una potencia de un primo p, es claro que cualquier oblongo m(m+1) múltiplo de n ha de contener el factor primo p, luego lo contendrá m o m+1, porque no se puede repartir entre ellos, luego el mínimo será (n-1)n

El mínimo oblongo múltiplo de p^k (p primo) es (p^k-1)p^k

Así, el número 243=3^5 poseerá como menor oblongo múltiplo el 242*243=58806.

Es fácil comprobarlo con el Buscador:

Los dos únicos oblongos de la solución son 242*243 y 243*244. En las factorizaciones destaca el número 3 repetido cinco veces, luego son múltiplos de 243.

Números que solo poseen dos factores primos

Si un número presenta la factorización N=p^a * q^b con p y q primos, es claro que en un oblongo m(m+1) m será múltiplo de uno de los primos, y m+1 lo será del otro. Esto nos lleva a una ecuación diofántica: p^ax - q^by = ±1

Esta ecuación siempre tendrá solución, al ser los coeficientes primos entre sí, y la duda será si el segundo miembro deberá valer 1 o -1 y si las soluciones serán positivas.

Por ejemplo, el número N=3²*5³=1125 poseerá un oblongo múltiplo si 3²x - 5³y = ±1

Si tomamos el valor 1, será x=(1+125y)/9, con lo que habrá que buscar múltiplos de 125 que al sumarles 1 sean múltiplos de 9

Creamos una tabla con esos cocientes:

Observamos que (1, 14) es una solución y, en efecto, 14*9=126 y 1*125=125, luego m=125 y m+1=126, con lo que su producto será un oblongo múltiplo de 1125, 15750. Pero la cuestión es que no sabemos si es el mínimo, porque más abajo hay otra solución, 10, 139, en la que 139*9=1251 y 10*125=1250, con lo que el oblongo sería 1250*1251, claramente mayor que 15750.

A esto hay que añadir que habrá que repetir todo con el caso -1.

En nuestro ejemplo aparecería la solución 8, 111, es decir 8*125=1000 y 111*9=999, que también sería válida.

Vemos que la resolución es posible, pero que no nos garantiza el carácter de mínimo múltiplo.

Estudio diofántico

Podemos plantear

125x-9y=1 o bien 12x-9y=-1

Usamos WolframAlpha:

Caso +1

Paramétricas:

Caso -1

Paramétricas:

Se observa que en las dos paramétricas el mínimo valor positivo se alcanza si n=0.

En la primera tendríamos x=8, y=111, con lo que m=999 y m+1=1000, resultando el oblongo 999000.

En la segunda, x=1 y=14, m=125, m+1=126 y el oblongo el ya conocido

En la práctica es más rápido usar el Buscador ya que sabemos que existen soluciones.

En la siguiente captura de pantalla observamos que se ha buscado un oblongo múltiplo menor que 15750 y no se ha encontrado, luego este es el mínimo:

Caso general

Para un número con más de dos factores primos, bastará agruparlos en dos productos cuyos factores sean primos entre sí, y aplicar la misma técnica de ecuación diofántica, además de las técnicas de búsqueda ya estudiadas. Para encontrar el mínimo deberemos recorrer todos los pares de factores unitarios. Puedes leer la propuesta de Sloane en la sucesión A344005.