Menu Close

Etiqueta: genericIndex

La sucesión de Sylvester

La sucesión de Sylvester es la sucesión que comienza en 2 y sus restantes términos se obtienen multiplicando los anteriores y sumándole 1.

Definir las funciones

   sylvester        :: Integer -> Integer
   graficaSylvester :: Integer -> Integer -> IO ()

tales que

  • (sylvester n) es el n-ésimo término de la sucesión de Sylvester. Por ejemplo,
     λ> [sylvester n | n <- [0..7]]
     [2,3,7,43,1807,3263443,10650056950807,113423713055421844361000443]
     λ> length (show (sylvester 25))
     6830085
  • (graficaSylvester d n) dibuja la gráfica de los d últimos dígitos de los n primeros términos de la sucesión de Sylvester. Por ejemplo,
    • (graficaSylvester 3 30) dibuja
      La_sucesion_de_Sylvester_(3,30)
    • (graficaSylvester 4 30) dibuja
      La_sucesion_de_Sylvester_(4,30)
    • (graficaSylvester 5 30) dibuja
      La_sucesion_de_Sylvester_(5,30)

Nota: Se puede usar programación dinámica para aumentar la eficiencia.

Soluciones

import Data.List               (genericIndex)
import Data.Array              ((!), array)
import Graphics.Gnuplot.Simple (plotList, Attribute (Key, PNG))
 
-- 1ª solución (por recursión)
-- ===========================
 
sylvester1 :: Integer -> Integer
sylvester1 0 = 2
sylvester1 n = 1 + product [sylvester1 k | k <- [0..n-1]]
 
-- 2ª solución (con programación dinámica)
-- =======================================
 
sylvester2 :: Integer -> Integer
sylvester2 n = v ! n where
  v = array (0,n) [(i,f i) | i <- [0..n]]
  f 0 = 2
  f m = 1 + product [v!k | k <- [0..m-1]]
 
-- 3ª solución
-- ===========
 
-- Observando que
--    S(n) = 1 + S(0)*S(1)*...*S(n-2)*S(n-1)
--         = 1 + (1 + S(0)*S(1)*...*S(n-2))*S(n-1) - S(n-1)
--         = 1 + S(n-1)*S(n-1) - S(n-1)
--         = 1 + S(n-1)^2 - S(n-1)
-- se obtiene la siguiente definición.
sylvester3 :: Integer -> Integer
sylvester3 0 = 2
sylvester3 n = 1 + x^2 - x
  where x = sylvester3 (n-1)
 
-- 4ª solución
-- ===========
 
sylvester4 :: Integer -> Integer
sylvester4 n = v ! n where
  v = array (0,n) [(i,f i) | i <- [0..n]]
  f 0 = 2
  f m = 1 + x^2 - x
    where x = v ! (m-1)
 
-- 5ª solución
-- ===========
 
sylvester5 :: Integer -> Integer
sylvester5 n = sucSylvester5 `genericIndex` n
 
sucSylvester5 :: [Integer]
sucSylvester5 = iterate (\x -> (x-1)*x+1) 2 
 
-- La comparación es
--    λ> length (show (sylvester1 23))
--    1707522
--    (6.03 secs, 4,090,415,704 bytes)
--    λ> length (show (sylvester2 23))
--    1707522
--    (0.33 secs, 109,477,296 bytes)
--    λ> length (show (sylvester3 23))
--    1707522
--    (0.35 secs, 109,395,136 bytes)
--    λ> length (show (sylvester4 23))
--    1707522
--    (0.33 secs, 109,402,440 bytes)
--    λ> length (show (sylvester5 23))
--    1707522
--    (0.30 secs, 108,676,256 bytes)
 
graficaSylvester :: Integer -> Integer -> IO ()
graficaSylvester d n =
  plotList [ Key Nothing
           , PNG ("La_sucesion_de_Sylvester_" ++ show (d,n) ++ ".png")
           ]
           [sylvester5 k `mod` (10^d) | k <- [0..n]]

Triángulo de Bell

El triágulo de Bell es el triángulo numérico, cuya primera fila es [1] y en cada fila, el primer elemento es el último de la fila anterior y el elemento en la posición j se obtiene sumando el elemento anterior de su misma fila y de la fila anterior. Sus primeras filas son

   1 
   1   2
   2   3   5
   5   7  10  15
   15 20  27  37  52
   52 67  87 114 151 203

Definir la función

   trianguloDeBell :: [[Integer]]

tal que trianguloDeBell es la lista con las filas de dicho triángulo. Por ejemplo

   λ> take 5 trianguloDeBell
   [[1],[1,2],[2,3,5],[5,7,10,15],[15,20,27,37,52]]

Comprobar con QuickCheck que los números que aparecen en la primera columna del triángulo coinciden con los números de Bell; es decir, el primer elemento de la n-ésima fila es el n-ésimo número de Bell.

Soluciones

import Data.List (genericIndex, genericLength)
import Test.QuickCheck
 
trianguloDeBell :: [[Integer]]
trianguloDeBell = iterate siguiente [1]
 
-- (siguiente xs) es la fila siguiente de xs en el triángulo de
-- Bell. Por ejemplo,
--    siguiente [1]     ==  [1,2]
--    siguiente [1,2]   ==  [2,3,5]
--    siguiente [2,3,5] ==  [5,7,10,15]
siguiente :: [Integer] -> [Integer]
siguiente xs = last xs : zipWith (+) xs (siguiente xs)
 
-- Propiedad
-- =========
 
-- La propiedad es
prop_TrianguloDeBell :: Integer -> Property
prop_TrianguloDeBell n =
  n > 0 ==> head (trianguloDeBell `genericIndex` n) == bell n
 
