Menu Close

Número de sumandos en suma de cuadrados

José A. Alonso,

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

Avanzado
, , , , , , , , , ,

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

  1. Responder
    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. Responder
    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. Responder
    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. Responder
    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. Responder
    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

Escribe tu solución

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