Menu Close

Etiqueta: sqrt

Distancia esperada entre dos puntos de un cuadrado unitario

José A. Alonso---1 Comentario

Definir, por simulación, la función

   distanciaEsperada :: Int -> IO Double

tal que (distanciaEsperada n) es la distancia esperada entre n puntos del cuadrado unitario de vértices opuestos (0,0) y (1,1), elegidos aleatoriamente. Por ejemplo,

   distanciaEsperada 10     ==  0.43903617921423593
   distanciaEsperada 10     ==  0.6342350621260004
   distanciaEsperada 100    ==  0.5180418995364429
   distanciaEsperada 100    ==  0.5288261085653962
   distanciaEsperada 1000   ==  0.5143804432569616
   distanciaEsperada 10000  ==  0.5208360147922616

El valor exacto de la distancia esperada es

   ve = (sqrt(2) + 2 + 5*log(1+sqrt(2)))/15 = 0.5214054331647207

Definir la función

   graficaDistanciaEsperada :: [Int] -> IO ()

tal que (graficaDistanciaEsperadan n) dibuja las gráficas de los pares (n, distanciaEsperada n) para n en la lista creciente ns junto con la recta y = ve, donde ve es el valor exacto. Por ejemplo, (graficaDistanciaEsperada [10,30..4000]) dibuja

Soluciones

import Data.List     (genericLength)
import System.Random (newStdGen, randomRIO, randomRs)
import Control.Monad (replicateM)
import Graphics.Gnuplot.Simple
 
-- 1ª solución
-- ===========
 
-- Un punto es un par de números reales.
type Punto = (Double, Double)
 
-- (puntosDelCuadrado n) es una lista de n puntos del cuadrado
-- unitario de vértices opuestos (0,0) y (1,1). Por ejemplo, 
--    λ> puntosDelCuadrado 3
--    [(0.6067427807212623,0.24785843546479303),
--     (0.9579158098726746,8.047408846191773e-2),
--     (0.856758357789639,0.9814972717003113)]
--    λ> puntosDelCuadrado 3
--    [(1.9785720974027532e-2,0.6343219201012211),
--     (0.21903717179861604,0.20947986189590784),
--     (0.4739903340716357,1.2262474491489095e-2)]
puntosDelCuadrado :: Int -> IO [Punto]
puntosDelCuadrado n = do
  gen <- newStdGen
  let xs = randomRs (0,1) gen
      (as, ys) = splitAt n xs
      (bs, _)  = splitAt n ys
  return (zip as bs)
 
-- (distancia p1 p2) es la distancia entre los puntos p1 y p2. Por
-- ejemplo,
--    distancia (0,0) (3,4)  ==  5.0
distancia :: Punto -> Punto -> Double
distancia (x1,y1) (x2,y2) = sqrt ((x1-x2)^2+(y1-y2)^2)
 
-- (distancias ps) es la lista de las distancias entre los elementos 1º
-- y 2º, 3º y 4º, ... de ps. Por ejemplo,
--    distancias [(0,0),(3,4),(1,1),(7,9)]  ==  [5.0,10.0]
distancias :: [Punto] -> [Double]
distancias []         = []
distancias (p1:p2:ps) = distancia p1 p2 : distancias ps
 
-- (media xs) es la media aritmética de los elementos de xs. Por ejemplo,
--    media [1,7,1]  ==  3.0
media :: [Double] -> Double
media xs =
  sum xs / genericLength xs
 
-- (distanciaEsperada n) es la distancia esperada entre n puntos
-- aleatorios en el cuadrado unitario. Por ejemplo,
distanciaEsperada :: Int -> IO Double
distanciaEsperada n = do
  ps <- puntosDelCuadrado (2*n)
  return (media (distancias ps))
 
-- 2ª solución
-- ===========
 
distanciaEsperada2 :: Int -> IO Double
distanciaEsperada2 n = do
  ps <- puntosDelCuadrado2 (2*n)
  return (media (distancias ps))
 
-- (puntosDelCuadrado2 n) es una lista de n puntos del cuadrado
-- unitario de vértices opuestos (0,0) y (1,1). Por ejemplo, 
--    λ> puntosDelCuadrado2 3
--    [(0.9836699352638695,0.5143414844876929),
--     (0.8715237339877027,0.9905157772823782),
--     (0.29502946161912935,0.16889248111565192)]
--    λ> puntosDelCuadrado2 3
--    [(0.20405570457106392,0.47574116941605116),
--     (0.7128182811364226,3.201419787777959e-2),
--     (0.5576891231675457,0.9994474730919443)]
puntosDelCuadrado2 :: Int -> IO [Punto]
puntosDelCuadrado2 n =
  replicateM n puntoDelCuadrado2
 
