Euler – Exercitium

Suma de primos menores

José A. Alonso, 9-diciembre-2019, Medio

La suma de los primos menores que 10 es 2 + 3 + 5 + 7 = 17.

Definir la función

   sumaPrimosMenores :: Integer -> Integer

tal que (sumaPrimosMenores n) es la suma de los primos menores que n. Por ejemplo,

   sumaPrimosMenores 10        ==  17
   sumaPrimosMenores (5*10^5)  ==  9914236195

Nota: Este ejercicio está basado en el problema 10 del Proyecto Euler

Soluciones

import Data.Numbers.Primes (primes)
 
-- 1ª solución
-- ===========
 
sumaPrimosMenores :: Integer -> Integer
sumaPrimosMenores n = sum (takeWhile (<n) primos)
 
-- primos es la lista de los números primos. Por ejemplo,
--    λ> take 12 primos
--    [2,3,5,7,11,13,17,19,23,29,31,37]
primos :: [Integer]
primos = 2 : filter esPrimo [3,5..]
 
esPrimo :: Integer -> Bool
esPrimo n = null [x | x <- [2..(ceiling . sqrt . fromIntegral) n]
                    , n `mod` x == 0]
 
-- 2ª solución
-- ===========
 
sumaPrimosMenores2 :: Integer -> Integer
sumaPrimosMenores2 n = sum (takeWhile (<n) primos2)
 
primos2 :: [Integer]
primos2 = 2 : filter esPrimo2 [3,5..]
 
esPrimo2 :: Integer -> Bool
esPrimo2 x =
  all ((/= 0) . mod x)
  (takeWhile (<= floor (sqrt (fromIntegral x))) primos2)
 
-- 3ª solución
-- ===========
 
sumaPrimosMenores3 :: Integer -> Integer
sumaPrimosMenores3 n = sum (takeWhile (<n) primes)
 
-- Comparación de eficiencia
-- =========================
 
--    λ> sumaPrimosMenores (2*10^5)
--    1709600813
--    (2.56 secs, 1,522,015,240 bytes)
--    λ> sumaPrimosMenores2 (2*10^5)
--    1709600813
--    (0.56 secs, 376,951,456 bytes)
--    λ> sumaPrimosMenores3 (2*10^5)
--    1709600813
--    (0.07 secs, 62,321,888 bytes)

Pensamiento

El movimiento no es nada esencial. La fuerza puede ser inmóvil (lo es en su estado de pureza); mas no por ello deja de ser activa.

Antonio Machado

Leer más →

Múltiplos palíndromos

José A. Alonso, 2-diciembre-2019, Medio

Los números 545, 5995 y 15151 son los tres menores palíndromos (capicúas) que son divisibles por 109.

Definir las funciones

   multiplosPalindromos :: Integer -> [Integer]
   multiplosPalindromosMenores :: Integer -> Integer -> [Integer]

tales que

(multiplosPalindromos n) es la lista de los palíndromos divisibles por n. Por ejemplo,

     take 5 (multiplosPalindromos 109) == [545,5995,15151,64746,74447]

(multiplosPalindromosMenores x n) es la lista de los palíndromos divisibles por n, menores que x. Por ejemplo,

     λ> multiplosPalindromosMenores (10^5) 109
     [545,5995,15151,64746,74447,79897,84148,89598,99299]

Nota: Este ejercicio está basado en el problema 655 del Proyecto Euler.

Soluciones

-- 1ª definición de multiplosPalindromos
-- =====================================
 
multiplosPalindromos :: Integer -> [Integer]
multiplosPalindromos n =
  [x | x <- multiplos n
     , esPalindromo x]
 
-- (esPalindromo n) se verifica si n es palíndromo. Por ejemplo, 
--    esPalindromo 32523  ==  True
--    esPalindromo 32533  ==  False
esPalindromo :: Integer -> Bool
esPalindromo n = reverse xs == xs
  where xs = show n
 
-- (multiplos n) es la lista de los múltiplos de n. Por ejemplo, 
--    take 12 (multiplos 5)  ==  [5,10,15,20,25,30,35,40,45,50,55,60]
multiplos :: Integer -> [Integer]
multiplos n = [n,2*n..]
 
