miércoles, 21 de septiembre de 2011

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.2n-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.

jueves, 15 de septiembre de 2011

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=33*52*72


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.

sábado, 3 de septiembre de 2011

Baldosas, pasos y farolas

Después del descanso veraniego, iniciamos el cuarto curso de este blog. Un saludo afectuoso a quienes nos siguen.

Comenzamos con unas ideas para el aula

Como casi todos los profesores de Matemáticas de mi generación he intentado en clase la estimación de distancias, alturas o tiempos, a veces terminada con un aleccionador fracaso. Lo sabréis si habéis intentado medir alturas con medidores de ángulos o sombras. Creo que es una actividad muy educativa, especialmente si no se usan instrumentos de precisión, sino medidas de nuestro propio cuerpo (pasos, pies, manos,..), elementos repetidos (baldosas, vagones de un tren, farolas,…) o representaciones a escala, como los mapas de Google.

Para garantizarnos un resultado honorable y una buena práctica de medición creo que tenemos que contar con al menos estos elementos:

* Repetición de elementos razonablemente iguales (como medir por pies) y, a ser posible, pertenecientes a conjuntos distintos. Así se realizan varias mediciones.
* Un elemento al menos cuya medida real sea fiable: longitud de una baldosa, distancia entre dos bancos de un paseo, altura de un piso…
* Uso de fracciones comparativas entre medidas. Lo que desde la antigüedad hemos llamado “razón entre dos magnitudes”.
* Uso, si es posible, de la media aritmética entre estimaciones.

Ilustro estas ideas con un ejemplo que me sirvió de ejercicio y entretenimiento en mis últimas vacaciones.

Pasé unos días junto a las Salinas de San Pedro del Pinatar (Murcia, España). Un paseo muy popular es el que une dos molinos salineros abandonados, que tiene una longitud aproximada de tres kilómetros. Comienza siendo un paseo urbano (tramo A), frecuentado por quienes se aplican la terapia de los barros de las salinas, y termina como una senda ecológica (tramo B) que va a desembocar al mar abierto.








Como lo recorría con frecuencia, me planteé efectuar una estimación de la distancia total entre los dos molinos usando sólo los elementos propios de un paseo y los de la misma ruta. Para ello contaba con lo siguiente:

Pasos

La parte urbanizada del camino, quizás para estimular a las personas de cierta edad que lo usan, contiene en el pavimento la referencia a la distancia recorrida de 50 en 50 metros. Al final de esta primera parte A figura la distancia de 1182 m. Esa era la parte “fiable” de mi estimación.

Medí los pasos que tenía que dar para recorrer 50 m. Repetí varias veces esa medida contando mentalmente y me resultó una media aproximada de 60 pasos por cada 50 metros. Ya tenía un primer elemento repetitivo razonablemente conocido. Conté los pasos del segundo tramo, con la idea de multiplicarlos por la razón 50/60=5/6. No es fácil contar tantos pasos (intentadlo y veréis) y al final sólo sabía que serían unos 1850, pero con poca seguridad. Esto me daba una primera estimación: 1850*5/6= 1542 metros.

Postes

Al segundo día me di cuenta de que existían unos pequeños postes, de unos 40 cm. de altura, aparentemente equidistantes. Los medí por pasos varias veces y así confirmé que lo eran. Los conté y la parte A contenía 76 y la parte B, cuya distancia deseaba estimar, 102. Ya tenía mi segunda razón fiable: 102/76 = 51/38



Mi siguiente estimación sería 1182*51/38 = 1586 metros. Me quedaba la sospecha de que en el tramo B la distancia entre postes fuera algo menor, porque el número de pasos se acercaba en él a 19 y en el A a 20, pero no estaba seguro.

Minutos

Como sospechaba que los postes podían presentar diferencias en sus distancias mutuas, cronometré varias veces mi paseo por los dos tramos, obteniendo 17 minutos para el tramo B  y 13 para la distancia conocida 1182 m., o algo más conservando la proporción. Fue una buena noticia para mí, pues confirmó mi buen estado de forma en esos días. Así que mi segunda razón podía ser 17/13 y la estimación 1182*17/13 = 1545.

Google

Sólo me quedaba acudir a un mapa en Internet. Me costó trabajo, pues no se veía bien la transición entre los dos tramos. Imprimí el mapa, pero la diferencia con las otras estimaciones era demasiado grande. Recordé entonces que el paseo urbanizado terminaba en una especie de semicírculo. Amplié la visión lo más posible hasta que apareció, cuidando después de identificar los accidentes del terreno cuando alejé el zoom para imprimir. Medí con una regla de dibujo en el mapa impreso y me resultó la razón 103/82   estimando con ella una distancia de 1182*103/82=1484

Resumiendo, la distancia total podría ser:

Pasos: 1182+1542 = 2724 m.
Postes: 1182+1586 = 2768 m.
Minutos: 1182+1545=2727 m.
Google: 1182+1484=2666 m.

Antes de encontrar la media quise criticar cada método:

* Contar pasos es cansado y desalentador, sujeto por tanto a olvidos y saltos en la cuenta.
* Los postes parecían estar más cercanos en el segundo tramo.
* Conté minutos, y no segundos, lo que disminuye la precisión.
* En el mapa no se veía bien la transición y tampoco el final de los postes respecto al segundo molino. Me pareció la menos fiable.

Así que mi estimación media fue de 2721 m. Unos días después de este juego, vi un cartel no muy visible al principio del paseo y en él se afirmaba que la distancia entre los dos molinos era de 2,7 km. ¡Pues no estuvo mal!

Ideas para el aula

Se pueden efectuar mediciones semejantes combinando varios conjuntos repetitivos:

  • Ancho de un andén de ferrocarril contando baldosas, pasos, vagones o carteles publicitarios. Como elemento fiable se puede usar una baldosa medida con una regla de dibujo.
  • Tramo de una calle mediante pasos, farolas, coches aparcados (asignando unos cuatro o cinco metros por coche). El elemento fiable podrá ser la distancia entre dos farolas medida con una cinta métrica.
  • Avenida de un paseo, usando pasos, bancos, distancia entre árboles, etc. Aquí el único elemento fiable sería el de los pasos.

Pues nada, a intentarlo y divertirse con ello. No todo van a ser fórmulas y ecuaciones. Y siempre por equipos.