Menu Close

Etiqueta: sqrt

Sucesión de raíces enteras de los números primos

Definir las siguientes funciones

   raicesEnterasPrimos :: [Integer]
   posiciones :: Integer -> (Int,Int)
   frecuencia :: Integer -> Int
   grafica_raicesEnterasPrimos :: Int -> IO ()
   grafica_posicionesIniciales :: Integer -> IO ()
   grafica_frecuencias :: Integer -> IO ()

tales que

  • raicesEnterasPrimos es la sucesión de las raíces enteras (por defecto) de los números primos. Por ejemplo,
     λ> take 20 raicesEnterasPrimos
     [1,1,2,2,3,3,4,4,4,5,5,6,6,6,6,7,7,7,8,8]
     λ> raicesEnterasPrimos !! 2500000
     6415
  • (posiciones x) es el par formado por la menor y la mayor posición de x en la sucesión de las raíces enteras de los números primos. Por ejemplo,
      posiciones 2     ==  (2,3)
      posiciones 4     ==  (6,8)
      posiciones 2017  ==  (287671,287931)
      posiciones 2018  ==  (287932,288208)
  • (frecuencia x) es el número de veces que aparece x en la sucesión de las raíces enteras de los números primos. Por ejemplo,
      frecuencia 2     ==  2
      frecuencia 4     ==  3
      frecuencia 2017  ==  261
      frecuencia 2018  ==  277
  • (grafica_raicesEnterasPrimos n) dibuja la gráfica de los n primeros términos de la sucesión de las raíces enteras de los números primos. Por ejemplo, (grafica_raicesEnterasPrimos 200) dibuja
    Sucesion_de_raices_enteras_de_primos_1
  • (grafica_posicionesIniciales n) dibuja la gráfica de las menores posiciones de los n primeros números en la sucesión de las raíces enteras de los números primos. Por ejemplo, (grafica_posicionesIniciales 200) dibuja
    Sucesion_de_raices_enteras_de_primos_2
  • (grafica_frecuencia n) dibuja la gráfica de las frecuencia de los n primeros números en la sucesión de las raíces enteras de los números primos. Por ejemplo, (grafica_frecuencia 200) dibuja
    Sucesion_de_raices_enteras_de_primos_3

Soluciones

import Data.Numbers.Primes (primes)
import Graphics.Gnuplot.Simple
 
raicesEnterasPrimos :: [Integer]
raicesEnterasPrimos = map raizEntera primes                       
 
raizEntera :: Integer -> Integer
raizEntera = floor . sqrt . fromIntegral
 
posiciones :: Integer -> (Int,Int)
posiciones x = (n,n+m-1)
  where (as,bs) = span (<x) raicesEnterasPrimos
        cs      = takeWhile (==x) bs 
        n       = length as
        m       = length cs
 
frecuencia :: Integer -> Int
frecuencia x =
  ( length
  . takeWhile (==x)
  . dropWhile (<x)
  ) raicesEnterasPrimos
 
grafica_raicesEnterasPrimos :: Int -> IO ()
grafica_raicesEnterasPrimos n = 
  plotList [ Title "Raices enteras de primos"
           , XLabel "Posiciones de numeros primos"
           , YLabel "Raiz entera del n-esimo primo"
           , Key Nothing
           , PNG "Sucesion_de_raices_enteras_de_primos_1.png"
           ]
           (take n raicesEnterasPrimos)
 
grafica_posicionesIniciales :: Integer -> IO ()
grafica_posicionesIniciales n = 
  plotList [ Title "Posiciones iniciales en raices enteras de primos"
           , XLabel "Numeros enteros"
           , YLabel "Posicion del numero n en las raices enteras de primos"
           , Key Nothing
           , PNG "Sucesion_de_raices_enteras_de_primos_2.png"
           ]
           (map (fst . posiciones) [1..n])
 
grafica_frecuencias :: Integer -> IO ()
grafica_frecuencias n = 
  plotList [ Title "Frecuencias en raices enteras de primos"
           , XLabel "Numeros enteros n"
           , YLabel "Frecuencia del numero n en las raices enteras de primos"
           , Key Nothing
           , PNG "Sucesion_de_raices_enteras_de_primos_3.png"
           ]
           (map frecuencia [1..n])