-- (bell n) es el n-ésimo número de Bell definido en el ejercicio
-- anterior.  
bell :: Integer -> Integer
bell n = genericLength (particiones [1..n])
 
particiones :: [a] -> [[[a]]]
particiones [] = [[]]
particiones (x:xs) =
  concat [([x] : yss) : inserta x yss | yss <- ysss]
  where ysss = particiones xs
 
inserta :: a -> [[a]] -> [[[a]]]
inserta _ []       = []
inserta x (ys:yss) = ((x:ys):yss) : [ys : zs | zs <- inserta x yss] 
 
-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=10}) prop_TrianguloDeBell
--    +++ 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>

Pensamiento

“La ciencia es lo que entendemos lo suficientemente bien como para explicarle a una computadora. El arte es todo lo demás.”

Donald Knuth.

Triángulo de Euler

El triángulo de Euler se construye a partir de las siguientes relaciones

   A(n,1) = A(n,n) = 1
   A(n,m) = (n-m)A(n-1,m-1) + (m+1)A(n-1,m).

Sus primeros términos son

   1 
   1 1                                                       
   1 4   1                                            
   1 11  11    1                                    
   1 26  66    26    1                             
   1 57  302   302   57     1                    
   1 120 1191  2416  1191   120   1            
   1 247 4293  15619 15619  4293  247   1   
   1 502 14608 88234 156190 88234 14608 502 1

Definir las siguientes funciones:

  numeroEuler        :: Integer -> Integer -> Integer
  filaTrianguloEuler :: Integer -> [Integer]
  trianguloEuler     :: [[Integer]]

tales que

  • (numeroEuler n k) es el número de Euler A(n,k). Por ejemplo,
     numeroEuler 8 3  == 15619
     numeroEuler 20 6 == 21598596303099900
     length (show (numeroEuler 1000 500)) == 2567
  • (filaTrianguloEuler n) es la n-ésima fila del triángulo de Euler. Por ejemplo,
     filaTrianguloEuler 7  ==  [1,120,1191,2416,1191,120,1]
     filaTrianguloEuler 8  ==  [1,247,4293,15619,15619,4293,247,1]
     length (show (maximum (filaTrianguloEuler 1000)))  ==  2567
  • trianguloEuler es la lista con las filas del triángulo de Euler
     λ> take 6 trianguloEuler
     [[1],[1,1],[1,4,1],[1,11,11,1],[1,26,66,26,1],[1,57,302,302,57,1]]
     λ> length (show (maximum (trianguloEuler !! 999)))
     2567

Soluciones

import Data.List  (genericLength, genericIndex)
import Data.Array (Array, (!), array)
 
-- 1ª solución
-- ===========
 
trianguloEuler :: [[Integer]]
trianguloEuler = iterate siguiente [1]
 
-- (siguiente xs) es la fila siguiente a la xs en el triángulo de
-- Euler. Por ejemplo,
--    λ> siguiente [1]
--    [1,1]
--    λ> siguiente it
--    [1,4,1]
--    λ> siguiente it
--    [1,11,11,1]
siguiente :: [Integer] -> [Integer]
siguiente xs = zipWith (+) us vs
  where n = genericLength xs
        us = zipWith (*) (0:xs) [n+1,n..1]
        vs = zipWith (*) (xs++[0]) [1..n+1]
 
filaTrianguloEuler :: Integer -> [Integer]
filaTrianguloEuler n = trianguloEuler `genericIndex` (n-1)
 
numeroEuler :: Integer -> Integer -> Integer
numeroEuler n k = filaTrianguloEuler n `genericIndex` k
 
-- 2ª solución
-- ===========
 
numeroEuler2 :: Integer -> Integer -> Integer
numeroEuler2 n 0 = 1
numeroEuler2 n m 
  | n == m    = 0
  | otherwise = (n-m) * numeroEuler2 (n-1) (m-1) + (m+1) * numeroEuler2 (n-1) m
 
filaTrianguloEuler2 :: Integer -> [Integer]
filaTrianguloEuler2 n = map (numeroEuler2 n) [0..n-1]
 
trianguloEuler2 :: [[Integer]]
trianguloEuler2 = map filaTrianguloEuler2 [1..]
 
-- 3ª solución
-- ===========
 
numeroEuler3 :: Integer -> Integer -> Integer
numeroEuler3 n k = (matrizEuler n k) ! (n,k)
 
-- (matrizEuler n m) es la matriz de n+1 filas y m+1 columnsa formada
-- por los números de Euler. Por ejemplo,
--   λ> [[matrizEuler 6 6 ! (i,j) | j <- [0..i-1]] | i <- [1..6]]
--   [[1],[1,1],[1,4,1],[1,11,11,1],[1,26,66,26,1],[1,57,302,302,57,1]]
matrizEuler :: Integer -> Integer -> Array (Integer,Integer) Integer
matrizEuler n m = q
  where q = array ((0,0),(n,m)) [((i,j), f i j) | i <- [0..n], j <- [0..m]]
        f i 0 = 1
        f i j
          | i == j    = 0
          | otherwise = (i-j) * q!(i-1,j-1) + (j+1)* q!(i-1,j)
 
filaTrianguloEuler3 :: Integer -> [Integer]
filaTrianguloEuler3 n = map (numeroEuler3 n) [0..n-1]
 
