Programacion recreativa Ejercicios resueltos en C++ y cuentos

Luis Tomas Wayar

c 2015 Luis Tomas Wayar Copyright WWW. RETRONET. COM . COM

Licenciado bajo Creative Commons Reconocimiento – Compartir Igual (by-sa): Se permite el uso comercial de la obra y de las posibles obras derivadas, la distribución de las cuales se debe hacer con una licencia igual a la que regula la obra original. Esta licencia es una licencia libre según la Freedom Defined. Primera edicion, Mayo 2015

Índice general

Ejercicios

I 1

Numeros primos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.1

Números primos

14

1.2

Primos gemelos

14

1.3

Primos de Mersenne

15

1.4

Primos de Sofia y cadenas de Cunningham

15

1.5

Conjetura de Goldbach

16

2

Divisores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.1

Divisores consecutivos

20

2.2

Números amigos

20

2.3

Perfectos y binarios

21

2.4

Números deficientes, abundantes y perfectos

22

2.5

Congruentes con modulo 42

23

II

Soluciones

1

Soluciones Numeros primos . . . . . . . . . . . . . . . . . . . . . . . . . . 27

1.1

Numeros primos

28

1.2

Primos gemelos

29

1.3

Primos de Mersenne

30

1.4

Primos de Sofia y cadenas de Cunningham

31

1.5

Conjetura de Goldbach

32

2

Soluciones Divisores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.1

Divisores consecutivos

33

2.2

Números amigos

34

2.3

Números perfectos

35

2.4

Números deficientes, abundantes y perfectos

36

2.5

Congruentes con módulo 42

37

III

Cuentos

1

El amor de una mujer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

2

La Mujer del Panadero . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

3

Emanuel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

4

Kroshnak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

5

Prologo Programación Recreativa es una obra que con originalidad combina problemas y cuentos; en esta combinación se ve la mano del autor que nos propone la elaboración de un tejido particular entre dos componentes. Por un lado los ejercicios, ejemplos y aplicaciones acerca de números primos, divisores, números especiales, secuencias, criptografía y problemas misceláneos; agrupados como Parte I problemas. Esta parte del libro da cuenta de elementos e ideas provenientes de un mundo abstracto corporizadas en esos problemas y constituyen productos de la compleja y no siempre evidente belleza de las relaciones en la aritmética de números enteros, relaciones estas, que estructuran el edificio de la matemática. Es importante destacar que estos ejercicios no sólo son mostrados como curiosidad matemática, sino que también tienen un aterrizaje en las Ciencias de la Computación a través de la expresión en programas en lenguaje C++. El tejido que muestra el libro se enlaza, por otro lado, en la parte 2 “Cuentos” constituida por dos narraciones, de muy buena factura, que nos relatan situaciones cotidianas aparentemente alejadas de un razonamiento abstracto. Lo interesante de la visión del autor es que en la ingeniosa trama que elabora establece un hilo de Adriadna que puede recorrer el laberinto formado por este aparente alejamiento entre las dos partes del libro; que vinculan el razonamiento abstracto de la aritmética de los números enteros con un mundo cotidiano, no siempre satisfactorio, que sabemos incompleto. Y es ese hilo el que nos ayuda y nos hace desencriptar el mensaje del texto y que es el descubrimiento de Gödel que encuentra incompletud también en la formidable y armónica construcción de la aritmética de números enteros. Entonces si bien conocemos que en nuestro mundo humano no siempre la verdad se cumple o se demuestra; veamos también que en algo tan perfecto como ciertos aspectos de la matemática podemos encontrar incompletud. Es de notar la cercanía entre la literatura y la informática; en el sentido de que un producto informático también es un relato", escrito en un lenguaje con su sintaxis y gramática particular, que dice algo respecto a una historia real o ficticia (virtual); muy parecida a una novela o a un cuento o en general un producto literario. Ing. José Humberto Paganini

6