-- (puntoDelCuadrado2 n) es un punto del cuadrado unitario de vértices
-- opuestos (0,0) y (1,1). Por ejemplo,  
--    λ> puntoDelCuadrado2
--    (0.7512991739803923,0.966436016138578)
--    λ> puntoDelCuadrado2
--    (0.7306826194847795,0.8984574498515252)
puntoDelCuadrado2 :: IO Punto
puntoDelCuadrado2 = do
  x <- randomRIO (0, 1.0)
  y <- randomRIO (0, 1.0)
  return (x, y)
 
-- 3ª solución
-- ===========
 
distanciaEsperada3 :: Int -> IO Double
distanciaEsperada3 n = do
  ds <- distanciasAleatorias n
  return (media ds)
 
-- (distanciasAleatorias n) es la lista de las distancias aleatorias
-- entre n pares de puntos del cuadrado unitario. Por ejemplo, 
--    λ> distanciasAleatorias 3
--    [0.8325589110989705,0.6803336613847881,0.1690051224111662]
--    λ> distanciasAleatorias 3
--    [0.3470124940889039,0.459002678562019,0.7665623634969365]
distanciasAleatorias :: Int -> IO [Double]
distanciasAleatorias n = 
  replicateM n distanciaAleatoria
 
-- distanciaAleatoria es la distancia de un par de punto del cuadrado
-- unitario elegidos aleatoriamente. Por ejemplo,
--    λ> distanciaAleatoria
--    0.8982361685460913
--    λ> distanciaAleatoria
--    0.9777207485571939
--    λ> distanciaAleatoria
--    0.6042223512347842
distanciaAleatoria :: IO Double
distanciaAleatoria = do 
  p1 <- puntoDelCuadrado2
  p2 <- puntoDelCuadrado2
  return (distancia p1 p2)
 
-- 4ª solución
-- ===========
 
distanciaEsperada4 :: Int -> IO Double
distanciaEsperada4 n =
  media <$> distanciasAleatorias n
 
-- Gráfica
-- =======
 
graficaDistanciaEsperada :: [Int] -> IO ()
graficaDistanciaEsperada ns = do
  ys <- mapM distanciaEsperada ns
  let e = (sqrt(2) + 2 + 5*log(1+sqrt(2)))/15
  plotLists [ Key Nothing
            -- , PNG "Distancia_esperada_entre_dos_puntos.png"
            ]
            [ zip ns ys
            , zip ns (repeat e)]

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

“El matemático no estudia las matemáticas puras porque sean útiles; las estudia porque se deleita en ellas y se deleita en ellas porque son hermosas.”

Henri Poincaré.

Seguir leyendo →

La menos conocida de las conjeturas de Goldbach

José A. Alonso---3 Comentarios

Goldbach, el de la famosa conjetura, hizo por lo menos otra conjetura que finalmente resultó ser falsa.

Esta última decía que todo número compuesto impar puede expresarse como la suma de un número primo más dos veces la suma de un cuadrado. Así por ejemplo,

    9 =  7 + 2×1^2
   15 =  7 + 2×2^2
   21 =  3 + 2×3^2
   25 =  7 + 2×3^2
   27 = 19 + 2×2^2
   33 = 31 + 2×1^2

Definir las sucesiones

   imparesCompuestos :: [Integer]
   descomposiciones :: Integer -> [(Integer,Integer)]
   contraejemplosGoldbach :: [Integer]

tales que

  • imparesCompuestos es la lista de los números impares compuestos. Por ejemplo,
     take 9 imparesCompuestos  ==  [9,15,21,25,27,33,35,39,45]
  • (descomposiciones n) es la lista de las descomposiciones de n de n como la suma de un número primo más dos veces la suma de un cuadrado. Por ejemplo, 
     descomposiciones 9     ==  [(7,1)]
     descomposiciones 21    ==  [(3,9),(13,4),(19,1)]
     descomposiciones 5777  ==  []

Las 3 descomposiciones de 21 son

     21 =  3 + 2*9 = 21 + 2*3^2
     21 = 13 + 2*4 = 13 + 2*3^2
     21 = 19 + 2*1 = 19 + 2*1^2
  • contraejemplosGoldbach es la lista de los contraejemplos de la anterior conjetura de Goldbach; es decir, los números impares compuestos que no pueden expresarse como la suma de un número primo más dos veces la suma de un cuadrado. Por ejemplo,
   take 2 contraejemplosGoldbach  ==  [5777,5993]

Comprobar con QuickCheck que la conjetura de Golbach se verifica a partir de 5993; es decir, todo número compuesto impar mayor que 5993 puede expresarse como la suma de un número primo más dos veces la suma de un cuadrado.

Nota: Basado en el artículo La menos conocida de las conjeturas de Goldbach de Claudio Meller en el blog Números y algo más.

Soluciones

import Data.Numbers.Primes
import Test.QuickCheck
 
imparesCompuestos :: [Integer]
imparesCompuestos = filter esCompuesto [3,5..]
 
-- (esCompuesto x) se verifica si x es un número compuesto. Por ejemplo,
--    esCompuesto 6  ==  True
--    esCompuesto 7  ==  False
esCompuesto :: Integer -> Bool
esCompuesto = not . isPrime
 