trianguloEuler3 :: [[Integer]]
trianguloEuler3 = map filaTrianguloEuler3 [1..]
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--   λ> numeroEuler 22 11
--   301958232385734088196
--   (0.01 secs, 118,760 bytes)
--   λ> numeroEuler2 22 11
--   301958232385734088196
--   (3.96 secs, 524,955,384 bytes)
--   λ> numeroEuler3 22 11
--   301958232385734088196
--   (0.01 secs, 356,296 bytes)
--   
--   λ> length (show (numeroEuler 800 400))
--   1976
--   (0.01 secs, 383,080 bytes)
--   λ> length (show (numeroEuler3 800 400))
--   1976
--   (2.13 secs, 508,780,696 bytes)

Pensamiento

Señor San Jerónimo,
suelte usted la piedra
con que se machaca.
Me pegó con ella.

Antonio Machado

Números construidos con los dígitos de un conjunto dado

Definir las siguientes funciones

   numerosCon      :: [Integer] -> [Integer]
   numeroDeDigitos :: [Integer] -> Integer -> Int

tales que

  • (numerosCon ds) es la lista de los números que se pueden construir con los dígitos de ds (cuyos elementos son distintos elementos del 1 al 9) . Por ejemplo,
     λ> take 22 (numerosCon [1,4,6,9])
     [1,4,6,9,11,14,16,19,41,44,46,49,61,64,66,69,91,94,96,99,111,114]
     λ> take 15 (numerosCon [4,6,9])
     [4,6,9,44,46,49,64,66,69,94,96,99,444,446,449]
     λ> take 15 (numerosCon [6,9])
     [6,9,66,69,96,99,666,669,696,699,966,969,996,999,6666]
  • (numeroDeDigitos ds k) es el número de dígitos que tiene el k-ésimo elemento (empezando a contar en 0) de la sucesión (numerosCon ds). Por ejemplo,
     numeroDeDigitos [1,4,6,9]   3  ==  1
     numeroDeDigitos [1,4,6,9]   6  ==  2
     numeroDeDigitos [1,4,6,9]  22  ==  3
     numeroDeDigitos [4,6,9]    15  ==  3
     numeroDeDigitos [6,9]      15  ==  4
     numeroDeDigitos [1,4,6,9] (10^(10^5))  ==  166097
     numeroDeDigitos   [4,6,9] (10^(10^5))  ==  209590
     numeroDeDigitos     [6,9] (10^(10^5))  ==  332192

Soluciones

import Data.List (genericIndex, genericLength)
 
-- Definición de numerosCon
-- ========================
 
numerosCon :: [Integer] -> [Integer]
numerosCon xs = [n | n <- [0..]
                   , n `tieneSusDigitosEn` xs]
 
-- (tieneSusDigitosEn xs n) se verifica si los dígitos de n están contenidos en
-- xs. Por ejemplo,
--    4149 `tieneSusDigitosEn` [1,4,6,9]  ==  True
--    4143 `tieneSusDigitosEn` [1,4,6,9]  ==  False
tieneSusDigitosEn :: Integer -> [Integer] -> Bool
tieneSusDigitosEn n xs =
  digitos n `esSubconjunto` xs
 
-- (digitos n) es la lista de los dígitos de n. Por ejemplo,
--    digitos 325  ==  [3,2,5]
digitos :: Integer -> [Integer]
digitos n = [read [c] | c <- show n]
 
-- (esSubconjunto xs ys) se verifica si xs es subconjunto de ys. Por
-- ejemplo, 
--    esSubconjunto [3,2,5] [4,2,5,7,3]  ==  True
--    esSubconjunto [3,2,5] [4,2,5,7]  ==  False
esSubconjunto :: Eq a => [a] -> [a] -> Bool
esSubconjunto xs ys = all (`elem` ys) xs
 
-- 1ª definición de numeroDeDigitos
-- ================================
 
numeroDeDigitos :: [Integer] -> Integer -> Int
numeroDeDigitos xs n =
  length (show (numerosCon xs `genericIndex` n))
 
-- 2ª definición de numeroDeDigitos
-- ================================
 
-- Observando que si el conjunto de dígitos tiene n elementos, entonces
-- hay n^k números con k dígitos.
 
numeroDeDigitos2 :: [Integer] -> Integer -> Int
numeroDeDigitos2 xs n =
  1 + length (takeWhile (<= n) (sumasDePotencias (genericLength xs)))
 
-- (potencia n) son las potencias de n. Por ejemplo,
--    take 5 (potencias 3)  ==  [3,9,27,81,243]
potencias :: Integer -> [Integer]
potencias k = iterate (*k) k 
 
-- (sumasDePotencias n) es la lista de las sumas acumuladas de las
-- potencias de n. Por ejemplo,
--    take 5 (sumasDePotencias 3)  ==  [3,12,39,120,363]
sumasDePotencias :: Integer -> [Integer]
sumasDePotencias k = scanl1 (+) (potencias k)
 
-- Comparación de eficiencia
-- =========================
 
--    λ> numeroDeDigitos [1,4,6,9] 2000
--    6
--    (3.98 secs, 1,424,390,064 bytes)
--    λ> numeroDeDigitos2 [1,4,6,9] 2000
--    6
--    (0.01 secs, 127,464 bytes)

Número de triangulaciones de un polígono

Una triangulación de un polígono es una división del área en un conjunto de triángulos, de forma que la unión de todos ellos es igual al polígono original, y cualquier par de triángulos es disjunto o comparte únicamente un vértice o un lado. En el caso de polígonos convexos, la cantidad de triangulaciones posibles depende únicamente del número de vértices del polígono.

Si llamamos T(n) al número de triangulaciones de un polígono de n vértices, se verifica la siguiente relación de recurrencia:

    T(2) = 1
    T(n) = T(2)*T(n-1) + T(3)*T(n-2) + ... + T(n-1)*T(2)

Definir la función

   numeroTriangulaciones :: Integer -> Integer

tal que (numeroTriangulaciones n) es el número de triangulaciones de un polígono convexo de n vértices. Por ejemplo,

   numeroTriangulaciones 3  == 1
   numeroTriangulaciones 5  == 5
   numeroTriangulaciones 6  == 14
   numeroTriangulaciones 7  == 42
   numeroTriangulaciones 50 == 131327898242169365477991900
   length (show (numeroTriangulaciones   800)) ==  476
   length (show (numeroTriangulaciones  1000)) ==  597
   length (show (numeroTriangulaciones 10000)) == 6014

Soluciones

import Data.Array (Array, (!), array)
import Data.List  (genericIndex)
import qualified Data.Vector as V
 
-- 1ª solución (por recursión)
-- ===========================
 
numeroTriangulaciones :: Integer -> Integer
numeroTriangulaciones 2 = 1
numeroTriangulaciones n = sum (zipWith (*) ts (reverse ts))
  where ts = [numeroTriangulaciones k | k <- [2..n-1]]
 
-- 2ª solución
-- ===========
 
--    λ> map numeroTriangulaciones2 [2..15]
--    [1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900]
numeroTriangulaciones2 :: Integer -> Integer
numeroTriangulaciones2 n = 
  head (sucNumeroTriangulacionesInversas `genericIndex` (n-2))
 
--    λ> mapM_ print (take 10 sucNumeroTriangulacionesInversas)
--    [1]
--    [1,1]
--    [2,1,1]
--    [5,2,1,1]
--    [14,5,2,1,1]
--    [42,14,5,2,1,1]
--    [132,42,14,5,2,1,1]
--    [429,132,42,14,5,2,1,1]
--    [1430,429,132,42,14,5,2,1,1]
--    [4862,1430,429,132,42,14,5,2,1,1]
sucNumeroTriangulacionesInversas :: [[Integer]]        
sucNumeroTriangulacionesInversas = iterate f [1]
  where f ts = sum (zipWith (*) ts (reverse ts)) : ts
 
-- 3ª solución (con programación dinámica)
-- =======================================
 
numeroTriangulaciones3 :: Integer -> Integer
numeroTriangulaciones3 n = vectorTriang n ! n
 
--    λ> vectorTriang 9
--    array (2,9) [(2,1),(3,1),(4,2),(5,5),(6,14),(7,42),(8,132),(9,429)]
vectorTriang :: Integer -> Array Integer Integer
vectorTriang n = v
  where v = array (2,n) [(i, f i) | i <-[2..n]]
        f 2 = 1
        f i = sum [v!j*v!(i-j+1) | j <-[2..i-1]]
 
-- 4ª solución (con los números de Catalan)
-- ========================================
 
-- Al calcular por primeros números de triangulaciones se obtiene
--    λ> map numeroTriangulaciones [2..12]
--    [1,1,2,5,14,42,132,429,1430,4862,16796]
-- Se observa que se corresponden con los números de Catalan
-- http://bit.ly/2FOc1S1
-- 
-- El n-ésimo número de Catalan es
--    (2n)! / (n! * (n+1)!)
-- El número de triangulaciones de un polígono de n lados es el
-- (n-2)-ésimo número de Catalan.
 
numeroTriangulaciones4 :: Integer -> Integer
numeroTriangulaciones4 n = numeroCatalan (n-2) 
 
numeroCatalan :: Integer -> Integer
numeroCatalan n =
  factorial (2*n) `div` (factorial (n+1) * factorial n)
 
factorial :: Integer -> Integer
factorial n = product [1..n]
 
-- 5ª solución
-- ===========
 
numeroTriangulaciones5 :: Integer -> Integer
numeroTriangulaciones5 n = v V.! (m-2)
   where v = V.constructN m
           (\w -> if   V.null w then 1
                  else V.sum (V.zipWith (*) w (V.reverse w)))
         m = fromIntegral n
 
 
-- 6ª solución
-- ===========
 
numeroTriangulaciones6 :: Integer -> Integer
numeroTriangulaciones6 n = nCr (2*n-4, n-2) `div` (n-1)
  where nCr (n,m)   = factorial n `div` (factorial (n-m) * factorial m)
        factorial n = product [1..n]
 
-- Comparación de eficiencia
-- =========================
 
--    λ> numeroTriangulaciones 22
--    6564120420
--    (3.97 secs, 668,070,936 bytes)
--    λ> numeroTriangulaciones2 22
--    6564120420
--    (0.01 secs, 180,064 bytes)
--    λ> numeroTriangulaciones3 22
--    6564120420
--    (0.01 secs, 285,792 bytes)
--    
--    λ> length (show (numeroTriangulaciones2 800))
--    476
--    (0.59 secs, 125,026,824 bytes)
--    λ> length (show (numeroTriangulaciones3 800))
--    476
--    (1.95 secs, 334,652,936 bytes)
--    λ> length (show (numeroTriangulaciones4 800))
--    476
--    (0.01 secs, 2,960,088 bytes)
--    λ> length (show (numeroTriangulaciones5 800))
--    476
--    (0.65 secs, 200,415,640 bytes)
--    λ> length (show (numeroTriangulaciones6 800))
--    476
--    (0.01 secs, 2,960,224 bytes)
--    
--    λ> length (show (numeroTriangulaciones4 (10^4)))
--    6014
--    (1.80 secs, 542,364,320 bytes)
--    λ> length (show (numeroTriangulaciones6 (10^4)))
--    6014
--    (1.87 secs, 542,351,136 bytes)

La sucesión de Sylvester

La sucesión de Sylvester es la sucesión que comienza en 2 y sus restantes términos se obtienen multiplicando los anteriores y sumándole 1.

Definir las funciones

   sylvester        :: Integer -> Integer
   graficaSylvester :: Integer -> Integer -> IO ()

tales que

  • (sylvester n) es el n-ésimo término de la sucesión de Sylvester. Por ejemplo,
     λ> [sylvester n | n <- [0..7]]
     [2,3,7,43,1807,3263443,10650056950807,113423713055421844361000443]
     λ> length (show (sylvester 25))
     6830085
  • (graficaSylvester d n) dibuja la gráfica de los d últimos dígitos de los n primeros términos de la sucesión de Sylvester. Por ejemplo,
    • (graficaSylvester 3 30) dibuja
      La_sucesion_de_Sylvester_(3,30)
    • (graficaSylvester 4 30) dibuja
      La_sucesion_de_Sylvester_(4,30)
    • (graficaSylvester 5 30) dibuja
      La_sucesion_de_Sylvester_(5,30)

Soluciones

import Data.List               (genericIndex)
import Data.Array              ((!), array)
import Graphics.Gnuplot.Simple (plotList, Attribute (Key, PNG))
 
-- 1ª solución (por recursión)
-- ===========================
 
sylvester1 :: Integer -> Integer
sylvester1 0 = 2
sylvester1 n = 1 + product [sylvester1 k | k <- [0..n-1]]
 
-- 2ª solución (con programación dinámica)
-- =======================================
 
sylvester2 :: Integer -> Integer
sylvester2 n = v ! n where
  v = array (0,n) [(i,f i) | i <- [0..n]]
  f 0 = 2
  f m = 1 + product [v!k | k <- [0..m-1]]
 
-- 3ª solución
-- ===========
 
sylvester3 :: Integer -> Integer
sylvester3 0 = 2
sylvester3 n = 1 + x^2 - x
  where x = sylvester3 (n-1)
 
-- 4ª solución
-- ===========
 
sylvester4 :: Integer -> Integer
sylvester4 n = v ! n where
  v = array (0,n) [(i,f i) | i <- [0..n]]
  f 0 = 2
  f m = 1 + x^2 - x
    where x = v ! (m-1)
 
-- 4ª solución
-- ===========
 
sylvester5 :: Integer -> Integer
sylvester5 0 = 2
sylvester5 n = 1 + (productosSylvester `genericIndex` (n-1))
 
sucSylvester5 :: [Integer]
sucSylvester5 = map sylvester5 [0..]
 
productosSylvester :: [Integer]
productosSylvester = scanl1 (*) sucSylvester5
 
-- Comparación de eficiencia
-- =========================
 
--    λ> length (show (sylvester1 20))
--    213441
--    (3.40 secs, 519,249,840 bytes)
--    λ> length (show (sylvester2 20))
--    213441
--    (0.10 secs, 13,716,024 bytes)
--    λ> length (show (sylvester3 20))
--    213441
--    (0.16 secs, 13,646,472 bytes)
--    λ> length (show (sylvester4 20))
--    213441
--    (0.18 secs, 13,654,064 bytes)
--    λ> length (show (sylvester5 20))
--    213441
--    (0.12 secs, 13,497,192 bytes)
 
graficaSylvester :: Integer -> Integer -> IO ()
graficaSylvester d n =
  plotList [ Key Nothing
           , PNG ("La_sucesion_de_Sylvester_" ++ show (d,n) ++ ".png")
           ]
           [sylvester5 k `mod` (10^d) | k <- [0..n]]

Suma de las sumas de los cuadrados de los divisores

La suma de las sumas de los cuadrados de los divisores de los 6 primeros números enteros positivos es

     1² + (1²+2²) + (1²+3²) + (1²+2²+4²) + (1²+5²) + (1²+2²+3²+6²)
   = 1  + 5       + 10      + 21         + 26      + 50
   = 113

Definir la función

   sumaSumasCuadradosDivisores :: Integer -> Integer

tal que (sumaSumasCuadradosDivisores n) es la suma de las sumas de los cuadrados de los divisores de los n primeros números enteros positivos. Por ejemplo,

   sumaSumasCuadradosDivisores 6       ==  113
   sumaSumasCuadradosDivisores (10^6)  ==  400686363385965077

Soluciones

import Data.List (genericIndex)
 
-- 1ª solución
-- ===========
 
sumaSumasCuadradosDivisores :: Integer -> Integer
sumaSumasCuadradosDivisores n =
  sum [sumaCuadradosDivisores k | k <- [1..n]]
 
-- (sumaCuadradosDivisores n) es la suma de los cuadrados de los
-- divisores de n. Por ejemplo,
--    sumaCuadradosDivisores 6  ==  50
sumaCuadradosDivisores :: Integer -> Integer
sumaCuadradosDivisores n = sum (map (^2) (divisores n))
 
-- (divisores n) es la lista de los divisores de n. Por ejemplo, 
--    divisores 6  ==  [1,6,2,3]
divisores :: Integer -> [Integer]
divisores 1 = [1]
divisores n = 1 : n : [x | x <- [2..n `div` 2], n `mod` x == 0]
 
-- 2ª solución
-- ===========
 
sumaSumasCuadradosDivisores2 :: Integer -> Integer
sumaSumasCuadradosDivisores2 n =
  sumasSumasCuadradosDivisores `genericIndex` (n-1)
 
-- sumasSumasCuadradosDivisores es la sucesión cuyo n-ésimo término es
-- la suma de las sumas de los cuadrados de los divisores de n. Por
-- ejemplo, 
--    take 6 sumasSumasCuadradosDivisores  ==  [1,6,16,37,63,113]
sumasSumasCuadradosDivisores :: [Integer]
sumasSumasCuadradosDivisores = 1 : sig 1 2
  where sig m n = y : sig y (n+1)
          where y = m + sumaCuadradosDivisores n
 
-- 3ª solución
-- ===========
 
sumaSumasCuadradosDivisores3 :: Integer -> Integer
sumaSumasCuadradosDivisores3 n =
  last (sumasSumasCuadradosDivisores3 n)
 
-- (sumasSumasCuadradosDivisores3 n) es la sucesión cuyo k-ésimo término
-- es la suma de las sumas de los cuadrados de los divisores de k, para
-- k entre 0 y n. Por ejemplo, 
--    sumasSumasCuadradosDivisores3 6  ==  [0,6,18,36,52,77,113]
sumasSumasCuadradosDivisores3 :: Integer -> [Integer]
sumasSumasCuadradosDivisores3 n = scanl f 0 [1..n]
  where f x k = x + k^2 * (n `div` k)
 
-- 4ª solución
-- ===========
 
sumaSumasCuadradosDivisores4 :: Integer -> Integer
sumaSumasCuadradosDivisores4 n =
  last (sumasSumasCuadradosDivisores4 n)
 
-- (sumasSumasCuadradosDivisores4 n) es la sucesión cuyo k-ésimo término
-- es la suma de las sumas de los cuadrados de los divisores de k, para
-- k entre 0 y n. Por ejemplo, 
--    sumasSumasCuadradosDivisores4 6  ==  [0,6,18,36,52,77,113]
sumasSumasCuadradosDivisores4 :: Integer -> [Integer]
sumasSumasCuadradosDivisores4 n = scanl1 f [0,1..n]
  where f x k = x + k^2 * (n `div` k)
 
-- 5ª solución
-- ===========
 
sumaSumasCuadradosDivisores5 :: Integer -> Integer
sumaSumasCuadradosDivisores5 n =
  last (sumasSumasCuadradosDivisores5 n)
 
-- (sumasSumasCuadradosDivisores5 n) es la sucesión cuyo k-ésimo término
-- es la suma de las sumas de los cuadrados de los divisores de k, para
-- k entre 0 y n. Por ejemplo, 
--    sumasSumasCuadradosDivisores5 6  ==  [0,6,18,36,52,77,113]
sumasSumasCuadradosDivisores5 :: Integer -> [Integer]
sumasSumasCuadradosDivisores5 n = scanl1 f [0,1..n]
  where f x k = x + k * (n - (n `mod` k))
 
-- 6ª solución
-- ===========
 
-- Cada elemento k de [1..n], al cuadrado, aparece tantas veces como la
-- parte entera de n/k; luego,
--    sumaSumasCuadradosDivisores n =
--       1^2*n + 2^2*(n `div` 2) + 3^2*(n `div` 3) + ... + n^2*1
 
sumaSumasCuadradosDivisores6 :: Integer -> Integer
sumaSumasCuadradosDivisores6 n = sum (zipWith (*) ds vs)
  where ds = map (^2) [1..n]
        vs = [n `div` k | k <- [1..n]]
 
-- Comparación de eficiencia:
-- =========================
 
--    λ> sumaSumasCuadradosDivisores (3*10^3)
--    10825397502
--    (3.29 secs, 468,721,192 bytes)
--    λ> sumaSumasCuadradosDivisores2 (3*10^3)
--    10825397502
--    (3.25 secs, 469,462,600 bytes)
--    λ> sumaSumasCuadradosDivisores3 (3*10^3)
--    10825397502
--    (0.03 secs, 2,788,752 bytes)
--    λ> sumaSumasCuadradosDivisores4 (3*10^3)
--    10825397502
--    (0.03 secs, 2,813,304 bytes)
--    λ> sumaSumasCuadradosDivisores5 (3*10^3)
--    10825397502
--    (0.03 secs, 1,467,056 bytes)
--    λ> sumaSumasCuadradosDivisores6 (3*10^3)
--    10825397502
--    (0.03 secs, 3,291,664 bytes)
--    
--    λ> sumaSumasCuadradosDivisores3 (5*10^5)
--    50085873311988831
--    (2.34 secs, 440,961,640 bytes)
--    λ> sumaSumasCuadradosDivisores4 (5*10^5)
--    50085873311988831
--    (2.29 secs, 444,962,904 bytes)
--    λ> sumaSumasCuadradosDivisores5 (5*10^5)
--    50085873311988831
--    (1.23 secs, 220,960,152 bytes)
--    λ> sumaSumasCuadradosDivisores6 (5*10^5)
--    50085873311988831
--    (2.76 secs, 524,962,464 bytes)

Números que no son cuadrados

Definir las funciones

   noCuadrados :: [Integer]
   graficaNoCuadrados :: Integer -> IO ()

tales que

  • noCuadrados es la lista de los números naturales que no son cuadrados. Por ejemplo,
     λ> take 25 noCuadrados
     [2,3,5,6,7,8,10,11,12,13,14,15,17,18,19,20,21,22,23,24,26,27,28,29,30]
  • (graficaNoCuadrados n) dibuja las diferencias entre los n primeros elementos de noCuadrados y sus posiciones. Por ejemplo, (graficaNoCuadrados 300) dibuja
    Numeros_que_no_son_cuadrados_300
    (graficaNoCuadrados 3000) dibuja
    Numeros_que_no_son_cuadrados_3000
    (graficaNoCuadrados 30000) dibuja
    Numeros_que_no_son_cuadrados_30000

Comprobar con QuickCheck que el término de noCuadrados en la posición n-1 es (n + floor(1/2 + sqrt(n))).

Soluciones

import Data.List (genericIndex)
import Graphics.Gnuplot.Simple
import Test.QuickCheck
 
-- 1ª definición
-- =============
 
noCuadrados :: [Integer]
noCuadrados = aux [0..] cuadrados
  where aux xs (y:ys) = as ++ aux bs ys
          where (as,_:bs) = span (<y) xs
 
cuadrados :: [Integer]
cuadrados = [x^2 | x <- [0..]]
 
-- 2ª definición
-- =============
 
noCuadrados2 :: [Integer]
noCuadrados2 = aux 2 [1..]
  where aux n (_:xs) = ys ++ aux (n+2) zs
          where (ys,zs) = splitAt n xs
 
-- Definición de graficaNoCuadrados
-- ================================
 
graficaNoCuadrados :: Integer -> IO ()
graficaNoCuadrados n =
  plotList [ Key Nothing
           , PNG ("Numeros_que_no_son_cuadrados_" ++ show n ++ ".png")
           ]
           (zipWith (-) noCuadrados [0..n-1])
 
-- La propiedad es
prop_noCuadrados :: Positive Integer -> Bool
prop_noCuadrados (Positive n) =
  noCuadrados `genericIndex` (n-1) ==
  n + floor (1/2 + sqrt (fromIntegral n))
 
-- La comprobación es
--    λ> quickCheck prop_noCuadrados
--    +++ OK, passed 100 tests.

Sumas parciales de Juzuk