-- 2ª definición de multiplosPalindromos
-- =====================================
 
multiplosPalindromos2 :: Integer -> [Integer]
multiplosPalindromos2 = filter esPalindromo . multiplos 
 
-- 1ª definición de multiplosPalindromosMenores
-- ============================================
 
multiplosPalindromosMenores :: Integer -> Integer -> [Integer]
multiplosPalindromosMenores x n =
  takeWhile (<x) (multiplosPalindromos n)
 
-- 2ª definición de multiplosPalindromosMenores
-- ============================================
 
multiplosPalindromosMenores2 :: Integer -> Integer -> [Integer]
multiplosPalindromosMenores2 x =
  takeWhile (<x) . multiplosPalindromos

Pensamiento

Esta luz de Sevilla… Es el palacio
donde nací, con su rumor de fuente.

Antonio Machado

Leer más →

Mayor producto de n dígitos consecutivos de un número

José A. Alonso, 29-noviembre-2019, Medio

Definir la función

   mayorProducto :: Int -> Integer -> Integer

tal que (mayorProducto n x) es el mayor producto de n dígitos consecutivos del número x (suponiendo que x tiene al menos n dígitos). Por ejemplo,

   mayorProducto 2 325                  ==  10
   mayorProducto 5 11111                ==  1
   mayorProducto 5 113111               ==  3
   mayorProducto 5 110111               ==  0
   mayorProducto 5 10151112             ==  10
   mayorProducto 5 101511124            ==  10
   mayorProducto 5 (product [1..1000])  ==  41472

Nota: Este ejercicio está basado en el problema 8 del Proyecto Euler

Soluciones

import Data.List (inits, tails)
import Data.Char (digitToInt)
 
-- 1ª solución
-- ===========
 
mayorProducto :: Int -> Integer -> Integer
mayorProducto n x =
  maximum [product xs | xs <- segmentos n (digitos x)]
 
-- (digitos x) es la lista de las digitos del número x. Por ejemplo, 
--    digitos 325  ==  [3,2,5]
digitos :: Integer -> [Integer]
digitos x = map (toInteger . digitToInt) (show x)
 
-- (segmentos n xs) es la lista de los segmentos de longitud n de la
-- lista xs. Por ejemplo,
--    segmentos 2 [3,5,4,6]  ==  [[3,5],[5,4],[4,6]]
segmentos :: Int -> [Integer] -> [[Integer]]
segmentos n xs = take (length xs - n + 1) (map (take n) (tails xs))
 
-- 2ª solución
-- ===========
 
mayorProducto2 :: Int -> Integer -> Integer
mayorProducto2 n x = maximum (aux ns)
    where ns     = [read [d] | d <- show x]
          aux xs | length xs < n = []
                 | otherwise     = product (take n xs) : aux (tail xs)
 
-- 3ª solución
-- ===========
 
mayorProducto3 :: Int -> Integer -> Integer
mayorProducto3 n = maximum
                 . map (product . take n)
                 . filter ((>=n) . length) 
                 . tails
                 . digitos
 
-- 4ª solución
-- ===========
 
mayorProducto4 :: Int -> Integer -> Integer
mayorProducto4 n = maximum  
                 . map (product . map (fromIntegral . digitToInt)) 
                 . filter ((==n) . length) 
                 . concatMap inits
                 . tails 
                 . show
 
-- Comparación de eficiencia
-- =========================
 
--    λ> mayorProducto 5 (product [1..500])
--    28224
--    (0.01 secs, 1,645,256 bytes)
--    λ> mayorProducto2 5 (product [1..500])
--    28224
--    (0.03 secs, 5,848,416 bytes)
--    λ> mayorProducto3 5 (product [1..500])
--    28224
--    (0.03 secs, 1,510,640 bytes)
--    λ> mayorProducto4 5 (product [1..500])
--    28224
--    (1.85 secs, 10,932,551,216 bytes)
--    
--    λ> mayorProducto 5 (product [1..7000])
--    46656
--    (0.10 secs, 68,590,808 bytes)
--    λ> mayorProducto2 5 (product [1..7000])
--    46656
--    (1.63 secs, 157,031,432 bytes)
--    λ> mayorProducto3 5 (product [1..7000])
--    46656
--    (1.55 secs, 65,727,176 bytes)