Convenciones y estructura del libro El presente libro esta escrito y organizado de manera que cada uno de los ejercicios planteados sea independiente y no requiera un cierto orden para ser leído, sin embargo se agruparon por temas para su mejor organizacion y existe referencias cruzadas entre ellos. Cada ejercicio consta de un tíulo, una introducción y fundamentación, en algunos casos con ejemplos y luego el planteo del problema y la solución propuesta, cabe destacar que la solución propuesta por el autor obviamente no es única y posiblemente en algunos casos sea perfectible, se agradecerá al lector cualquier sugerencia y corrección que pueda aportar para próximas posibles ediciones. La respuesta propuesta en todos los casos esta desarrollada en el lenguaje de programación C++. Para mayor comprensión y enriquecimiento de la lectura el texto esta complementado con notas al margen que profundizan en algunos aspectos o detallas cuestiones inherentes a la introducción. También se incluyen notas al pie para abundar en datos sobre las personalidades y bibliografía mencionada. En un segundo capitulo del libro se incluyen cuentos relacionados con la temática del libro algunos de ellos enriquecidos con ilustraciones, tanto los textos como las ilustraciones son del mismo autor

7

Introducción Cuando era niño, antes de ir a la cama me gustaba visitar la basta biblioteca de mi padre, un poco aburrido de la ciencia ficción, genero que siempre me fascino, comense a explorar otras áreas de la biblioteca, encontré así, un sector donde habían libros dedicados a la matemática, entre ellos unos con problemas lógicos y matemáticos, El Mula de Nusradin, El hombre que Calculaba, Matemáticas e Imaginación, entre otros y autores como Martin Gardner. Me apasiono el genero, eran problemas exquisitamente presentados. Siendo aun un niño intente crear mis propios desafíos que se los presentaba a familiares y amigos, debo reconocer que sin mucho éxito. Este libro es un primer intento en revertir esa situación. Luego, en mi carrera docente intentaba motivar a los alumnos a encarar el aprendizaje como una tarea recreativa, entretenida y apasionante, me complacía ver que en algunos de ellos se despertaba el placer por adquirir conocimientos y destrezas divirtiéndose. En realidad el descubrir que aprender es una tarea placentera y divertida. Siendo aficionado a la matemática tengo una colección de libros sobre el tema, de cada nueva lectura surgía siempre algún problema que luego era publicado en mi blog personal o mis cuentas en redes sociales, luego de un tiempo pensé en hacer una recopilación de algunos de los problemas y crear un libro con ellos. Este compendio es el resultado, espero que sea de su agrado y les de algunas horas de diversión. Se trata de problemas lógico-matemáticos a los que se propone abordar desde la practica de la programación. En todos los casos se ofrece el código fuente en C++ de una solución que da respuesta al desafío. El objetivo de este libro no es académico sino de esparcimiento y recreación mental, sin embargo espero que sirva para el desarrollo de habilidades y mejor comprensión y dominio de la programación, puede servir como apoyo y soporte a docentes tanto del área de matemáticas como de computación. Apunta a atrapar al lector en base a el desafío y reto mental que representa cada uno de sus problemas, también a introducirlo en algunas de las cuestiones mas interesantes y curiosas de la matemática. También incluí en cuatro cuentos inéditos con ilustraciones, la idea es que estos cuentos sean un descanso entre problema y problema, se tratan de historias que tienen como tematica subyacente algunas de las cuestiones tratadas en el libro. Este libro surge como un intento de compensación por mi imposibilidad de concurrir a cumplir con mi obligación laboral por problemas de salud, razón por la cual todos los derechos y regalías son donados a la UNJU - Universidad Nacional de Jujuy - Facultad de Ingeniería. Espero que les guste el trabajo y los disfruten tanto como yo disfrute hacerlo.

I

Ejercicios

1

Numeros primos . . . . . . . . . . . . . . . . . . . . . 13

1.1 1.2 1.3 1.4 1.5

Números primos Primos gemelos Primos de Mersenne Primos de Sofia y cadenas de Cunningham Conjetura de Goldbach

2

Divisores . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.1 2.2 2.3 2.4 2.5

Divisores consecutivos Números amigos Perfectos y binarios Números deficientes, abundantes y perfectos Congruentes con modulo 42

