Productos simultáneos de dos y tres números consecutivos
Definir la función
1 |
productos :: Integer -> Integer -> [[Integer]] |
tal que (productos n x) es las listas de n elementos consecutivos cuyo producto es x. Por ejemplo,
1 2 3 4 |
productos 2 6 == [[2,3]] productos 3 6 == [[1,2,3]] productos 4 1680 == [[5,6,7,8]] productos 2 5 == [] |
Comprobar con QuickCheck que si n > 0 y x > 0, entonces
1 |
productos n (product [x..x+n-1]) == [[x..x+n-1]] |
Usando productos, definir la función
1 |
productosDe2y3consecutivos :: [Integer] |
cuyos elementos son los números naturales (no nulos) que pueden expresarse simultáneamente como producto de dos y tres números consecutivos. Por ejemplo,
1 |
head productosDe2y3consecutivos == 6 |
Nota. Según demostró Mordell en 1962, productosDe2y3consecutivos sólo tiene dos elementos.
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 |
import Test.QuickCheck -- 1ª solución -- =========== productos1 :: Integer -> Integer -> [[Integer]] productos1 n x = [[y..y+n-1] | y <- [1..x] , product [y..y+n-1] == x] -- 2ª solución -- =========== productos2 :: Integer -> Integer -> [[Integer]] productos2 n x = [[z..z+n-1] | z <- [1..y] , product [z..z+n-1] == x] where y = head (filter (\y -> y^n >= x) [2..]) -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> let (n,x) = (3,200) in productos1 n (product [x..x+n-1]) -- [[200,201,202]] -- (7.38 secs, 7,235,956,440 bytes) -- λ> let (n,x) = (3,200) in productos2 n (product [x..x+n-1]) -- [[200,201,202]] -- (0.01 secs, 451,928 bytes) -- -- λ> productos2 3 1000018000107000210 -- [[1000005,1000006,1000007]] -- (1.57 secs, 1,560,159,144 bytes) -- En lo que sigue se usa la 2ª definición productos :: Integer -> Integer -> [[Integer]] productos = productos2 -- La propiedad es prop_productos :: Integer -> Integer -> Property prop_productos n x = n > 0 && x > 0 ==> productos n (product [x..x+n-1]) == [[x..x+n-1]] -- La comprobación es -- λ> quickCheck prop_productos -- +++ OK, passed 100 tests. productosDe2y3consecutivos :: [Integer] productosDe2y3consecutivos = [x | x <- [1..] , let ys = productos 2 x , not (null ys) , let zs = productos 3 x , not (null zs)] -- El cálculo es -- λ> take 2 productosDe2y3consecutivos -- [6,210] |
Pensamiento
Mis ojos en el espejo
son ojos ciegos que miran
los ojos con que los veo.Antonio Machado
Con una adecuada aproximación del logaritmo de la función Gamma (ésta no lo es) puede obtenerse eficientemente el (si es) primer número de la secuencia buscada.
La definición es incorrecta. Por ejemplo,
pero 60 = 3x4x5. Por tanto, en lugar de [] debería de haber dado [[3,4,5]].