Esta semana he publicado en Exercitium las soluciones de los siguientes problemas:
A continuación se muestran las soluciones.
1. Huecos maximales entre primos
El hueco de un número primo p es la distancia entre p y primo siguiente de p. Por ejemplo, el hueco de 7 es 4 porque el primo siguiente de 7 es 11 y 4 = 11-7. Los huecos de los primeros números son
|
|
Primo Hueco 2 1 3 2 7 4 11 2 |
El hueco de un número primo p es maximal si es mayor que huecos de todos los números menores que p. Por ejemplo, 4 es un hueco maximal de 7 ya que los huecos de los primos menores que 7 son 1 y 2 y ambos son menores que 4. La tabla de los primeros huecos maximales es
|
|
Primo Hueco 2 1 3 2 7 4 23 6 89 8 113 14 523 18 887 20 |
Definir la sucesión
|
|
primosYhuecosMaximales :: [(Integer,Integer)] |
cuyos elementos son los números primos con huecos maximales junto son sus huecos. Por ejemplo,
|
|
λ> take 8 primosYhuecosMaximales [(2,1),(3,2),(7,4),(23,6),(89,8),(113,14),(523,18),(887,20)] λ> primosYhuecosMaximales !! 20 (2010733,148) |
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 85 86 87 88 89 |
import Data.Numbers.Primes (primes) import Test.QuickCheck (NonNegative (NonNegative), quickCheckWith, maxSize, stdArgs) -- 1ª solución -- =========== primosYhuecosMaximales1 :: [(Integer,Integer)] primosYhuecosMaximales1 = [(p,huecoPrimo p) | p <- primes, esMaximalHuecoPrimo p] -- (siguientePrimo x) es el menor primo mayor que x. Por ejemplo, -- siguientePrimo 7 == 11 -- siguientePrimo 8 == 11 siguientePrimo :: Integer -> Integer siguientePrimo p = head (dropWhile (<= p) primes) -- (huecoPrimo p) es la distancia del primo p hasta el siguiente -- primo. Por ejemplo, -- huecoPrimo 7 == 4 huecoPrimo :: Integer -> Integer huecoPrimo p = siguientePrimo p - p -- (esMaximalHuecoPrimo p) se verifica si el hueco primo de p es -- maximal. Por ejemplo, -- esMaximalHuecoPrimo 7 == True -- esMaximalHuecoPrimo 11 == False esMaximalHuecoPrimo :: Integer -> Bool esMaximalHuecoPrimo p = and [huecoPrimo n < h | n <- takeWhile (< p) primes] where h = huecoPrimo p -- 2ª solución -- =========== primosYhuecosMaximales2 :: [(Integer,Integer)] primosYhuecosMaximales2 = aux primosYhuecos where aux ((x,y):ps) = (x,y) : aux (dropWhile (\(_,b) -> b <= y) ps) -- primosYhuecos es la lista de los números primos junto son sus -- huecos. Por ejemplo, -- λ> take 10 primosYhuecos -- [(2,1),(3,2),(5,2),(7,4),(11,2),(13,4),(17,2),(19,4),(23,6),(29,2)] primosYhuecos :: [(Integer,Integer)] primosYhuecos = [(x,y-x) | (x,y) <- zip primes (tail primes)] -- 3ª solución -- =========== primosYhuecosMaximales3 :: [(Integer,Integer)] primosYhuecosMaximales3 = aux 0 primes where aux n (x:y:zs) | y-x > n = (x,y-x) : aux (y-x) (y:zs) | otherwise = aux n (y:zs) -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_primosYhuecosMaximales :: NonNegative Int -> Bool prop_primosYhuecosMaximales (NonNegative n) = all (== primosYhuecosMaximales1 !! n) [primosYhuecosMaximales2 !! n, primosYhuecosMaximales3 !! n] -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=12}) prop_primosYhuecosMaximales -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> primosYhuecosMaximales1 !! 10 -- (9551,36) -- (2.63 secs, 7,400,316,112 bytes) -- λ> primosYhuecosMaximales2 !! 10 -- (9551,36) -- (0.01 secs, 7,060,744 bytes) -- λ> primosYhuecosMaximales3 !! 10 -- (9551,36) -- (0.01 secs, 4,000,368 bytes) -- -- λ> primosYhuecosMaximales2 !! 22 -- (17051707,180) -- (7.90 secs, 17,275,407,712 bytes) -- λ> primosYhuecosMaximales3 !! 22 -- (17051707,180) -- (3.78 secs, 8,808,779,096 bytes) |
Referencias
Basado en el ejercicio Maximal prime gaps de
Programming Praxis.
Otras referencias
El código se encuentra en GitHub.
2. Números belgas
Un número n es k-belga si la sucesión cuyo primer elemento es k y cuyos elementos se obtienen sumando reiteradamente las cifras de n contiene a n.
El 18 es 0-belga, porque a partir del 0 vamos a ir sumando sucesivamente 1, 8, 1, 8, … hasta llegar o sobrepasar el 18: 0, 1, 9, 10, 18, … Como se alcanza el 18, resulta que el 18 es 0-belga.
El 19 no es 1-belga, porque a partir del 1 vamos a ir sucesivamente 1, 9, 1, 9, … hasta llegar o sobrepasar el 18: 0, 1, 10, 11, 20, 21, … Como no se alcanza el 19, resulta que el 19 no es 1-belga.
Definir la función
|
|
esBelga :: Int -> Int -> Bool |
tal que (esBelga k n) se verifica si n es k-belga. Por ejemplo,
|
|
esBelga 0 18 == True esBelga 1 19 == False esBelga 0 2016 == True [x | x <- [0..30], esBelga 7 x] == [7,10,11,21,27,29] [x | x <- [0..30], esBelga 10 x] == [10,11,20,21,22,24,26] length [n | n <- [1..10^6], esBelga 0 n] == 272049 |
Comprobar con QuickCheck que para todo número entero positivo n, si k es el resto de n entre la suma de los dígitos de n, entonces n es k-belga.
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 |
import Data.Char (digitToInt) import Test.QuickCheck (Positive (Positive), quickCheck) -- 1ª solución -- =========== esBelga1 :: Int -> Int -> Bool esBelga1 k n = n == head (dropWhile (<n) (scanl (+) k (cycle (digitos n)))) digitos :: Int -> [Int] digitos n = map digitToInt (show n) -- 2ª solución -- =========== esBelga2 :: Int -> Int -> Bool esBelga2 k n = k <= n && n == head (dropWhile (<n) (scanl (+) (k + q * s) ds)) where ds = digitos n s = sum ds q = (n - k) `div` s -- Equivalencia -- ============ -- La propiedad es prop_esBelga :: Positive Int -> Positive Int -> Bool prop_esBelga (Positive k) (Positive n) = esBelga1 k n == esBelga2 k n -- La comprobación es -- λ> quickCheck prop_esBelga -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length [n | n <- [1..2*10^4], esBelga1 0 n] -- 6521 -- (6.27 secs, 6,508,102,192 bytes) -- λ> length [n | n <- [1..2*10^4], esBelga2 0 n] -- 6521 -- (0.07 secs, 46,741,144 bytes) -- Verificación de la propiedad -- ============================ -- La propiedad es prop_Belga :: Positive Int -> Bool prop_Belga (Positive n) = esBelga2 k n where k = n `mod` sum (digitos n) -- La comprobación es -- λ> quickCheck prop_Belga -- +++ OK, passed 100 tests. |
Referencias
Basado en el artículo Números belgas del blog Números y hoja de cálculo de Antonio Roldán Martínez.
El código se encuentra en GitHub.
3. La serie de Thue-Morse
La serie de Thue-Morse comienza con el término [0] y sus siguientes términos se construyen añadiéndole al anterior su complementario (es decir, la lista obtenida cambiando el 0 por 1 y el 1 por 0). Los primeros términos de la serie son
|
|
[0] [0,1] [0,1,1,0] [0,1,1,0,1,0,0,1] [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0] |
Definir la lista
|
|
serieThueMorse :: [[Int]] |
tal que sus elementos son los términos de la serie de Thue-Morse. Por ejemplo,
|
|
λ> take 4 serieThueMorse [[0],[0,1],[0,1,1,0],[0,1,1,0,1,0,0,1]] |
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 |
import Test.QuickCheck (NonNegative (NonNegative), quickCheckWith, maxSize, stdArgs) -- 1ª solución -- =========== serieThueMorse1 :: [[Int]] serieThueMorse1 = map termSerieThueMorse [0..] -- (termSerieThueMorse n) es el término n-ésimo de la serie de -- Thue-Morse. Por ejemplo, -- termSerieThueMorse 1 == [0,1] -- termSerieThueMorse 2 == [0,1,1,0] -- termSerieThueMorse 3 == [0,1,1,0,1,0,0,1] -- termSerieThueMorse 4 == [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0] termSerieThueMorse :: Int -> [Int] termSerieThueMorse 0 = [0] termSerieThueMorse n = xs ++ complementaria xs where xs = termSerieThueMorse (n-1) -- (complementaria xs) es la complementaria de la lista xs (formada por -- ceros y unos); es decir, la lista obtenida cambiando el 0 por 1 y el -- 1 por 0. Por ejemplo, -- complementaria [1,0,0,1,1,0,1] == [0,1,1,0,0,1,0] complementaria :: [Int] -> [Int] complementaria = map (1-) -- 2ª solución -- =========== serieThueMorse2 :: [[Int]] serieThueMorse2 = [0] : map paso serieThueMorse2 where paso xs = xs ++ complementaria xs -- 3ª solución -- =========== serieThueMorse3 :: [[Int]] serieThueMorse3 = iterate paso [0] where paso xs = xs ++ complementaria xs -- 4ª solución -- =========== -- Observando que cada término de la serie de Thue-Morse se obtiene del -- anterior sustituyendo los 1 por 1, 0 y los 0 por 0, 1. serieThueMorse4 :: [[Int]] serieThueMorse4 = [0] : map (concatMap paso4) serieThueMorse4 where paso4 x = [x,1-x] -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_serieThueMorse :: NonNegative Int -> Bool prop_serieThueMorse (NonNegative n) = all (== serieThueMorse1 !! n) [serieThueMorse2 !! n, serieThueMorse3 !! n, serieThueMorse4 !! n] -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=20}) prop_serieThueMorse -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> (serieThueMorse1 !! 23) !! (2^22) -- 1 -- (1.08 secs, 839,419,224 bytes) -- λ> (serieThueMorse2 !! 23) !! (2^22) -- 1 -- (0.61 secs, 839,413,592 bytes) -- λ> (serieThueMorse3 !! 23) !! (2^22) -- 1 -- (1.43 secs, 839,413,592 bytes) -- λ> (serieThueMorse4 !! 23) !! (2^22) -- 1 -- (1.57 secs, 1,007,190,024 bytes) |
El código se encuentra en [GitHub](https://github.com/jaalonso/Exercitium/blob/main/src/
Referencias
4. La sucesión de Thue-Morse
La serie de Thue-Morse comienza con el término [0] y sus siguientes términos se construyen añadiéndole al anterior su complementario. Los primeros términos de la serie son
|
|
[0] [0,1] [0,1,1,0] [0,1,1,0,1,0,0,1] [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0] |
De esta forma se va formando una sucesión
|
|
0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,... |
que se conoce como la sucesión de Thue-Morse.
Definir la sucesión
cuyos elementos son los de la sucesión de Thue-Morse. Por ejemplo,
|
|
λ> take 30 sucThueMorse [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0] λ> map (sucThueMorse4 !!) [1234567..1234596] [1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0] λ> map (sucThueMorse4 !!) [4000000..4000030] [1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1] |
Comprobar con QuickCheck que si s(n) representa el término n-ésimo de la sucesión de Thue-Morse, entonces
|
|
s(2n) = s(n) s(2n+1) = 1 - s(n) |
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 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 |
import Test.QuickCheck -- 1ª solución -- =========== sucThueMorse1 :: [Int] sucThueMorse1 = map termSucThueMorse1 [0..] -- (termSucThueMorse1 n) es el n-ésimo término de la sucesión de -- Thue-Morse. Por ejemplo, -- termSucThueMorse1 0 == 0 -- termSucThueMorse1 1 == 1 -- termSucThueMorse1 2 == 1 -- termSucThueMorse1 3 == 0 -- termSucThueMorse1 4 == 1 termSucThueMorse1 :: Int -> Int termSucThueMorse1 0 = 0 termSucThueMorse1 n = (serieThueMorse !! k) !! n where k = 1 + floor (logBase 2 (fromIntegral n)) -- serieThueMorse es la lista cuyos elementos son los términos de la -- serie de Thue-Morse. Por ejemplo, -- λ> take 4 serieThueMorse3 -- [[0],[0,1],[0,1,1,0],[0,1,1,0,1,0,0,1]] serieThueMorse :: [[Int]] serieThueMorse = iterate paso [0] where paso xs = xs ++ map (1-) xs -- 2ª solución -- =========== sucThueMorse2 :: [Int] sucThueMorse2 = 0 : intercala (map (1-) sucThueMorse2) (tail sucThueMorse2) -- (intercala xs ys) es la lista obtenida intercalando los elementos de -- las listas infinitas xs e ys. Por ejemplo, -- take 10 (intercala [1,5..] [2,4..]) == [1,2,5,4,9,6,13,8,17,10] intercala :: [a] -> [a] -> [a] intercala (x:xs) ys = x : intercala ys xs -- 3ª solución -- =========== sucThueMorse3 :: [Int] sucThueMorse3 = 0 : 1 : aux (tail sucThueMorse3) where aux (x : xs) = x : (1 - x) : aux xs -- 4ª solución -- =========== sucThueMorse4 :: [Int] sucThueMorse4 = 0 : aux [1] where aux xs = xs ++ aux (xs ++ map (1-) xs) -- Comprobación de la propiedad -- ============================ -- La propiedad es prop_termSucThueMorse :: NonNegative Int -> Bool prop_termSucThueMorse (NonNegative n) = sucThueMorse1 !! (2*n) == sn && sucThueMorse1 !! (2*n+1) == 1 - sn where sn = sucThueMorse1 !! n -- La comprobación es -- λ> quickCheck prop_termSucThueMorse -- +++ OK, passed 100 tests. -- 5ª solución -- =========== sucThueMorse5 :: [Int] sucThueMorse5 = map termSucThueMorse5 [0..] -- (termSucThueMorse5 n) es el n-ésimo término de la sucesión de -- Thue-Morse. Por ejemplo, -- termSucThueMorse5 0 == 0 -- termSucThueMorse5 1 == 1 -- termSucThueMorse5 2 == 1 -- termSucThueMorse5 3 == 0 -- termSucThueMorse5 4 == 1 termSucThueMorse5 :: Int -> Int termSucThueMorse5 0 = 0 termSucThueMorse5 n | even n = termSucThueMorse5 (n `div` 2) | otherwise = 1 - termSucThueMorse5 (n `div` 2) -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_sucThueMorse :: NonNegative Int -> Bool prop_sucThueMorse (NonNegative n) = all (== sucThueMorse1 !! n) [sucThueMorse2 !! n, sucThueMorse3 !! n, sucThueMorse4 !! n, sucThueMorse5 !! n] -- La comprobación es -- λ> quickCheck prop_sucThueMorse -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> sucThueMorse1 !! (10^7) -- 0 -- (3.28 secs, 3,420,080,168 bytes) -- λ> sucThueMorse2 !! (10^7) -- 0 -- (3.01 secs, 1,720,549,640 bytes) -- λ> sucThueMorse3 !! (10^7) -- 0 -- (1.80 secs, 1,360,550,040 bytes) -- λ> sucThueMorse4 !! (10^7) -- 0 -- (0.88 secs, 1,254,772,768 bytes) -- λ> sucThueMorse5 !! (10^7) -- 0 -- (0.62 secs, 1,600,557,072 bytes) |
El código se encuentra en GitHub.
Referencias
5. Sumas de dos primos
Definir la sucesión
|
|
sumasDeDosPrimos :: [Integer] |
cuyos elementos son los números que se pueden escribir como suma de dos números primos. Por ejemplo,
|
|
λ> take 23 sumasDeDosPrimos [4,5,6,7,8,9,10,12,13,14,15,16,18,19,20,21,22,24,25,26,28,30,31] λ> sumasDeDosPrimos !! (5*10^5) 862878 |
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 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
import Data.Numbers.Primes (isPrime, primes) import Test.QuickCheck -- 1ª solución -- =========== sumasDeDosPrimos1 :: [Integer] sumasDeDosPrimos1 = [n | n <- [1..], not (null (sumaDeDosPrimos1 n))] -- (sumaDeDosPrimos1 n) es la lista de pares de primos cuya suma es -- n. Por ejemplo, -- sumaDeDosPrimos 9 == [(2,7),(7,2)] -- sumaDeDosPrimos 16 == [(3,13),(5,11),(11,5),(13,3)] -- sumaDeDosPrimos 17 == [] sumaDeDosPrimos1 :: Integer -> [(Integer,Integer)] sumaDeDosPrimos1 n = [(x,n-x) | x <- primosN, isPrime (n-x)] where primosN = takeWhile (< n) primes -- 2ª solución -- =========== sumasDeDosPrimos2 :: [Integer] sumasDeDosPrimos2 = [n | n <- [1..], not (null (sumaDeDosPrimos2 n))] -- (sumasDeDosPrimos2 n) es la lista de pares (x,y) de primos cuya suma -- es n y tales que x <= y. Por ejemplo, -- sumaDeDosPrimos2 9 == [(2,7)] -- sumaDeDosPrimos2 16 == [(3,13),(5,11)] -- sumaDeDosPrimos2 17 == [] sumaDeDosPrimos2 :: Integer -> [(Integer,Integer)] sumaDeDosPrimos2 n = [(x,n-x) | x <- primosN, isPrime (n-x)] where primosN = takeWhile (<= (n `div` 2)) primes -- 3ª solución -- =========== sumasDeDosPrimos3 :: [Integer] sumasDeDosPrimos3 = filter esSumaDeDosPrimos3 [4..] -- (esSumaDeDosPrimos3 n) se verifica si n es suma de dos primos. Por -- ejemplo, -- esSumaDeDosPrimos3 9 == True -- esSumaDeDosPrimos3 16 == True -- esSumaDeDosPrimos3 17 == False esSumaDeDosPrimos3 :: Integer -> Bool esSumaDeDosPrimos3 n | odd n = isPrime (n-2) | otherwise = any isPrime [n-x | x <- takeWhile (<= (n `div` 2)) primes] -- 4ª solución -- =========== -- Usando la conjetura de Goldbach que dice que "Todo número par mayor -- que 2 puede escribirse como suma de dos números primos" . sumasDeDosPrimos4 :: [Integer] sumasDeDosPrimos4 = filter esSumaDeDosPrimos4 [4..] -- (esSumaDeDosPrimos4 n) se verifica si n es suma de dos primos. Por -- ejemplo, -- esSumaDeDosPrimos4 9 == True -- esSumaDeDosPrimos4 16 == True -- esSumaDeDosPrimos4 17 == False esSumaDeDosPrimos4 :: Integer -> Bool esSumaDeDosPrimos4 n = even n || isPrime (n-2) -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_sumasDeDosPrimos :: NonNegative Int -> Bool prop_sumasDeDosPrimos (NonNegative n) = all (== sumasDeDosPrimos1 !! n) [sumasDeDosPrimos2 !! n, sumasDeDosPrimos3 !! n, sumasDeDosPrimos4 !! n] -- La comprobación es -- λ> quickCheck prop_sumasDeDosPrimos -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> sumasDeDosPrimos1 !! 5000 -- 7994 -- (2.61 secs, 9,299,106,792 bytes) -- λ> sumasDeDosPrimos2 !! 5000 -- 7994 -- (1.48 secs, 5,190,651,760 bytes) -- λ> sumasDeDosPrimos3 !! 5000 -- 7994 -- (0.12 secs, 351,667,104 bytes) -- λ> sumasDeDosPrimos4 !! 5000 -- 7994 -- (0.04 secs, 63,464,320 bytes) -- -- λ> sumasDeDosPrimos3 !! (5*10^4) -- 83674 -- (2.23 secs, 7,776,049,264 bytes) -- λ> sumasDeDosPrimos4 !! (5*10^4) -- 83674 -- (0.34 secs, 1,183,604,984 bytes) |
El código se encuentra en GitHub.
Referencia
Se puede imprimir o compartir con