Exercitium

Múltiplos con ceros y unos

José A. Alonso, 3-diciembre-2019, Avanzado

Se observa que todos los primeros números naturales tienen al menos un múltiplo no nulo que está formado solamente por ceros y unos. Por ejemplo, 1×10=10, 2×5=10, 3×37=111, 4×25=100, 5×2=10, 6×185=1110; 7×143=1001; 8X125=1000; 9×12345679=111111111.

Definir la función

   multiplosCon1y0 :: Integer -> [Integer]

tal que (multiplosCon1y0 n) es la lista de los múltiplos de n cuyos dígitos son 1 ó 0. Por ejemplo,

   take 4 (multiplosCon1y0 3)      ==  [111,1011,1101,1110]
   take 3 (multiplosCon1y0 23)     ==  [110101,1011011,1101010]
   head (multiplosCon1y0 1234658)  ==  110101101101000000110

Comprobar con QuickCheck que todo entero positivo tiene algún múltiplo cuyos dígitos son 1 ó 0.

Soluciones

import Test.QuickCheck
 
-- 1ª definición
-- =============
 
multiplosCon1y0 :: Integer -> [Integer]
multiplosCon1y0 n = [x | x <- multiplos n
                       , todos1y0 x]
 
-- (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..]
 
-- (todos1y0 n) se verifica si todos los dígitos de n son el 1 o el
-- 0. Por ejmplo,
--    todos1y0 1101110  ==  True
--    todos1y0 1102110  ==  False
todos1y0 :: Integer -> Bool
todos1y0 n = all (`elem` "01") (show n)
 
-- 2ª definición
-- =============
 
multiplosCon1y0b :: Integer -> [Integer] 
multiplosCon1y0b n = 
    [x | x <- numerosCon1y0
       , x `rem` n == 0] 
 
-- numerosCon1y0 es la lista de los números cuyos dígitos son 1 ó 0. Por
-- ejemplo,  
--    ghci> take 15 numerosCon1y0
--    [1,10,11,100,101,110,111,1000,1001,1010,1011,1100,1101,1110,1111]
numerosCon1y0 :: [Integer]
numerosCon1y0 = 1 : concat [[10*x,10*x+1] | x <- numerosCon1y0]
 
-- Comparación de eficiencia
-- =========================
 
--    λ> head (multiplosCon1y0 9)
--    111111111
--    (7.70 secs, 10,853,320,456 bytes)
--    λ> head (multiplosCon1y0b 9)
--    111111111
--    (0.01 secs, 167,992 bytes)
 
-- Comprobación de la propiedad
-- ============================
 
-- La propiedad es
prop_existe_multiplosCon1y0 :: Integer -> Property
prop_existe_multiplosCon1y0 n = 
    n > 0 ==> (not . null) (multiplosCon1y0b n)
 
-- La comprobación es
--    λ> quickCheck prop_existe_multiplosCon1y0
--    +++ OK, passed 100 tests.

Pensamiento

Huye del triste amor, amor pacato,
sin peligro, sin venda ni aventura,
que espera del amor prenda segura,
porque en amor locura es lo sensato.

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 →

Exercitium

Exercitium

Múltiplos con ceros y unos

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

mayo 2023
L	M	X	J	V	S	D
« Abr
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