Menu Close

Etiqueta: scanl1

Producto infinito

Definir la función

   productoInfinito :: [Int] -> [Int]

tal que (productoInfinito xs) es la lista infinita que en la posición N tiene el producto de los N primeros elementos de la lista infinita xs. Por ejemplo,

   take 5 (productoInfinito [1..])    ==  [1,2,6,24,120]
   take 5 (productoInfinito [2,4..])  ==  [2,8,48,384,3840]
   take 5 (productoInfinito [1,3..])  ==  [1,3,15,105,945]

Nota: Este ejercicio es parte del examen del grupo 3 del 2 de diciembre.

Soluciones

-- 1ª definición (por comprensión):
productoInfinito1 :: [Integer] -> [Integer]
productoInfinito1 xs = [product (take n xs) | n <- [1..]]
 
-- 2ª definición (por recursión)
productoInfinito2 :: [Integer] -> [Integer]
productoInfinito2 (x:y:zs) = x : productoInfinito2 (x*y:zs)
 
-- 2ª definición (por recursión y map)
productoInfinito3 :: [Integer] -> [Integer]
productoInfinito3 []     = [1]
productoInfinito3 (x:xs) = map (x*) (1 : productoInfinito3 xs)
 
-- 4ª definición (con scanl1)
productoInfinito4 :: [Integer] -> [Integer]
productoInfinito4 = scanl1 (*)
 
-- Comparación de eficiencia
--    λ> take 20 (show (productoInfinito1 [2,4..] !! 10000))
--    "11358071114466915693"
--    (0.35 secs, 98,287,328 bytes)
--    λ> take 20 (show (productoInfinito2 [2,4..] !! 10000))
--    "11358071114466915693"
--    (0.35 secs, 98,840,440 bytes)
--    λ> take 20 (show (productoInfinito3 [2,4..] !! 10000))
--    "11358071114466915693"
--    (7.36 secs, 6,006,360,472 bytes)
--    λ> take 20 (show (productoInfinito4 [2,4..] !! 10000))
--    "11358071114466915693"
--    (0.34 secs, 96,367,000 bytes)

Sumas alternas de factoriales

Las primeras sumas alternas de los factoriales son números primos; en efecto,

   3! - 2! + 1! = 5
   4! - 3! + 2! - 1! = 19
   5! - 4! + 3! - 2! + 1! = 101
   6! - 5! + 4! - 3! + 2! - 1! = 619
   7! - 6! + 5! - 4! + 3! - 2! + 1! = 4421
   8! - 7! + 6! - 5! + 4! - 3! + 2! - 1! = 35899

son primos, pero

   9! - 8! + 7! - 6! + 5! - 4! + 3! - 2! + 1! = 326981

no es primo.

Definir las funciones

   sumaAlterna         :: Integer -> Integer
   sumasAlternas       :: [Integer]
   conSumaAlternaPrima :: [Integer]

tales que

  • (sumaAlterna n) es la suma alterna de los factoriales desde n hasta 1. Por ejemplo,
     sumaAlterna 3  ==  5
     sumaAlterna 4  ==  19
     sumaAlterna 5  ==  101
     sumaAlterna 6  ==  619
     sumaAlterna 7  ==  4421
     sumaAlterna 8  ==  35899
     sumaAlterna 9  ==  326981
  • sumasAlternas es la sucesión de las sumas alternas de factoriales. Por ejemplo,
     λ> take 10 sumasAlternas1
     [0,1,1,5,19,101,619,4421,35899,326981]
  • conSumaAlternaPrima es la sucesión de los números cuya suma alterna de factoriales es prima. Por ejemplo,
     λ> take 8 conSumaAlternaPrima1
     [3,4,5,6,7,8,10,15]

Soluciones

import Data.List (cycle, genericTake)
import Data.Numbers.Primes (isPrime)
 
-- ---------------------------------------------------------------------
-- § Definiciones de sumaAlterna                                      --
-- ---------------------------------------------------------------------
 
-- 1ª definición
-- =============
 