11 “Me dijo que hacia 1886 había discurrido un sistema original de numeración y que en muy pocos días había rebasado el veinticuatro mil. No lo había escrito, porque lo pensado una sola vez ya no podía borrársele. Su primer estímulo, creo, fue el desagrado de que los treinta y tres orientales requieran dos signos y tres palabras, en lugar de una sola palabra y un solo signo. Aplicó luego ese disparatado principio a los otros números. En lugar de siete mil trece, decía (por ejemplo) Máximo Pérez; en lugar de siete mil catorce, El Ferrocarril; otros números eran Luis Meleán Lafinur, Olimar, azufre, los bastos, la ballena, el gas, la caldera, Napoleón, Agustín de Vedia. En lugar de quinientos, decía nueve. Cada palabra tenía un signo particular, una especie de marca; las últimas eran muy complicadas. . . Yo traté de explicarle que esa rapsodia de voces inconexas era precisamente lo contrario de un sistema de numeración. Le dije que decir 365 era decir tres centenas, seis decenas, cinco unidades: análisis que no existe en los “números” El Negro Timoteo o manta de carne. Funes no entendió o no quiso entenderme.” Jorge Luis Borges - El culteranismo

La inteligencia humana apenas vislumbra en la oscuridad la inmensidad de relaciones, características, reglas y aplicaciones que los números tienen. Desde tiempos inmemoriales, cuando alguno de nuestros ancestros se sentó por primera vez a observar se percato que una de las características de los objetos era la cantidad, el mundo de la matemática y los números fue adquiriendo cada vez mas importancia y ayudándonos a comprender como funciona el universo, los números son los símbolos y la matemática el lenguaje con que esta escrito el software que mueve este universo. En todo lo relacionado a la computación se necesita de la matemática, debajo de cualquier programa que se ejecute en una computadora, desde un juego hasta los mas complejos sistemas de simulación o redes neuronales existe un intrincados mundo de números y cálculos subyacente que lo hace posible. Sin temor a equivocarnos podemos afirmar que la relación entre la matemática y la programación se produjo desde antes de la construcción de la primera computadora. Las ciencias de la computación se interrelacionan con otras áreas de la ciencia y la investigación, incluso me atrevería a decir que actualmente esta inmersa e involucrada directa o indirectamente con la mayoría de los campos de la investigación y la ciencia. Pero es con las matemáticas con las que se considera que tiene un grado mayor de relación, los primeros trabajos en el área fueran fuertemente influenciados por matemáticos como Kurt GödelKurt Gödel (28 de abril de 1906 Brünn – 14 de enero de 1978, Princeton, Estados Unidos) fue un lógico, matemático y filósofo austriaco-estadounidense reconocido como uno de los más importantes lógicos de todos los tiempos, el trabajo de Gödel ha tenido un impacto inmenso en el pensamiento científico y filosófico del siglo XX. y Alan Turing1 . En la actualidad es creciente el intercambio de ideas entre ambos campos en áreas como la lógica matemática, la teoría de categorías, la teoría de dominios, el álgebra y la geometría. En este libro vamos a explorar y resolver algunos problemas relacionados con la matemática y los números en general, los enunciados están agrupados por categorías tales como números primo o divisores, en muchos casos se trata de problemas simples que podríamos resolver fácilmente con lápiz y papel, pero el desafío se trata de lograr adaptar la lógica y la mecánica de la resolución manual a términos de pro1 Alan Mathison Turing, (Londres, 23 de junio de 1912 - Wilmslow, Cheshire, 7 de junio de 1954), fue un matemático, lógico, científico de la computación, criptógrafo y filósofo británico.

12 gramación y algoritmia. Son en todos los casos ejercicios y divertimentos mentales que espero resulten de su agrado.

1. Numeros primos

“Si las matemáticas (sistema especializado de pocos signos, fundado y gobernado con asiduidad por la inteligencia) entrañan incomprensibilidades y son objeto permanente de discusión, ¿cuántas no oscurecerán el idioma, colecticio tropel de miles de símbolos, manejado casi al azar?” Jorge Luis Borges - El culteranismo

Desde hace unos miles de años los números primos han atrapado la atención de la humanidad especialmente de matemáticos y filósofos. Una de las principales razones es la fascinación que produce su irregular distribución a lo largo de la recta numérica. Los números primos aparecen esparcidos hasta ahora sin orden aparente, encontrándose algunos agrupados y abundantes y otros muy espaciados y escasos. Son un desafío para el intelecto humano ya que parecen escapar a todo intento de deducir y establecer leyes sobre ellos pues no parece existir ninguna regla que determine su ubicación entre los demás números naturales. La computación como ciencia ha ayudado en mucho a la comprensión de los números primos y a su búsqueda, y se ha valido de ellos para lograr entre otras cosas y como ya dije anteriormente comunicaciones y almacenamiento de información mas seguros. Como dice Don Zagier, sorprenden tanto la evidente falta de orden y reglas que rijan a los números primos, pero también se intuye que algo aun escapa al entendimiento humano, personalmente creo que posiblemente aun no podamos vislumbrar estas reglas, pero que si existen. Lo que inicialmente fue una curiosidad con el devenir de los años y la evolución de las comunicaciones y la tecnología se convirtió en la piedra angular de la seguridad informática. Los números primos hoy son imprescindibles para garantizar cierto grado aceptable de fortaleza en los sistemas de codificación de la información y las comunicaciones. Existen muchos y muy variados proyectos de investigación que buscan desde métodos para determinar la primalidad de un numero hasta la búsqueda de nuevos y mas grandes números primos.