import Data.List (inits, tails) import Data.Char (digitToInt) -- 1ª solución -- =========== mayorProducto :: Int -> Integer -> Integer mayorProducto n x = maximum [product xs | xs <- segmentos n (digitos x)] -- (digitos x) es la lista de las digitos del número x. Por ejemplo, -- digitos 325 == [3,2,5] digitos :: Integer -> [Integer] digitos x = map (toInteger . digitToInt) (show x) -- (segmentos n xs) es la lista de los segmentos de longitud n de la -- lista xs. Por ejemplo, -- segmentos 2 [3,5,4,6] == [[3,5],[5,4],[4,6]] segmentos :: Int -> [Integer] -> [[Integer]] segmentos n xs = take (length xs - n + 1) (map (take n) (tails xs)) -- 2ª solución -- =========== mayorProducto2 :: Int -> Integer -> Integer mayorProducto2 n x = maximum (aux ns) where ns = [read [d] | d <- show x] aux xs | length xs < n = [] | otherwise = product (take n xs) : aux (tail xs) -- 3ª solución -- =========== mayorProducto3 :: Int -> Integer -> Integer mayorProducto3 n = maximum . map (product . take n) . filter ((>=n) . length) . tails . digitos -- 4ª solución -- =========== mayorProducto4 :: Int -> Integer -> Integer mayorProducto4 n = maximum . map (product . map (fromIntegral . digitToInt)) . filter ((==n) . length) . concatMap inits . tails . show -- Comparación de eficiencia -- ========================= -- λ> mayorProducto 5 (product [1..500]) -- 28224 -- (0.01 secs, 1,645,256 bytes) -- λ> mayorProducto2 5 (product [1..500]) -- 28224 -- (0.03 secs, 5,848,416 bytes) -- λ> mayorProducto3 5 (product [1..500]) -- 28224 -- (0.03 secs, 1,510,640 bytes) -- λ> mayorProducto4 5 (product [1..500]) -- 28224 -- (1.85 secs, 10,932,551,216 bytes) -- -- λ> mayorProducto 5 (product [1..7000]) -- 46656 -- (0.10 secs, 68,590,808 bytes) -- λ> mayorProducto2 5 (product [1..7000]) -- 46656 -- (1.63 secs, 157,031,432 bytes) -- λ> mayorProducto3 5 (product [1..7000]) -- 46656 -- (1.55 secs, 65,727,176 bytes)

Pensamiento

«El control de la complejidad es la esencia de la programación.» ~ B.W. Kernigan

Leer más →

Menor divisible por todos

José A. Alonso, 28-noviembre-2019, Medio

Definir la función

   menorDivisible :: Integer -> Integer -> Integer

tal que (menorDivisible a b) es el menor número divisible por todos los números desde a hasta b, ambos inclusive. Por ejemplo,

   menorDivisible 1 10                        ==  2520
   length (show (menorDivisible 1 (3*10^5)))  ==  130141

Nota: Este ejercicio está basado en el problema 5 del Proyecto Euler

Soluciones

