Menor con suma de dígitos dada
Definir la función
1 |
minSumDig :: Integer -> Integer |
tal que (minSumDig n) es el menor número x tal que la suma de los dígitos de x es n. Por ejemplo,
1 2 3 4 5 6 7 8 |
minSumDig 1 == 1 minSumDig 12 == 39 minSumDig 21 == 399 (length . show . minSumDig) (3*10^5) == 33334 (length . show . minSumDig) (3*10^6) == 333334 (length . show . minSumDig) (3*10^7) == 3333334 (length . show . minSumDig) (4*10^7) == 4444445 (length . show . minSumDig) (5*10^7) == 5555556 |
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 |
import Data.List (genericIndex) -- 1ª definición -- ============= minSumDig1 :: Integer -> Integer minSumDig1 n = head [x | x <- [0..], sumaDigitos x == n] sumaDigitos :: Integer -> Integer sumaDigitos n | n < 10 = n | otherwise = y + sumaDigitos x where (x, y) = divMod n 10 -- 2ª definición minSumDig2 :: Integer -> Integer minSumDig2 n | n < 10 = n | otherwise = 9 + 10 * minSumDig2 (n - 9) -- 3ª definición minSumDig3 :: Integer -> Integer minSumDig3 n = (r + 1) * 10^d - 1 where (d,r) = divMod n 9 -- Comparación de eficiencia -- ========================= -- λ> minSumDig1 46 -- 199999 -- (3.21 secs, 542,721,696 bytes) -- λ> minSumDig2 46 -- 199999 -- (0.01 secs, 142,056 bytes) -- λ> minSumDig3 46 -- 199999 -- (0.01 secs, 155,984 bytes) -- -- λ> (length . show . minSumDig2) (3*10^5) -- 33334 -- (1.79 secs, 492,200,376 bytes) -- λ> (length . show . minSumDig3) (3*10^5) -- 33334 -- (0.11 secs, 50,119,840 bytes) |
Se puede definir por recursión (aunque es menos eficiente que la fórmula directa).