Capítulo 1. Numeros primos

14

En esta sección del libro nos enfrentaremos con los primos, alguno de los problemas planteados esta basados y famosos y conocidos problemas como la Conjetura de Goldbach.

1.1

Números primos Un número primo es un número natural, que tiene exactamente dos divisores positivos la unidad y el mismo. También podemos definirlo como aquel número entero positivo que no puede expresarse como producto de dos números enteros positivos más pequeños que él, o bien, como producto de dos enteros positivos de más de una forma. Existen varios métodos para buscar los números primos en un intervalo dado, uno de ellos es la Criba de Eratostenes. Ejercicio: Generar números primos

El numero 1 no es considerado un numero primo, por lo tanto queda excluido. En contraposición a primo un numero compuesto es aquel que tiene mas de dos divisores positivos.

1.2

A partir del par (5, 7), el número intermedio es siempre múltiplo de 6.

El algoritmo más sencillo que puede utilizarse para saber si un número n es primo es el de la división. Se trata de ir probando para ver si tiene algún divisor propio. Para ello vamos dividiendo el número n entre 2, 3, 4, 5, ... , √ n − 1. Si alguna de las divisiones es exacta (da resto cero) podemos asegurar que el número n es compuesto. Si ninguna de estas divisiones es exacta, el número n es primo. Este método puede hacerse más eficiente observando simplemente, que si es un número compuesto. Por lo tanto, el número de divisiones a realizar es √ mucho menor. Sólo hay que dividir entre 2, 3, 4, 5, ... , [ n] Escriba un programa que reciba como entrada un numero entero positivo y como salida diga si es o no un número primo, use para ello el algoritmo descripto anteriormente.

Primos gemelos En matemáticas, y más concretamente en teoría de números, dos números primos (p, q) son números primos gemelos si están separados por una distancia de 2, es decir, si q = p + 2 La conjetura de los primos gemelos postula la existencia de infinitos pares de primos gemelos. Por ejemplo tenemos el primer par de primos gemelos que son 3 y 5, como puede observase ambos son impares y están separados por un solo numero, en este caso el 4 que obviamente es par. Ejercicio: Primos gemelos En el libro Recreations in the Theory of Numbers", de A. H. Beiler dice que si obtenemos un numero n de aplicar la formula n = 30 ∗ (2 ∗ x − 27) ∗ (x − 15) para valores de x en el rango de 1 a 20, obtenemos pares de números primos gemelos en n-1 y n+1 para todos los valores de x a excepción de dos. Escribir un programa que encuentre y muestre por pantalla valores de x que no generan pares de números primos gemelos y así refute la afirmación.

1.3 Primos de Mersenne

1.3

15

Primos de Mersenne Vamos a comenzar definiendo lo que es un número de Mersenne (M) se dice que un numero es un numero de Mersenne si es una unidad menor que una potencia de 2. Mn = 2n − 1 Por otra parte, un número primo de Mersenne es un número de Mersenne que es primo, es decir: Mn = 2n − 1 Con n primo No es condicion suficiente que n sea primo para que M n lo sea. Reciben ese nombre en honor al filósofo del siglo XVII Marin Mersenne 1 quien en su “Cognitata Physico-Mathematica” realizó una serie de postulados sobre ellos que sólo pudo refinarse tres siglos después. También compiló una lista de números primos de Mersenne con exponentes menores o iguales a 257, y conjeturó que eran los únicos números primos de esa forma. Su lista sólo resultó ser parcialmente correcta, ya que por error incluyó M67 y M257, que son compuestos, y omitió M61, M89, y M107, que son primos; y su conjetura se revelaría falsa con el descubrimiento de números primos de Mersenne más grandes. No proporcionó ninguna indicación de cómo dio con esa lista, y su verificación rigurosa sólo se completó más de dos siglos después. Actualmente se conocen 48 primos de Mersenne, los últimos 14 encontrados, han sido descubiertos por GIMPS (Great Internet Mersenne Prime Search) que se constituyó en 1996 para descubrir nuevos primos de Mersenne. Es un proyecto que combina los esfuerzos de docenas de expertos y miles de amateurs, y la potencia de miles de computadoras personales. Ejercicio: Primos de Mersene Escribir un programa que encuentre e imprima por pantalla el primer numero que generado con la formula de Mersenne que no es un numero primo.

