Un ejemplo claro es el de sumar números compuestos de varios divisores y que el resultado resulte ser un número primo. Así, 60=22*3*5 y 931=72*19 y sin embargo su suma 991 es un número primo. La operación de sumar ha significado una pérdida de complejidad.
Otro ejemplo: En una entrada anterior (http://hojaynumeros.blogspot.com/2011/06/un-par-de-abundantes.html) vimos que todo número par mayor que 46 es suma de dos abundantes. Esta operación también puede suponer una pérdida de complejidad. Así, 18 y 40, ambos abundantes, con su suma producen el número 58, que es deficiente.
Estudiaremos con detenimiento otro ejemplo: La función sigma (http://hojaynumeros.blogspot.com/2011/03/la-familia-de-las-sigmas-2.html) suma todos los divisores de un número. Es una operación que requiere varios pasos y bastantes operaciones. ¿Podrá producir resultados primos o semiprimos?
Podríamos intentar una búsqueda simple con hoja de cálculo: recorreríamos todos los números en un cierto rango, calculando su sigma y viendo si es prima o semiprima. El resultado sería el siguiente (para números menores que 1000):
Número N | Sigma | Tipo | Factores de N | Factores de Sigma(N) |
3 | 4 | Semiprimo | 3 | 2 2 |
4 | 7 | Primo | 2 2 | 7 |
5 | 6 | Semiprimo | 5 | 2 3 |
8 | 15 | Semiprimo | 2 2 2 | 3 5 |
9 | 13 | Primo | 3 3 | 13 |
13 | 14 | Semiprimo | 13 | 2 7 |
16 | 31 | Primo | 2 2 2 2 | 31 |
18 | 39 | Semiprimo | 2 3 3 | 3 13 |
25 | 31 | Primo | 5 5 | 31 |
36 | 91 | Semiprimo | 2 2 3 3 | 7 13 |
37 | 38 | Semiprimo | 37 | 2 19 |
49 | 57 | Semiprimo | 7 7 | 3 19 |
50 | 93 | Semiprimo | 2 5 5 | 3 31 |
61 | 62 | Semiprimo | 61 | 2 31 |
64 | 127 | Primo | 2 2 2 2 2 2 | 127 |
73 | 74 | Semiprimo | 73 | 2 37 |
81 | 121 | Semiprimo | 3 3 3 3 | 11 11 |
100 | 217 | Semiprimo | 2 2 5 5 | 7 31 |
121 | 133 | Semiprimo | 11 11 | 7 19 |
144 | 403 | Semiprimo | 2 2 2 2 3 3 | 13 31 |
157 | 158 | Semiprimo | 157 | 2 79 |
169 | 183 | Semiprimo | 13 13 | 3 61 |
193 | 194 | Semiprimo | 193 | 2 97 |
225 | 403 | Semiprimo | 3 3 5 5 | 13 31 |
256 | 511 | Semiprimo | 2 2 2 2 2 2 2 2 | 7 73 |
277 | 278 | Semiprimo | 277 | 2 139 |
289 | 307 | Primo | 17 17 | 307 |
313 | 314 | Semiprimo | 313 | 2 157 |
361 | 381 | Semiprimo | 19 19 | 3 127 |
397 | 398 | Semiprimo | 397 | 2 199 |
400 | 961 | Semiprimo | 2 2 2 2 5 5 | 31 31 |
421 | 422 | Semiprimo | 421 | 2 211 |
457 | 458 | Semiprimo | 457 | 2 229 |
529 | 553 | Semiprimo | 23 23 | 7 79 |
541 | 542 | Semiprimo | 541 | 2 271 |
576 | 1651 | Semiprimo | 2 2 2 2 2 2 3 3 | 13 127 |
578 | 921 | Semiprimo | 2 17 17 | 3 307 |
613 | 614 | Semiprimo | 613 | 2 307 |
625 | 781 | Semiprimo | 5 5 5 5 | 11 71 |
661 | 662 | Semiprimo | 661 | 2 331 |
673 | 674 | Semiprimo | 673 | 2 337 |
729 | 1093 | Primo | 3 3 3 3 3 3 | 1093 |
733 | 734 | Semiprimo | 733 | 2 367 |
757 | 758 | Semiprimo | 757 | 2 379 |
841 | 871 | Semiprimo | 29 29 | 13 67 |
877 | 878 | Semiprimo | 877 | 2 439 |
961 | 993 | Semiprimo | 31 31 | 3 331 |
997 | 998 | Semiprimo | 997 | 2 499 |
Se ve que en algunos casos, como el del 576, la pérdida de complejidad es notable.
Concretemos un poco, y supongamos que N es semiprimo: N=p*q con p y q ambos primos. ¿Cuándo su sigma resultaría ser prima o semiprima?
Podemos razonar que p ha de ser igual a q: si son ambos iguales a 2, se cumple, porque 4=2*2 y sigma(4)=1+2+4=7 que es primo. En caso contrario, uno de ellos, supongamos que sea p, ha de ser impar, con lo que sigma(N)=(1+p)(1+q)=2h(1+q), con al menos tres factores, por lo que no puede ser primo ni semiprimo. En resumen: N ha de tener la forma de N=p2 con p primo. Puedes comprobarlo en la tabla anterior, pues todos los valores de N que presentan dos factores son cuadrados de primos (aunque no están todos)
Número N | Sigma | Factores de sigma |
4 | 7 | 7 |
9 | 13 | 13 |
25 | 31 | 31 |
49 | 57 | 3 19 |
121 | 133 | 7 19 |
169 | 183 | 3 61 |
289 | 307 | 307 |
361 | 381 | 3 127 |
529 | 553 | 7 79 |
841 | 871 | 13 67 |
961 | 993 | 3 331 |
En efecto, no están todos los cuadrados de primos, y además, los factores que aparecen en sigma(N) son el 3 y números primos del tipo 6m+1. ¿Por qué? Aclararemos algo a continuación. Repasaremos con ello la teoría de los restos cuadráticos:
Para este tipo de números sigma(N)=1+p+p2. Como el caso de p=2 está resuelto, podemos suponer que p>2 y por tanto impar, N será impar y sigma(N) también. Por tanto, si poseen divisores h, estos serán mayores que 2. Llamemos k a un posible divisor de sigma(N). Al ser primo impar, podremos aplicar la teoría de los restos cuadráticos (ver Parra Restos cuadráticos y Ley de reciprocidad cuadrática http://hojamat.es/parra/restocuad.pdf)
(NOTA: Por razones tipográficas usamos el signo = en las congruencias).
Si k es un divisor, se ha de cumplir que 1+p+p2=0 (mod k). Si multiplicamos por 4 quedará:
4+4p+4p2=(2p+1)2+3=0 (Mod k) (1)
Esta congruencia puede darse en dos situaciones:
(a) Que sea k=3. Con ello se cumpliría (1) siempre que 2p+1=0 (mod 3), 2p=2 (mod 3), p=1 (mod 3) (se puede dividir entre 2 porque es primo con k), es decir que p ha de ser de la forma 3m+1. Esta es condición necesaria para que k=3, pero no suficiente.
(b) Que k no sea 3. En ese caso el número -3 ha de ser resto cuadrático respecto a k (Ver Parra http://hojamat.es/parra/restocuad.pdf). Para que esto se cumpla, k ha de tener la forma k=6m+1. Esto completa el razonamiento: k ha de ser 3 o del tipo 6m+1, como puedes comprobar en la tabla anterior.
Una vez determinada la naturaleza de los factores (que sean el 3 u otro primo de la forma 6m+1), debemos tener en cuenta que sigma(N) puede tener un sólo factor y por tanto ser primo, o bien dos, pasando a ser semiprimo.
(A) Sigma(N) es primo
Para el caso de sigma prima puedes consultar https://oeis.org/A023194. Es interesante que leas algunos comentarios, pero ten en cuenta que aquí solo hemos estudiado el caso en el que N era el cuadrado de un primo. Por tanto, nuestra secuencia de estos primos
2, 3, 5, 17, 41, 59, 71, 89, 101, 131, 167, 173, 293, 383, 677, 701, 743, 761, 773, 827, 839, 857, 911, 1091, 1097, 1163, 1181, 1193, 1217…
es una subsecuencia de https://oeis.org/A055638 y coincide con https://oeis.org/A053182 en la que figura un comentario de nuestro amigo Claudio Meller.
Todos sus elementos, salvo los primeros 2 y 3, son números primos de la forma 6m-1.
(A) Sigma(N) es semiprimo
En este caso los resultados son:
Primo p | Sigma(p*p) | Factores de Sigma |
7 | 57 | 3 19 |
11 | 133 | 7 19 |
13 | 183 | 3 61 |
19 | 381 | 3 127 |
23 | 553 | 7 79 |
29 | 871 | 13 67 |
31 | 993 | 3 331 |
43 | 1893 | 3 631 |
47 | 2257 | 37 61 |
53 | 2863 | 7 409 |
73 | 5403 | 3 1801 |
83 | 6973 | 19 367 |
97 | 9507 | 3 3169 |
103 | 10713 | 3 3571 |
113 | 12883 | 13 991 |
127 | 16257 | 3 5419 |
157 | 24807 | 3 8269 |
179 | 32221 | 7 4603 |
197 | 39007 | 19 2053 |
199 | 39801 | 3 13267 |
223 | 49953 | 3 16651 |
227 | 51757 | 73 709 |
Como se ve, los factores primos de Sigma sólo pueden ser el 3 o los del tipo 6m+1