Números divisibles respecto de una sucesión
El enunciado de un problema para la IMO (Olimpiada Internacional de Matemáticas) de 1968 es
Sean a(0), a(1), …, a(n) (con n ≥ 1) números enteros positivos. Encontrar todos los números enteros y tales que
a(0) | y; (a(0)+a(1)) | (y+a(1)); … ; (a(0)+a(n)) | (y+a(n)).
donde «x | y» significa que «y es divisible por x».
Se dice que un número y es divisible respecto de la sucesión a(0), a(1), …, a(n) si verifica la propiedad anterior; es decir,
|
1 |
a(0) | y; (a(0)+a(1)) | (y+a(1)); ... ; (a(0)+a(n)) | (y+a(n)). |
Definir la función
|
1 |
divisiblesSucesion :: [Integer] -> [Integer] |
tal que (divisiblesSucesion xs) es la lista de los números enteros divisibles respecto de xs. Por ejemplo,
|
1 2 3 4 |
take 6 (divisiblesSucesion [2,5,3]) == [2,72,142,212,282,352] divisiblesSucesion [3,5..30] !! (10^5) == 144144000003 divisiblesSucesion [3,5..30] !! (10^6) == 1441440000003 divisiblesSucesion [3,5..30] !! (10^7) == 14414400000003 |
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 61 62 63 64 65 66 67 68 69 70 71 72 73 |
import Test.QuickCheck (quickCheck) -- 1ª solución -- =========== divisiblesSucesion :: [Integer] -> [Integer] divisiblesSucesion xs = filter (esDivisibleSucesion xs) [1..] -- (esDivisibleSucesion xs y) se verifica si y es divisible respecto de -- la sucesión xs. Por ejemplo, -- esDivisibleSucesion [2,5,3] 72 == True -- esDivisibleSucesion [2,5,3] 12 == False esDivisibleSucesion :: [Integer] -> Integer -> Bool esDivisibleSucesion [] _ = True esDivisibleSucesion (a0:as) y = y `mod` a0 == 0 && and [(y+a) `mod` (a0+a) == 0 | a <- as] -- 2ª solución -- =========== -- En los siguientes cálculos -- λ> take 5 (divisiblesSucesion [2,3,5]) -- [2,72,142,212,282] -- λ> foldl1 lcm [2, 2+3, 2+5] -- 70 -- λ> take 5 (divisiblesSucesion [2,3,5,6]) -- [2,282,562,842,1122] -- λ> foldl1 lcm [2, 2+3, 2+5, 2+6] -- 280 -- λ> take 5 (divisiblesSucesion [1,3,5,6]) -- [1,85,169,253,337] -- λ> foldl1 lcm [1, 1+3, 1+5, 1+6] -- 84 -- se observa que los resultados son progresiones aritméticas cuyo -- primer elemento es a(0) y la diferencia es el mínimo común múltiplo -- de [a(0), a(0)+a(1), a(0)+a(2), ..., a(0)+a(n)] divisiblesSucesion2 :: [Integer] -> [Integer] divisiblesSucesion2 [] = [1..] divisiblesSucesion2 (a0:as) = [a0,a0+m..] where m = mcm (a0 : [a0+a | a <- as]) -- (mcm xs) es el mínimo común múltiplo de xs. Por ejemplo, -- mcm [2,5,3] == 30 -- mcm [2,2+5,2+3] == 70 mcm :: [Integer] -> Integer mcm = foldl1 lcm -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_equivalencia :: [Integer] -> Bool prop_equivalencia xs = take 3 (divisiblesSucesion ys) == take 3 (divisiblesSucesion2 ys) where ys = take 5 [1 + (x `mod` 10) | x <- xs] -- La comprobación es -- λ> quickCheck prop_equivalencia -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> divisiblesSucesion [3,5..30] !! 20 -- 28828803 -- (16.86 secs, 15,933,990,784 bytes) -- λ> divisiblesSucesion2 [3,5..30] !! 20 -- 28828803 -- (0.01 secs, 112,496 bytes) |
Nuevas soluciones
- En los comentarios se pueden escribir nuevas soluciones.
- El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>