Menu Close

Etiqueta: genericReplicate

Suma de segmentos iniciales

José A. Alonso, ,

Los segmentos iniciales de [3,1,2,5] son [3], [3,1], [3,1,2] y [3,1,2,5]. Sus sumas son 3, 4, 6 y 9, respectivamente. La suma de dichas sumas es 24.

Definir la función

   sumaSegmentosIniciales :: [Integer] -> Integer

tal que (sumaSegmentosIniciales xs) es la suma de las sumas de los segmentos iniciales de xs. Por ejemplo,

   sumaSegmentosIniciales [3,1,2,5]     ==  24
   sumaSegmentosIniciales [1..3*10^6]  ==  4500004500001000000

Comprobar con QuickCheck que la suma de las sumas de los segmentos iniciales de la lista formada por n veces el número uno es el n-ésimo número triangular; es decir que

   sumaSegmentosIniciales (genericReplicate n 1)

es igual a

   n * (n + 1) `div` 2

Soluciones

import Data.List (genericLength, genericReplicate)
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
sumaSegmentosIniciales :: [Integer] -> Integer
sumaSegmentosIniciales xs =
  sum [sum (take k xs) | k <- [1.. length xs]]
 
-- 2ª solución
-- ===========
 
sumaSegmentosIniciales2 :: [Integer] -> Integer
sumaSegmentosIniciales2 xs =
  sum (zipWith (*) [n,n-1..1] xs)
  where n = genericLength xs
 
-- 3ª solución
-- ===========
 
sumaSegmentosIniciales3 :: [Integer] -> Integer
sumaSegmentosIniciales3 xs =
  sum (scanl1 (+) xs)
 
-- Comprobación de la equivalencia
-- ===============================
 
-- La propiedad es
prop_sumaSegmentosInicialesEquiv :: [Integer] -> Bool
prop_sumaSegmentosInicialesEquiv xs =
  all (== sumaSegmentosIniciales xs) [f xs | f <- [ sumaSegmentosIniciales2
                                                  , sumaSegmentosIniciales3]]
 
-- La comprobación es
--   λ> quickCheck prop_sumaSegmentosInicialesEquiv
--   +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
--   λ> sumaSegmentosIniciales [1..10^4]
--   166716670000
--   (2.42 secs, 7,377,926,824 bytes)
--   λ> sumaSegmentosIniciales2 [1..10^4]
--   166716670000
--   (0.01 secs, 4,855,176 bytes)
--   
--   λ> sumaSegmentosIniciales2 [1..3*10^6]
--   4500004500001000000
--   (2.68 secs, 1,424,404,168 bytes)
--   λ> sumaSegmentosIniciales3 [1..3*10^6]
--   4500004500001000000
--   (1.54 secs, 943,500,384 bytes)
 
-- Comprobación de la propiedad
-- ============================
 
-- La propiedad es
prop_sumaSegmentosIniciales :: Positive Integer -> Bool
prop_sumaSegmentosIniciales (Positive n) =
  sumaSegmentosIniciales3 (genericReplicate n 1) ==
  n * (n + 1) `div` 2
 
-- La compronación es
--   λ> quickCheck prop_sumaSegmentosIniciales
--   +++ OK, passed 100 tests.

Otras soluciones

  • Se pueden escribir otras soluciones en los comentarios.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>
Leer más →

Suma de segmentos iniciales

José A. Alonso, ,

Los segmentos iniciales de [3,1,2,5] son [3], [3,1], [3,1,2] y [3,1,2,5]. Sus sumas son 3, 4, 6 y 9, respectivamente. La suma de dichas sumas es 24.

Definir la función

   sumaSegmentosIniciales :: [Integer] -> Integer

tal que (sumaSegmentosIniciales xs) es la suma de las sumas de los segmentos iniciales de xs. Por ejemplo,

   sumaSegmentosIniciales [3,1,2,5]     ==  24
   sumaSegmentosIniciales3 [1..3*10^6]  ==  4500004500001000000

