PDF de programación - Inevitables primos

Inevitables primos



1

Edición 2016

Colección Hojamat.es

© Antonio Roldán Martínez

http://www.hojamat.es







PRESENT ACIÓN


Nada sin números primos. Inciden en la mayoría de las cuestiones
sobre números, son escurridizos e inabarcables y nos sorprenden
siempre. La gran cantidad de cuestiones planteadas sobre ellos hace
necesaria una clasificación, pues si no, no habría forma de establecer
un orden mínimo.



No existe relación entre unas cuestiones y otras, pues se han ido
publicando según la actualidad o las lecturas del autor. No es negativa
esta situación, pues convierte esta publicación en un desenfadado y
caótico viaje por el mundo de los números primos. Además, estos
temas son los que más aparecen en los blogs y redes sociales, por lo
que
constituyen
y
experimentaciones.

buenos manantiales

de

propuestas



Como advertiremos en todos los documentos de esta colección, el
material presentado no contiene desarrollos sistemáticos, ni pretende
ser un manual teórico. En cada tema se incluirán cuestiones curiosas o
relacionadas con las hojas de cálculo, con la única pretensión de
explicar algunos conceptos de forma amena.



2





T AB L A D E C O N T E N I D O

Presentación .................................................................................... 2

Primos y potencias de 2 .................................................................. 5

Historia de una conjetura ............................................................... 5

Relaciones entre primos y potencias de 2 .................................... 11

Los huecos de un primo ............................................................... 11

Distancia binaria entre primos ...................................................... 14

¿Dónde están esos primos? ......................................................... 18

Nidos de primos ........................................................................... 18

Cerca del cuadrado de un primo .................................................. 19

Fórmulas que atraen primos ........................................................ 21

Damos vueltas a primos y al 18 ................................................... 24

Suma con el próximo primo ......................................................... 29

Los interprimos ............................................................................ 38

¿Qué hay entre dos primos consecutivos? .................................. 45

“Palprimos” (primos palindrómicos) .............................................. 59

Primos y sus parientes .................................................................. 65

Primos, semiprimos y casi primos ................................................ 65

Tozudos semiprimos .................................................................... 68

Proporción entre cubo y cuadrado ............................................... 70

Al complicar se simplifica ............................................................. 71

Pasito a pasito hacia la complejidad ............................................ 77

Más pasos hacia la complejidad .................................................. 83

Va a resultar que eres primo ........................................................ 90

3





Primos por todas partes ............................................................... 93

Semiprimos consecutivos ............................................................ 94

Los primos como conjunto ......................................................... 101

Primo y su número de orden ...................................................... 101

Restos en la función primo(n) .................................................... 105

Suma de dos números primos consecutivos .............................. 109

Miscelánea ................................................................................... 118

Dos búsquedas de primos ......................................................... 118

Uno de olimpiadas ..................................................................... 119

Soluciones ................................................................................... 120

Primos y potencias de 2 ............................................................. 120

¿Dónde están esos primos? ...................................................... 120

Primos y sus parientes ............................................................... 123

Miscelánea ................................................................................ 124

Apéndice ...................................................................................... 127



4


PRIMOS Y PO TENCI AS DE 2


H I S T O R IA D E U NA C O N J E T U R A


Hace unas semanas, con motivo del año nuevo, llegué a la expresión
2011=211-37. Una vez publicada, se me ocurrió preguntarme qué otros
números primos se podrían expresar igualmente como una potencia de
2 menos otro número primo.

Programé la hoja de cálculo para encontrar el menor número primo que
sumado a otro dado produce una potencia de 2. Todo fue bien salvo en
ciertos primos, como 7, 43, 101, 127, 151, 223,…Busqué e investigué
qué podían tener de particular esos primos y no llegué a ninguna
conclusión. Mejoré y simplifiqué el algoritmo y me di cuenta de que
simplemente los resultados sobrepasaban los registros de la hoja.

Así que definí, para todo número primo p, la función comple2(p), como
el menor número primo que sumado a p da como resultado una
potencia de 2.

Por ejemplo: comple2(857)=167, ya que 857+167=1024=210.