sumaAlterna1 :: Integer -> Integer
sumaAlterna1 1 = 1
sumaAlterna1 n = factorial n - sumaAlterna1 (n-1)
 
factorial :: Integer -> Integer
factorial n = product [1..n]
 
-- 2ª definición
-- =============
 
sumaAlterna2 :: Integer -> Integer
sumaAlterna2 n = sum (zipWith (*) signos (tail factoriales))
    where
      signos | odd n     = 1 : concat (replicate (m `div` 2) [-1,1])
             | otherwise = concat (replicate (m `div` 2) [-1,1])
      m = fromIntegral n
 
-- factoriales es la lista de los factoriales. Por ejemplo,
--    take 7 factoriales  ==  [1,1,2,6,24,120,720]
factoriales :: [Integer]
factoriales = 1 : scanl1 (*) [1..]
 
-- 3ª definición
-- =============
 
sumaAlterna3 :: Integer -> Integer
sumaAlterna3 n = 
    sum (genericTake n (zipWith (*) signos (tail factoriales)))
    where signos | odd n     = cycle [1,-1]
                 | otherwise = cycle [-1,1]
 
-- Comparación de eficiencia
-- =========================
 
--    λ> sumaAlterna1 3000 `mod` (10^6)
--    577019
--    (5.33 secs, 7,025,937,760 bytes)
--    λ> sumaAlterna2 3000 `mod` (10^6)
--    577019
--    (0.03 secs, 15,738,480 bytes)
--    λ> sumaAlterna3 3000 `mod` (10^6)
--    577019
--    (0.05 secs, 16,520,896 bytes)
 
-- En lo que sigue se usa la 2ª definición
sumaAlterna :: Integer -> Integer
sumaAlterna = sumaAlterna2
 
-- ---------------------------------------------------------------------
-- § sumasAlternas                                                    --
-- ---------------------------------------------------------------------
 
-- 1ª definición
-- =============
 
sumasAlternas1 :: [Integer]
sumasAlternas1 = [sumaAlterna n | n <- [0..]]
 
-- 2ª definición
sumasAlternas2 :: [Integer]
sumasAlternas2 = 0 : zipWith (-) (tail factoriales) sumasAlternas2
 
-- ---------------------------------------------------------------------
-- § Definiciones de conSumaAlternaPrima                              --
-- ---------------------------------------------------------------------
 
-- 1ª definición
-- =============
 
conSumaAlternaPrima1 :: [Integer]
conSumaAlternaPrima1 =
    [n | n <- [0..], isPrime (sumaAlterna n)]
 
-- 2ª definición
-- =============
 
conSumaAlternaPrima2 :: [Integer]
conSumaAlternaPrima2 =
    [x | (x,y) <- zip [0..] sumasAlternas2, isPrime y]

Números como sumas de primos consecutivos

En el artículo Integers as a sum of consecutive primes in 2,3,4,.. ways se presentan números que se pueden escribir como sumas de primos consecutivos de varias formas. Por ejemplo, el 41 se puede escribir de dos formas distintas

   41 =  2 +  3 +  5 + 7 + 11 + 13
   41 = 11 + 13 + 17

el 240 se puede escribir de tres formas

   240 =  17 +  19 + 23 + 29 + 31 + 37 + 41 + 43
   240 =  53 +  59 + 61 + 67
   240 = 113 + 127

y el 311 se puede escribir de 4 formas

   311 =  11 +  13 +  17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47
   311 =  31 +  37 +  41 + 43 + 47 + 53 + 59
   311 =  53 +  59 +  61 + 67 + 71
   311 = 101 + 103 + 107

Definir la función

   sumas :: Integer -> [[Integer]]

tal que (sumas x) es la lista de las formas de escribir x como suma de dos o más números primos consecutivos. Por ejemplo,

   ghci> sumas 41
   [[2,3,5,7,11,13],[11,13,17]]
   ghci> sumas 240
   [[17,19,23,29,31,37,41,43],[53,59,61,67],[113,127]]
   ghci> sumas 311
   [[11,13,17,19,23,29,31,37,41,43,47],[31,37,41,43,47,53,59],
    [53,59,61,67,71],[101,103,107]]
   ghci> maximum [length (sumas n) | n <- [1..600]]
   4

