Números de suma prima hereditarios por la derecha
Decimos que un número es de suma prima si la suma de todos sus dígitos es un número primo. Por ejemplo el número 562 es de suma prima pues la suma de sus dígitos es el número primo 13; sin embargo, el número 514 no es de suma prima pues la suma de sus dígitos es 10, que no es primo.
Decimos que un número es de suma prima hereditario por la derecha si es de suma prima y los números que se obtienen eliminando sus últimas cifras también son de suma prima. Por ejemplo 7426 es de suma prima hereditario por la derecha pues 7426, 742, 74 y 7 son todos números de suma prima.
Definir la constante
|
1 |
listaSumaPrimaHD :: [Integer] |
cuyo valor es la lista infinita de los números de suma prima hereditarios por la derecha. Por ejemplo,
|
1 2 |
take 10 listaSumaPrimaHD == [2,3,5,7,20,21,23,25,29,30] listaSumaPrimaHD !! 2000000 == 3800024668046 |
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 74 75 76 77 78 79 80 81 82 83 84 |
import Data.Char (digitToInt) import Data.Array import Data.Numbers.Primes (isPrime) -- 1ª definición -- ============= listaSumaPrimaHD1 :: [Integer] listaSumaPrimaHD1 = filter sumaPrimaHD [1..] -- (sumaPrimaHD n) se verifica si n es de suma prima hereditario por la -- derecha. Por ejemplo, -- sumaPrimaHD 7426 == True -- sumaPrimaHD 7427 == False sumaPrimaHD n | n < 10 = isPrime n | otherwise = sumaPrima n && sumaPrimaHD (n `div` 10) -- (sumaPrima n) se verifica si n es un número de suma prima. Por -- ejemplo, -- sumaPrima 562 == True -- sumaPrima 514 == False sumaPrima :: Integer -> Bool sumaPrima = isPrime . sum . digitos -- (digitos n) es la lista de los dígitos de n. Por ejemplo, -- digitos 325 == [3,2,5] digitos :: Integer -> [Integer] digitos = map (fromIntegral . digitToInt) . show -- 2ª definición -- ============= listaSumaPrimaHD2 :: [Integer] listaSumaPrimaHD2 = map fst paresSumaPrimaHDDigitos paresSumaPrimaHDDigitos :: [(Integer, Integer)] paresSumaPrimaHDDigitos = paresSumaPrimaHDDigitosAux 1 [(2,2),(3,3),(5,5),(7,7)] paresSumaPrimaHDDigitosAux :: Integer -> [(Integer,Integer)] -> [(Integer,Integer)] paresSumaPrimaHDDigitosAux n ac = ac ++ paresSumaPrimaHDDigitosAux (n+1) (concatMap extiendeSumaPrimaHD ac) extiendeSumaPrimaHD :: (Integer,Integer) -> [(Integer,Integer)] extiendeSumaPrimaHD (n,s) = [(n*10+k,s+k) | k <- [0..9], isPrime (s+k)] -- 3ª definición -- ============= listaSumaPrimaHD3 :: [Integer] listaSumaPrimaHD3 = map fst (concat (iterate (concatMap extiendeSumaPrimaHD3) [(2,2),(3,3),(5,5),(7,7)])) extiendeSumaPrimaHD3 :: (Integer,Integer) -> [(Integer,Integer)] extiendeSumaPrimaHD3 (n,s) = [(n*10+k,s+k) | k <- extensiones ! s] extensiones :: Array Integer [Integer] extensiones = array (1,1000) [(n,[k | k <- [0..9], isPrime (n+k)]) | n <- [1..1000]] -- Comparación de eficiencia -- ========================= -- ghci> listaSumaPrimaHD1 !! 600 -- 34004 -- (2.47 secs, 1565301720 bytes) -- ghci> listaSumaPrimaHD2 !! 600 -- 34004 -- (0.02 secs, 7209000 bytes) -- ghci> listaSumaPrimaHD3 !! 600 -- 34004 -- (0.01 secs, 1579920 bytes) -- -- ghci> listaSumaPrimaHD2 !! 2000000 -- 3800024668046 -- (45.41 secs, 29056613824 bytes) -- ghci> listaSumaPrimaHD3 !! 2000000 -- 3800024668046 -- (4.29 secs, 973265400 bytes) |
4 Comentarios