Implementé esta función en Excel y OpenOffice.org con este código:

Public Function comple2(n)
Dim b, a
b = 2
a = b - n
While esprimo(a) = 0
b = b * 2
a = b - n
Wend
comple2 = a
End Function


y así logré esta tabla



5





P

2

3

5

7

11

13

17

19

23

29

31

37

41

43

47

53

59

61

67

71

73

79

83

89

COMPLE2(P)

2

5

3

549755813881

5

3

47

13

41

3

97

2011

23

536870869

17

11

5

3

61

953

439

433

173

167

COMPLE2(P)

31

67108763

409

149

19

911

140737488355201

16253

887

373

107

2147483497

32611

349

89

83

3917

331

16193

2096959

59

313

33554221

¡Parece imposible!

P

97

101

103

107

109

113

127

131

137

139

149

151

157

163

167

173

179

181

191

193

197

199

211

223

6


Sólo existe un primo que resulta
igual a su complementario:
naturalmente el 2. La relación no es simétrica, porque por ejemplo
comple2(13)=3 y sin embargo comple2(3)=5

Al llegar al 223 fue imposible lograr su imagen. Los registros de datos
no daban más de sí. Por ello, me decidí a usar un programa CAS.
Como intento trabajar siempre con software gratuito, acudí a la
calculadora Wiris, con el algoritmo que se puede estudiar en la imagen,
y ahí se produjeron los resultados sorprendentes:

Comple2(223)=2261-223=



=37053468555941182535542715202780130513046395093004980492626426882532
20148477729

Comple2(809) 2636-809=

=28515253860138720116507322535626820780582678170303499566119953236870
469795054233665661955070733571248616514434834965045691804404508596487
4890791332482638386765749667147516559380179637015411927

Comple2(947)= 2278-947

485667223056432267729865476705879726660601709763034880312953102434726
071301302123597

Como no me acababa de fiar, acudí al programa wxMaxima con un
código similar, pero ajustando el valor inicial de la potencia para evitar
valores negativos:

n:223$
b:256$
c:b-n$
for i:1 unless primep(c) do (
b:b*2,



7


c:b-n
)$
display(c);

y confirmé los resultados anteriores.

Me di cuenta de que el cálculo de este complementario de un número
primo se podía complicar muchísimo, pero, ¿daría lugar en algún caso
a un bucle sin fin? ¿existiría algún número primo que nunca pudiera
ser completado a una potencia de 2?

Estudio con restos potenciales

Intenté cambiar el punto de vista del estudio, y en lugar de una
búsqueda ciega, me propuse usar restos potenciales. He aquí el
resultado.

Dado un número primo p, la expresión 2n-p representará un compuesto
si el resto potencial de 2n para cualquier posible divisor primo r coincide
con el resto de p respecto a ese mismo divisor r.

Lo vemos con un ejemplo: Si p=7, que descubrimos en la entrada
anterior que tenía un complementario muy grande (comple2(7)=
549755813881), podríamos recorrer los distintos números primos (no
considerando obviamente el 2, por cuestión de paridad) para ver si
coinciden los restos de las potencias de 2 con los de 7.

Si r=3, los restos potenciales del 2 respecto al 3 son alternativamente
iguales a 2,1,2,1,… y el resto de 7 respecto a 3 es igual a 1, luego la
expresión 2n-7 en sus valores positivos será divisible entre 3 de forma
alternativa: 24-7=9=3.3, 26-7=57=19.3, 28-7=249=83.3,…

Como buscamos que la expresión 2n-7 sea un número primo, ya
sabríamos que los valores n=2,4,6,8,…no nos valdrían.

r=5,

los

restos potenciales de 2

Para
la secuencia
2,4,3,1,2,4,3,1,…y el resto de 7 respecto a 5 es 2. Por tanto para los
valores de n=5,9,13,…la expresión 2n-7 también será compuesta.

forman

Imaginemos que recorremos todos los posibles divisores primos de 2n-
7, al igual que hemos hecho con 3 y 5 y cada vez que coincidan el
resto potencial de 2 con el de 7, tachamos esa posibilidad. Es como



8


una criba. Si al terminar el análisis quedan hueco