Comprobar con QuickCheck que la suma de las sumas de los segmentos iniciales de la lista formada por n veces el número uno es el n-ésimo número triangular; es decir que

   sumaSegmentosIniciales (genericReplicate n 1)

es igual a

   n * (n + 1) `div` 2

Soluciones

import Data.List (genericLength, genericReplicate)
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
sumaSegmentosIniciales :: [Integer] -> Integer
sumaSegmentosIniciales xs =
  sum [sum (take k xs) | k <- [1.. length xs]]
 
-- 2ª solución
-- ===========
 
sumaSegmentosIniciales2 :: [Integer] -> Integer
sumaSegmentosIniciales2 xs =
  sum (zipWith (*) [n,n-1..1] xs)
  where n = genericLength xs
 
-- 3ª solución
-- ===========
 
sumaSegmentosIniciales3 :: [Integer] -> Integer
sumaSegmentosIniciales3 xs =
  sum (scanl1 (+) xs)
 
-- Comprobación de la equivalencia
-- ===============================
 
-- La propiedad es
prop_sumaSegmentosInicialesEquiv :: [Integer] -> Bool
prop_sumaSegmentosInicialesEquiv xs =
  all (== sumaSegmentosIniciales xs) [f xs | f <- [ sumaSegmentosIniciales2
                                                  , sumaSegmentosIniciales3]]
 
-- La comprobación es
--   λ> quickCheck prop_sumaSegmentosInicialesEquiv
--   +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
--   λ> sumaSegmentosIniciales [1..10^4]
--   166716670000
--   (2.42 secs, 7,377,926,824 bytes)
--   λ> sumaSegmentosIniciales2 [1..10^4]
--   166716670000
--   (0.01 secs, 4,855,176 bytes)
--   
--   λ> sumaSegmentosIniciales2 [1..3*10^6]
--   4500004500001000000
--   (2.68 secs, 1,424,404,168 bytes)
--   λ> sumaSegmentosIniciales3 [1..3*10^6]
--   4500004500001000000
--   (1.54 secs, 943,500,384 bytes)
 
-- Comprobación de la propiedad
-- ============================
 
-- La propiedad es
prop_sumaSegmentosIniciales :: Positive Integer -> Bool
prop_sumaSegmentosIniciales (Positive n) =
  sumaSegmentosIniciales3 (genericReplicate n 1) ==
  n * (n + 1) `div` 2
 
-- La compronación es
--   λ> quickCheck prop_sumaSegmentosIniciales
--   +++ OK, passed 100 tests.

Pensamiento

Al andar se hace camino,
y al volver la vista atrás
se ve la senda que nunca
se ha de volver a pisar.

Antonio Machado

Leer más →

Suma de los dígitos de las repeticiones de un número

José A. Alonso, ,

Dados dos números naturales n y x, su suma reducida se obtiene a partir del número obtenido repitiendo n veces el x sumando sus dígitos hasta obtener un número con sólo un dígito. Por ejemplo, si n es 3 y x es 24 las transformaciones son

   242424 ==> 18 ==> 9

Análogamente, si n es 4 y x es 7988 las transformaciones son

   7988798879887988 ==> 128 ==> 11 ==> 2

Definir las funciones

   sumaReducidaDigitosRepeticiones :: Integer -> Integer -> Integer
   grafica                         :: Integer -> IO ()

tales que

  • (sumaReducidaDigitosRepeticiones n x) es la suma reducida de n repeticiones de x. Por ejemplo 
     sumaReducidaDigitosRepeticiones 3 24                    ==  9
     sumaReducidaDigitosRepeticiones 4 7988                  == 2
     sumaReducidaDigitosRepeticiones (12^(10^7)) (12^(10^7)) == 9
  • (grafica n) dibuja la gráfica de los n primeros elementos de la sucesión cuyo elementos k-ésimo es (sumaReducidaDigitosRepeticiones k k). Por ejemplo, (grafica 50) dibuja
    Suma_de_los_digitos_de_las_repeticiones_de_un_numero50

Soluciones

