jueves, 29 de noviembre de 2012

Más pasos hacia la complejidad (1)



En estas entradas de nuestro blog

http://hojaynumeros.blogspot.com.es/2011/11/pasito-pasito-hacia-la-complejidad.html
http://hojaynumeros.blogspot.com.es/2011/11/pasito-pasito-hacia-la-complejidad_25.html
http://hojaynumeros.blogspot.com.es/2011/11/pasito-pasito-hacia-la-complejidad_29.html

estudiamos los casos en los que partiendo de un número simple, como es un primo, al avanzar o retroceder unidad a unidad iban apareciendo números con cada vez más factores primos: semiprimos, 3-casiprimos, 4-casiprimos,…hasta que se rompía esa tendencia. Dábamos el ejemplo de 807905281, que es primo y cumple que

807905282 = 2*403952641
807905283 = 3*15733*17117
807905284 = 2*2*1871*107951
807905285 = 5*11*43*211*1619
807905286 = 2*3*3*3*37*404357
807905287 = 7*7*7*7*29*41*283

Si recordamos que la función BIGOMEGA cuenta los factores primos de un número teniendo en cuenta los repetidos, la situación anterior se podría representar así:



Revisando esta entrada para su inclusión en el resumen anual, nos hemos dado cuenta de que el tema de alcanzar complejidades mayores moviendo un número hacia adelante y hacia atrás daba para más estudios, por lo que os los presentamos en esta entrada.

¿POR QUÉ AVANZAR DE UNO EN UNO?

Se dan casos en los que N es primo y N+2 semiprimo:

2, 7, 13, 19, 23, 31, 37, 47, 53, 67, 83, 89,...

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

Toma un número de la sucesión. Por ejemplo, el 53. Le sumas 2 y se convierte en 55=5*11, que es el semiprimo más cercano (esto no lo exigimos y ya lo veremos más adelante), porque 54=2*3*3*3.

Estos números son de la forma p*q-2, con p y q primos.

También puede ser N primo y N-2 semiprimo

11, 17, 23, 37, 41, 53, 59, 67, 71, 79, 89, 97, 113,...

http://oeis.org/A063638

Estos números son de la forma p*q+2, con p y q primos.

Saltos de tres unidades

Existen números p primos con p+3 semiprimo

3, 7, 11, 19, 23, 31, 43, 59, 71, 79, 83, 103,…

http://oeis.org/A092109

Son del tipo p=4k+3 (¿por qué?) y cumplen que (p+3)/2 es primo (piensa que p+3 es par y semiprimo)

Existen números p primos con p-3 semiprimo

7, 13, 17, 29, 37, 41, 61, 89, 97, 109, 137,...

http://oeis.org/A089531

Sus propiedades son simétricas de las de los anteriores

Función DISTSEMI

En lugar de seguir buscando saltos mayores podemos definir dos funciones: DISTSEMI, que medirá la distancia mínima k tal que P sea primo y P+k sea semiprimo y DISTSEMI2, que hará lo mismo por la izquierda, ver el valor mínimo k para el que P sea primo y P-k semiprimo.

El código de la primera podría ser

Function distsemi(p)
Dim d, k
Dim noess

d = 0
If esprimo(p) Then
k = 0
noess = True
While noess
k = k + 1
If essemiprimo(p + k) Then d = k: noess = False
Wend
End If
distsemi = d
End Function

Se entiende fácilmente, e igual, con dos pequeñas variaciones podemos definir DISTSEMI2.


FUNCIÓN DISTSEMI2

Los valores de esta segunda función están publicados en http://oeis.org/A121885
No se puede definir para P=2 ni para P=3. Para los siguientes a partir del 5 tenemos los valores



5
7
11
13
17
19
23
29
31
37
1
1
1
3
2
4
1
3
5
2


Salvo para 2 y 3 esta función está definida para todo número natural, porque el conjunto de los semiprimos inferiores al mismo no está vacío, ya que al menos contiene al 4, y al ser un conjunto acotado de naturales tendrá un máximo Q (ver http://oeis.org/A102415) y la diferencia entre P y Q será el valor de DISTSEMI2 buscado.

Su gráfica para los primeros primos tiene este aspecto
















Si vas leyendo los valores de X que se corresponden con valores concretos de Y te resultarán sucesiones similares a las que hemos presentado al principio. Así, los mínimos se corresponden con los primos P en los que P-1 es semiprimo, contenidos en https://oeis.org/A005385 y ya tratados en este blog.

En el nivel 2 están estos números primos

17, 37, 41, 53, 67, 71, 79, 89, 97, 113, 131, 157, 163, 211, 223, 239, 251, 269, 293, 307, 311, 331, 337, 367, 373, 379, 397, 409, 419, 439, 449, 487, 491, 499,…,

en los que p-2 es el semiprimo más cercano por la izquierda Los hemos publicado en https://oeis.org/A217195 con el siguiente código:

(PARI) forprime(p=3, 9999, bigomega(p-2)==2 && bigomega(p-1)!=2 & print1(p", "))

Y en el 3

13, 29, 61, 109, 137, 149, 181, 197, 229, 257, 277, 281, 317, 349, 389, 401, 457, 461, 541, 557, 569, 617, 677, 761, 797, 821, 929, 937, 977,…

(Los publicamos en https://oeis.org/A217197)

con el código

(PARI) forprime(p=5, 9999, bigomega(p-3)==2 && bigomega(p-1)!=2 && bigomega(p-2)!=2 & print1(p", "))

Entre los máximos destacan el 103 (ver gráfico), que necesita 8 pasos hacia atrás para encontrar el primer semiprimo. Entre los primos menores que 1000 el máximo se da en el 647, que está a 12 unidades de su máximo semiprimo inferior y entre los menores de 10000 se da en el 6381, con DISTSEMI2(6581)=22
Aquí tienes una lista de los números que presentan máximos respecto a sus anteriores:

13           3
19           4
31           5
101         6
103         8
607       10
647       12
1433     15
2699     18
6581     22
17989   24
32803   26
36011   30
36013   32
36017   36

No crecen mucho los valores máximos, porque al ir aumentando el valor de P van siendo posibles cada vez más combinaciones de dos primos que podrán estar bastante cerca de P. Esto es una observación nada más, sin fundamento riguroso.

Se impone una conjetura: ¿Tenderá a cero el cociente DISTSEMI2(P)/P con P primo al tender P a infinito? Lo dejamos ahí para quien tenga más preparación en estos temas.