Caminos minimales en un árbol numérico

En la librería Data.Tree se definen los árboles y los bosques como sigue

   data Tree a   = Node a (Forest a)
   type Forest a = [Tree a]

Se pueden definir árboles. Por ejemplo,

   ej = Node 3 [Node 5 [Node 9 []], Node 7 []]

Y se pueden dibujar con la función drawTree. Por ejemplo,

   λ> putStrLn (drawTree (fmap show ej))
   3
   |
   +- 5
   |  |
   |  `- 9
   |
   `- 7

Los mayores divisores de un número x son los divisores u tales que u > 1 y existe un v tal que 1 < v < u y u*v = x. Por ejemplo, los mayores divisores de 24 son 12, 8 y 6.

El árbol de los predecesores y mayores divisores de un número x es el árbol cuya raíz es x y los sucesores de cada nodo y > 1 es el conjunto formado por y-1 junto con los mayores divisores de y. Los nodos con valor 1 no tienen sucesores. Por ejemplo, el árbol de los predecesores y mayores divisores del número 6 es

       6
      / \
     5   3 
     |   |
     4   2
    / \  |
   3   2 1 
   |   | 
   2   1
   |
   1

Definir las siguientes funciones

   mayoresDivisores :: Int -> [Int]
   arbol            :: Int -> Tree Int
   caminos          :: Int -> [[Int]]
   caminosMinimales :: Int -> [[Int]]

tales que

  • (mayoresDivisores x) es la lista de los mayores divisores de x. Por ejemplo,
     mayoresDivisores 24  ==  [12,8,6]
     mayoresDivisores 16  ==  [8,4]
     mayoresDivisores 10  ==  [5]
     mayoresDivisores 17  ==  []
  • (arbol x) es el árbol de los predecesores y mayores divisores del número x. Por ejemplo,
     λ> putStrLn (drawTree (fmap show (arbol 6)))
     6
     |
     +- 5
     |  |
     |  `- 4
     |     |
     |     +- 3
     |     |  |
     |     |  `- 2
     |     |     |
     |     |     `- 1
     |     |
     |     `- 2
     |        |
     |        `- 1
     |
     `- 3
        |
        `- 2
           |
           `- 1
  • (caminos x) es la lista de los caminos en el árbol de los predecesores y mayores divisores del número x. Por ejemplo,
     λ> caminos 6
     [[6,5,4,3,2,1],[6,5,4,2,1],[6,3,2,1]]
  • (caminosMinimales x) es la lista de los caminos en de menor longitud en el árbol de los predecesores y mayores divisores del número x. Por ejemplo,
     λ> caminosMinimales 6
     [[6,3,2,1]]
     λ> caminosMinimales 17
     [[17,16,4,2,1]]
     λ> caminosMinimales 50
     [[50,25,5,4,2,1],[50,10,9,3,2,1],[50,10,5,4,2,1]]

Soluciones

import Data.Tree
 
mayoresDivisores :: Int -> [Int]
mayoresDivisores x =
  [max u v | u <- [2..floor (sqrt (fromIntegral x))]
           , x `mod` u == 0
           , let v = x `div` u]  
 
arbol :: Int -> Tree Int
arbol 1 = Node 1 []
arbol x = Node x (arbol (x-1) : [arbol y | y <- mayoresDivisores x])
 
caminos :: Int -> [[Int]]
caminos = caminosArbol . arbol
 
--    λ> caminosArbol (arbol 6)
--    [[6,5,4,3,2,1],[6,5,4,2,1],[6,3,2,1]]
caminosArbol :: Tree a -> [[a]]
caminosArbol (Node x []) = [[x]]
caminosArbol (Node x as) = [x:ys | ys <- caminosBosque as]
 
caminosBosque :: Forest a -> [[a]]
caminosBosque = concatMap caminosArbol
 
caminosMinimales :: Int -> [[Int]]
caminosMinimales x = [ys | ys <- yss, length ys == m]
  where yss = caminos x
        m   = minimum (map length yss)