import Data.List (genericReplicate)
import Graphics.Gnuplot.Simple
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
sumaReducidaDigitosRepeticiones :: Integer -> Integer -> Integer
sumaReducidaDigitosRepeticiones n x =
  sumaReducidaDigitos (repeticiones n x) 
 
-- (repeticiones n x) es el número obtenido repitiendo n veces el x. Por
-- ejemplo, 
--    repeticiones 3 24   ==  242424
--    repeticiones 4 325  ==  325325325325
repeticiones :: Integer -> Integer -> Integer
repeticiones n x = read (concat (genericReplicate n (show x)))
 
-- (sumaDigitos x) es la suma de los dígitos de x. Por ejemplo,
--    sumaDigitos 325  ==  10
sumaDigitos :: Integer -> Integer
sumaDigitos x | x < 10    = x
              | otherwise = b + sumaDigitos a
  where (a,b) = divMod x 10
 
-- (sumaReducidaDigitos x) es el número obtenido a partir de x
-- reiterando la suma de los dígitos hasta obtener un número con sólo un
-- dígito. Por ejemplo,
--    sumaReducidaDigitos 24   ==  6
--    sumaReducidaDigitos 325  ==  1
sumaReducidaDigitos :: Integer -> Integer
sumaReducidaDigitos x | x < 10    = x
                      | otherwise = sumaReducidaDigitos (sumaDigitos x)
 
-- 2ª solución
-- ===========
 
sumaReducidaDigitosRepeticiones2 :: Integer -> Integer -> Integer
sumaReducidaDigitosRepeticiones2 n x =
  sumaReducidaDigitos2 (n * sumaReducidaDigitos2 x) 
 
sumaReducidaDigitos2 :: Integer -> Integer
sumaReducidaDigitos2 0 = 0
sumaReducidaDigitos2 x | y == 0    = 9
                       | otherwise = y
  where y = x `mod` 9
 
-- Equivalencia de las definiciones
-- ================================
 
-- La propiedad es
prop_equiv :: Positive Integer -> Positive Integer -> Bool
prop_equiv (Positive n) (Positive x) =
  sumaReducidaDigitosRepeticiones n x == sumaReducidaDigitosRepeticiones2 n x 
 
-- La comprobación es
--    λ> quickCheck prop_equiv
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
--    λ> sumaReducidaDigitosRepeticiones (10^4) (10^4)
--    1
--    (2.00 secs, 574,667,384 bytes)
--    λ> sumaReducidaDigitosRepeticiones2 (10^4) (10^4)
--    1
--    (0.03 secs, 141,120 bytes)
 
-- Gráfica
-- =======
 
grafica :: Integer -> IO ()
grafica n =
  plotList [Key Nothing]
           [sumaReducidaDigitosRepeticiones2 k k | k <- [1..n]]
Leer más →

Menor número divisible por 10^n cuyos dígitos suman n

José A. Alonso, ,

Definir la función

   menor :: Integer -> Integer

tal que (menor n) es el menor número divisible por 10^n cuyos dígitos suman n. Por ejemplo,

   menor 5   ==  500000
   menor 20  ==  29900000000000000000000

Soluciones

import Data.List (genericLength, genericReplicate)
 
menor :: Integer -> Integer
menor n = read (show (n-9*a) ++
                genericReplicate a '9' ++
                genericReplicate n '0')
  where a = n `div` 9
Leer más →

Números que sumados a su siguiente primo dan primos

José A. Alonso, ,

Introducción

La Enciclopedia electrónica de sucesiones de enteros (OEIS por sus siglas en inglés, de On-Line Encyclopedia of Integer Sequences) es una base de datos que registra sucesiones de números enteros. Está disponible libremente en Internet, en la dirección http://oeis.org.

La semana pasada Antonio Roldán añadió una nueva sucesión a la OEIS, la A249624 que sirve de base para el problema de hoy.

Enunciado

-- Definir la sucesión
--     a249624 :: [Integer]
-- tal que sus elementos son los números x tales que la suma de x y el
-- primo que le sigue es un número primo. Por ejemplo, 
--    ghci> take 20 a249624
--    [0,1,2,6,8,14,18,20,24,30,34,36,38,48,50,54,64,68,78,80]
-- 
-- El número 8 está en la sucesión porque su siguiente primo es 11 y
-- 8+11=19 es primo. El 12 no está en la sucesión porque su siguiente
-- primo es 13 y 12+13=25 no es primo.

