La sucesión del reloj astronómico de Praga
La cadena infinita «1234321234321234321…», formada por la repetición de los dígitos 123432, tiene una propiedad (en la que se basa el funcionamiento del reloj astronómico de Praga: la cadena se puede partir en una sucesión de números, de forma que la suma de los dígitos de dichos números es la sucesión de los números naturales, como se observa a continuación:
|
1 2 |
1, 2, 3, 4, 32, 123, 43, 2123, 432, 1234, 32123, ... 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... |
Definir la lista
|
1 |
reloj :: [Integer] |
cuyos elementos son los términos de la sucesión anterior. Por ejemplo,
|
1 2 3 4 |
λ> take 11 reloj [1,2,3,4,32,123,43,2123,432,1234,32123] λ> (reloj !! 1000) `mod` (10^50) 23432123432123432123432123432123432123432123432123 |
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 |
import Data.List (inits, tails) import Data.Char (digitToInt) import Test.QuickCheck (NonNegative (NonNegative), quickCheck) -- 1ª solución -- =========== reloj1 :: [Integer] reloj1 = aux [1..] (cycle "123432") where aux (n:ns) xs = read ys : aux ns zs where (ys,zs) = prefijoSuma n xs -- (prefijoSuma n xs) es el par formado por el primer prefijo de xs cuyo -- suma es n y el resto de xs. Por ejemplo, -- prefijoSuma 6 "12343" == ("123","43") prefijoSuma :: Int -> String -> (String,String) prefijoSuma n xs = head [(us,vs) | (us,vs) <- zip (inits xs) (tails xs) , sumaD us == n] -- (sumaD xs) es la suma de los dígitos de xs. Por ejemplo, -- sumaD "123" == 6 sumaD :: String -> Int sumaD = sum . map digitToInt -- 2ª solución -- =========== reloj2 :: [Integer] reloj2 = aux [1..] (cycle "123432") where aux (n:ns) xs = read ys : aux ns zs where (ys,zs) = prefijoSuma2 n xs -- (prefijoSuma n xs) es el par formado por el primer prefijo de xs cuyo -- suma es n y el resto de xs. Por ejemplo, -- prefijoSuma2 6 "12343" == ("123","43") prefijoSuma2 :: Int -> String -> (String,String) prefijoSuma2 n (x:xs) | y == n = ([x],xs) | otherwise = (x:ys,zs) where y = read [x] (ys,zs) = prefijoSuma2 (n-y) xs -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_reloj :: NonNegative Int -> Bool prop_reloj (NonNegative n) = reloj1 !! n == reloj2 !! n -- La comprobación es -- λ> quickCheck prop_reloj -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> (reloj1 !! 1000) `mod` (10^9) -- 123432123 -- (2.47 secs, 5,797,620,784 bytes) -- λ> (reloj2 !! 1000) `mod` (10^9) -- 123432123 -- (0.44 secs, 798,841,528 bytes) |
El código se encuentra en GitHub.