PDF de programación - Números y hoja de cálculo IV

Números y hoja de cálculo IV



Curso 2011-2012



Colección Hojamat.es

© Antonio Roldán Martínez
http://www.hojamat.es



1





PRESENTACIÓN



Llegamos al cuarto tomo de la colección y a partir del mismo sólo se
ofrecerán este y
los siguientes como documentos en PDF
descargables. La edición en papel suponía trabajo extra que no
compensaba
labor de divulgación que
pretendemos basta con el ofrecimiento del documento descargable.

lo suficiente. Para

la

El orden de las entradas recogidas en este tomo es el cronológico
dentro de cada capítulo. De esta forma nos garantizamos una revisión
realizada cuando han transcurrido unos meses, con lo que se amplían
las posibilidades de nuevas ideas complementarias.

Como en ocasiones anteriores, los números primos y los divisores son
los conceptos que más nos han inspirado en la confección de las
entradas, aunque en este curso se han desarrollado con cierto detalle
las funciones multiplicativas y los conceptos derivados del algoritmo
extendido de Euclides.

A partir de este curso disponemos ya de suficiente material para iniciar
publicaciones temáticas, cuya presentación se iniciará en el otoño de
2012. Mientras se mantenga el blog Números y hoja de cálculo estos
documentos permanecerán actualizados a
través de sucesivas
ediciones.



2



CONTENIDO



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

Contenido ................................................................................................. 3

Primos inagotables .................................................................................. 5

Los huecos de un primo ......................................................................... 5

Distancia binaria entre primos ................................................................ 7

Al complicar se simplifica ......................................................................11

Pasito a pasito hacia la complejidad ......................................................17

Números de Aquiles ..............................................................................23

Primorial................................................................................................30

Subida a ritmo de M.C.M .......................................................................34

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

Va a resultar que eres primo .................................................................43

Cuestiones modulares ............................................................................46

La exponenciación modular ...................................................................46

El algoritmo extendido de Euclides ........................................................49

La ecuación Ax=B (mod m) ...................................................................53

El anillo Zm ............................................................................................56

El teorema chino de los restos...............................................................60

La función indicatriz de Euler (n) .........................................................64

Combinar y contar ...................................................................................69

Suma de los elementos de todos los subconjuntos ................................69

Lo tengo repe ........................................................................................72

La hoja echa humo ..................................................................................82

Obtención de la lista de divisores ..........................................................82

El algoritmo de Moessner ......................................................................85



3



Simulación para vagos ..........................................................................87

Funciones recursivas en las hojas de cálculo ........................................90

A propósito de Ormiston ........................................................................95

el problema de Hamming ....................................................................100

Funciones multiplicativas .....................................................................105

Definiciones ........................................................................................105

El conjunto de los divisores .................................................................109

Emparedado de cuadrados .................................................................114

Cuadrados divisores de N ...................................................................124

Ideas para el aula ..................................................................................128

Baldosas, pasos y farolas ....................................................................128

Alfabeto Braille ....................................................................................131

Terrones de azúcar .............................................................................136

Miscelánea .............................................................................................137

Mi pequeño homenaje al 11/11/11 ......................................................137

No hay que dejarse llevar por la admiración ........................................137

Soluciones .............................................................................................140

Primos inagotables ..............................................................................140

La hoja echa humo ..............................................................................142

Funciones multiplicativas .....................................................................142

Ideas ara el aula..................................................................................144



4





PRIMOS INAGOT ABLES


L O S H U EC O S D E U N P R I MO


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 razonar que los de Fermat son los
únicos posibles, pues su expresión ha de ser del tipo 2n+1

¿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. Su expresión sería del tipo 22n+2n+1. Golomb
dedujo que para que sean primos n ha de ser potencia de 3. Puedes también
consultar http://www.alpertron.com.ar/MODFERM.HTM

primos

con

estructuras

si

buscáramos

a
¿Y
1000100010001?, con cuatro unos? Pues yo no lo haría. Seguro que
son compuestos. 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.

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



5



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

422657

110011100110001

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:



6





134323393

1000000000011001110011000001

137442334721

10000000000000001100111001100000000001


¿Deseas investigar otras estructuras? Puedes probar con

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

Números de Carol: Sólo tienen un hueco, pero bien situado. Tampoco
hay muchos
en
http://oeis.org/A091516

puedes

primos

ver

entre

ellos.

Los

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 v