1.4

Primos de Sofia y cadenas de Cunningham Un número primo p es un numero primo de Sophie si 2p+1 también es un número primo. Para p = 2: 2x2 + 1 = 5 Que también es un número primo.

1 Marin MersenneMarin Mersenne ( 1588 – 1648) fue un filósofo francés del siglo XVII que estudió diversos campos de la teología, matemáticas y la teoría musical.

El ultimo primo de Mersenne hallado a la fecha de publicación de este libro se encontro el 25 de enero de 2013.

Capítulo 1. Numeros primos

16

Recibieron ese nombre por la matemática francesa Sophie Germain 2 quien a pesar de la oposición de sus padres y las dificultades presentadas por una sociedad sexista, ganó su educación de libros extraídos de la biblioteca de su padre y de correspondencia con famosos matemáticos como Lagrange, Legendre y Gauss. Por los prejuicios contra su sexo, no pudo establecer una carrera en matemáticas, por lo que trabajó independientemente a lo largo de su vida. En matemáticas, una cadena de Cunningham es una sucesión de números primos (p1, ..., pn) en la cual se cumple que cada término es igual al doble del anterior más uno: pi + 1 = 2pi + 1 Para todo 1 ≤ i < n en cuyo caso se denomina Cadena de Cunningham de primera especie; O bien que cada término es igual al doble del anterior menos uno pi + 1 = 2pi − 1 Para todo 1 ≤ i < n en cuyo caso se denomina Cadena de Cunningham de segunda especie Se denominan así en honor al matemático A. J. C. Cunningham. Ejercicio: Primos de Sofia y cadenas de Cunningham Escribir un programa que encuentre cual es el primo de Sophie menor a 100 que genera la cadena de Cunningham de la primera especie mas larga y cuales son los miembros de esa cadena. Para el numero 2 tenemos la siguiente cadena: 2 ⇒ 2∗2+1 = 5 5 ⇒ 2 ∗ 5 + 1 = 11 11 ⇒ 2 ∗ 11 + 1 = 23 23 ⇒ 2 ∗ 23 + 1 = 47 47 ⇒ 2 ∗ 47 + 1 = 95 (ya no es primo) Por lo tanto la cadena de Cunningham para 2 tiene 4 miembros y estos son [2,5,11,23].

1.5

Conjetura de Goldbach La conjetura de Goldbach es uno de los problemas abiertos más antiguos en matemáticas. Algunos lo califican como el problema más difícil en la historia. Goldbach formuló dos conjeturas relacionadas entre sí sobre la suma de números primos la conjetura fuerte de Goldbach y la conjetura débil de Goldbach. La que se discute aquí es la fuerte, y es la que se suele mencionar como «Conjetura de Goldbach».

El tío Petros y la conjetura de Goldbach es una nove2 Sophie GermainMarie-Sophie Germain (1776 - 1831) matemática francesa que hizo importantes la escrita en 1992 por el escritor y ma- contribuciones a la teoría de números y la teoría de la elasticidad temático griego Apostolos Doxiadis.

1.5 Conjetura de Goldbach

17

El matemático peruano Harald Andrés Helfgott ha resuelto la Conjetura débil de Goldbach, la formulación afirma que todo número impar mayor que 5 puede escribirse como suma de tres números primos. El enunciado reza: Todo número par mayor que 2 puede escribirse como suma de dos números primos. Se puede emplear dos veces el mismo número primo. Veamos algunos: 4 = 2+2 6 = 3+3 8 = 3+5 10 = 3 + 7 12 = 5 + 7 14 = 3 + 11 Ejercicio: Conjetura de Goldbach Escriba un programa que reciba como entrada un numero par y muestre todas las combinaciones posibles de sumas de números primos que lo componen.