import Data.List (foldl')
 
-- 1ª solución
-- ===========
 
menorDivisible :: Integer -> Integer -> Integer
menorDivisible a b =
  head [x | x <- [b..]
          , and [x `mod` y == 0 | y <- [a..b]]]
 
-- 2ª solución
-- ===========
 
menorDivisible2 :: Integer -> Integer -> Integer
menorDivisible2 a b  
  | a == b    = a
  | otherwise = lcm a (menorDivisible (a+1) b)
 
-- 3ª solución
-- ============
 
menorDivisible3 :: Integer -> Integer -> Integer
menorDivisible3 a b = foldl lcm 1 [a..b] 
 
-- 4ª solución
-- ===========
 
menorDivisible4 :: Integer -> Integer -> Integer
menorDivisible4 a b = foldl1 lcm [a..b] 
 
-- 5ª solución
-- ===========
 
menorDivisible5 :: Integer -> Integer -> Integer
menorDivisible5 a b = foldl' lcm 1 [a..b] 
 
-- 6ª solución
-- ===========
 
menorDivisible6 :: Integer -> Integer -> Integer
menorDivisible6 a b = foldr1 lcm [a..b] 
 
-- 7ª solución
-- ===========
 
menorDivisible7 :: Integer -> Integer -> Integer
menorDivisible7 a = foldr1 lcm . enumFromTo a
 
-- Comparación de eficiencia
-- =========================
 
--   λ> menorDivisible 1 17
--   12252240
--   (18.63 secs, 15,789,475,488 bytes)
--   λ> menorDivisible2 1 17
--   12252240
--   (13.29 secs, 11,868,764,272 bytes)
--   λ> menorDivisible3 1 17
--   12252240
--   (0.00 secs, 114,688 bytes)
--   λ> menorDivisible4 1 17
--   12252240
--   (0.01 secs, 114,752 bytes)
--   λ> menorDivisible5 1 17
--   12252240
--   (0.01 secs, 110,640 bytes)
--   λ> menorDivisible6 1 17
--   12252240
--   (0.01 secs, 114,752 bytes)
--   λ> menorDivisible7 1 17
--   12252240
--   (0.00 secs, 110,912 bytes)
--   
--   λ> length (show (menorDivisible3 1 (10^5)))
--   43452
--   (1.54 secs, 2,021,887,000 bytes)
--   λ> length (show (menorDivisible4 1 (10^5)))
--   43452
--   (1.47 secs, 2,021,886,616 bytes)
--   λ> length (show (menorDivisible5 1 (10^5)))
--   43452
--   (0.65 secs, 2,009,595,568 bytes)
--   λ> length (show (menorDivisible6 1 (10^5)))
--   43452
--   (0.30 secs, 172,986,840 bytes)
--   λ> length (show (menorDivisible7 1 (10^5)))
--   43452
--   (0.30 secs, 172,986,920 bytes)
--   
--   λ> length (show (menorDivisible5 1 (2*10^5)))
--   86871
--   (2.47 secs, 7,989,147,304 bytes)
--   λ> length (show (menorDivisible6 1 (2*10^5)))
--   86871
--   (0.89 secs, 533,876,496 bytes)
--   λ> length (show (menorDivisible7 1 (2*10^5)))
--   86871
--   (0.88 secs, 533,875,608 bytes)

import Data.List (foldl') -- 1ª solución -- =========== menorDivisible :: Integer -> Integer -> Integer menorDivisible a b = head [x | x <- [b..] , and [x `mod` y == 0 | y <- [a..b]]] -- 2ª solución -- =========== menorDivisible2 :: Integer -> Integer -> Integer menorDivisible2 a b | a == b = a | otherwise = lcm a (menorDivisible (a+1) b) -- 3ª solución -- ============ menorDivisible3 :: Integer -> Integer -> Integer menorDivisible3 a b = foldl lcm 1 [a..b] -- 4ª solución -- =========== menorDivisible4 :: Integer -> Integer -> Integer menorDivisible4 a b = foldl1 lcm [a..b] -- 5ª solución -- =========== menorDivisible5 :: Integer -> Integer -> Integer menorDivisible5 a b = foldl' lcm 1 [a..b] -- 6ª solución -- =========== menorDivisible6 :: Integer -> Integer -> Integer menorDivisible6 a b = foldr1 lcm [a..b] -- 7ª solución -- =========== menorDivisible7 :: Integer -> Integer -> Integer menorDivisible7 a = foldr1 lcm . enumFromTo a -- Comparación de eficiencia -- ========================= -- λ> menorDivisible 1 17 -- 12252240 -- (18.63 secs, 15,789,475,488 bytes) -- λ> menorDivisible2 1 17 -- 12252240 -- (13.29 secs, 11,868,764,272 bytes) -- λ> menorDivisible3 1 17 -- 12252240 -- (0.00 secs, 114,688 bytes) -- λ> menorDivisible4 1 17 -- 12252240 -- (0.01 secs, 114,752 bytes) -- λ> menorDivisible5 1 17 -- 12252240 -- (0.01 secs, 110,640 bytes) -- λ> menorDivisible6 1 17 -- 12252240 -- (0.01 secs, 114,752 bytes) -- λ> menorDivisible7 1 17 -- 12252240 -- (0.00 secs, 110,912 bytes) -- -- λ> length (show (menorDivisible3 1 (10^5))) -- 43452 -- (1.54 secs, 2,021,887,000 bytes) -- λ> length (show (menorDivisible4 1 (10^5))) -- 43452 -- (1.47 secs, 2,021,886,616 bytes) -- λ> length (show (menorDivisible5 1 (10^5))) -- 43452 -- (0.65 secs, 2,009,595,568 bytes) -- λ> length (show (menorDivisible6 1 (10^5))) -- 43452 -- (0.30 secs, 172,986,840 bytes) -- λ> length (show (menorDivisible7 1 (10^5))) -- 43452 -- (0.30 secs, 172,986,920 bytes) -- -- λ> length (show (menorDivisible5 1 (2*10^5))) -- 86871 -- (2.47 secs, 7,989,147,304 bytes) -- λ> length (show (menorDivisible6 1 (2*10^5))) -- 86871 -- (0.89 secs, 533,876,496 bytes) -- λ> length (show (menorDivisible7 1 (2*10^5))) -- 86871 -- (0.88 secs, 533,875,608 bytes)

Pensamiento

Será el peor de los malos
bribón que olvide
su vocación de diablo.

Antonio Machado

Leer más →

Menor número triangular con más de n divisores

José A. Alonso, 27-noviembre-2019, Inicial

La sucesión de los números triangulares se obtiene sumando los números naturales.

   *     *      *        *         *   
        * *    * *      * *       * *  
              * * *    * * *     * * * 
                      * * * *   * * * *
                               * * * * * 
   1     3      6        10        15

Así, el 7º número triangular es

   1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.

Los primeros 10 números triangulares son

   1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Los divisores de los primeros 7 números triangulares son:

    1: 1
    3: 1,3
    6: 1,2,3,6
   10: 1,2,5,10
   15: 1,3,5,15
   21: 1,3,7,21
   28: 1,2,4,7,14,28

Como se puede observar, 28 es el menor número triangular con más de 5 divisores.

Definir la función

   menorTriangularConAlMenosNDivisores :: Int -> Integer

tal que (menorTriangularConAlMenosNDivisores n) es el menor número triangular que tiene al menos n divisores. Por ejemplo,

   menorTriangularConAlMenosNDivisores 5    ==  28
   menorTriangularConAlMenosNDivisores 50   ==  25200
   menorTriangularConAlMenosNDivisores 500  ==  76576500

Nota: Este ejercicio está basado en el problema 12 del Proyecto Euler

Soluciones

import Data.List (group)
import Data.Numbers.Primes (primeFactors)
 
menorTriangularConAlMenosNDivisores :: Int -> Integer
menorTriangularConAlMenosNDivisores n = 
  head [x | x <- triangulares, nDivisores x >= n]
 
-- Nota: Se usarán las funciones
-- + triangulares definida en [Números triangulares](http://bit.ly/2rtr6a3) y
-- + nDivisores definida en [Número de divisores](http://bit.ly/2DgVh74)
 
-- triangulares es la sucesión de los números triangulares. Por ejemplo,
--    take 10 triangulares  ==  [1,3,6,10,15,21,28,36,45,55]
triangulares :: [Integer]
triangulares = scanl1 (+) [1..]
 
-- (nDivisores x) es el número de divisores de x. Por ejemplo,
--    nDivisores 28  ==  6
nDivisores :: Integer -> Int
nDivisores = product . map ((+1) . length) . group . primeFactors

Pensamiento

«La Matemática es una ciencia experimental y la computación es el experimento.» ~ Rivin

Leer más →

Etiqueta: Euler

Suma de primos menores

Soluciones

Pensamiento

Múltiplos palíndromos

Soluciones

Pensamiento

Mayor producto de n dígitos consecutivos de un número

Soluciones

Pensamiento

Menor divisible por todos

Soluciones

Pensamiento

Subscribe to Blog via Email

Entradas recientes

Etiquetas