Sumas de dos cuadrados

Definir la función

   sumasDe2Cuadrados :: Integer -> [(Integer, Integer)]

tal que (sumasDe2Cuadrados n) es la lista de los pares de números tales que la suma de sus cuadrados es n y el primer elemento del par es mayor o igual que el segundo. Por ejemplo,

   sumasDe2Cuadrados 25                ==  [(5,0),(4,3)]
   sumasDe2Cuadrados 32                ==  [(4,4)]
   sumasDe2Cuadrados 55                ==  []
   sumasDe2Cuadrados 850               ==  [(29,3),(27,11),(25,15)]
   length (sumasDe2Cuadrados (10^12))  ==  7

Soluciones

-- 1ª definición
sumasDe2Cuadrados1 :: Integer -> [(Integer, Integer)]
sumasDe2Cuadrados1 n = 
  [(x,y) | x <- [n,n-1..0]
         , y <- [0..x]
         , x*x+y*y == n]
 
-- 2ª definición:
sumasDe2Cuadrados2 :: Integer -> [(Integer, Integer)]
sumasDe2Cuadrados2 n = 
  [(x,y) | x <- [a,a-1..0]
         , y <- [0..x]
         , x*x+y*y == n]
  where a = (floor . sqrt . fromIntegral) n
 
-- 3ª definición
sumasDe2Cuadrados3 :: Integer -> [(Integer, Integer)]
sumasDe2Cuadrados3 n =
  [(raizEntera x, raizEntera y)
  | y <- takeWhile (<= n `div` 2) cuadrados
  , let x = n - y
  , esCuadrado x]
 
cuadrados :: [Integer]
cuadrados = map (^2) [0..]
 
esCuadrado :: Integer -> Bool
esCuadrado x =
  x == y * y
  where y = raizEntera x
 
raizEntera :: Integer -> Integer
raizEntera x =
  (floor . sqrt . fromIntegral) x
 
-- 4ª definición
sumasDe2Cuadrados4 :: Integer -> [(Integer, Integer)]
sumasDe2Cuadrados4 n = aux ((floor . sqrt . fromIntegral) n) 0 
  where aux x y | x < y          = [] 
                | x*x + y*y <  n = aux x (y+1)
                | x*x + y*y == n = (x,y) : aux (x-1) (y+1)
                | otherwise      = aux (x-1) y
 
-- Comparación de eficiencia
--    λ> sumasDe2Cuadrados1 2020
--    [(42,16),(38,24)]
--    (4.29 secs, 621,601,336 bytes)
--    λ> sumasDe2Cuadrados2 2020
--    [(42,16),(38,24)]
--    (0.01 secs, 488,496 bytes)
--    λ> sumasDe2Cuadrados3 2020
--    [(42,16),(38,24)]
--    (0.02 secs, 197,256 bytes)
--    λ> sumasDe2Cuadrados4 2020
--    [(42,16),(38,24)]
--    (0.01 secs, 175,088 bytes)
--
--    λ> length (sumasDe2Cuadrados2 48612265)
--    32
--    (51.25 secs, 7,395,035,904 bytes)
--    λ> length (sumasDe2Cuadrados3 48612265)
--    32
--    (0.06 secs, 8,368,296 bytes)
--    λ> length (sumasDe2Cuadrados4 48612265)
--    32
--    (0.04 secs, 3,483,168 bytes)
--    
--    λ> length (sumasDe2Cuadrados3 (10^12))
--    7
--    (7.32 secs, 1,137,167,688 bytes)
--    λ> length (sumasDe2Cuadrados4 (10^12))
--    7
--    (3.64 secs, 480,776,736 bytes)
[/schedule]

Números oblongos

Un número oblongo es un número que es el producto de dos números naturales consecutivos; es decir, n es un número oblongo si existe un número natural x tal que n = x(x+1). Por ejemplo, 42 es un número oblongo porque 42 = 6 x 7.

Definir las funciones

   esOblongo :: Integer -> Bool
   oblongos  :: [Integer]