En 1939 Dov Juzuk extendió el método de Nicómaco del cálculo de los cubos. La extensión se basaba en los siguientes pasos:

  • se comienza con la lista de todos los enteros positivos
     [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ...
  • se agrupan tomando el primer elemento, los dos siguientes, los tres
    siguientes, etc.
     [[1], [2, 3], [4, 5, 6], [7, 8, 9, 10], [11, 12, 13, 14, 15], ...
  • se seleccionan los elementos en posiciones pares
     [[1],         [4, 5, 6],                [11, 12, 13, 14, 15], ...
  • se suman los elementos de cada grupo
     [1,           15,                       65,                   ...
  • se calculan las sumas acumuladas
     [1,           16,                       81,                   ...

Las sumas obtenidas son las cuantas potencias de los números enteros positivos.

Definir las funciones

   listasParcialesJuzuk :: [a] -> [[a]]
   sumasParcialesJuzuk  :: [Integer] -> [Integer]

tal que

  • (listasParcialesJuzuk xs) es lalista de ls listas parciales de Juzuk; es decir, la selección de los elementos en posiciones pares de la agrupación de los elementos de xs tomando el primer elemento, los dos siguientes, los tres siguientes, etc. Por ejemplo,
     λ> take 4 (listasParcialesJuzuk [1..])
     [[1],[4,5,6],[11,12,13,14,15],[22,23,24,25,26,27,28]]
     λ> take 4 (listasParcialesJuzuk [1,3..])
     [[1],[7,9,11],[21,23,25,27,29],[43,45,47,49,51,53,55]]
  • (sumasParcialesJuzuk xs) es la lista de las sumas acumuladas de los elementos de las listas de Juzuk generadas por xs. Por ejemplo,
     take 4 (sumasParcialesJuzuk [1..])  ==  [1,16,81,256]
     take 4 (sumasParcialesJuzuk [1,3..])  ==  [1,28,153,496]

Comprobar con QuickChek que, para todo entero positivo n,

  • el elemento de (sumasParcialesJuzuk [1..]) en la posición (n-1) es n^4.
  • el elemento de (sumasParcialesJuzuk [1,3..]) en la posición (n-1) es n^2*(2*n^2 - 1).
  • el elemento de (sumasParcialesJuzuk [1,5..]) en la posición (n-1) es 4*n^4-3*n^2.
  • el elemento de (sumasParcialesJuzuk [2,3..]) en la posición (n-1) es n^2*(n^2+1).

Soluciones

import Data.List (genericIndex)
import Test.QuickCheck
 
listasParcialesJuzuk :: [a] -> [[a]]
listasParcialesJuzuk = elementosEnPares . listasParciales
 
-- (listasParciales xs) es la agrupación de los elementos de xs obtenida
-- tomando el primer elemento, los dos siguientes, los tres siguientes,
-- etc. Por ejemplo, 
--    λ> take 5 (listasParciales [1..])
--    [[1],[2,3],[4,5,6],[7,8,9,10],[11,12,13,14,15]]
listasParciales :: [a] -> [[a]]
listasParciales = aux 1
  where aux n xs = ys : aux (n+1) zs  
          where (ys,zs) = splitAt n xs
 
-- (elementosEnPares xs) es la lista de los elementos de xs en
-- posiciones pares. Por ejemplo,
--    λ> elementosEnPares [[1],[2,3],[4,5,6],[7,8,9,10],[11,12,13,14,15]]
--    [[1],[4,5,6],[11,12,13,14,15]]
elementosEnPares :: [a] -> [a]
elementosEnPares []       = []
elementosEnPares [x]      = [x]
elementosEnPares (x:_:xs) = x : elementosEnPares xs
 
sumasParcialesJuzuk :: [Integer] -> [Integer]
sumasParcialesJuzuk xs =
  scanl1 (+) (map sum (listasParcialesJuzuk xs))
 
-- La primera propiedad es
prop_sumasParcialesJuzuk :: (Positive Integer) -> Bool
prop_sumasParcialesJuzuk (Positive n) =
  sumasParcialesJuzuk [1..] `genericIndex` (n-1) == n^4
 
-- Su comprobación es
--    λ> quickCheck prop_sumasParcialesJuzuk
--    +++ OK, passed 100 tests.
 
-- La segunda propiedad es
prop_sumasParcialesJuzuk2 :: (Positive Integer) -> Bool
prop_sumasParcialesJuzuk2 (Positive n) =
  sumasParcialesJuzuk [1,3..] `genericIndex` (n-1) == n^2*(2*n^2 - 1)
 
-- Su comprobación es
--    λ> quickCheck prop_sumasParcialesJuzuk2
--    +++ OK, passed 100 tests.
 
-- La tercera propiedad es
prop_sumasParcialesJuzuk3 :: (Positive Integer) -> Bool
prop_sumasParcialesJuzuk3 (Positive n) =
  sumasParcialesJuzuk [1,5..] `genericIndex` (n-1) == 4*n^4-3*n^2
 
-- Su comprobación es
--    λ> quickCheck prop_sumasParcialesJuzuk3
--    +++ OK, passed 100 tests.
 
-- La cuarta propiedad es
prop_sumasParcialesJuzuk4 :: (Positive Integer) -> Bool
prop_sumasParcialesJuzuk4 (Positive n) =
  sumasParcialesJuzuk [2,3..] `genericIndex` (n-1) == n^2*(n^2+1)
 
-- Su comprobación es
--    λ> quickCheck prop_sumasParcialesJuzuk4
--    +++ OK, passed 100 tests.

Número de dígitos del factorial

Definir las funciones

   nDigitosFact :: Integer -> Integer
   graficas     :: [Integer] -> IO ()

tales que

  • (nDigitosFact n) es el número de dígitos de n!. Por ejemplo,
     nDigitosFact 0        ==  1
     nDigitosFact 4        ==  2
     nDigitosFact 5        ==  3
     nDigitosFact 10       ==  7
     nDigitosFact 100      ==  158
     nDigitosFact 1000     ==  2568
     nDigitosFact 10000    ==  35660
     nDigitosFact 100000   ==  456574
     nDigitosFact 1000000  ==  5565709
  • (graficas xs) dibuja las gráficas de los números de dígitos del factorial de k (para k en xs) y de la recta y = 5.5 x. Por ejemplo, (graficas [0,500..10^6]) dibuja
    Numero_de_digitos_del_factorial

Nota: Este ejercicio está basado en el problema How many digits? de Kattis en donde se impone la restricción de calcular, en menos de 1 segundo, el número de dígitos de los factoriales de 10.000 números del rango [0,1.000.000].

Se puede simular como sigue

   λ> import System.Random 
   λ> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^3]]
   λ> maximum (map nDigitosFact xs)
   5561492
   λ> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^3]]
   λ> maximum (map nDigitosFact xs)
   5563303

Soluciones

import Data.List (genericLength, genericIndex)
import Graphics.Gnuplot.Simple
 
-- 1ª definición
nDigitosFact1 :: Integer -> Integer
nDigitosFact1 n =
  genericLength (show (product [1..n]))
 
-- 2ª definición (usando logaritmos)
-- =================================
 
-- Basado en
--    nDigitos (n!) = 1 + floor (log (n!))
--                  = 1 + floor (log (1*2*3*...*n))
--                  = 1 + floor (log(1) + log(2) + log(3) +...+ log(n))
 
nDigitosFact2 :: Integer -> Integer
nDigitosFact2 n =
  1 + floor (sum [logBase 10 (fromIntegral k) | k <- [1..n]])
 
-- 3ª definición (usando logaritmos y programación dinámica)
-- =========================================================
 
nDigitosFact3 :: Integer -> Integer
nDigitosFact3 0 = 1
nDigitosFact3 n = 1 + floor ((sumLogs `genericIndex` (n-1)) / log 10)
 
logs :: [Double]
logs = map log [1..]
 
sumLogs :: [Double]
sumLogs = scanl1 (+) logs
 
-- 4ª definición (Usando la fórmula de Kamenetsky)
-- ===============================================
 
-- La fórmula se encuentra en https://oeis.org/A034886
 
nDigitosFact4 :: Integer -> Integer
nDigitosFact4 0 = 1
nDigitosFact4 1 = 1
nDigitosFact4 n =
  1 + floor (m * logBase 10 (m/e) + logBase 10 (2*pi*m)/2)
  where m = fromIntegral n
        e = exp 1
 
--    λ> nDigitosFact1 (4*10^4)
--    166714
--    (5.61 secs, 1,649,912,864 bytes)
--    λ> nDigitosFact2 (4*10^4)
--    166714
--    (0.10 secs, 13,741,360 bytes)
--
--    λ> nDigitosFact2 (7*10^5)
--    3787566
--    (1.86 secs, 187,666,328 bytes)
--    λ> nDigitosFact3 (7*10^5)
--    3787566
--    (0.02 secs, 0 bytes)
--    λ> nDigitosFact3 (7*10^5)
--    3787566
--    (1.01 secs, 238,682,064 bytes)
--    λ> nDigitosFact4 (7*10^5)
--    3787566
--    (0.01 secs, 0 bytes)
-- 
--    λ> import System.Random 
--    λ> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^2]]
--    λ> maximum (map nDigitosFact3 xs)
--    5565097
--    (11.19 secs, 7,336,595,440 bytes)
--    λ> maximum (map nDigitosFact4 xs)
--    5565097
--    (0.01 secs, 0 bytes)
 
graficas :: [Integer] -> IO ()
graficas xs = 
    plotLists [Key Nothing]
              [p1, p2]
    where p1, p2 :: [(Float, Float)]
          p1 = [(fi k, fi (nDigitosFact4 k)) | k <- xs]
          p2 = [(k',5.5*k') | k <- xs, let k' = fi k]
          fi = fromIntegral