contraejemplosGoldbach :: [Integer]
contraejemplosGoldbach = filter esContraejemplo imparesCompuestos
 
-- (esContraejemplo x) es verifica si el número impar compuesto x es un
-- contraejemplo de la conjetura de Goldbach. Por ejemplo,
--    esContraejemplo 5777  ==  True
--    esContraejemplo 15    ==  False
esContraejemplo :: Integer -> Bool
esContraejemplo = null . descomposiciones
 
descomposiciones :: Integer -> [(Integer,Integer)]
descomposiciones n =
  [(p,x) | p <- takeWhile (<=n) primes
         , (n - p) `mod` 2 == 0
         , let x = (n - p) `div` 2
         , esCuadrado x]
 
-- (esCuadrado x) es verifica si x es un cuadrado perfecto. Por ejemplo, 
--    esCuadrado 16  ==  True
--    esCuadrado 27  ==  False
esCuadrado :: Integer -> Bool
esCuadrado x = y^2 == x
  where y = ceiling (sqrt (fromIntegral x))
 
-- La propiedad es
prop_conjetura :: Int -> Property
prop_conjetura n =
  n >= 0 ==> not (esContraejemplo (imparesCompuestosMayore5993 !! n))
  where imparesCompuestosMayore5993 = dropWhile (<=5993) imparesCompuestos
 
-- La comprobación es
--    λ> quickCheck prop_conjetura
--    +++ 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

“Obvio es la palabra más peligrosa de las matemáticas.”

Eric Temple Bell

Seguir leyendo →

La conjetura de Mertens

José A. Alonso---3 Comentarios

Un número entero n es libre de cuadrados si no existe un número primo p tal que p² divide a n; es decir, los factores primos de n son todos distintos.

La función de Möbius μ(n) está definida para todos los enteros positivos como sigue:

  • μ(n) = 1 si n es libre de cuadrados y tiene un número par de factores primos.
  • μ(n) = -1 si n es libre de cuadrados y tiene un número impar de factores primos.
  • μ(n) = 0 si n no es libre de cuadrados.

Sus primeros valores son 1, -1, -1, 0, -1, 1, -1, 0, 0, 1, …

La función de Mertens M(n) está definida para todos los enteros positivos como la suma de μ(k) para 1 ≤ k ≤ n. Sus primeros valores son 1, 0, -1, -1, -2, -1, -2, -2, …

La conjetura de Mertens afirma que

Para todo entero x mayor que 1, el valor absoluto de la función de Mertens en x es menor que la raíz cuadrada de x.

La conjetura fue planteada por Franz Mertens en 1897. Riele Odlyzko, demostraronen 1985 que la conjetura de Mertens deja de ser cierta más o menos a partir de 10^{10^{64}}, cifra que luego de algunos refinamientos se redujo a 10^{10^{40}}.

Definir las funciones

   mobius :: Integer -> Integer
   mertens :: Integer -> Integer
   graficaMertens :: Integer -> IO ()

tales que

  • (mobius n) es el valor de la función de Möbius en n. Por ejemplo,
     mobius 6   ==  1
     mobius 30  ==  -1
     mobius 12  ==  0
  • (mertens n) es el valor de la función de Mertens en n. Por ejemplo,
     mertens 1     ==  1
     mertens 2     ==  0
     mertens 3     ==  -1
     mertens 5     ==  -2
     mertens 661   ==  -11
     mertens 1403  ==  11
  • (graficaMertens n) dibuja la gráfica de la función de Mertens, la raíz cuadrada y el opuestos de la raíz cuadrada para los n primeros n enteros positivos. Por ejemplo, (graficaMertens 1000) dibuja

Comprobar con QuickCheck la conjetura de Mertens.

Nota: El ejercicio está basado en La conjetura de Merterns y su relación con un número tan raro como extremada y colosalmente grande publicado por @Alvy la semana pasada en Microsiervos.

Soluciones

import Data.Numbers.Primes (primeFactors)
import Test.QuickCheck
import Graphics.Gnuplot.Simple
 
mobius :: Integer -> Integer
mobius n | tieneRepetidos xs = 0
         | otherwise         = (-1)^(length xs)
  where xs = primeFactors n
 
tieneRepetidos :: [Integer] -> Bool
tieneRepetidos xs =
  or [x == y | (x,y) <- zip xs (tail xs)]
 
mertens :: Integer -> Integer
mertens n = sum (map mobius [1..n])
 
-- Definición de graficaMertens
-- ============================
 
graficaMertens :: Integer -> IO ()
graficaMertens n = do
  plotLists [ Key Nothing
            , Title "Conjetura de Mertens"
            , PNG "La_conjetura_de_Mertens.png"
            ]
            [ [mertens k | k <- [1..n]]
            , raices
            , map negate raices
            ]
 
  where
    raices = [ceiling (sqrt k) | k <- [1..fromIntegral n]]
 
