Números y hoja de cálculo: Semiprimos con plantilla

martes, 9 de abril de 2024

Semiprimos con plantilla

(Ver entradas anteriores sobre números semiprimos)

Los semiprimos del tipo N=pq admiten otros condicionamientos, a los que llamaremos “plantillas”. Por ejemplo, semiprimos del tipo p(p+4). Los de tipo p(p+2), producto de dos primos gemelos, se estudian en otra parte de esta publicación.

N=p(p+4)

Los pares de primos p y p+4 son llamados “cousin” en inglés. En nuestro idioma, lo de “primos primos” no suena bien, pero así se designan en la Wikipedia.

Búsqueda directa

Con el Buscador hemos organizado las condiciones de forma que las soluciones caen en la segunda columna:

Al ser 4 la diferencia entre los dos factores, ambos serán del tipo 4k+1 o bien del 4k+3. En el primer caso, el semiprimo se podrá descomponer en dos sumas de cuadrados, como le ocurre al 12317=109*113, que admite estas dos:

12317=94^2+59^2=101^2+46^2

En los otros casos, como el 4757, no admitirán descomponerse en suma de dos cuadrados, por ser sus factores del tipo 4k+3.

Ayuda algebraica

Para encontrar el valor de p de forma directa nos basamos en dos desigualdades:

N=p(p+4)=p²+4p<p²+4p+4=(p+2)²

N=p(p+4)=p²+4p>p²+2p+1=(p+1)²

Según esto, p será la parte entera de la raíz cuadrada de N menos una unidad:

Por ejemplo, lo aplicamos a 16637, con el lenguaje de las hojas de cálculo:

p=ENTERO(RAIZ(16637)-1)=127, lo que es correcto, porque 16637=127*131

Esto nos permite reconocer semiprimos del tipo p(p+4) sin tener que recorrer los posibles divisores de N. Basta encontrar p, exigir que p y p+4 sean primos y que su producto sea igual a N.

Con este procedimiento hemos averiguado en un tiempo de cálculo razonable, que entre 1000000 y 1100000 solo existe un semiprimo de este tipo:

1022117=1009*1013

Más álgebra

Aún podemos concretar mejor las búsquedas de estos semiprimos. Con este desarrollo lo aclararemos muy bien:

N=pq=p(p+4)=p²+4p

Es fácil ver, según esto, que N+4 es un cuadrado, luego para buscar N podemos restringirnos a los números que equivalen a k²-4 para un valor adecuado de k. Así que, en cualquier búsqueda nos dedicaremos a aquellos números de este tipo, con el consiguiente ahorro de tiempo. Además, si escribimos la equivalencia como p²+4p-N=0, podemos hallar p de forma directa. Sería:

Al ser 4+N cuadrado, la solución es entera, como era de esperar.

Esto simplifica la búsqueda, pues comenzamos por exigir que 4+N sea cuadrado perfecto. Después calculamos p con la fórmula anterior, y bastará exigir que tanto p como p+4 sean primos.

Así lo hemos efectuado en esta búsqueda, en el intervalo (10000,50000):

Como era de esperar, las soluciones coinciden con las obtenidas con otros métodos.

Prescindimos del cuadrado

Si lo que nos interesa es conseguir una lista de soluciones a partir de la unidad, podemos prescindir del carácter de cuadrado de N+4, ya que podemos crear una variable k=1 e irle sumando los impares en cada paso, con lo que se irán construyendo los cuadrados, pues 1+3=4, 4+5=9, 9+7=16,…

Así lo hemos construido en PARI, y nos devuelve, por ejemplo, todas las soluciones menores que 10^6 de forma casi instantánea en su aplicación GP/PARI CALCULATOR, y con cierta rapidez en su web

https://pari.math.u-bordeaux.fr/gp.html

El código es

k=1;d=3;tope=10^6;while(k<=tope,k=k+d;n=k-4;p=-2+sqrtint(k);if(isprime(p)&&isprime(p+4),print(k-4,", ",p,", ",p+4));d+=2)

El tope, fijado en 10^6, se puede cambiar según sean nuestros objetivos. Los primeros resultados son:

Caso general

Los razonamientos útimos sobre el tipo de semiprimo p(p+4) se generalizan fácilmente a N=p(p+2k). Nos limitamos a traducirlos:

N ha de ser del tipo m²-k², para un valor de m adecuado. Expresado de otra forma, N+k² ha de ser cuadrado, y al tener raíz cuadrada entera, nos permite despejar p:

Después de este cálculo, basta exigir que tanto p como p+2k sean primos.

Como ejemplo, buscamos todos los semiprimos del tipo p(p+12) entre 10000 y 50000:

Por último, estos serían los primeros de seis cifras del tipo p(p+20):

Ha sido entretenido el estudio. Lo dejamos aquí.

Otras plantillas

El tema de plantillas de tipo polinómico es muy extenso, por lo que sólo estudiaremos algunas más como ejemplo.

N=p(2p+1)

Comenzamos con el Buscador para ir iniciando el estudio con algo intuitivo.

Los semiprimos aparecen en la columna de Detalles.

Es claro que p es un primo de Sophie Germain y 2p+1 un primo seguro.

Están publicados en

https://oeis.org/A156592:

10, 21, 55, 253, 1081, 1711, 3403, 5671, 13861, 15931, 25651, 34453, 60031, 64261, 73153, 108811, 114481, 126253, 158203, 171991, 258121, 351541, 371953, 392941, 482653

Todos estos semiprimos son números triangulares de orden par. La razón es que se pueden escribir como 2n(2n+1)/2=T(2n).

Esta propiedad nos facilita el trabajo, porque un criterio previo sería que N fuera triangular, y tenemos un criterio adecuado, y es que 1+8N sea un cuadrado. En realidad, si no se conociera este criterio, aparecería de forma natural con alguna manipulación algebraica. En efecto, se cumplirá siempre que

2p²+p-N=0

Despejamos p y resulta:

Luego para identificar estos números hay que comenzar con que 1+8N sea cuadrado y el numerador múltiplo de 4.

Todo este desarrollo se justifica porque para manejar números grandes no sería eficiente comenzar por la unidad, como hemos procedido con el Buscador, sino que es más útil calcular el valor de p si se cumplen las condiciones.

Así que debemos proceder por verificar los criterios, el de que 1+8N sea cuadrado y el que el valor de p sea entero (en realidad, basta con lo segundo, pero así queda más claro). Después verificaríamos si tanto p como p+2k son primos:

En Vbasic exigiríamos

D=1+8N
P=(-1+RAIZ(D))/4
ESCUAD(D) AND ESENTERO(P)

Después vendría el que tanto P como 2P+1 sea primos.

Procediendo así, obtenemos los mismos resultados que con el Buscador:

Es cierto que este método es muy útil para búsquedas de números grandes. En la imagen puedes consultar el primer semiprimo de este tipo a partir de 10^6: