Menu Close

Descomposiciones como sumas de consecutivos

El enunciado de un problema para la IMO (Olimpiada Internacional de Matemáticas) de 1966 es

  • (a) Calcular el número de maneras de expresar 500 como suma de números naturales consecutivos.
  • (b) Calcular el número de tales representaciones para n = 2^x·3^y·5^z, con x, y, z ∈ ℕ. ¿Cuántas de ellas están formadas por un único elemento?
  • (c) Calcular el número de tales representaciones para un número natural n.

Definir las funciones

   consecutivosConSuma    :: Integer -> [(Integer,Integer)]
   nDeConsecutivosConSuma :: Integer -> Integer

tales que

  • (consecutivosConSuma n) es la lista de los extremos de las sucesiones de números naturales consecutivos cuya suma es n. Por ejemplo,
     consecutivosConSuma 3  ==  [(0,2),(1,2),(3,3)]
     consecutivosConSuma 4  ==  [(4,4)]
     consecutivosConSuma 5  ==  [(2,3),(5,5)]
     consecutivosConSuma 6  ==  [(0,3),(1,3),(6,6)]
     consecutivosConSuma 15 ==  [(0,5),(1,5),(4,6),(7,8),(15,15)]
     maximum [length (consecutivosConSuma n) | n <- [1..1000]] == 16
  • (nDeConsecutivosConSuma n) es la cantidad de sucesiones de números naturales consecutivos cuya suma es n. Por ejemplo,
     nDeConsecutivosConSuma 3  ==  3
     nDeConsecutivosConSuma 4  ==  1
     nDeConsecutivosConSuma 5  ==  2
     nDeConsecutivosConSuma 6  ==  3
     nDeConsecutivosConSuma 15 ==  5
     maximum [nDeConsecutivosConSuma n | n <- [1..10^5]] == 49
     nDeConsecutivosConSuma (product [1..17])            == 672

Usando las funciones anteriores, calcular las respuestas del problema de la Olimpiada.

Soluciones

import Data.List (genericLength, genericTake, group)
import Data.Numbers.Primes (primeFactors)
import Test.QuickCheck (Positive(..), quickCheck)
 
-- 1ª  definición de consecutivosConSuma
-- =====================================
 
consecutivosConSuma :: Integer -> [(Integer,Integer)]
consecutivosConSuma n =
  [(x,y) | y <- [0..n],
           x <- [0..y],
           sum [x..y] == n]
 
-- 2ª  definición de consecutivosConSuma
-- =====================================
 
consecutivosConSuma2 :: Integer -> [(Integer,Integer)]
consecutivosConSuma2 n =
  [(x,y) | y <- [0..n],
           x <- [0..y],
           (x+y)*(y-x+1) == 2*n]
 
-- 3ª  definición de consecutivosConSuma
-- =====================================
 
consecutivosConSuma3 :: Integer -> [(Integer,Integer)]
consecutivosConSuma3 n
  | esTriangular n = (0, p n - 1) : [(p x, p y - 1) | (x,y) <- aux n]
  | otherwise      = [(p x, p y - 1) | (x,y) <- aux n]
  where p x = posicion x triangulares
        aux n = [(x,y) | y <- zs,
                         let x = y-n,
                         x `elem` zs]
          where zs = genericTake (n+1) triangulares
 
-- (esTriangular n) se verifica si n es un número triangular (es decir,
-- existe un m tal que n es 1+2+···+m). Por ejemplo,
--    esTriangular 6  ==  True
--    esTriangular 8  ==  False
esTriangular :: Integer -> Bool
esTriangular n =
  n `pertenece` triangulares
 
-- triangulares es la sucesión de los números triangulares. Por ejemplo,
--    take 10 triangulares  ==  [0,1,3,6,10,15,21,28,36,45]
triangulares :: [Integer]
triangulares = scanl1 (+) [0..]
 
-- (pertenece x ys) se verifica si x pertenece a la lista infinita
-- creciente ys. Por ejemplo,
--    pertenece 11 [1,3..]  ==  True
--    pertenece 12 [1,3..]  ==  False
pertenece :: Ord a => a -> [a] -> Bool
pertenece x ys =
  x == head (dropWhile (< x) ys)
 
-- (posicion x ys) es la posición de x en la lista ys. Por ejemplo,
--    posicion 7 [1,3..]  ==  4
posicion :: Eq a => a -> [a] -> Integer
posicion x (y:ys) | x == y    = 1
                  | otherwise = 1 + posicion x ys
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> maximum [length (consecutivosConSuma2 n) | n <- [1..200]]
--    9
--    (0.96 secs, 651,218,112 bytes)
--    λ> maximum [length (consecutivosConSuma3 n) | n <- [1..200]]
--    9
--    (0.04 secs, 6,664,544 bytes)
--
--    λ> maximum [length (consecutivosConSuma2 n) | n <- [1..300]]
--    9
--    (3.14 secs, 2,172,860,536 bytes)
--    λ> maximum [length (consecutivosConSuma3 n) | n <- [1..300]]
--    9
--    (0.16 secs, 14,523,880 bytes)
 