-- Conjetura de Mertens
-- ====================
 
-- La conjetura es
conjeturaDeMertens :: Integer -> Property
conjeturaDeMertens n =
  n > 1
  ==>
  abs (mertens n) < ceiling (sqrt n')
  where n' = fromIntegral n
 
-- La comprobación es
--    λ> quickCheck conjeturaDeMertens
--    +++ 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

“El control de la complejidad es la esencia de la programación informática.”

Brian Kernighan.

Seguir leyendo →

Productos de sumas de cuatro cuadrados

José A. Alonso---2 Comentarios

Definir la función

   productoSuma4Cuadrados :: Integral a => [a] -> [a] -> [a] -> [a] -> a

tal que (productoSuma4Cuadrados as bs cs ds) es el producto de las sumas de los cuadrados de cada una de las listas que ocupan la misma posición (hasta que alguna se acaba). Por ejemplo,

   productoSuma4Cuadrados [2,3] [1,5] [4,6] [0,3,9]
   = (2² + 1² + 4² + 0²) * (3² + 5² + 6² + 3²)
   = (4 +  1 + 16  + 0)  * (9 + 25 + 36  + 9)
   = 1659

Comprobar con QuickCheckWith que si as, bs cs y ds son listas no vacías de enteros positivos, entonces (productoSuma4Cuadrados as bs cs ds) se puede escribir como la suma de los cuadrados de cuatro enteros positivos.

Soluciones

import Data.List (zip4)
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
productoSuma4Cuadrados :: Integral a => [a] -> [a] -> [a] -> [a] -> a
productoSuma4Cuadrados (a:as) (b:bs) (c:cs) (d:ds) =
  (a^2+b^2+c^2+d^2) * productoSuma4Cuadrados as bs cs ds
productoSuma4Cuadrados _ _ _ _ = 1
 
-- 2ª solución
-- ===========
 
productoSuma4Cuadrados2 :: Integral a => [a] -> [a] -> [a] -> [a] -> a
productoSuma4Cuadrados2 as bs cs ds =
  product [a^2 + b^2 + c^2 + d^2 | (a,b,c,d) <- zip4 as bs cs ds]
 
-- Propiedad
-- =========
 
-- La propiedad es
prop_productoSuma4Cuadrados ::
  [Integer] -> [Integer] -> [Integer] -> [Integer] -> Property
prop_productoSuma4Cuadrados as bs cs ds =
  all (not . null) [as, bs, cs, ds]
  ==> 
  esSuma4Cuadrados (productoSuma4Cuadrados as' bs' cs' ds')
  where as' = [1 + abs a | a <- as]
        bs' = [1 + abs b | b <- bs]
        cs' = [1 + abs c | c <- cs]
        ds' = [1 + abs d | d <- ds]
 
-- (esSuma4Cuadrados n) se verifica si n es la suma de 4 cuadrados. Por
-- ejemplo, 
--    esSuma4Cuadrados 42  ==  True
--    esSuma4Cuadrados 11  ==  False
--    esSuma4Cuadrados 41  ==  False
esSuma4Cuadrados :: Integer -> Bool
esSuma4Cuadrados = not . null . sumas4Cuadrados
 
-- (sumas4Cuadrados n) es la lista de las descomposiciones de n como
-- sumas de 4 cuadrados. Por ejemplo,
--    sumas4Cuadrados 42  ==  [(16,16,9,1),(25,9,4,4),(36,4,1,1)]
sumas4Cuadrados :: Integer -> [(Integer,Integer,Integer,Integer)]
sumas4Cuadrados n =
  [(a^2,b^2,c^2,d) | a <- [1 .. floor (sqrt (fromIntegral n / 4))]
                   , b <- [a .. floor (sqrt (fromIntegral (n-a^2) / 3))]
                   , c <- [b .. floor (sqrt (fromIntegral (n-a^2-b^2) / 2))]
                   , let d = n - a^2 - b^2 - c^2
                   , c^2 <= d 
                   , esCuadrado d]
 
-- (esCuadrado x) se verifica si x es un número al cuadrado. Por
-- ejemplo,
--    esCuadrado 25  ==  True
--    esCuadrado 26  ==  False
esCuadrado :: Integer -> Bool
esCuadrado x = x == y * y
  where y = raiz x
 
-- (raiz x) es la raíz cuadrada entera de x. Por ejemplo,
--    raiz 25  ==  5
--    raiz 24  ==  4
--    raiz 26  ==  5
raiz :: Integer -> Integer
raiz x = floor (sqrt (fromIntegral x))
 
-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=5}) prop_productoSuma4Cuadrados
--    +++ 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

¿Vivir? Sencillamente:
la sed y el agua cerca …
o el agua lejos, más, la sed y el agua,
un poco de cansancio ¡y a beberla!.

Antonio Machado

Seguir leyendo →

Sumas de cuatro cuadrados

José A. Alonso---1 Comentario