tales que

  • (esOblongo n) se verifica si n es oblongo. Por ejemplo,
     esOblongo 42               ==  True
     esOblongo 40               ==  False
     esOblongo 100000010000000  ==  True
  • oblongos es la suceción de los números oblongos. Por ejemplo,
     take 15 oblongos   == [0,2,6,12,20,30,42,56,72,90,110,132,156,182,210]
     oblongos !! 50     == 2550
     oblongos !! (10^7) == 100000010000000

Soluciones

-- 1ª definición de esOblongo
esOblongo1 :: Integer -> Bool
esOblongo1 n =
  n == x * (x+1)
  where x = round (sqrt (fromIntegral n))
 
-- 2ª definición de esOblongo
esOblongo2 :: Integer -> Bool
esOblongo2 n =
  n `pertenece` oblongos3
 
pertenece :: Integer -> [Integer] -> Bool
pertenece x ys =
  x == head (dropWhile (< x) ys)
 
-- 1ª definición de oblongos
oblongos1 :: [Integer]
oblongos1 = [n | n <- [0..]
               , esOblongo1 n]
 
-- 2ª definición de oblongos
oblongos2 :: [Integer]
oblongos2 = filter esOblongo1 [0..]
 
-- 3ª definición de oblongos
oblongos3 :: [Integer]
oblongos3 = zipWith (*) [0..] [1..]

Números completos

Las descomposiciones de un número n son las parejas de números (x,y) tales que x >= y y la suma de las cuatro operaciones básicas (suma, producto, resta (el mayor menos el menor) y cociente (el mayor entre el menor)) es el número n. Por ejemplo, (8,2) es una descomposición de 36 ya que

   (8 + 2) + (8 - 2) + (8 * 2) + (8 / 2) = 36

Un número es completo si tiene alguna descomposición como las anteriores. Por ejemplo, el 36 es completo pero el 21 no lo es.

Definir las siguientes funciones

   descomposiciones :: Integer -> [(Integer,Integer)]
   completos        :: [Integer]

tales que

  • (descomposiciones n) es la lista de las descomposiones de n. Por ejemplo,
     descomposiciones 12   ==  [(3,1)]
     descomposiciones 16   ==  [(3,3),(4,1)]
     descomposiciones 36   ==  [(5,5),(8,2),(9,1)]
     descomposiciones 288  ==  [(22,11),(40,5),(54,3),(64,2),(72,1)]
     descomposiciones 21   ==  []
  • completos es la lista de los números completos. Por ejemplo,
     take 15 completos  ==  [4,8,9,12,16,18,20,24,25,27,28,32,36,40,44]
     completos !! 100   ==  261

Soluciones

-- 1ª solución de descomposiciones
descomposiciones1 :: Integer -> [(Integer,Integer)]
descomposiciones1 n =
  [(x,y) | x <- [1..n]
         , y <- [1..x]
         , x `rem` y == 0
         , (x + y) + (x - y) + (x * y) + (x `div` y) == n]
 
-- 2ª solución de descomposiciones
descomposiciones2 :: Integer -> [(Integer,Integer)]
descomposiciones2 n =
  [(n `div` ((y+1)^2) * y,y)
  | y <- [1..(floor . sqrt . fromIntegral) n]
  , n `mod` ((y+1)^2) == 0]
 
-- Comparación de eficiencia
--    λ> length (descomposiciones1 4000)
--    5
--    (3.16 secs, 1,618,693,272 bytes)
--    λ> length (descomposiciones2 4000)
--    5
--    (0.00 secs, 188,208 bytes)
 
-- Usaremos la 2ª definició de descomposiciones
descomposiciones :: Integer -> [(Integer,Integer)]
descomposiciones = descomposiciones2
 
-- 1ª definición de completos
completos1 :: [Integer]
completos1 = [n | n <- [1..]
                , not (null (descomposiciones n))]
 
-- 2ª definición de completos
completos2 :: [Integer]
completos2 = filter (not . null . descomposiciones) [1..]
 
-- Usaremos la 2ª definición de completos
completos :: [Integer]
completos = completos2