Gráficas – Página 7

Las sucesiones de Loomis

José A. Alonso, 30-abril-2018, Ejercicio

La sucesión de Loomis generada por un número entero positivo x es la sucesión cuyos términos se definen por

f(0) es x
f(n) es la suma de f(n-1) y el producto de los dígitos no nulos de f(n-1)

Los primeros términos de las primeras sucesiones de Loomis son

Generada por 1: 1, 2, 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, 108, 116, 122, …
Generada por 2: 2, 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, 108, 116, 122, 126, …
Generada por 3: 3, 6, 12, 14, 18, 26, 38, 62, 74, 102, 104, 108, 116, 122, 126, …
Generada por 4: 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, 108, 116, 122, 126, 138, …
Generada por 5: 5, 10, 11, 12, 14, 18, 26, 38, 62, 74, 102, 104, 108, 116, 122, …

Se observa que a partir de un término todas coinciden con la generada por 1. Dicho término se llama el punto de convergencia. Por ejemplo,

la generada por 2 converge a 2
la generada por 3 converge a 26
la generada por 4 converge a 4
la generada por 5 converge a 26

Definir las siguientes funciones

   sucLoomis           :: Integer -> [Integer]
   convergencia        :: Integer -> Integer
   graficaConvergencia :: [Integer] -> IO ()

tales que

(sucLoomis x) es la sucesión de Loomis generada por x. Por ejemplo,

     λ> take 15 (sucLoomis 1)
     [1,2,4,8,16,22,26,38,62,74,102,104,108,116,122]
     λ> take 15 (sucLoomis 2)
     [2,4,8,16,22,26,38,62,74,102,104,108,116,122,126]
     λ> take 15 (sucLoomis 3)
     [3,6,12,14,18,26,38,62,74,102,104,108,116,122,126]
     λ> take 15 (sucLoomis 4)
     [4,8,16,22,26,38,62,74,102,104,108,116,122,126,138]
     λ> take 15 (sucLoomis 5)
     [5,10,11,12,14,18,26,38,62,74,102,104,108,116,122]
     λ> take 15 (sucLoomis 20)
     [20,22,26,38,62,74,102,104,108,116,122,126,138,162,174]
     λ> take 15 (sucLoomis 100)
     [100,101,102,104,108,116,122,126,138,162,174,202,206,218,234]
     λ> sucLoomis 1 !! (2*10^5)
     235180736652

(convergencia x) es el término de convergencia de la sucesioń de Loomis generada por x xon la geerada por 1. Por ejemplo,

     convergencia  2      ==  2
     convergencia  3      ==  26
     convergencia  4      ==  4
     convergencia 17      ==  38
     convergencia 19      ==  102
     convergencia 43      ==  162
     convergencia 27      ==  202
     convergencia 58      ==  474
     convergencia 63      ==  150056
     convergencia 81      ==  150056
     convergencia 89      ==  150056
     convergencia (10^12) ==  1000101125092