El número 42 es una suma de cuatro cuadrados de números enteros positivos ya que

   42 = 16 + 16 + 9 + 1 = 4² + 4² + 3² + 1²

Definir las funciones

   sumas4Cuadrados :: Integer -> [(Integer,Integer,Integer,Integer)]
   graficaNumeroSumas4Cuadrados :: Integer -> IO ()

tales que

  • (sumas4Cuadrados n) es la lista de las descompociones de n como suma de cuatro cuadrados. Por ejemplo,
     sumas4Cuadrados 42  ==  [(16,16,9,1),(25,9,4,4),(36,4,1,1)]
     sumas4Cuadrados 14  ==  []
     length (sumas4Cuadrados (5*10^4))  ==  260
  • (graficaNumeroSumas4Cuadrados n) dibuja la gráfica del número de descomposiciones en sumas de 4 cuadrados de los n primeros. Por ejemplo, (graficaNumeroSumas4Cuadrados 600) dibuja

Soluciones

Pensamiento

import Graphics.Gnuplot.Simple
 
-- 1ª definición de sumas4Cuadrados
-- ================================
 
sumas4Cuadrados :: Integer -> [(Integer,Integer,Integer,Integer)]
sumas4Cuadrados n =
  [(a^2,b^2,c^2,d) | a <- [1..n]
                   , b <- [a..n]
                   , c <- [b..n]
                   , let d = n - a^2 - b^2 - c^2
                   , c^2 <= d 
                   , esCuadrado d]
 
-- (esCuadrado x) se verifica si x es un número al cuadrado. Por
-- ejemplo,
--    esCuadrado 25  ==  True
--    esCuadrado 26  ==  False
esCuadrado :: Integer -> Bool
esCuadrado x = x == y * y
  where y = raiz x
 
-- (raiz x) es la raíz cuadrada entera de x. Por ejemplo,
--    raiz 25  ==  5
--    raiz 24  ==  4
--    raiz 26  ==  5
raiz :: Integer -> Integer
raiz x = floor (sqrt (fromIntegral x))
 
-- 2ª definición de sumas4Cuadrados
-- ================================
 
-- Los intervalos de búqueda en la definición anterior se pueden reducir
-- teniendo en cuenta las siguientes restricciones
--    1 <= a <= b <= c <= d 
--    n = a² + b² + c² + d² >= 4a² ==> a <= sqrt (n/4)
--    n - a² = b² + c² + d² >= 3b² ==> b <= sqrt ((n-a²)/3)
--    n - a² - b² = c² + d² >= 2c² ==> c <= sqrt ((n-a²-b²)/2)
 
sumas4Cuadrados2 :: Integer -> [(Integer,Integer,Integer,Integer)]
sumas4Cuadrados2 n =
  [(a^2,b^2,c^2,d) | a <- [1 .. floor (sqrt (fromIntegral n / 4))]
                   , b <- [a .. floor (sqrt (fromIntegral (n-a^2) / 3))]
                   , c <- [b .. floor (sqrt (fromIntegral (n-a^2-b^2) / 2))]
                   , let d = n - a^2 - b^2 - c^2
                   , c^2 <= d 
                   , esCuadrado d]
 
-- Comparación de eficiencia
-- =========================
 
-- La comprobación es
--    λ> length (sumas4Cuadrados 300)
--    11
--    (7.93 secs, 11,280,814,312 bytes)
--    λ> length (sumas4Cuadrados2 300)
--    11
--    (0.01 secs, 901,520 bytes)
 
-- Definición de graficaConvergencia
-- ==================================
 
graficaNumeroSumas4Cuadrados :: Integer -> IO ()
graficaNumeroSumas4Cuadrados n =
  plotList [ Key Nothing
           , Title "Numero de sumas como 4 cuadrados"
           , PNG "Sumas_de_cuatro_cuadrados.png"
           ]
           [length (sumas4Cuadrados2 k) | k <- [0..n]] 
 
-- Definición de esSuma4Cuadrados
-- ==============================
 
-- (esSuma4Cuadrados n) se verifica si n es la suma de 4 cuadrados. Por
-- ejemplo, 
--    esSuma4Cuadrados 42  ==  True
--    esSuma4Cuadrados 11  ==  False
--    esSuma4Cuadrados 41  ==  False
esSuma4Cuadrados :: Integer -> Bool
esSuma4Cuadrados = not . null . sumas4Cuadrados2

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>

¿Cuál es el peor de todos
los afanes? Preguntar.
¿Y el mejor? – Hacer camino
sin volver la vista atrás.

Antonio Machado

Seguir leyendo →

El teorema de Navidad de Fermat

José A. Alonso---2 Comentarios

El 25 de diciembre de 1640, en una carta a Mersenne, Fermat demostró la conjetura de Girard: todo primo de la forma 4n+1 puede expresarse de manera única como suma de dos cuadrados. Por eso es conocido como el Teorema de Navidad de Fermat.

