Enteros como sumas de tres coprimos.
Dos números enteros son coprimos (o primos entre sí) si no tienen ningún factor primo en común. Por ejemplo, 4 y 15 son coprimos.
Una terna coprima es una terna (a,b,c) tal que
- a y b son coprimos,
- a y c son coprimos y
- b y c son coprimos.
Por ejemplo, (3,4,5) es una terna coprima.
Definir la función
|
1 |
sumas3coprimos :: Integer -> [(Integer,Integer,Integer)] |
tal que (sumas3coprimos n) es la lista de las ternas coprimas cuya suma es n. Por ejemplo,
|
1 2 3 4 |
sumas3coprimos 10 == [(2,3,5)] sumas3coprimos 11 == [] sumas3coprimos 12 == [(2,3,7),(3,4,5)] length (sumas3coprimos 4000) == 546146 |
Comprobar con QuickCheck que todo número entero mayor que 17 se puede escribir como suma de alguna terna coprima; es decir, para todo entero n, (sumas3coprimos2 (18 + abs n)) tiene algún elemento.
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
import Test.QuickCheck -- 1ª solución -- =========== sumas3coprimos :: Integer -> [(Integer,Integer,Integer)] sumas3coprimos n = [(a,b,c) | a <- [2..n] , b <- [a+1..n] , c <- [b+1..n] , a + b + c == n , gcd a b == 1 , gcd a c == 1 , gcd b c == 1] -- 2ª solución -- =========== sumas3coprimos2 :: Integer -> [(Integer,Integer,Integer)] sumas3coprimos2 n = [(a,b,c) | a <- [2..n `div` 3] , b <- [a+1..(n - a) `div` 2] , gcd a b == 1 , let c = n - a - b , gcd a c == 1 , gcd b c == 1] -- Equivalencia de las definiciones -- ================================ -- La propiedad de equivalencia es prop_sumas3coprimos_equiv :: Integer -> Property prop_sumas3coprimos_equiv n = n > 0 ==> sumas3coprimos n == sumas3coprimos2 n -- La comprobación es -- λ> quickCheck prop_sumas3coprimos_equiv -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- λ> length (sumas3coprimos 400) -- 5345 -- (4.16 secs, 2,894,799,744 bytes) -- λ> length (sumas3coprimos2 400) -- 5345 -- (0.06 secs, 16,565,136 bytes) -- Propiedad -- ========= -- La propiedad prop_sumas3coprimos :: Integer -> Bool prop_sumas3coprimos n = not (null (sumas3coprimos2 (18 + abs n))) -- La comprobación es -- λ> quickCheck prop_sumas3coprimos -- +++ OK, passed 100 tests. |
Referencias
- Basado en Integers as sum of three pairwise coprime integers de ProofWiki.
Pensamiento
Todo amor es fantasía;
él inventa el año, el día,
la hora y su melodía;
inventa el amante y, más
la amada. No prueba nada,
contra el amor, que la amada
no haya existido jamás.Antonio Machado
Un comentario