Los huecos de un primo

 (Con esta entrada participamos en el Carnaval de Matemáticas Edición 2.6, organizado en esta ocasión por La vaca esférica)


Los cinco primos de Fermat conocidos, 3, 5, 17, 257 y 65537, tienen en común que su representación en el sistema de numeración binario está formada por un 1, un conjunto de ceros y al final otro 1. Son números con un gran hueco entre dos unidades. Por ejemplo el 65537 está representado por 10000000000000001. Sólo se conocen esos cinco primos con esa estructura (es fácil demostrar que los de Fermat son los únicos posibles).

¿Habrá primos con otras estructuras posibles en sus huecos entre unos?

Podíamos buscar los que estuvieran formados por dos intervalos iguales, como 100010001. ¿Habrá alguno? Sí, pero sólo se conocen tres: 7, 73 y 262657. Puedes leer algunos detalles en http://oeis.org/A051154

¿Y si buscáramos primos con estructuras similares a 1000100010001, con cuatro unos? Pues yo no lo haría. Seguro que son compuestos ¿por qué? En realidad no debes probar con ningún ejemplo que contenga un número par de unos situados de forma equidistante.

No hemos encontrado más ejemplos con un número impar de huecos similares.

Podemos renunciar a la periodicidad de los ceros. Pueden existir primos con dos unos iniciales y el resto ceros hasta el último uno. Los hemos buscado con hoja de cálculo y aparecieron 7, 13, 97, 193, 769, 12289, 786433, 3221225473, 206158430209,…El primero, 7, sólo presenta los unos, 111, pero los demás son espectaculares, como 206158430209 con expresión 11000000000000000000000000000000000001.
Puedes ver los siguientes en http://oeis.org/A039687

El problema inverso de encontrar estructuras del tipo 1000000011 ya está también resuelto y publicado en http://oeis.org/A057733

Podíamos buscar otros con dos unos al principio y al final, pero me temo que sería inútil ¿no?. Ahí no hay primos.

Otras estructuras

Los siguientes primos poseen sus huecos en magnitud creciente:
3                                 11
11                               1011
68990043211             1000000010000001000001000010001001011
36064050381096011 10000000001000000001000000010000001000001000010001001011

Con la estructura simétrica de conjuntos de ceros de longitud creciente de derecha a izquierda, al menos con hoja de cálculo, sólo he encontrado el 3 y el 13.

A estos otros les llamo “primos piano”:

26417           110011100110001
422657         1100111001100000001
108199937    110011100110000000000000001

Si deseas saber el porqué, mira el teclado de un piano.

Este otro es similar, con otra visión del “teclado”:
989721526273  es un primo con estos huecos:
1110011001110000000000000000000000000001
 
Y estos otros son más simétricos:

134323393       1000000000011001110011000001
137442334721  10000000000000001100111001100000000001

¿Deseas investigar otras estructuras? Puedes probar con

Números repunits (o repunos o repitunos): No tienen huecos en el sistema binario. Busca por ahí cuáles son primos, y verás qué escasez.

Números de Carol: Sólo tienen un hueco, pero bien situado. Tampoco hay muchos primos entre ellos.

Números de Thabit: Los números del tipo 3.2ⁿ-1 se llaman números de Thabit y en el sistema de numeración binario vienen representados por las cifras 1, 0 seguidas de la cifra 1 repetida hasta terminar la expresión. Por ejemplo, el número de Thabit 786431 viene representado por 10111111111111111111. Investiga por ahí cuáles son primos.

Obtención de la lista de divisores

Algoritmo con hoja de cálculo

(Si no te interesa la programación en Basic puedes dejar de leer)

Para encontrar los divisores de un número N la búsqueda más simple consiste (salvo alguna pequeña modificación que la acelere) en recorrer todos los números menores o iguales a N y tomar nota de los que son divisores suyos. Es muy sencilla de programar y sólo ocupa unas pocas líneas de código. Tiene el inconveniente de que para números de más de cuatro o cinco cifras decimales resulta muy lenta en hoja de cálculo, que es la herramienta que usamos en este blog.