Soluciones

import Data.Numbers.Primes (primes)
import Data.List (span)
 
sumas :: Integer -> [[Integer]]
sumas x = [ys | n <- takeWhile (< x) primes, 
                let ys = sumaDesde x n,
                not (null ys)]
 
-- (sumaDesde x n) es la lista de al menos dos números primos
-- consecutivos a partir del número primo n cuya suma es x, si existen y
-- la lista vacía en caso contrario. Por ejemplo,
--    sumaDesde 15 3  ==  [3,5,7]
--    sumaDesde  7 3  ==  []
sumaDesde :: Integer -> Integer -> [Integer]
sumaDesde x n | x == y    = take (1 + length us) ys
              | otherwise = []
    where ys       = dropWhile (<n) primes
          (us,y:_) = span (<x) (scanl1 (+) ys)

Numeración con múltiples bases

Sea (b_i)_{i \geq 1} una sucesión infinita de números enteros mayores que 1. Entonces todo entero x mayor que cero se puede escribir de forma única como x = x_0 +x_1b_1 + x_2b_1b_2 + \dots + x_nb_1b_2 \dots b_n donde cada x_i satisface la condición 0 \leq x_i < b_{i+1}[/latex]. Se dice que [latex][x_n,x_{n-1},\dots,x_2,x_1,x_0][/latex] es la representación de x en la base [latex](b_i)[/latex]. Por ejemplo, la representación de 377 en la base [latex](2i)_{i >= 1} es [7,5,0,1] ya que 377 = 1 + 0 \times 2 + 5 \times 2 \times 4 + 7 \times 2 \times 4 \times 6 y, además, 0 ≤ 1 < 2, 0 ≤ 0 < 4, 0 ≤ 5 < 6 y 0 ≤ 7 < 8.

Definir las funciones

   decimalAmultiple :: [Integer] -> Integer -> [Integer]
   multipleAdecimal :: [Integer] -> [Integer] -> Integer

tales que (decimalAmultiple bs x) es la representación del número x en la base bs y (multipleAdecimal bs cs) es el número decimal cuya representación en la base bs es cs. Por ejemplo,

   decimalAmultiple [2,4..] 377                      ==  [7,5,0,1]
   multipleAdecimal [2,4..] [7,5,0,1]                ==  377
   decimalAmultiple [2,5..] 377                      ==  [4,5,3,1]
   multipleAdecimal [2,5..] [4,5,3,1]                ==  377
   decimalAmultiple [2^n | n <- [1..]] 2015          ==  [1,15,3,3,1]
   multipleAdecimal [2^n | n <- [1..]] [1,15,3,3,1]  ==  2015
   decimalAmultiple (repeat 10) 2015                 ==  [2,0,1,5]
   multipleAdecimal (repeat 10) [2,0,1,5]            ==  2015

Comprobar con QuickCheck que se verifican las siguientes propiedades

   prop_inversas :: [Integer] -> Integer -> Property
   prop_inversas bs x =
       x > 0 ==> multipleAdecimal bs (decimalAmultiple bs x) == x
 
   prop_coeficientes :: [Integer] -> Integer -> Property
   prop_coeficientes bs x =
       x > 0 ==> and [0 <= c && c < b | (c,b) <- zip cs bs]
       where cs = reverse (decimalAmultiple bs x)

para distintas bases dadas. Por ejemplo,

   ghci> quickCheck (prop_inversas [2,4..])
   +++ OK, passed 100 tests.
   ghci> quickCheck (prop_inversas [3,5..])
   +++ OK, passed 100 tests.
   ghci> quickCheck (prop_coeficientes [2,4..])
   +++ OK, passed 100 tests.
   ghci> quickCheck (prop_coeficientes [3,5..])
   +++ OK, passed 100 tests.

Soluciones

import Test.QuickCheck
import Data.List (unfoldr)
 
-- decimalAmultiple
-- ================
 