-- 1ª definición de nDeConsecutivosConSuma
-- =======================================
 
nDeConsecutivosConSuma :: Integer -> Integer
nDeConsecutivosConSuma = genericLength . consecutivosConSuma
 
-- 2ª definición de nDeConsecutivosConSuma
-- =======================================
 
nDeConsecutivosConSuma2 :: Integer -> Integer
nDeConsecutivosConSuma2 = genericLength . consecutivosConSuma2
 
-- 3ª definición de nDeConsecutivosConSuma
-- =======================================
 
nDeConsecutivosConSuma3 :: Integer -> Integer
nDeConsecutivosConSuma3 = genericLength . consecutivosConSuma3
 
-- Cálculo de las respuestas
-- =========================
 
-- El número de maneras de expresar 500 como suma de números naturales
-- consecutivos se calcula con
--    λ> nDeConsecutivosConSuma 500
--    4
-- Por tanto, se puede expresar de 4 formas distintas. Dichas
-- expresiones se pueden calcular consecutivos
--    λ> consecutivosConSuma 500
--    [(8,32),(59,66),(98,102),(500,500)]
-- Es decir,
--    500 = sum [8..32]
--    500 = sum [59..66]
--    500 = sum [98..102]
--    500 = sum [500..500]
 
-- Para la segunda pregunta realizamos los siguientes cálculos
--    λ> ts = [(x,y,z) | x <- [0..3], y <- [0..3], z <- [0..3]]
--    λ> as = [nDeConsecutivosConSuma3 (2^x*3^y*5^z) | (x,y,z) <- ts]
--    λ> as
--    [2,2,3,4,3,5,6,8,3,7,9,12,4,8,12,16,
--     1,3,3,4,3,4,6,8,3,6,9,12,4,8,12,16,
--     1,2,3,4,2,4,7,8,4,6,9,12,4,8,12,16,
--     1,2,3,4,2,5,6,8,3,6,9,12,4,8,12,16]
--    λ> bs = [(y+1)*(z+1) | (x,y,z) <- ts]
--    λ> bs
--    [1,2,3,4,2,4,6,8,3,6,9,12,4,8,12,16,
--     1,2,3,4,2,4,6,8,3,6,9,12,4,8,12,16,
--     1,2,3,4,2,4,6,8,3,6,9,12,4,8,12,16,
--     1,2,3,4,2,4,6,8,3,6,9,12,4,8,12,16]
-- Casi todos elementos de as son iguales que los de bs y los que no lo
-- son se diferencian en 1 como se observa en el siguiente cálculo
--    λ> zipWith (-) as bs
--    [1,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,
--     0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,
--     0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,
--     0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0]
-- Los que no son iguales se calcula con
--    λ> [n | (x,y,z) <- ts, let n = 2^x*3^y*5^z, nDeConsecutivosConSuma3 n /= (y+1)*(z+1)]
--    [1,3,15,45,10,6,300,36,120]
-- Dichos elementos son los números triangulares (es decir, los son
-- sumas de los primeros números naturales) como se comprueba con
--    λ> [n | (x,y,z) <- ts, let n = 2^x*3^y*5^z, esTriangular n]
--    [1,3,15,45,10,6,300,36,120]
--
-- En definitiva, el número de representaciones de n = 2^x·3^y·5^z es
-- + (y+1)*(z+1), si n no es triangular,
-- + 1 + (y+1)*(z+1), si n es triangular,
 
-- En el número n = 2^x·3^y·5^z, la parte 3^y·5^z es la parte impar de
-- n y (y+1)*(z+1) es el número de divisores de la parte impar de n. Por
-- tanto, el número de representaciones de n = 2^x·3^y·5^z es
-- + el número de divisores de la parte impar de n, si n no es triangular,
-- + uno más el número de divisores de la parte impar de n, si n es triangular,
 
-- El cálculo de la segunda parte del apartado (b) es
--    λ> [n | n <- [0..100], nDeConsecutivosConSuma3 n == 1]
--    [2,4,8,16,32,64]
--  que son las potencias de 2 con exponentes positivos.
 
-- Finalmente, para el apartado (c), se puede generalizar el resultado
-- anterior y el número de representaciones de n = 2^x·3^y·5^z es
-- + el número de divisores de la parte impar de n, si n no es triangular,
-- + uno más el número de divisores de la parte impar de n, si n es triangular,
-- donde la parte impar de n es el número impar y tal que existe un
-- número natural k tal que n = 2^k·y.
 
-- Vamas a comprobar la conjetura haciendo la siguente definición y
-- comprobando que es equivalente a la anterior.
 