Un algoritmo más rápido consiste en reproducir en la hoja el esquema que siempre se ha usado en las clases de Matemáticas, el que desarrolla las distintas potencias del primer divisor primo y después las combina con las de los demás en una tabla bidimensional como la siguiente, que se corresponde con los divisores del número 33075=3³*5²*7²


3        1          3          9          27
5        5        15         45        135
        25        75       225        675
7        7        21         63        189
        35      105       315        945
       175     525     1575      4725
        49     147        441      1323
       245    735      2205      6615
     1225    3675   11025    33075


En ella se han situado en la primera columna los factores primos, en la primera fila las potencias del 3 y en las demás filas los distintos productos que se pueden formar entre las potencias, sumandos formados en la fórmula

de la obtención de sigma(N).

Para poder construir este esquema en la hoja necesitamos saber qué factores primos posee el número y con qué exponentes. La siguiente subrutina en Basic nos los proporciona:

Global p(50) as long  Se definen las variables p para los factores, e los exponentes y np el número total
Global e(50) as integer
Global np%



Sub sacaprimos(a)
Dim f,i
dim vale as boolean


f=2:i=1:e(i)=0:vale=false:np=0
while f<=a  El bucle while_wend divide el número entre el factor todas las veces posibles
if esprimo(f) then
while a/f=int(a/f)  Es divisor primo
vale=true
p(i)=f
e(i)=e(i)+1  aumenta el exponente
a=a/f
wend
if vale then
np=np+1  aumenta el número de factores
i=i+1:e(i)=0 se inicia un nuevo exponente
end if
vale=false
end if
f=f+1 buscamos otro factor primo
wend
End sub

Con este código obtenemos la lista de factores primos p(i), la de exponentes e(i) y el número total de factores primos np.

Al usar estos datos la búsqueda de divisores se simplifica mucho, pues todo el trabajo consistirá ahora en construir la tabla que estudiamos en nuestros años escolares:

(a) Formamos una fila con las potencias posibles del primer factor primo. Tomamos nota de que la altura de la tabla es de 1. También recogeremos el dato de la variable fila en la que se han escrito.

(b) Vamos multiplicando esas potencias de la primera fila por todas las de los otros primos, pero teniendo cuidado de:

* En cada nuevo primo la altura queda multiplicada por e(i)+1, que es el número de sus potencias posibles.

* En cada nuevo producto deberemos incrementar la variable fila en una unidad, para que se vaya formando la tabla hacia abajo.

* Deberemos usar muchos bucles anidados, porque intervienen as variables del número de potencias de la primera fila, el de las del resto de primos y las del número de primos diferentes.

Un posible código en OpenOffice sería:

sub todosdivisores


dim i,j,k,l, altura,fila
dim divi as long


Rellena la primera fila con las potencias del primer primo
if np>=1 then
StarDesktop.CurrentComponent.sheets(1).GetCellByPosition(2,11).value=p(1)
for k=0 to e(1)
StarDesktop.CurrentComponent.sheets(1).GetCellByPosition(3+k,11).value=p(1)^k
next k
end if


Va multiplicando las potencias de los demás primos
if np>=2 then
altura=1:fila=12
for k=2 to np  Este bucle recorre los primos
StarDesktop.CurrentComponent.sheets(1).GetCellByPosition(2,fila).value=p(k)
for j=1 to e(k)  Recorre las potencias del primo actual
for i=1 to altura Recorre todos los divisores anteriores
for l=0 to e(1)  Ídem los elementos de cada fila
divi=StarDesktop.CurrentComponent.sheets(1).GetCellByPosition(3+l,10+i).value
divi=divi*p(k)^j  Efectúa el producto y lo escribe
StarDesktop.CurrentComponent.sheets(1).GetCellByPosition(3+l,fila).value=divi
next l
fila=fila+1  Una vez escritos, aumenta la fila
next i
next j
altura=altura*(e(k)+1)  La altura se amplía
next k
end if
end sub

Pues ya tienes una idea. El resto es cosa tuya. Seguro que la mejoras.