-- 1ª definición (por recursión)
decimalAmultiple :: [Integer] -> Integer -> [Integer]
decimalAmultiple bs n = reverse (aux bs n)
    where aux _ 0 = []
          aux (b:bs) n = r : aux bs q
              where (q,r) = quotRem n b
 
-- 2ª definición (con acumulador)
decimalAmultiple2 :: [Integer] -> Integer -> [Integer]
decimalAmultiple2 bs n = aux bs n []
    where aux _ 0  xs = xs
          aux (b:bs) n xs = aux bs q (r:xs)
              where (q,r) = quotRem n b
 
-- 3ª definición (con unfoldr):
decimalAmultiple3 :: [Integer] -> Integer -> [Integer]
decimalAmultiple3 xs n = reverse (unfoldr f (xs,n))
  where f (_     ,0) = Nothing 
        f ((x:xs),m) = Just (r,(xs,q))
                       where (q,r) = quotRem m x 
 
-- multipleAdecimal
-- ================
 
-- 1ª definición (por recursión)
multipleAdecimal :: [Integer] -> [Integer] -> Integer
multipleAdecimal xs ns = aux xs (reverse ns)
    where aux (x:xs) (n:ns) = n + x * (aux xs ns)
          aux _ _           = 0
 
-- 2ª definición (con scanl1)
multipleAdecimal2 :: [Integer] -> [Integer] -> Integer
multipleAdecimal2 bs xs =
    sum (zipWith (*) (reverse xs) (1 : scanl1 (*) bs))
 
prop_inversas :: [Integer] -> Integer -> Property
prop_inversas bs x =
    x > 0 ==> multipleAdecimal bs (decimalAmultiple bs x) == x
 
prop_coeficientes :: [Integer] -> Integer -> Property
prop_coeficientes bs x =
    x > 0 ==> and [0 <= c && c < b | (c,b) <- zip cs bs]
    where cs = reverse (decimalAmultiple bs x)

Mayor diferencia progresiva

La diferencia progresiva entre dos elementos de una lista es la resta entre el que ocupa la mayor posición y la menor. Por ejemplo, en la lista [1,5,8,2,9] la diferencia entre los elementos 5 y 8 es 3 y entre 5 y 2 es -3.

Definir la función

   mayorDiferencia :: [Int] -> Int

tal que (mayorDiferencia xs) es la mayor diferencia progresiva entre los elementos de xs. Por ejemplo,

   mayorDiferencia [1,5,8,2,9]  ==  8
   mayorDiferencia [9,5,8,2,1]  ==  3
   mayorDiferencia [7,2,6]      ==  4
   mayorDiferencia [3,2,1]      ==  0
   mayorDiferencia [1..10^7]    ==  9999999

Soluciones

import Data.List (inits)
 
-- 1ª definición (por recursión):
mayorDiferencia :: [Int] -> Int
mayorDiferencia ([_])  = 0
mayorDiferencia (x:xs) = 
    max (maximum [y-x | y <- xs]) (mayorDiferencia xs) 
 
-- 2ª definición (por comprensión)
mayorDiferencia2 :: [Int] -> Int
mayorDiferencia2 xs = 
    maximum [x-y | (x,y) <- zip xs (map minimum (tail (inits xs)))]
 
-- 3ª definición:
mayorDiferencia3 :: [Int] -> Int
mayorDiferencia3 xs = maximum (zipWith (-) xs (scanl1 min xs))
 
-- 4ª definición:
mayorDiferencia4 :: [Int] -> Int
mayorDiferencia4 xs = maximum . zipWith (-) xs $ scanl1 min xs
 
-- Comparación de eficiencia
--    ghci> mayorDiferencia [1..3000]
--    2999
--    (3.43 secs, 943439560 bytes)
--    
--    ghci> mayorDiferencia2 [1..3000]
--    2999
--    (3.38 secs, 978359192 bytes)
--    
--    ghci> mayorDiferencia3 [1..3000]
--    2999
--    (0.01 secs, 2877960 bytes)
--    
--    ghci> mayorDiferencia4 [1..3000]
--    2999
--    (0.01 secs, 2062616 bytes)