Menu Close

Número de sumandos en suma de cuadrados

El teorema de Lagrange de los cuatro cuadrados asegura que cualquier número entero positivo es la suma de, como máximo,cuatro cuadrados de números enteros. Por ejemplo,

   16 = 4²
   29 = 2² + 5²  
   14 = 1² + 2² + 3²
   15 = 1² + 1² + 2² + 3²

Definir las funciones

   ordenLagrange        :: Integer -> Int
   graficaOrdenLagrange :: Integer -> IO ()

tales que

  • (ordenLagrange n) es el menor número de cuadrados necesarios para escribir n como suma de cuadrados. Por ejemplo.
     ordenLagrange 16     ==  1
     ordenLagrange 29     ==  2
     ordenLagrange 14     ==  3
     ordenLagrange 15     ==  4
     ordenLagrange 10000  ==  1
     ordenLagrange 10001  ==  2
     ordenLagrange 10002  ==  3
     ordenLagrange 10007  ==  4
  • (graficaOrdenLagrange n) dibuja la gráfica de los órdenes de Lagrange de los n primeros números naturales. Por ejemplo, (graficaOrdenLagrange 100) dibuja

Comprobar con QuickCheck que. para todo entero positivo k, el orden de Lagrange de k es menos o igual que 4, el de 4k+3 es distinto de 2 y el de 8k+7 es distinto de 3.

Soluciones

import Data.Array (Array, (!), array)
import Graphics.Gnuplot.Simple
 
import Test.QuickCheck
 
-- 1ª definición
-- =============
 
ordenLagrange :: Integer -> Int
ordenLagrange n
  | esCuadrado n = 1
  | otherwise    = 1 + minimum [ ordenLagrange (n - x^2)
                               | x <- [1..raizEntera n]]
 