2. Divisores

“El mismo anhelo de orden que en el principio creó las matemáticas hizo que yo buscara un orden en esa aberración de las matemáticas que son las insensatas piedras que engendran. En sus imprevisibles variaciones quise hallar una ley. Consagré los días y las noches a fijar una estadística de los cambios. Mi procedimiento era éste. Contaba con los ojos las piezas y anotaba la cifra. Luego las dividía en dos puñados que arrojaba sobre la mesa. Contaba las dos cifras, las anotaba y repetía la operación. Inútil fue la búsqueda de un orden, de un dibujo secreto en las rotaciones. El máximo de piezas que conté fue 419; el mínimo, tres. Hubo un momento que esperé, o temí, que desaparecieran. A poco de ensayar comprobé que un disco aislado de los otros no podía multiplicarse o desaparecer. Naturalmente, las cuatro operaciones de sumar, restar, multiplicar o dividir, eran imposibles. Las piedras se negaban a la aritmética y al cálculo de probabilidades. Cuarenta discos, podían, divididos, dar nueve; los nueve, divididos a su vez, podían ser trescientos.” Jorge Luis Borges - “Tigres azules”, La memoria de Shakespeare Todo numero compuesto tiene divisores, son algo así como los bloques de construcción de cada numero, especialmente los números primos que vendrían a ser las formas únicas de bloques con las que se arman las otras. Como dice el matemático polaco Leopold Kronecker 1 “Dios ha creado los números naturales, el resto es obra del hombre” y si bien fue dicha en un contexto diferente, hasta se podría decir que mas teológico que matemático, expresa mi pensamiento, considerando los divisores, se clasificaron los numeros, por ejemplo en 1 Leopold Kronecker (1823 - 1891). Matemático y lógico que defendía que la aritmética y el análisis deben estar fundados en los números enteros prescindiendo de los irracionales e imaginarios.

Capítulo 2. Divisores

20

abundantes, insuficientes y perfectos, o se encontraron extrañas y curiosas relaciones como los numeros amigos. En computación, mas precisamente en la programación, el término divide y vencerás (DYV) se refiera a una premisa para el diseño de algoritmos. El método está basado en la resolución recursiva de un problema dividiéndolo en subproblemas de igual tipo o similar continuando así hasta que estos subproblemas llegan a ser lo suficientemente sencillos como para que se resuelvan directamente. Al final, las soluciones a cada uno de los subproblemas se combinan para dar una solución al problema original. En el mundo de los programadores dividir por cero es uno de los errores mas comunes entre los estudiantes y se considera un error logico. Las computadoras generalmente usan algoritmos de restas sucesivas, al ser el divisor cero, la resta como tal se ejecuta por siempre, ya que el dividendo nunca cambia en consecuencia se entra en un bucle infinito. Esta sección aborda el tema de los divisores.

2.1

Divisores consecutivos En matemáticas, se dice que un número entero b es divisible entre un entero a (distinto de cero) si existe un entero c tal que: b = a ∗ c. Esto es equivalente a decir que b es «exactamente divisible» por a, o bien, que el resto de la división euclídea es cero. Se suele expresar de la forma a|b, que se lee: «a divide a b», o «a es un divisor de b» o también «b es múltiplo de a». 6 es divisible por 3, ya que 6 = 3 ∗ 2; pero 6 no es divisible por 4, pues no existe un entero c tal que 6 = 4·c, es decir que el resto de la división euclídea (entera) de 6 entre 4 no es cero. Ejercicio: DIvisores consecutivos Escribir un programa que encuentre el menor numero entero divisible por todos los enteros consecutivos a partir de 1 hasta un limite que recibirá como entrada por linea de comando. Por ejemplo numero 60 es el menor numero divisible por 1,2,3,4 y 5.

2.2

A la unidad se considera divisor propio, pero no lo es el mismo número.

