Metonymie.com :: Apuntes » 2008 » August
Bloque de Colores

Ejercicio 3.42 de THRTLMP

Icono de Post August 4 2008 :: Algebra, Lógica ::

Se nos pide demostrar si hay o no hay triplos de primos de la forma ( p , p+2, p+4 ) que no sean ( 3, 5, 7 ). Este ejercicio me gusto porque estuve unos 15 minutos pensando antes de poder resolverlo. Bueno, despues de mirar un poco la Criba de Eratosthenes y pensar en la aritmetica mod( 3 ) finalmente encontre la forma:

Demostración

Sabemos que p es primo por lo tanto no es multiplo de 3, o sea que es o de la forma 3k + 1 o 3k + 2 con k ∈ Z. Supongamos que es de la forma 3k + 1, entonces p + 2 = 3k + 1 + 2 = 3 ( k + 1 ) entonces p + 2 es multiplo de 3 y no es primo. Ahora si es de la forma 3k + 2 entonces p + 4 = 3k + 2 + 4 = 3 ( k + 2) por lo que p + 4 es multiplo de 3 y no es primo. De lo que sigue que no existen triplos de primos de la forma ( p, p+2, p+4 ) salvo ( 3, 5, 7 ).

De manera similar puede resolverse el ejercicio 3.43, que es demostrar que siendo p primo, no existen primos de la forma ( p2 + 2 ) ≠ 11 o lo que es lo mismo con p ≠ 3 .

Demostración

Si p es primo ≠ 3 , entonces necesariamente no es multiplo de 3, o sea que es de la forma 3k + 1 o 3k + 2 con k ∈ Z. Supongamos que es de la forma 3k + 1, entonces p2 + 2 = ( 9k2 + 6k + 1) + 2 = 3 ( 3k2 + 2k + 1 ) , porque lo que es multiplo de 3 y no es primo. Supongamos entonces que es de la forma 3k + 2, entonces p2 + 2 = ( 9k2 + 12k + 4) + 2 = 3 ( 3k2 + 4k + 2 ), multiplo de 3 y no primo. Por exhaustación de casos, la proposición queda demostarda.

Bueno termine con el cápitulo 3, si alguién tiene la solución del ejercicio 3.34 me haría un favor enorme si me lo mandan porque estuve un buen rato y no lo pude resolver. Mierda, me gustaría poder dedicarle más tiempo, pero si me cuelgo no avanzo más y quiero seguir aprendiendo Haskell.

Autor: Emiliano Martínez Luque.

Comments Off on Ejercicio 3.42 de THRTLMP

La inducción completa es un arma poderosa

Icono de Post August 4 2008 :: Algebra, Lógica ::

Resolución del ejercicio 3.41 de The Haskell Road To Logic, Math and Programming. Demostrar que 2n – 1

( 2n– 1 ) es un numéro perfecto ( la suma de todos sus divisores propios es igual al mismo número ) si ( 2n– 1 ) es primo ( un primo de mersenne en realidad ). Como es primo se puede descomponer en los siguientes divisores propios:

2n – 1

( 2n– 1 ) = 1 + 2 + 22 + …. + 2n – 1 + ( 2n– 1 ) + 2.( 2n-1 ) + 22.( 2n-1 ) + …. + 2n – 2.( 2n-1 )

= 1 + 2 + 22 + …. + 2n – 1 + ( 2n– 1 ) + ( 2n + 1 -2 ) + ( 2n + 2

– 22 ) + …. + ( 22n – 2

– 2n – 2)
Realizando las multiplicaciones de los terminos del final.

= 2n – 1
+ 2n + 2n + 1 +  2n + 2

+ …. + 22n – 2

Simplificando terminos equivalentes pero negativos.

= 2n – 1

( 1 + 2 + 22 + …. + 2n – 1 )
Por propiedades de la exponenciación.

= 2n – 1( 2  – 1 + 2 + 22 + …. + 2n – 1 )
Porque 2 – 1 = 1

Y es exactamente acá donde la cosa se pone interesante.  Ya logre 2n – 1 y el – 1 en el segundo termino. Pero me queda demostrar que ( 2 +2 + 22 + …. + 2n – 1 ) = 2n .

En principio no parece demasiado complicado.. digamos:

2 + 2 = 4 = 22

22 + 22 = 8 = 23

23 + 23 = 16 = 24

…….

2n – 1

+ 2n – 1 = 2n

Que se puede probar fácilmente por inducción completa.

2n = 2n – 1

+ 2n – 1

1) Demostrarlo para n = 1, es trivial: 2 = 1 +1.

2) 2n = 2n – 1
+ 2n – 1

=> 2n + 1
= 2n + 2n
2n + 2n = 2.(2n – 1

+ 2n – 1) = 2.2n (Por hipotesis) =  2n + 1

Ahora, en el texto todavía no vimos inducción y hay un capitulo entero dedicado al tema. El tema es como probar esto sin usar inducción completa. Ni la más puta idea.

DUH! Agregado ( 1 mes después releyendo mi post y sorprendiéndome por mi absoluta falta de lucidez al momento de escribirlo )

2n – 1 + 2n – 1 = 2. (2n – 1) = 2n

Autor: Emiliano Martínez Luque.

Comments Off on La inducción completa es un arma poderosa

Lazy Evaluation ( Evaluación perezosa ) en Haskell

Icono de Post August 4 2008 :: Algebra, Haskell, Programación Funcional ::

Del capitulo 3 de The Haskell Road To Logic, Math and Programming:



sieve :: [Integer] -> [Integer]

sieve (0:xs) = sieve xs

sieve (n : xs) = n : sieve ( mark xs 1 n )

	where

	mark :: [Integer] -> Integer -> Integer -> [Integer]

	mark (y:ys) k m | k == m 	= 0 : (mark ys 1 m)

					| otherwise = y : (mark ys (k+1) m)

LLamando a la función con sieve [2..] , nos retorna los números primos por el método de Criba de Eratosthenes.

Lo interesante es pensar en como la lista infinita que se le paso como parámetro es evaluada por Haskell. Si pensamos desde una perspectiva de programación imperativa, es imposible que una función sea procesada por otra función hasta que no haya terminado su procesamiento, entonces como es posible que sieve devuelva resultados si en este caso mark devuelve una lista infinita. Este es un ejemplo de Lazy Evaluation y una muy buena explicación se puede encontrar acá y con más profundidad acá.

Ejercicio 3.39 de THRTLMP

Agrego este ejercicio porque me gusto y es otro ejemplo de Lazy Evaluation. Se nos pide refutar la afirmación de que si p1, p2, … , pk son todos los números primos menores a n, entonces ( p1 . p2 . … . pk ) + 1 es también primo, para todo n perteneciente a los naturales.



filterMinor :: [Integer] -> Integer -> [Integer]

filterMinor [] _ = []

filterMinor (x:xs) n 	| x >= n	= []

			| otherwise = x : filterMinor(xs) n



proveSTforN :: Integer -> Bool

proveSTforN n = prime (product( filterMinor (sieve [2..]) n ) + 1)



proveST :: Bool

proveST = all (==True) (map proveSTforN [1..])

Y para ver los resultados:



proveSTforNShow :: Integer -> (Integer, Integer, Bool)

proveSTforNShow n = (n, a, prime(a)) 

		where

		a = product( filterMinor (sieve [2..]) n ) + 1



proveSTShow :: [(Integer, Integer, Bool)]

proveSTShow = map proveSTforNShow [2..]