Transformaciones lineales de números triangulares
La sucesión de los números triangulares se obtiene sumando los números naturales. Así, los 8 primeros números triangulares son
1 = 1 3 = 1+2 6 = 1+2+3 10 = 1+2+3+4 15 = 1+2+3+4+5 21 = 1+2+3+4+5+6 28 = 1+2+3+4+5+6+7 36 = 1+2+3+4+5+6+7+8
Para cada número triangular n existen números naturales a y b, tales que a . n + b también es triangular. Para n = 6, se tiene que
6 = 1 * 6 + 0 15 = 2 * 6 + 3 21 = 3 * 6 + 3 28 = 4 * 6 + 4 36 = 5 * 6 + 5
son números triangulares
Definir la función
transformaciones :: Integer -> [(Integer,Integer)]
tal que si n es triangular, (transformaciones n) es la lista de los pares (a,b) tales que a es un entero positivo y b el menor número tal que a . n + b es triangular. Por ejemplo,
take 5 (transformaciones 6) == [(1,0),(2,3),(3,3),(4,4),(5,6)] take 5 (transformaciones 15) == [(1,0),(2,6),(3,10),(4,6),(5,3)] transformaciones 21 !! (7*10^7) == (70000001,39732)
Soluciones
-- 1ª solución -- =========== transformaciones :: Integer -> [(Integer,Integer)] transformaciones n = (1,0) : [(a, f a) | a <- [2..]] where f a = head (dropWhile (<= a*n) triangulares) - a*n -- triangulares es la lista de los números triangulares. Por ejemplo, -- take 5 triangulares == [1,3,6,10,15] triangulares :: [Integer] triangulares = scanl1 (+) [1..] -- 2ª solución -- =========== transformaciones2 :: Integer -> [(Integer,Integer)] transformaciones2 n = (1,0): map g [2..] where g a = (a, head (dropWhile (<= a*n) triangulares) - a*n) -- Comparación de eficiencia -- ========================= -- λ> transformaciones 21 !! (2*10^7) -- (20000001,21615) -- (3.02 secs, 4,320,111,544 bytes) -- λ> transformaciones2 21 !! (2*10^7) -- (20000001,21615) -- (0.44 secs, 3,200,112,320 bytes) -- -- λ> transformaciones2 21 !! (7*10^7) -- (70000001,39732) -- (1.41 secs, 11,200,885,336 bytes)