Números amigos Dos números a y b son amigos si a es la suma de los divisores propios de b, y b es la suma de los divisores de a. El primer par de números amigos ( 220 y 284) ya era conocido por los griegos. El siguiente par de números amigos fue descubierto en el siglo XIII y redescubierto por Fermat en 1636 (los números 17.296 y 18.416). El filósofo francés R. Descartes descubrió el siguiente par: 9.363.584 y 9.437.056. Ambos grandes pensadores se saltaron el par de números amigos 1.184-1.210 que fue descubierto por un niño italiano de 16 años llamado Niccolò Paganini. No hay que olvidar al gran Euler 2 , puesto que él trabajo incansablemente tratando de encontrar fórmulas para encontrar números amigos. 2 Leonhard Paul Euler (15 de abril de 1707 - 18 de septiembre de 1783), fue un matemático y físico suizo.

2.3 Perfectos y binarios

21

Tabit ibn Qurra 3 descubrió una fórmula con la que podían se podían hallar números amigos: Decía el sabio árabe que si se cumplían las condiciones siguientes: p = 3 ∗ 2n−1 − 1 q = 3 ∗ 2n − 1 r = 9 ∗ 22n−1 − 1 Donde n > 1 es entero y p, q, y r son números primos, entonces 2n pq y 2n r son un par de números amigos. Esta fórmula genera los pares (220, 284), (1.184, 1.210), (17.296, 18.416) y (9.363.584, 9.437.056). Mientras que el par de números amigos (6.232, 6.368) no se puede hallar por la fórmula anterior. En consecuencia, hay que señalar que no todos los números amigos se obtienen con el procedimiento de Tabit, pero si son amigos todos los números que se obtienen con dicho procedimiento. El primer par de números amigos esta formado por los enteros (220, 284), dado que: Los divisores propios de 220 son 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284 Los divisores propios de 284 son 1 + 2 + 4 + 71 + 142 = 220 Si un número es amigo de sí mismo (es igual a la suma de sus divisores propios), recibe el nombre de número perfecto y no se considera amigo, por ejemplo el 6 o el 28. Ejercicio: Números amigos Encontrar todos los pares de números amigos menores a 1.000.000. No se deben considerar los pares invertidos.

2.3

Perfectos y binarios Mientras mas nos concentramos en cierto grupo de numero nos encontramos con algunas características, relaciones o curiosidades que a primera vista son realmente sorprendentes, casi mágicas en algunos casos. Pero si analizamos mas profundamente podemos descubrir que eso que parece tan sorprendente quizás sea algo relativamente evidente que no podemos ver sin un análisis mas profundo. Los números perfectos son uno de esos tipos de números que poseen características sorprendentes. Su propia definición hace que su denominación sea coherente con su especial característica: Un número entero positivo N es un número perfecto si la suma de todos sus divisores (excluyéndolo a él mismo) es igual al propio N. 3 Tabit

ibn Qurra Destacó en su época como un gran astrónomo y matemático.

El matemático Euclides descubrió que los cuatro primeros números perfectos vienen dados por la fórmula 2n−1 ∗ (2n − 1)

Capítulo 2. Divisores

22

6 = 1 + 2 + 3 28 = 1 + 2 + 4 + 7 + 14 496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248 Hay dos cuestiones interesantes sobre los números perfectos que actualmente no tienen respuesta. 1. ¿Existen infinitos números perfectos? 2. ¿Existen números perfectos impares? Si convertimos un numero perfecto a binario y observamos su representación binaria notaremos algo muy especial, ya que en todos los casos aparecen una cierta cantidad de unos seguidos de otra cierta cantidad de ceros. La cantidad de unos es un número primo, la cantidad de ceros es un número par y la cantidad de ceros es igual a la cantidad de primos - 1.

Números perfectos Unos

Ceros

Decimal

Binario

2

1

6

110

3

2

28

11100

5

4

496

11111000

7

6

8182

1111111000000

Surgen a partir de esta observación dos nuevas preguntas 1. ¿Esto es siempre así? 2. ¿Tiene algún tipo de explicación? Pues sí, es así siempre que el número perfecto sea par. Y sí, tiene explicación y tiene que ver con la correspondencia de los números perfectos pares con los primos de Mersenne, pero dejo eso para que el lector lo investigue por su parte, pasemos al problema. Ejercicio: Números perfectos Escribir un programa que busque todos los números perfectos que se pueden representar con un binario de hasta 64 dígitos, para la búsqueda se compondrá cada binario perfecto según la formula binario perfecto = 1 repetido una cantidad primo de veces concatenado con 0 repetido la cantidad de unos menos 1 Para luego convertir este numero en decimal e imprimirlo por pantalla tanto la representación binaria como decimal.