Definir las funciones

   representaciones :: Integer -> [(Integer,Integer)]
   primosImparesConRepresentacionUnica :: [Integer]
   primos4nM1 :: [Integer]

tales que

  • (representaciones n) es la lista de pares de números naturales (x,y) tales que n = x^2 + y^2 con x <= y. Por ejemplo,
     representaciones  20           ==  [(2,4)]
     representaciones  25           ==  [(0,5),(3,4)]
     representaciones 325           ==  [(1,18),(6,17),(10,15)]
     representaciones 100000147984  ==  [(0,316228)]
     length (representaciones (10^10))    ==  6
     length (representaciones (4*10^12))  ==  7
  • primosImparesConRepresentacionUnica es la lista de los números primos impares que se pueden escribir exactamente de una manera como suma de cuadrados de pares de números naturales (x,y) con x <= y. Por ejemplo,
     λ> take 20 primosImparesConRepresentacionUnica
     [5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193]
  • primos4nM1 es la lista de los números primos que se pueden escribir como uno más un múltiplo de 4 (es decir, que son congruentes con 1 módulo 4). Por ejemplo,
     λ> take 20 primos4nM1
     [5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193]

El teorema de Navidad de Fermat afirma que un número primo impar p se puede escribir exactamente de una manera como suma de dos cuadrados de números naturales p = x² + y^2 (con x <= y) si, y sólo si, p se puede escribir como uno más un múltiplo de 4 (es decir, que es congruente con 1 módulo 4).

Comprobar con QuickCheck el teorema de Navidad de Fermat; es decir, que para todo número n, los n-ésimos elementos de primosImparesConRepresentacionUnica y de primos4nM1 son iguales.

Soluciones

import Data.Numbers.Primes (primes)
import Test.QuickCheck
 
-- 1ª definición de representaciones
-- =================================
 
representaciones :: Integer -> [(Integer,Integer)]
representaciones n =
  [(x,y) | x <- [0..n], y <- [x..n], n == x*x + y*y]
 
-- 2ª definición de representaciones
-- =================================
 
representaciones2 :: Integer -> [(Integer,Integer)]
representaciones2 n =
  [(x,raiz z) | x <- [0..raiz (n `div` 2)] 
              , let z = n - x*x
              , esCuadrado z]
 
-- (esCuadrado x) se verifica si x es un número al cuadrado. Por
-- ejemplo,
--    esCuadrado 25  ==  True
--    esCuadrado 26  ==  False
esCuadrado :: Integer -> Bool
esCuadrado x = x == y * y
  where y = raiz x
 
-- (raiz x) es la raíz cuadrada entera de x. Por ejemplo,
--    raiz 25  ==  5
--    raiz 24  ==  4
--    raiz 26  ==  5
raiz :: Integer -> Integer 
raiz 0 = 0
raiz 1 = 1
raiz x = aux (0,x)
    where aux (a,b) | d == x    = c
                    | c == a    = a
                    | d < x     = aux (c,b)
                    | otherwise = aux (a,c) 
              where c = (a+b) `div` 2
                    d = c^2
 
-- 3ª definición de representaciones
-- =================================
 
representaciones3 :: Integer -> [(Integer,Integer)]
representaciones3 n =
  [(x,raiz3 z) | x <- [0..raiz3 (n `div` 2)] 
               , let z = n - x*x
               , esCuadrado3 z]
 
-- (esCuadrado x) se verifica si x es un número al cuadrado. Por
-- ejemplo,
--    esCuadrado3 25  ==  True
--    esCuadrado3 26  ==  False
esCuadrado3 :: Integer -> Bool
esCuadrado3 x = x == y * y
  where y = raiz3 x
 
-- (raiz3 x) es la raíz cuadrada entera de x. Por ejemplo,
--    raiz3 25  ==  5
--    raiz3 24  ==  4
--    raiz3 26  ==  5
raiz3 :: Integer -> Integer
raiz3 x = floor (sqrt (fromIntegral x))
 
-- 4ª definición de representaciones
-- =================================
 
representaciones4 :: Integer -> [(Integer, Integer)]
representaciones4 n = aux 0 (floor (sqrt (fromIntegral n)))
  where aux x y
          | x > y     = [] 
          | otherwise = case compare (x*x + y*y) n of
                          LT -> aux (x + 1) y
                          EQ -> (x, y) : aux (x + 1) (y - 1)
                          GT -> aux x (y - 1)
 
-- Equivalencia de las definiciones de representaciones
-- ====================================================
 
-- La propiedad es
prop_representaciones_equiv :: (Positive Integer) -> Bool
prop_representaciones_equiv (Positive n) =
  representaciones  n == representaciones2 n &&
  representaciones2 n == representaciones3 n &&
  representaciones3 n == representaciones4 n
 
-- La comprobación es
--    λ> quickCheck prop_representaciones_equiv
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia de las definiciones de representaciones
-- =================================================================
 