-- (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 = (raizEntera x)^2 == x
 
-- (raizEntera n) es el mayor entero cuya raíz cuadrada es menor o igual
-- que n. Por ejemplo,
--    raizEntera 15  ==  3
--    raizEntera 16  ==  4
--    raizEntera 17  ==  4
raizEntera :: Integer -> Integer
raizEntera = floor . sqrt . fromIntegral 
 
-- 2ª definición
-- =============
 
ordenLagrange2 :: Integer -> Int
ordenLagrange2 n = (vectorOrdenLagrange n) ! n
 
vectorOrdenLagrange :: Integer -> Array Integer Int
vectorOrdenLagrange n = v where
  v = array (0,n) [(i,f i) | i <- [0..n]]
  f i | esCuadrado i = 1
      | otherwise    = 1 + minimum [ v ! (i - j^2)
                                   | j <- [1..raizEntera i]]
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> ordenLagrange 50
--    2
--    (10.39 secs, 1,704,144,464 bytes)
--    λ> ordenLagrange2 50
--    2
--    (0.01 secs, 341,920 bytes)
 
-- Definición de graficaOrdenLagrange
-- ==================================
 
graficaOrdenLagrange :: Integer -> IO ()
graficaOrdenLagrange n = 
  plotList [ Key Nothing
           , PNG ("Numero_de_sumandos_en_suma_de_cuadrados.png")
           ]
           (map ordenLagrange2 [0..n-1])
 
-- Comprobación de la propiedad
-- ============================
 
-- La propiedad es
prop_OrdenLagrange :: Positive Integer -> Bool
prop_OrdenLagrange (Positive k) =
  ordenLagrange2 k <= 4 &&
  ordenLagrange2 (4*k+3) /= 2 &&
  ordenLagrange2 (8*k+7) /= 3
 
-- La comprobación es
--    λ> quickCheck prop_OrdenLagrange
--    +++ OK, passed 100 tests.

Pensamiento

— Nuestro español bosteza.
¿Es hambre? ¿Sueño? ¿Hastío?
Doctor, ¿tendrá el estómago vacío?
— El vacío es más bien en la cabeza.

Antonio Machado

5 soluciones de “Número de sumandos en suma de cuadrados

  1. frahidzam
    import Data.Array
    import Data.List (genericLength)
    import Test.QuickCheck
    import Graphics.Gnuplot.Simple
     
    ordenLagrange :: Integer -> Int
    ordenLagrange 0 = 0
    ordenLagrange 1 = 1
    ordenLagrange n | (v!u) == n = 1
                    | n > 11 = 1 + minimum [(ordenLagrange (n - (v!(u-a))))| a <- [0..(genericLength (show (n)))] ]
                    | otherwise = 1 + (ordenLagrange (n - (v!(u))))
      where u = floor (sqrt (fromIntegral n))
            v = listArray (1,u) [a^2 | a <- [1..u]]
     
    graficaOrdenLagrange :: Integer -> IO ()
    graficaOrdenLagrange n = plotList [Key Nothing] [ordenLagrange a | a <- [1..n]]
     
    prop_ordenLagrange :: Integer -> Property
    prop_ordenLagrange n = n >= 0 ==> ordenLagrange n <= 4 &&
                                      ordenLagrange (4*n+3) /= 2 &&
                                      ordenLagrange (8*n+7) /= 3
  2. adogargon
    import Test.QuickCheck
    import Graphics.Gnuplot.Simple
     
    cuadradoperfecto :: Integer -> Bool
    cuadradoperfecto x = aux x 0
      where aux x n | n^2 > x = False
                    | n^2 == x = True
                    | otherwise = aux x (n+1)
     
    cuadradodoble :: Integer -> Bool
    cuadradodoble n = n`elem`[ x^2 + y^2 | x <-(take (k`div`2) [1..]),
                               y <-(take (k`div`2) [1..])]
      where k = fromIntegral n 
     
    ordenLagrange :: Integer -> Int
    ordenLagrange x | cuadradoperfecto x = 1
                    | cuadradodoble x  = 2
                    | cuadradotriple x  = 3
                    | otherwise = 4
     
     
    cuadradotriple :: Integer -> Bool
    cuadradotriple n = n`elem`[ x^2 + y^2 +z^2 | x <-(take (k`div`2) [1..]),
                               y <-(take (k`div`2) [1..]), z <-(take (k`div`2) [1..])]
      where k = fromIntegral n
     
    graficaOrdenLagrange :: Integer -> IO ()
    graficaOrdenLagrange n = plotList [Key Nothing] [ordenLagrange a | a <- [1..n]]
     
    prop_ordenLagrange :: Integer -> Property
    prop_ordenLagrange n = n >= 0 ==> ordenLagrange n <= 4 &&
                                      ordenLagrange (4*n+3) /= 2 &&
                                      ordenLagrange (8*n+7) /= 3
  3. luipromor
    ordenLagrange        :: Integer -> Int             
    ordenLagrange x = fromIntegral (aux ! x)
      where aux :: Array Integer Integer
            aux  = array (1,x) [ (i ,lagrange i ) | i <- [1..x]]             
            lagrange 0 = 0
            lagrange 1 = 1
            lagrange n | esCuadrado n = 1
                       | otherwise = 1 + minimum [ aux ! (n-k^2) | k <- [1..n-1], k ^2 < n]
    esCuadrado :: Integer -> Bool
    esCuadrado n = (floor.sqrt.fromIntegral ) n ^2 == n
     
    graficaOrdenLagrange :: Integer -> IO ()
    graficaOrdenLagrange n = plotList [] (map ordenLagrange [1..n])
    prop_lagranja :: Integer -> Property
    prop_lagranja x = x > 0  ==> ordenLagrange x <= 4 && f x
      where f k | mod (k-3) 4 == 0 = ordenLagrange k /=2
                | mod (k-7) 8 ==0 = ordenLagrange k /=3
                | otherwise = True
  4. javmarcha1
    import Data.Char
    import Test.QuickCheck
    import Graphics.Gnuplot.Simple
     
    ordenLagrange :: Integer -> Int
    ordenLagrange n = minimum [ ordenLagrange1 n a | a <- [0..(parteEntera n -1)]]
     
    ordenLagrange1 :: Integer -> Integer -> Int
    ordenLagrange1 n a | (parte2 n a) ==  n = 1
                       | otherwise = 1 + (ordenLagrange1 (n-(parte2 n a)) 0)
     
    alHeron :: Integer -> Int -> Double -> Double
    alHeron x n a | n == 0 = a
                  | otherwise = 0.5*(d+((fromIntegral x)/d))
            where d = (alHeron x (n-1) a)
     
    parteEntera :: Integer -> Integer
    parteEntera x = floor (alHeron x 15 ((fromIntegral x)/2))
     
    parte2 :: Integer -> Integer -> Integer
    parte2 x a = ((parteEntera x) -a)^2
     
     
    graficaOrdenLagrange :: Integer -> IO ()
    graficaOrdenLagrange n = plotList [Key Nothing] [ordenLagrange a | a <- [1..n]]
     
    prop_ordenLagrange :: Integer -> Property
    prop_ordenLagrange n = n >= 0 ==> ordenLagrange n <= 4 &&
                                      ordenLagrange (4*n+3) /= 2 &&
                                      ordenLagrange (8*n+7) /= 3
  5. berarcmat
    import Data.Array
    import Data.List (genericLength)
    import Test.QuickCheck
    import Graphics.Gnuplot.Simple
     
    ordenLagrange :: Integer -> Int
    ordenLagrange n = (vectorLagrange n) ! n
     
    vectorLagrange ::  Integer -> Array Integer Int
    vectorLagrange n = v where
      v = array (0,n) [(i,f i) | i <- [0..n]]
      f 0 = 0
      f 1 = 1
      f i | i == fromIntegral (w ! c) = 1
          | i <= 11                   = 1 + v ! (i - raiz i^2)
          | otherwise                 =
            1 + minimum [v ! (i - (raiz i - b)^2)
                              | b <- [0..genericLength (show n)]]
      w = array (1,c) [(i,i^2) | i <- [1..c]]
      c = raiz n
     
    raiz :: Integer -> Integer
    raiz = floor. sqrt. fromIntegral
     
    graficaOrdenLagrange :: Integer -> IO ()
    graficaOrdenLagrange n = plotList [Key Nothing] [ordenLagrange a | a <- [1..n]]
     
    prop_ordenLagrange :: Integer -> Property
    prop_ordenLagrange n = n >= 0 ==> ordenLagrange n <= 4 &&
                                      ordenLagrange (4*n+3) /= 2 &&
                                      ordenLagrange (8*n+7) /= 3

Leave a Reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.