Soluciones

import Data.Numbers.Primes (primes, isPrime)
import Data.List (genericReplicate)
 
-- 1ª definición
-- =============
 
a249624 :: [Integer]
a249624 = 0: 1: [x | x <- [2,4..], primo (x + siguientePrimo x)]
 
primo :: Integer -> Bool
primo x = [y | y <- [1..x], x `rem` y == 0] == [1,x]
 
siguientePrimo :: Integer -> Integer
siguientePrimo x = head [y | y <- [x+1..], primo y]
 
-- 2ª definición (por recursión)
-- =============================
 
a249624b :: [Integer]
a249624b = 0 : 1 : 2: aux [2,4..] primos where
    aux (x:xs) (y:ys) 
        | y < x                = aux (x:xs) ys
        | (x+y) `pertenece` ys = x : aux xs (y:ys)
        | otherwise            = aux xs (y:ys)
    pertenece x ys = x == head (dropWhile (<x) ys)
 
primos :: [Integer]
primos = 2 : [x | x <- [3,5..], primo x]
 
-- 3ª definición (con la librería de primos)
-- =========================================
 
a249624c :: [Integer]
a249624c = 0: 1: [x | x <- [2,4..], isPrime (x + siguientePrimo3 x)]
 
siguientePrimo3 x = head [y | y <- [x+1..], isPrime y]
 
-- 4ª definición (por recursión con la librería de primos)
-- =======================================================
 
a249624d :: [Integer]
a249624d = 0 : 1 : 2: aux [2,4..] primes where
    aux (x:xs) (y:ys) 
        | y < x                = aux (x:xs) ys
        | (x+y) `pertenece` ys = x : aux xs (y:ys)
        | otherwise            = aux xs (y:ys)
    pertenece x ys = x == head (dropWhile (<x) ys)
 
-- 5ª definición
-- =============
 
a249624e :: [Integer]
a249624e = [a | q <- primes, 
                let p = siguientePrimo3 (q `div` 2),
                let a = q-p,
                siguientePrimo3 a == p]
 
-- 6ª definición
-- =============
 
a249624f :: [Integer]
a249624f = [x | (x,y) <- zip [0..] ps, isPrime (x+y)]
    where ps = 2:2:concat (zipWith f primes (tail primes))
          f p q = genericReplicate (q-p) q
 
-- 7ª definición
-- =============
 
a249624g :: [Integer]
a249624g = 0:1:(aux primes (tail primes) primes)
    where aux (x:xs) (y:ys) zs
              | null rs   = aux xs ys zs2
              | otherwise = [r-y | r <- rs] ++ (aux xs ys zs2)
              where a = x+y
                    b = 2*y-1
                    zs1 = takeWhile (<=b) zs
                    rs = [r | r <- [a..b], r `elem` zs1]
                    zs2 = dropWhile (<=b) zs
 
-- ---------------------------------------------------------------------
-- § Comparación de eficiencia                                        --
-- ---------------------------------------------------------------------
 
-- La comparación es
--    ghci> :set +s
--    
--    ghci> a249624 !! 700
--    5670
--    (12.72 secs, 1245938184 bytes)
--    
--    ghci> a249624b !! 700
--    5670
--    (8.01 secs, 764775268 bytes)
-- 
--    ghci> a249624c !! 700
--    5670
--    (0.22 secs, 108982640 bytes)
--    
--    ghci> a249624d !! 700
--    5670
--    (0.20 secs, 4707384 bytes)
--    
--    ghci> a249624e !! 700
--    5670
--    (0.17 secs, 77283064 bytes)
--    
--    ghci> a249624f !! 700
--    5670
--    (0.08 secs, 31684408 bytes)
--    
--    ghci> a249624g !! 700
--    5670
--    (0.03 secs, 4651576 bytes)
Leer más →