--    λ> representaciones 3025
--    [(0,55),(33,44)]
--    (2.86 secs, 1,393,133,528 bytes)
--    λ> representaciones2 3025
--    [(0,55),(33,44)]
--    (0.00 secs, 867,944 bytes)
--    λ> representaciones3 3025
--    [(0,55),(33,44)]
--    (0.00 secs, 173,512 bytes)
--    λ> representaciones4 3025
--    [(0,55),(33,44)]
--    (0.00 secs, 423,424 bytes)
--    
--    λ> length (representaciones2 (10^10))
--    6
--    (3.38 secs, 2,188,903,544 bytes)
--    λ> length (representaciones3 (10^10))
--    6
--    (0.10 secs, 62,349,048 bytes)
--    λ> length (representaciones4 (10^10))
--    6
--    (0.11 secs, 48,052,360 bytes)
--
--    λ> length (representaciones3 (4*10^12))
--    7
--    (1.85 secs, 1,222,007,176 bytes)
--    λ> length (representaciones4 (4*10^12))
--    7
--    (1.79 secs, 953,497,480 bytes)
 
-- Definición de primosImparesConRepresentacionUnica
-- =================================================
 
primosImparesConRepresentacionUnica :: [Integer]
primosImparesConRepresentacionUnica =
  [x | x <- tail primes
     , length (representaciones4 x) == 1]
 
-- Definición de primos4nM1
-- ========================
 
primos4nM1 :: [Integer]
primos4nM1 = [x | x <- primes
                , x `mod` 4 == 1]
 
-- Teorema de Navidad de Fermat
-- ============================
 
-- La propiedad es
prop_teoremaDeNavidadDeFermat :: Positive Int -> Bool
prop_teoremaDeNavidadDeFermat (Positive n) =
  primosImparesConRepresentacionUnica !! n == primos4nM1 !! n
 
-- La comprobación es
--    λ> quickCheck prop_teoremaDeNavidadDeFermat
--    +++ OK, passed 100 tests.

Pensamiento

Dijo Dios: brote la nada
Y alzó su mano derecha,
hasta ocultar su mirada.
Y quedó la nada hecha.

Antonio Machado

Seguir leyendo →

Cálculo de pi usando la fórmula de Vieta

José A. Alonso---5 Comentarios

La fórmula de Vieta para el cálculo de pi es la siguiente
Calculo_de_pi_usando_la_formula_de_Vieta

Definir las funciones

   aproximacionPi :: Int -> Double
   errorPi :: Double -> Int

tales que

  • (aproximacionPi n) es la aproximación de pi usando n factores de la fórmula de Vieta. Por ejemplo, 
     aproximacionPi  5  ==  3.140331156954753
     aproximacionPi 10  ==  3.1415914215112
     aproximacionPi 15  ==  3.141592652386592
     aproximacionPi 20  ==  3.1415926535886207
     aproximacionPi 25  ==  3.141592653589795
  • (errorPi x) es el menor número de factores de la fórmula de Vieta necesarios para obtener pi con un error menor que x. Por ejemplo, 
     errorPi 0.1        ==  2
     errorPi 0.01       ==  4
     errorPi 0.001      ==  6
     errorPi 0.0001     ==  7
     errorPi 1e-4       ==  7
     errorPi 1e-14      ==  24
     pi                 ==  3.141592653589793
     aproximacionPi 24  ==  3.1415926535897913

Soluciones

-- 1ª definición de aproximacionPi
aproximacionPi :: Int -> Double
aproximacionPi n = product [2 / aux x | x <- [0..n]]
  where
    aux 0 = 1
    aux 1 = sqrt 2
    aux n = sqrt (2 + aux (n-1))
 
-- 2ª definición de aproximacionPi
aproximacionPi2 :: Int -> Double
aproximacionPi2 n = product [2/x | x <- 1 : xs] 
  where xs = take n $ iterate (\x -> sqrt (2+x)) (sqrt 2)
 
-- 3ª definición de aproximaxionPi
aproximacionPi3 :: Int -> Double
aproximacionPi3 n =  product (2 : take n (map (2/) xs))
  where xs = sqrt 2 : [sqrt (2 + x) | x <- xs]
 
-- 1ª definición de errorPi
errorPi :: Double -> Int
errorPi x = head [n | n <- [1..]
                    , abs (pi - aproximacionPi n) < x]
 
-- 2ª definición de errorPi
errorPi2 :: Double -> Int
errorPi2 x = until aceptable (+1) 1
  where aceptable n = abs (pi - aproximacionPi n) < x

Pensamiento

El tiempo que la barba me platea,
cavó mis ojos y agrandó mi frente,
va siendo en mi recuerdo transparente,
y mientras más al fondo, más clarea.

Antonio Machado

Seguir leyendo →

Suma de primos menores

José A. Alonso---4 Comentarios

La suma de los primos menores que 10 es 2 + 3 + 5 + 7 = 17.

Definir la función

   sumaPrimosMenores :: Integer -> Integer

