Semiprimos de la forma n²+k

 Una forma de obtener ideas para el blog es la de elegir un número al azar y buscarlo en OEIS (http://oeis.org), la Enciclopedia de sucesiones enteras. En una de estas exploraciones aparecieron las relaciones de los números semiprimos con los cuadrados. Me pareció un tema que podía dar juego, y aquí lo tenéis.

Comenzamos con aquellos semiprimos que sobrepasan a un cuadrado en un número k prefijado. Recorreremos algunos casos de k.

Podemos imaginar una función en la que identificamos n como semiprimo le restamos k y vemos si es cuadrado. Por motivos de rendimiento, es preferible pensarlo al revés, que sería averiguar si el número es de la forma n²+k y después comprobar si es semiprimo. Se puede disponer de una función essemiprimo (o, en algunos lenguajes de programación, hacer bigomega(n)=2), pero integraremos esa comprobación en el código general.

Se puede usar una función (semiconcuad(n,k)) construida para Excel o Calc, pero fácilmente trasladable a otros lenguajes. Usaremos en ella la función escuad, que identifica los cuadrados y que puede tener este listado:

Public Function escuad(n) As Boolean

 If n < 0 Then

escuad = False

Else

If n = Int(Sqr(n)) ^ 2 Then escuad = True Else escuad = False

End If

End Function

También usamos la función esprimo que puedes encontrar en cualquier buscador escribiendo “función esprimo hoja”. Se ha usado mucho en este blog, por lo que se puede omitir cualquier explicación sobre ella.

function semiconcuad(n,k) as boolean

dim d,m,r,q

dim noes as boolean

 If not escuad(n-k) or n=1 then semiconcuad=false:exit function

‘Si n-k no es cuadrado o n=1, sale del algoritmo

d=2:noes=true:r=sqr(n) ‘La raíz cuadrada de n es el tope de los divisores propios

while d<=r and noes ‘Se busca si es semiprimo

q=int(n/d) ‘Para cada divisor se busca el complementario

if n=d*q and esprimo(q) and esprimo(d) then noes=false ‘Busca dos factores primos

d=d+1

wend

semiconcuad=not noes ‘Es semiprimo

end function

Caso k=1

Si aplicamos una búsqueda para k=1 resultan estos primeros semiprimos:

10, 26, 65, 82, 122, 145, 226, 362, 485, 626, 785, 842, 901, 1157, 1226, 1522, 1765, 1937, 2026, 2117, 2305, 2402, 2501, 2602, 2705, 3365, 3482, 3601, 3722, 3845, 4097, 4226, 4762, 5042, 5777, 6085, 6242, 6401, 7226, 7397, 7745, 8465, 9026, 9217, 10001

Están publicados en http://oeis.org/A144255

En esa publicación se destaca que sus factores primos serán distintos, porque n²+1 no puede ser cuadrado. Por ejemplo, 26=5²+1=2*13.

Las bases de los cuadrados no presentan ninguna pauta aparente: 3, 5, 8, 9, 11, 12, 15, 19, 22, 25, 28, 29, 30, 34, 35, 39,…

Con la función presentada más arriba es fácil encontrar los primeros semiprimos de la forma n²+k. Es útil si deseamos saber si un número cualquiera cumple lo exigido, pero si solo nos interesa el listado, se puede sustituir por una subrutina. La que sigue escribe con rapidez las primeras 50 soluciones para k=1 en la celda 9,9 de la primera hoja:

sub listsemiconcuad() as boolean

 dim d,m,r,q,k

dim res$

dim noes as boolean

 k=1:res$=""

for n=1 to 50

m=n^2+1

d=2:noes=true:r=sqr(m)

while d<=r and noes

q=int(m/d)

if m=d*q and esprimo(q) and esprimo(d) then noes=false:res$=res$+", "+str$(m)

d=d+1

wend

next n

call escribestring(0,8,8,res$)

end sub

 Se obtiene el listado:

10,  26,  65,  82,  122,  145,  226,  362,  485,  626,  785,  842,  901,  1157,  1226,  1522,  1765,  1937,  2026,  2117,  2305,  2402,  2501

 Es interesante el listado en PARI publicado en esa página, pero requiere alguna corrección. Puedes usar este:

 print(select(n->bigomega(n)==2, vector(100, n, n^2+1)))

 Caso K=2

 Con nuestra función semiconcuad, haciendo k=2, es fácil obtener un listado:

 

En la tabla figuran el número semiprimo, la base del cuadrado correspondiente y la factorización del primero. Los semiprimos aquí tampoco serán cuadrados.

 Las bases de los cuadrados en la segunda columna están publicadas en http://oeis.org/A242330

 Con PARI obtenemos estas soluciones en forma de lista

 print(select(n->bigomega(n)==2, vector(100, n, n^2+2)))

 [6, 38, 51, 123, 146, 291, 326, 731, 843, 1227, 1371, 1766, 1851, 2306, 2603, 2811, 2918, 3027, 3602, 4227, 4358, 4763, 5186, 5331, 5627, 6243, 6891, 7058, 7571, 8102, 8651, 9411]

Igualmente, para k=3:

 

Las bases de los cuadrados, 1, 6, 16, 18, 20, 24, … están publicadas en http://oeis.org/A242331. Aquí sí hay una solución cuadrada, el 4, igual a 1²+3.

K=-1

 Este caso es interesante, porque en él el semiprimo equivale a n²-1=(n+1)(n-1) lo que nos lleva a que sus factores son primos gemelos, y por tanto el semiprimo pertenecerá a http://oeis.org/A037074

 Los primeros serán:

En la factorización de la derecha aparecen claramente los pares de primos gemelos.

Los números de la segunda columna, bases de los cuadrados correspondientes, será, pues, los promedios de los pares de primos gemelos.

 

Se puede plantear algo similar para los cubos, buscando semiprimos de la forma n³+k, pero está casi todo publicado y no tiene interés añadido. Lo dejamos aquí.