2.4

Números deficientes, abundantes y perfectos Se puede clasificar los números mediante la relación que la suma de sus divisores tengan con el propio numero.

2.5 Congruentes con modulo 42

23

ABUNDANTE: la suma de sus divisores propios es mayor que él. 12 sus divisores, 1, 2, 3, 4 y 6 suman 16 que es mayor que 12.

DEFICIENTE: la suma de sus divisores propios es menor que él. 10 sus divisores, 1, 2 y 5 suman 8 que es menor que 10.

PERFECTO: la suma de sus divisores propios es igual a él. 6 sus divisores, 1, 2 y 3 suman 6 que es igual a 6.

Los números Primos de Mersenne están íntimamente relacionados con los números perfectos. En efecto Euclides demostró que si M es un número primo de Mersenne, entonces M ∗ (M + 1)/2 es un número perfecto. Asímismo, Euler demostró en el En el siglo XVIII que todos los números perfectos pares son de la forma M ∗ (M + 1)/2. No se conocen en la actualidad números perfectos impares, y se sospecha que no existe ninguno. Ejercicio: Números deficientes, abundantes y perfectos

Los números naturales fueron clasificados por primera vez como deficientes, perfectos o abundantes por Nicómaco de Gerasa en su Introductio Arithmetica.

En este caso se pide un programa que reciba como entrada un entero que es el limite hasta donde se contaran la cantidad de números deficientes, abundantes y perfectos existentes y mostrar por pantalla estos resultados.

2.5

Congruentes con modulo 42 Todos sabemos que la respuesta a la pregunta sobre el sentido de la vida, el universo y todo lo demás es 42. En la saga “The Hitchhiker’s Guide to the Galaxy”, se construye una super-computadora llamada Pensamiento Profundo, la segunda mejor computadora de todos los tiempos con el solo fin de responder a la pregunta sobre el sentido de la vida, el universo y todo lo demás, puesta a calcular finalmente concluye después de siete millones y medio de años y da su respuesta a tan importante pregunta, dice “cuarenta y dos”, acotando que para poder comprender la respuesta se tiene que replantear la pregunta ya que esta fue mal formulada. Por otra parte, se dice que un par de números son congruentes cuando dos números enteros a y b tienen el mismo resto al dividirlos por un número natural m distinto de 0, llamado el módulo. Dicho de otra manera, dos números enteros a y b se dice que son congruentes respecto de un número natural (entero positivo) llamado módulo m si las divisiones a/m y b/m dan el mismo resto.

Guía del viajero intergaláctico es una radio-comedia escrita por Douglas Adams que se comenzo a transmitir en 1978.

Capítulo 2. Divisores

24

Una aplicación práctica es el calendario perpetuo para saber de forma fácil el día de la semana (lunes, martes, etc..) que corresponde a un día determinado.

Los números 13 y 21 son congruentes de módulo 4, ya que 13/4 nos da 3 de cociente y 1 de resto. Del mismo modo al dividir 21/4 obtenemos 5 de cociente y 1 de resto, por lo tanto verifica la definición anterior Se expresa utilizando la notación: a ≡ b(mod m) Ejercicio: E scribir un programa que responda si la cantidad de números congruentes en el intervalo 100..1000 es divisible por 42.

II

Soluciones

1

Soluciones Numeros primos . . . . . . . . . . 27

1.1 1.2 1.3 1.4 1.5

Numeros primos Primos gemelos Primos de Mersenne Primos de Sofia y cadenas de Cunningham Conjetura de Goldbach

2

Soluciones Divisores . . . . . . . . . . . . . . . . . 33

2.1 2.2 2.3 2.4 2.5

Divisores consecutivos Números amigos Números perfectos Números deficientes, abundantes y perfectos Congruentes con módulo 42

Capítulo 1. Soluciones Numeros primos

28

1. Soluciones Numeros primos

1.1

Numeros primos Solucion: Numeros primos 1 2 3 4

#include #include #include #include

< s t d i o . h> < s t d l i b . h>

5 6

using namespace std ;

7 8

bool EsPrimo ( i n t ) ;

9 10 11 12 13 14 15 16 17 18 19 20

i n t main ( i n t argc , const char ∗argv [ ] ) { i n t numero ; numero = a t o i ( argv [ 1 ] ) ; i f ( EsPrimo (numero) ) { cout