-- 4ª definición de nDeConsecutivosConSuma
-- =======================================
 
nDeConsecutivosConSuma4 :: Integer -> Integer
nDeConsecutivosConSuma4 n
  | esTriangular n = 1 + (numeroDivisores (parteImpar n))
  | otherwise      = numeroDivisores (parteImpar n)
 
-- (parteImpar n) es la parte impar de n. Por ejemplo,
--    parteImpar 60  ==  15
parteImpar :: Integer -> Integer
parteImpar n | odd n     = n
             | otherwise = parteImpar (n `div` 2)
 
-- (numeroDivisores n) es el número de divisores de n. Por ejemplo,
--    numeroDivisores 12  ==  6
--    numeroDivisores 14  ==  4
numeroDivisores :: Integer -> Integer
numeroDivisores =
  product . map ((+1) . genericLength) . group . primeFactors
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_equivalencia :: Positive Integer -> Bool
prop_equivalencia (Positive n) =
  nDeConsecutivosConSuma3 n == nDeConsecutivosConSuma4 n
 
-- La comprobación es
--    λ> quickCheck prop_equivalencia
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> nDeConsecutivosConSuma (product [1..6])
--    6
--    (2.34 secs, 8,110,570,304 bytes)
--    λ> nDeConsecutivosConSuma2 (product [1..6])
--    6
--    (0.24 secs, 123,044,288 bytes)
--    λ> nDeConsecutivosConSuma3 (product [1..6])
--    6
--    (0.04 secs, 443,408 bytes)
--    λ> nDeConsecutivosConSuma4 (product [1..6])
--    6
--    (0.01 secs, 103,424 bytes)
--
--    λ> nDeConsecutivosConSuma2 (product [1..7])
--    12
--    (10.27 secs, 5,999,094,088 bytes)
--    λ> nDeConsecutivosConSuma3 (product [1..7])
--    12
--    (0.44 secs, 2,465,936 bytes)
--    λ> nDeConsecutivosConSuma4 (product [1..7])
--    12
--    (0.01 secs, 107,424 bytes)
--
--    λ> nDeConsecutivosConSuma3 (product [1..8])
--    12
--    (53.51 secs, 19,137,984 bytes)
--    λ> nDeConsecutivosConSuma4 (product [1..8])
--    12
--    (0.01 secs, 107,808 bytes)

Nuevas soluciones

  • En los comentarios se pueden escribir nuevas soluciones.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

Una solución de “Descomposiciones como sumas de consecutivos

  1. Alejandro García Alcaide
    import Data.List (genericLength)
    import Data.Numbers.Primes
    import Test.QuickCheck
    -- Hacemos una primera definicion: 
    consecutivosConSuma' :: Integer -> [(Integer,Integer)]
    consecutivosConSuma' n =
      [(x,y) | x <- [0..s], y <- [0..s], f x y ==n] ++ [(n,n)] 
     where s = div n 2 + 1
           f x y = div (y*(y+1)) 2 - div (t*(t+1)) 2
             where t = x-1
     
    -- Observamos que si n es primo, entonces, la longitud de esta lista es
    -- dos. Comprobamos que esto sea cierto:
     
    prop :: Integer -> Property
    prop n = isPrime n && n > 3 ==> nDeConsecutivosConSuma n == 2
     
    -- quickCheck prop
    -- +++ OK, passed 100 tests.
    -- Aprovechando esto, pulimos un poco mas la funcion anterior. Si n es primo,
    -- se descompondra como (n,n) - descomposicion trivial- y como (div n 2, div n
    -- 2 +1). Verificamos que esto vuelva a ser cierto.
     
    prop2 :: Integer -> Property
    prop2 n = isPrime n && n > 3 ==>
      consecutivosConSuma' n == [(t, t + 1), (n,n)]
       where t = div n 2
     -- quickCheck prop2
     -- +++ OK, passed 100 tests.
     
    -- Luego, esto nos lleva a la siguiente definicion:
    consecutivosConSuma :: Integer -> [(Integer,Integer)]
    consecutivosConSuma n
      | isPrime n && n>3 = [(s-1, s), (n,n)]
      | otherwise        = [(x,y) | x <- [0..s-1], y <- [x..s], f x y == n] ++[(n,n)]
     where s = div n 2 + 1
           f x y = div (y*(y+1) - (x-1)*x) 2
             where t = x-1
     
    -- Gracias a esta funcion, podemos responder a la primera pregunta:
    -- consecutivosConSuma 500 == [(8,32),(59,66),(98,102),(500,500)]
    -- Luego, 500 se podra expresar como suma de cuatro sucesiones de numeros
    -- consecutivos distintas.
     
    nDeConsecutivosConSuma :: Integer -> Integer
    nDeConsecutivosConSuma n = genericLength $ consecutivosConSuma' n

Leave a Reply

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