(graficaConvergencia xs) dibuja la gráfica de los términos de convergencia de las sucesiones de Loomis generadas por los elementos de xs. Por ejemplo, (graficaConvergencia ([1..50]) dibuja

y graficaConvergencia ([1..148] \ [63,81,89,137]) dibuja

Soluciones

import Data.List               ((\\))
import Data.Char               (digitToInt)
import Graphics.Gnuplot.Simple (plotList, Attribute (Key, Title, XRange, PNG))
 
-- 1ª definición de sucLoomis
-- ==========================
 
sucLoomis :: Integer -> [Integer]
sucLoomis x = map (loomis x) [0..]
 
loomis :: Integer -> Integer -> Integer
loomis x 0 = x
loomis x n = y + productoDigitosNoNulos y
  where y = loomis x (n-1)
 
productoDigitosNoNulos :: Integer -> Integer
productoDigitosNoNulos = product . digitosNoNulos
 
digitosNoNulos :: Integer -> [Integer]
digitosNoNulos x =
  [read [c] | c <- show x, c /= '0']
 
-- 2ª definición de sucLoomis
-- ==========================
 
sucLoomis2 :: Integer -> [Integer]
sucLoomis2 = iterate siguienteLoomis 
 
siguienteLoomis :: Integer -> Integer
siguienteLoomis y = y + productoDigitosNoNulos y
 
-- 3ª definición de sucLoomis
-- ==========================
 
sucLoomis3 :: Integer -> [Integer]
sucLoomis3 =
  iterate ((+) <*> product .
           map (toInteger . digitToInt) .
           filter (/= '0') . show)
 
 
-- Comparación de eficiencia
-- =========================
 
--    λ> sucLoomis 1 !! 30000
--    6571272766
--    (2.45 secs, 987,955,944 bytes)
--    λ> sucLoomis2 1 !! 30000
--    6571272766
--    (2.26 secs, 979,543,328 bytes)
--    λ> sucLoomis3 1 !! 30000
--    6571272766
--    (0.31 secs, 88,323,832 bytes)
 
-- 1ª definición de convergencia
-- =============================
 
convergencia1 :: Integer -> Integer
convergencia1 x =
  head (dropWhile noEnSucLoomisDe1 (sucLoomis x))
 
noEnSucLoomisDe1 :: Integer -> Bool
noEnSucLoomisDe1 x = not (pertenece x sucLoomisDe1)
 
sucLoomisDe1 :: [Integer]
sucLoomisDe1 = sucLoomis 1
 
pertenece :: Integer -> [Integer] -> Bool
pertenece x ys =
  x == head (dropWhile (<x) ys)
 
-- 2ª definición de convergencia
-- =============================
 
convergencia2 :: Integer -> Integer
convergencia2 = aux (sucLoomis3 1) . sucLoomis3
 where aux as@(x:xs) bs@(y:ys) | x == y    = x
                               | x < y     = aux xs bs
                               | otherwise = aux as ys
 
-- 3ª definición de convergencia
-- =============================
 
convergencia3 :: Integer -> Integer
convergencia3 = head . interseccion (sucLoomis3 1) . sucLoomis3
 
-- (interseccion xs ys) es la intersección entre las listas ordenadas xs
-- e ys. Por ejemplo,
--    λ> take 10 (interseccion (sucLoomis3 1) (sucLoomis3 2))
--    [2,4,8,16,22,26,38,62,74,102]
interseccion :: Ord a => [a] -> [a] -> [a]
interseccion = aux
  where aux as@(x:xs) bs@(y:ys) = case compare x y of
                                    LT ->     aux xs bs
                                    EQ -> x : aux xs ys
                                    GT ->     aux as ys
        aux _         _         = []                           
 
-- 4ª definición de convergencia
-- =============================
 
convergencia4 :: Integer -> Integer
convergencia4 x = perteneceA (sucLoomis3 x) 1
  where perteneceA (y:ys) n | y == c    = y
                            | otherwise = perteneceA ys c
          where c = head $ dropWhile (< y) $ sucLoomis3 n
 
-- Comparación de eficiencia
-- =========================
 
--    λ> convergencia1 (10^4)
--    150056
--    (2.94 secs, 1,260,809,808 bytes)
--    λ> convergencia2 (10^4)
--    150056
--    (0.03 secs, 700,240 bytes)
--    λ> convergencia3 (10^4)
--    150056
--    (0.03 secs, 1,165,496 bytes)
--    λ> convergencia4 (10^4)
--    150056
--    (0.02 secs, 1,119,648 bytes)
--    
--    λ> convergencia2 (10^12)
--    1000101125092
--    (1.81 secs, 714,901,080 bytes)
--    λ> convergencia3 (10^12)
--    1000101125092
--    (1.92 secs, 744,932,184 bytes)
--    λ> convergencia4 (10^12)
--    1000101125092
--    (1.82 secs, 941,053,328 bytes)
 
-- Definición de graficaConvergencia
-- ==================================
 
graficaConvergencia :: [Integer] -> IO ()
graficaConvergencia xs =
  plotList [ Key Nothing
           , Title "Convergencia de sucesiones de Loomis"
           , XRange (fromIntegral (minimum xs),fromIntegral (maximum xs))
           , PNG "Las_sucesiones_de_Loomis_2.png"
           ]
           [(x,convergencia2 x) | x <- xs]

import Data.List ((\\)) import Data.Char (digitToInt) import Graphics.Gnuplot.Simple (plotList, Attribute (Key, Title, XRange, PNG)) -- 1ª definición de sucLoomis -- ========================== sucLoomis :: Integer -> [Integer] sucLoomis x = map (loomis x) [0..] loomis :: Integer -> Integer -> Integer loomis x 0 = x loomis x n = y + productoDigitosNoNulos y where y = loomis x (n-1) productoDigitosNoNulos :: Integer -> Integer productoDigitosNoNulos = product . digitosNoNulos digitosNoNulos :: Integer -> [Integer] digitosNoNulos x = [read [c] | c <- show x, c /= '0'] -- 2ª definición de sucLoomis -- ========================== sucLoomis2 :: Integer -> [Integer] sucLoomis2 = iterate siguienteLoomis siguienteLoomis :: Integer -> Integer siguienteLoomis y = y + productoDigitosNoNulos y -- 3ª definición de sucLoomis -- ========================== sucLoomis3 :: Integer -> [Integer] sucLoomis3 = iterate ((+) <*> product . map (toInteger . digitToInt) . filter (/= '0') . show) -- Comparación de eficiencia -- ========================= -- λ> sucLoomis 1 !! 30000 -- 6571272766 -- (2.45 secs, 987,955,944 bytes) -- λ> sucLoomis2 1 !! 30000 -- 6571272766 -- (2.26 secs, 979,543,328 bytes) -- λ> sucLoomis3 1 !! 30000 -- 6571272766 -- (0.31 secs, 88,323,832 bytes) -- 1ª definición de convergencia -- ============================= convergencia1 :: Integer -> Integer convergencia1 x = head (dropWhile noEnSucLoomisDe1 (sucLoomis x)) noEnSucLoomisDe1 :: Integer -> Bool noEnSucLoomisDe1 x = not (pertenece x sucLoomisDe1) sucLoomisDe1 :: [Integer] sucLoomisDe1 = sucLoomis 1 pertenece :: Integer -> [Integer] -> Bool pertenece x ys = x == head (dropWhile (<x) ys) -- 2ª definición de convergencia -- ============================= convergencia2 :: Integer -> Integer convergencia2 = aux (sucLoomis3 1) . sucLoomis3 where aux as@(x:xs) bs@(y:ys) | x == y = x | x < y = aux xs bs | otherwise = aux as ys -- 3ª definición de convergencia -- ============================= convergencia3 :: Integer -> Integer convergencia3 = head . interseccion (sucLoomis3 1) . sucLoomis3 -- (interseccion xs ys) es la intersección entre las listas ordenadas xs -- e ys. Por ejemplo, -- λ> take 10 (interseccion (sucLoomis3 1) (sucLoomis3 2)) -- [2,4,8,16,22,26,38,62,74,102] interseccion :: Ord a => [a] -> [a] -> [a] interseccion = aux where aux as@(x:xs) bs@(y:ys) = case compare x y of LT -> aux xs bs EQ -> x : aux xs ys GT -> aux as ys aux _ _ = [] -- 4ª definición de convergencia -- ============================= convergencia4 :: Integer -> Integer convergencia4 x = perteneceA (sucLoomis3 x) 1 where perteneceA (y:ys) n | y == c = y | otherwise = perteneceA ys c where c = head $ dropWhile (< y) $ sucLoomis3 n -- Comparación de eficiencia -- ========================= -- λ> convergencia1 (10^4) -- 150056 -- (2.94 secs, 1,260,809,808 bytes) -- λ> convergencia2 (10^4) -- 150056 -- (0.03 secs, 700,240 bytes) -- λ> convergencia3 (10^4) -- 150056 -- (0.03 secs, 1,165,496 bytes) -- λ> convergencia4 (10^4) -- 150056 -- (0.02 secs, 1,119,648 bytes) -- -- λ> convergencia2 (10^12) -- 1000101125092 -- (1.81 secs, 714,901,080 bytes) -- λ> convergencia3 (10^12) -- 1000101125092 -- (1.92 secs, 744,932,184 bytes) -- λ> convergencia4 (10^12) -- 1000101125092 -- (1.82 secs, 941,053,328 bytes) -- Definición de graficaConvergencia -- ================================== graficaConvergencia :: [Integer] -> IO () graficaConvergencia xs = plotList [ Key Nothing , Title "Convergencia de sucesiones de Loomis" , XRange (fromIntegral (minimum xs),fromIntegral (maximum xs)) , PNG "Las_sucesiones_de_Loomis_2.png" ] [(x,convergencia2 x) | x <- xs]

Leer más →

Alturas primas

José A. Alonso, 10-abril-2018, Inicial

Se considera una enumeración de los números primos:

    p(1)=2,  p(2)=3, p(3)=5, p(4)=7, p(5)=11, p(6)=13, p(7)=17,...

Dado un entero x > 1, su altura prima es el mayor i tal que el primo p(i) aparece en la factorización de x en números primos. Por ejemplo, la altura prima de 3500 tiene longitud 4, pues 3500=2^2×5^3×7^1 y la de 34 tiene es 7, pues 34 = 2×17. Además, se define la altura prima de 1 como 0.

Definir las funciones

   alturaPrima        :: Integer -> Integer
   alturasPrimas      :: Integer -> [Integer]
   graficaAlturaPrima :: Integer -> IO ()

tales que

(alturaPrima x) es la altura prima de x. Por ejemplo,

     alturaPrima 3500  ==  4
     alturaPrima 34    ==  7

(alturasPrimas n) es la lista de las altura prima de los primeros n números enteros positivos. Por ejemplo,

     alturasPrimas 15  ==  [0,1,2,1,3,2,4,1,2,3,5,2,6,4,3]
     maximum (alturasPrimas 10000)  ==  1229
     maximum (alturasPrimas 20000)  ==  2262
     maximum (alturasPrimas 30000)  ==  3245
     maximum (alturasPrimas 40000)  ==  4203

(graficaAlturaPrima n) dibuja las alturas primas de los números entre 2 y n. Por ejemplo, (graficaAlturaPrima 500) dibuja

Soluciones

import Data.List (genericLength)
import Data.Numbers.Primes (isPrime, primes, primeFactors)
import Data.Array
import Graphics.Gnuplot.Simple
 
-- 1ª definicioń de alturaPrima
-- ============================
 
alturaPrima :: Integer -> Integer
alturaPrima 1 = 0
alturaPrima n = indice (mayorFactorPrimo n)
 
-- (mayorFactorPrimo n) es el mayor factor primo de n. Por ejemplo,
--    mayorFactorPrimo 3500  ==  7
--    mayorFactorPrimo 34    ==  17
mayorFactorPrimo :: Integer -> Integer
mayorFactorPrimo = last . primeFactors
 
-- (indice p) es el índice de p en la sucesión de los números
-- primos. Por ejemplo,
--    indice 7   ==  4
--    indice 17  ==  7
indice :: Integer -> Integer
indice p = genericLength (takeWhile (<=p) primes)
 
-- 2ª definicioń de alturaPrima
-- ============================
 
alturaPrima2 :: Integer -> Integer
alturaPrima2 n = v ! n
  where v = array (1,n) [(i,f i) | i <- [1..n]]
        f 1 = 0
        f k | isPrime k = indice2 k
            | otherwise = v ! (k `div` (head (primeFactors k)))
 
indice2 :: Integer -> Integer
indice2 p = head [n | (x,n) <- indicesPrimos, x == p]
 
-- indicesPrimos es la suceción formada por los números primos y sus
-- índices. Por ejemplo,
--    λ> take 10 indicesPrimos
--    [(2,1),(3,2),(5,3),(7,4),(11,5),(13,6),(17,7),(19,8),(23,9),(29,10)]
indicesPrimos :: [(Integer,Integer)]
indicesPrimos = zip primes [1..]
 
-- 1ª definición de alturasPrimas
-- ==============================
 
alturasPrimas :: Integer -> [Integer]
alturasPrimas n = map alturaPrima [1..n]
 
-- 2ª definición de alturasPrimas
-- ==============================
 
alturasPrimas2 :: Integer -> [Integer]
alturasPrimas2 n = elems v 
  where v = array (1,n) [(i,f i) | i <- [1..n]]
        f 1 = 0
        f k | isPrime k = indice2 k
            | otherwise = v ! (k `div` (head (primeFactors k)))
 
-- Comparación de eficiencia
-- =========================
 
--    λ> maximum (alturasPrimas 20000)
--    2262
--    (29.97 secs, 13,179,984,536 bytes)
--    λ> maximum (alturasPrimas2 20000)
--    2262
--    (2.11 secs, 455,259,448 bytes)
 
-- Definición de graficaAlturaPrima
-- ================================
 
graficaAlturaPrima :: Integer -> IO ()
graficaAlturaPrima n =
  plotList [ Key Nothing
           , PNG "Alturas_primas.png"
           ]
           (alturasPrimas2 n)

import Data.List (genericLength) import Data.Numbers.Primes (isPrime, primes, primeFactors) import Data.Array import Graphics.Gnuplot.Simple -- 1ª definicioń de alturaPrima -- ============================ alturaPrima :: Integer -> Integer alturaPrima 1 = 0 alturaPrima n = indice (mayorFactorPrimo n) -- (mayorFactorPrimo n) es el mayor factor primo de n. Por ejemplo, -- mayorFactorPrimo 3500 == 7 -- mayorFactorPrimo 34 == 17 mayorFactorPrimo :: Integer -> Integer mayorFactorPrimo = last . primeFactors -- (indice p) es el índice de p en la sucesión de los números -- primos. Por ejemplo, -- indice 7 == 4 -- indice 17 == 7 indice :: Integer -> Integer indice p = genericLength (takeWhile (<=p) primes) -- 2ª definicioń de alturaPrima -- ============================ alturaPrima2 :: Integer -> Integer alturaPrima2 n = v ! n where v = array (1,n) [(i,f i) | i <- [1..n]] f 1 = 0 f k | isPrime k = indice2 k | otherwise = v ! (k `div` (head (primeFactors k))) indice2 :: Integer -> Integer indice2 p = head [n | (x,n) <- indicesPrimos, x == p] -- indicesPrimos es la suceción formada por los números primos y sus -- índices. Por ejemplo, -- λ> take 10 indicesPrimos -- [(2,1),(3,2),(5,3),(7,4),(11,5),(13,6),(17,7),(19,8),(23,9),(29,10)] indicesPrimos :: [(Integer,Integer)] indicesPrimos = zip primes [1..] -- 1ª definición de alturasPrimas -- ============================== alturasPrimas :: Integer -> [Integer] alturasPrimas n = map alturaPrima [1..n] -- 2ª definición de alturasPrimas -- ============================== alturasPrimas2 :: Integer -> [Integer] alturasPrimas2 n = elems v where v = array (1,n) [(i,f i) | i <- [1..n]] f 1 = 0 f k | isPrime k = indice2 k | otherwise = v ! (k `div` (head (primeFactors k))) -- Comparación de eficiencia -- ========================= -- λ> maximum (alturasPrimas 20000) -- 2262 -- (29.97 secs, 13,179,984,536 bytes) -- λ> maximum (alturasPrimas2 20000) -- 2262 -- (2.11 secs, 455,259,448 bytes) -- Definición de graficaAlturaPrima -- ================================ graficaAlturaPrima :: Integer -> IO () graficaAlturaPrima n = plotList [ Key Nothing , PNG "Alturas_primas.png" ] (alturasPrimas2 n)

Leer más →

Sucesiones de números consecutivos con suma dada

José A. Alonso, 29-marzo-2018, Medio

El número 15 se puede escribir de 5 formas como suma de números naturales consecutivos:

   15 = 0+1+2+3+4+5 = 1+2+3+4+5 = 4+5+6 = 7+8 = 15.

Definir las funciones

   sucesionesConSuma        :: Int -> [(Int,Int)]
   graficaSucesionesConSuma :: Int -> IO ()

tales que

(sucesionesConSuma n) es la lista de los pares formados por el primero y por el último elemento de las sucesiones de números naturales consecutivos con suma n. Por ejemplo,

     sucesionesConSuma 15             ==  [(0,5),(1,5),(4,6),(7,8),(15,15)]
     length (sucesionesConSuma 3000)  ==  8

(graficaSucesionesConSuma n) dibuja la gráfica del número de formas de escribir los n primeros números como suma de números naturales consecutivos. Por ejemplo, (graficaSucesionesConSuma 100) dibuja

Soluciones

import Graphics.Gnuplot.Simple
 
-- 1ª solución
sucesionesConSuma :: Int -> [(Int,Int)]
sucesionesConSuma n =
  [(x,y) | y <- [0..n], x <- [0..y], sum [x..y] == n]
 
-- 2ª solución
sucesionesConSuma2 :: Int -> [(Int,Int)]
sucesionesConSuma2 n = 
    [(x,y) | y <- [0..n], x <- [0..y], (x+y)*(y-x+1) == 2*n]
 
-- Comparación de eficiencia
--    λ> sucesionesConSuma 700
--    [(3,37),(16,40),(84,91),(97,103),(138,142),(700,700)]
--    (2.71 secs, 7,894,718,264 bytes)
--    λ> sucesionesConSuma2 700
--    [(3,37),(16,40),(84,91),(97,103),(138,142),(700,700)]
--    (0.22 secs, 118,104,176 bytes)
 
-- Gráfica
graficaSucesionesConSuma :: Int -> IO ()
graficaSucesionesConSuma n =
  plotList [ Key Nothing
           , PNG "Sucesiones_de_numeros_consecutivos_con_suma_dada.png"]
           [length (sucesionesConSuma2 k) | k <- [0..n]]

Leer más →

Números tetranacci

José A. Alonso, 27-marzo-2018, Inicial

Los números tetranacci son una generalización de los números de Fibonacci definidos por

   T(0) = 0,
   T(1) = 1,
   T(2) = 1,
   T(3) = 2, 
   T(n) = T(n-1) + T(n-2) + T(n-3) + T(n-4), para n > 3.

Los primeros números tetranacci son

   0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208

Definir las funciones

   tetranacci        :: Int -> Integer
   graficaTetranacci :: Int -> IO ()

tales que

(tetranacci n) es el n-ésimo número tetranacci. Por ejemplo,

     λ> tetranacci 10
     208
     λ> map tetranacci [0..10]
     [0,1,1,2,4,8,15,29,56,108,208]
     λ> length (show (tetranacci5 (10^5)))
     28501

(graficaTetranacci n) dibuja la gráfica de los cocientes de n primeros pares de número tetranacci. Por ejemplo, (graficaTetranacci 300) dibuja

Soluciones

import Data.List (zipWith4)
import Data.Array
import Graphics.Gnuplot.Simple
 
-- 1ª solución (por recursión) 
-- ===========================
 
tetranacci :: Int -> Integer
tetranacci 0 = 0
tetranacci 1 = 1
tetranacci 2 = 1
tetranacci 3 = 2
tetranacci n =
  tetranacci (n-1) + tetranacci (n-2) + tetranacci (n-3) + tetranacci (n-4) 
 
-- 2ª solución (programación dinámica con zipWith4)
-- ================================================
 
tetranacci2 :: Int -> Integer
tetranacci2 n = tetranaccis2 !! n
 
tetranaccis2 :: [Integer]
tetranaccis2 = 
    0 : 1 : 1 : 2 : zipWith4 f (r 0) (r 1) (r 2) (r 3)
    where f a b c d = a+b+c+d
          r n       = drop n tetranaccis2
 
-- 3ª solución (con acumuladores)
-- ==============================
 
tetranacci3 :: Int -> Integer
tetranacci3 n = tetranaccis3 !! n
 
tetranaccis3 :: [Integer]
tetranaccis3 = p (0, 1, 1, 2)
    where p (a, b, c, d) = a : p (b, c, d, a + b + c + d)
 
-- 4ª solución
-- =============
 
tetranacci4 :: Int -> Integer
tetranacci4 n = tetranaccis4 !! n
 
tetranaccis4 :: [Integer]
tetranaccis4 = 0 : 1 : 1 : 2 : p tetranaccis4
   where p (a:b:c:d:xs) = (a+b+c+d): p (b:c:d:xs)
 
-- 5ª solución (programación dinámica con vectores)
-- ================================================
 
tetranacci5 :: Int -> Integer
tetranacci5 n = v ! n where
  v = array (0,n) [(i,f i) | i <- [0..n]]
  f 0 = 0
  f 1 = 1
  f 2 = 1
  f 3 = 2
  f k = v!(k-1) + v!(k-2) + v!(k-3) + v!(k-4) 
 
-- Comparación de eficiencia
-- =========================
 
--    λ> tetranacci 26
--    7555935
--    (3.04 secs, 1,649,520,064 bytes)
--    λ> tetranacci2 26
--    7555935
--    (0.00 secs, 148,064 bytes)
-- 
--    λ> length (show (tetranacci2 (10^5)))
--    28501
--    (1.22 secs, 1,844,457,288 bytes)
--    λ> length (show (tetranacci3 (10^5)))
--    28501
--    (0.88 secs, 1,860,453,968 bytes)
--    λ> length (show (tetranacci4 (10^5)))
--    28501
--    (0.77 secs, 1,882,852,168 bytes)
--    λ> length (show (tetranacci5 (10^5)))
--    28501
--    (0.72 secs, 1,905,707,408 bytes)
 
-- Gráfica
-- =======
 
graficaTetranacci :: Int -> IO ()
graficaTetranacci n =
  plotList [ Key Nothing
           , Title "Tasa de crecimiento de los numeros tetranacci"
           , PNG ("Numeros_tetranacci_" ++ show n ++ ".png")
           ]
           (take n (zipWith (/) (tail xs) xs))
  where xs = (map fromIntegral tetranaccis4) :: [Double]

import Data.List (zipWith4) import Data.Array import Graphics.Gnuplot.Simple -- 1ª solución (por recursión) -- =========================== tetranacci :: Int -> Integer tetranacci 0 = 0 tetranacci 1 = 1 tetranacci 2 = 1 tetranacci 3 = 2 tetranacci n = tetranacci (n-1) + tetranacci (n-2) + tetranacci (n-3) + tetranacci (n-4) -- 2ª solución (programación dinámica con zipWith4) -- ================================================ tetranacci2 :: Int -> Integer tetranacci2 n = tetranaccis2 !! n tetranaccis2 :: [Integer] tetranaccis2 = 0 : 1 : 1 : 2 : zipWith4 f (r 0) (r 1) (r 2) (r 3) where f a b c d = a+b+c+d r n = drop n tetranaccis2 -- 3ª solución (con acumuladores) -- ============================== tetranacci3 :: Int -> Integer tetranacci3 n = tetranaccis3 !! n tetranaccis3 :: [Integer] tetranaccis3 = p (0, 1, 1, 2) where p (a, b, c, d) = a : p (b, c, d, a + b + c + d) -- 4ª solución -- ============= tetranacci4 :: Int -> Integer tetranacci4 n = tetranaccis4 !! n tetranaccis4 :: [Integer] tetranaccis4 = 0 : 1 : 1 : 2 : p tetranaccis4 where p (a:b:c:d:xs) = (a+b+c+d): p (b:c:d:xs) -- 5ª solución (programación dinámica con vectores) -- ================================================ tetranacci5 :: Int -> Integer tetranacci5 n = v ! n where v = array (0,n) [(i,f i) | i <- [0..n]] f 0 = 0 f 1 = 1 f 2 = 1 f 3 = 2 f k = v!(k-1) + v!(k-2) + v!(k-3) + v!(k-4) -- Comparación de eficiencia -- ========================= -- λ> tetranacci 26 -- 7555935 -- (3.04 secs, 1,649,520,064 bytes) -- λ> tetranacci2 26 -- 7555935 -- (0.00 secs, 148,064 bytes) -- -- λ> length (show (tetranacci2 (10^5))) -- 28501 -- (1.22 secs, 1,844,457,288 bytes) -- λ> length (show (tetranacci3 (10^5))) -- 28501 -- (0.88 secs, 1,860,453,968 bytes) -- λ> length (show (tetranacci4 (10^5))) -- 28501 -- (0.77 secs, 1,882,852,168 bytes) -- λ> length (show (tetranacci5 (10^5))) -- 28501 -- (0.72 secs, 1,905,707,408 bytes) -- Gráfica -- ======= graficaTetranacci :: Int -> IO () graficaTetranacci n = plotList [ Key Nothing , Title "Tasa de crecimiento de los numeros tetranacci" , PNG ("Numeros_tetranacci_" ++ show n ++ ".png") ] (take n (zipWith (/) (tail xs) xs)) where xs = (map fromIntegral tetranaccis4) :: [Double]

Leer más →

Conjetura de Goldbach

José A. Alonso, 21-marzo-2018, Medio

Una forma de la conjetura de Golbach afirma que todo entero mayor que 1 se puede escribir como la suma de uno, dos o tres números primos.

Si se define el índice de Goldbach de n > 1 como la mínima cantidad de primos necesarios para que su suma sea n, entonces la conjetura de Goldbach afirma que todos los índices de Goldbach de los enteros mayores que 1 son menores que 4.

Definir las siguientes funciones

   indiceGoldbach  :: Int -> Int
   graficaGoldbach :: Int -> IO ()

tales que

(indiceGoldbach n) es el índice de Goldbach de n. Por ejemplo,

     indiceGoldbach 2                        ==  1
     indiceGoldbach 4                        ==  2
     indiceGoldbach 27                       ==  3
     sum (map indiceGoldbach [2..5000])      ==  10619
     maximum (map indiceGoldbach [2..5000])  ==  3

(graficaGoldbach n) dibuja la gráfica de los índices de Goldbach de los números entre 2 y n. Por ejemplo, (graficaGoldbach 150) dibuja

Comprobar con QuickCheck la conjetura de Goldbach anterior.

Soluciones

import Data.Array
import Data.Numbers.Primes
import Graphics.Gnuplot.Simple
import Test.QuickCheck
 
 
-- 1ª definición
-- =============
 
indiceGoldbach :: Int -> Int
indiceGoldbach n =
  minimum (map length (particiones n))
 
particiones :: Int -> [[Int]]
particiones n = v ! n where
  v = array (0,n) [(i,f i) | i <- [0..n]]
    where f 0 = [[]]
          f m = [x:y | x <- xs, 
                       y <- v ! (m-x), 
                       [x] >= take 1 y]
            where xs = reverse (takeWhile (<= m) primes)
 
-- 2ª definición
-- =============
 
indiceGoldbach2 :: Int -> Int
indiceGoldbach2 x =
  head [n | n <- [1..], esSumaDe x n]
 
-- (esSumaDe x n) se verifica si x se puede escribir como la suma de n
-- primos. Por ejemplo,
--    esSumaDe 2  1  ==  True
--    esSumaDe 4  1  ==  False
--    esSumaDe 4  2  ==  True
--    esSumaDe 27 2  ==  False
--    esSumaDe 27 3  ==  True
esSumaDe :: Int -> Int -> Bool
esSumaDe x 1 = isPrime x
esSumaDe x n = or [esSumaDe (x-p) (n-1) | p <- takeWhile (<= x) primes]
 
-- 3ª definición
-- =============
 
indiceGoldbach3 :: Int -> Int
indiceGoldbach3 x =
  head [n | n <- [1..], esSumaDe3 x n]
 
esSumaDe3 :: Int -> Int -> Bool
esSumaDe3 x n = a ! (x,n) where
  a = array ((2,1),(x,9)) [((i,j),f i j) | i <- [2..x], j <- [1..9]]
  f i 1 = isPrime i
  f i j = or [a!(i-k,j-1) | k <- takeWhile (<= i) primes]
 
-- 4ª definición
-- =============
 
indiceGoldbach4 :: Int -> Int
indiceGoldbach4 n = v ! n where
  v = array (2,n) [(i,f i) | i <- [2..n]]
  f i | isPrime i = 1
      | otherwise = 1 + minimum [v!(i-p) | p <- takeWhile (< (i-1)) primes]
 
-- Comparación de eficiencia
-- =========================
 
--    λ> sum (map indiceGoldbach [2..80])
--    142
--    (2.66 secs, 1,194,330,496 bytes)
--    λ> sum (map indiceGoldbach2 [2..80])
--    142
--    (0.01 secs, 1,689,944 bytes)
--    λ> sum (map indiceGoldbach3 [2..80])
--    142
--    (0.03 secs, 27,319,296 bytes)
--    λ> sum (map indiceGoldbach4 [2..80])
--    142
--    (0.03 secs, 47,823,656 bytes)
--    
--    λ> sum (map indiceGoldbach2 [2..1000])
--    2030
--    (0.10 secs, 200,140,264 bytes)
--    λ> sum (map indiceGoldbach3 [2..1000])
--    2030
--    (3.10 secs, 4,687,467,664 bytes)
 
-- Gráfica
-- =======
 
graficaGoldbach :: Int -> IO ()
graficaGoldbach n =
  plotList [ Key Nothing
           , XRange (2,fromIntegral n)
           , PNG ("Conjetura_de_Goldbach_" ++ show n ++ ".png")
           ]
           [indiceGoldbach2 k | k <- [2..n]]
 
-- Comprobación de la conjetura de Goldbach
-- ========================================
 
-- La propiedad es
prop_Goldbach :: Int -> Property
prop_Goldbach x =
  x >= 2 ==> indiceGoldbach2 x < 4
 
-- La comprobación es
--    λ> quickCheck prop_Goldbach
--    +++ OK, passed 100 tests.

import Data.Array import Data.Numbers.Primes import Graphics.Gnuplot.Simple import Test.QuickCheck -- 1ª definición -- ============= indiceGoldbach :: Int -> Int indiceGoldbach n = minimum (map length (particiones n)) particiones :: Int -> [[Int]] particiones n = v ! n where v = array (0,n) [(i,f i) | i <- [0..n]] where f 0 = [[]] f m = [x:y | x <- xs, y <- v ! (m-x), [x] >= take 1 y] where xs = reverse (takeWhile (<= m) primes) -- 2ª definición -- ============= indiceGoldbach2 :: Int -> Int indiceGoldbach2 x = head [n | n <- [1..], esSumaDe x n] -- (esSumaDe x n) se verifica si x se puede escribir como la suma de n -- primos. Por ejemplo, -- esSumaDe 2 1 == True -- esSumaDe 4 1 == False -- esSumaDe 4 2 == True -- esSumaDe 27 2 == False -- esSumaDe 27 3 == True esSumaDe :: Int -> Int -> Bool esSumaDe x 1 = isPrime x esSumaDe x n = or [esSumaDe (x-p) (n-1) | p <- takeWhile (<= x) primes] -- 3ª definición -- ============= indiceGoldbach3 :: Int -> Int indiceGoldbach3 x = head [n | n <- [1..], esSumaDe3 x n] esSumaDe3 :: Int -> Int -> Bool esSumaDe3 x n = a ! (x,n) where a = array ((2,1),(x,9)) [((i,j),f i j) | i <- [2..x], j <- [1..9]] f i 1 = isPrime i f i j = or [a!(i-k,j-1) | k <- takeWhile (<= i) primes] -- 4ª definición -- ============= indiceGoldbach4 :: Int -> Int indiceGoldbach4 n = v ! n where v = array (2,n) [(i,f i) | i <- [2..n]] f i | isPrime i = 1 | otherwise = 1 + minimum [v!(i-p) | p <- takeWhile (< (i-1)) primes] -- Comparación de eficiencia -- ========================= -- λ> sum (map indiceGoldbach [2..80]) -- 142 -- (2.66 secs, 1,194,330,496 bytes) -- λ> sum (map indiceGoldbach2 [2..80]) -- 142 -- (0.01 secs, 1,689,944 bytes) -- λ> sum (map indiceGoldbach3 [2..80]) -- 142 -- (0.03 secs, 27,319,296 bytes) -- λ> sum (map indiceGoldbach4 [2..80]) -- 142 -- (0.03 secs, 47,823,656 bytes) -- -- λ> sum (map indiceGoldbach2 [2..1000]) -- 2030 -- (0.10 secs, 200,140,264 bytes) -- λ> sum (map indiceGoldbach3 [2..1000]) -- 2030 -- (3.10 secs, 4,687,467,664 bytes) -- Gráfica -- ======= graficaGoldbach :: Int -> IO () graficaGoldbach n = plotList [ Key Nothing , XRange (2,fromIntegral n) , PNG ("Conjetura_de_Goldbach_" ++ show n ++ ".png") ] [indiceGoldbach2 k | k <- [2..n]] -- Comprobación de la conjetura de Goldbach -- ======================================== -- La propiedad es prop_Goldbach :: Int -> Property prop_Goldbach x = x >= 2 ==> indiceGoldbach2 x < 4 -- La comprobación es -- λ> quickCheck prop_Goldbach -- +++ OK, passed 100 tests.

Leer más →

Etiqueta: Gráficas

Las sucesiones de Loomis

Soluciones

Alturas primas

Soluciones

Sucesiones de números consecutivos con suma dada

Soluciones

Números tetranacci

Soluciones

Conjetura de Goldbach

Soluciones

Subscribe to Blog via Email

Entradas recientes

Etiquetas

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