tal que (sumaPrimosMenores n) es la suma de los primos menores que n. Por ejemplo,

   sumaPrimosMenores 10        ==  17
   sumaPrimosMenores (5*10^5)  ==  9914236195

Nota: Este ejercicio está basado en el problema 10 del Proyecto Euler

Soluciones

import Data.Numbers.Primes (primes)
 
-- 1ª solución
-- ===========
 
sumaPrimosMenores :: Integer -> Integer
sumaPrimosMenores n = sum (takeWhile (<n) primos)
 
-- primos es la lista de los números primos. Por ejemplo,
--    λ> take 12 primos
--    [2,3,5,7,11,13,17,19,23,29,31,37]
primos :: [Integer]
primos = 2 : filter esPrimo [3,5..]
 
esPrimo :: Integer -> Bool
esPrimo n = null [x | x <- [2..(ceiling . sqrt . fromIntegral) n]
                    , n `mod` x == 0]
 
-- 2ª solución
-- ===========
 
sumaPrimosMenores2 :: Integer -> Integer
sumaPrimosMenores2 n = sum (takeWhile (<n) primos2)
 
primos2 :: [Integer]
primos2 = 2 : filter esPrimo2 [3,5..]
 
esPrimo2 :: Integer -> Bool
esPrimo2 x =
  all ((/= 0) . mod x)
  (takeWhile (<= floor (sqrt (fromIntegral x))) primos2)
 
-- 3ª solución
-- ===========
 
sumaPrimosMenores3 :: Integer -> Integer
sumaPrimosMenores3 n = sum (takeWhile (<n) primes)
 
-- Comparación de eficiencia
-- =========================
 
--    λ> sumaPrimosMenores (2*10^5)
--    1709600813
--    (2.56 secs, 1,522,015,240 bytes)
--    λ> sumaPrimosMenores2 (2*10^5)
--    1709600813
--    (0.56 secs, 376,951,456 bytes)
--    λ> sumaPrimosMenores3 (2*10^5)
--    1709600813
--    (0.07 secs, 62,321,888 bytes)

Pensamiento

El movimiento no es nada esencial. La fuerza puede ser inmóvil (lo es en su estado de pureza); mas no por ello deja de ser activa.

Antonio Machado

Seguir leyendo →

Mayor divisor primo

José A. Alonso---6 Comentarios

Los divisores primos de 13195 son 5, 7, 13 y 29. Por tanto, el mayor divisor primo de 13195 es 29.

Definir la función

   mayorDivisorPrimo :: Integer -> Integer

tal que (mayorDivisorPrimo n) es el mayor divisor primo de n. Por ejemplo,

   mayorDivisorPrimo 13195            ==  29
   mayorDivisorPrimo 152416333181401  ==  12345701

Nota: Este ejercicio está basado en el problema 3 del Proyecto Euler

Soluciones

import Data.Numbers.Primes (primeFactors)
 
-- 1ª solución  (sin librerías auxiliares)
-- =======================================
 
mayorDivisorPrimo :: Integer -> Integer
mayorDivisorPrimo = last . divisoresPrimos 
 
-- (divisoresPrimos n) es la lista de los divisores primos de n. Por
-- ejemplo, 
--    divisoresPrimos 13195  ==  [5,7,13,29]
divisoresPrimos :: Integer -> [Integer]
divisoresPrimos 0 = []
divisoresPrimos 1 = []
divisoresPrimos n = m : divisoresPrimos (n `div` m)
  where m = menorDivisorPrimo n 
 
-- (menorDivisorPrimo n) es el menor divisor primo de n. Por ejemplo, 
--    menorDivisorPrimo 24  ==  2
--    menorDivisorPrimo 25  ==  5
--    menorDivisorPrimo 29  ==  29
menorDivisorPrimo :: Integer -> Integer
menorDivisorPrimo x =
  head [y | y <- 2 : [3,5..(ceiling . sqrt . fromIntegral) x] ++ [x]
          , x `mod` y == 0]
 
-- 2ª solución (con la librería Data.Numbers.Primes)
-- =================================================
 
mayorDivisorPrimo2 :: Integer -> Integer
mayorDivisorPrimo2 = last . primeFactors
 
-- Comparación de eficiencia
-- =========================
 
--   λ> mayorDivisorPrimo 152416333181401
--   12345701
--   (1.96 secs, 1,630,201,856 bytes)
--   λ> mayorDivisorPrimo2 152416333181401
--   12345701
--   (2.01 secs, 5,445,284,432 bytes)

Pensamiento

“Un programa de ordenador es una demostración.” ~ Igor Rivin

Seguir leyendo →

Caminos minimales en un árbol numérico

José A. Alonso---6 Comentarios

En la librería Data.Tree se definen los tipos de árboles y 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
import Test.QuickCheck
 
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)

Pensamiento

Tras el vivir y el soñar,
está lo que más importa:
despertar.

Antonio Machado

Seguir leyendo →