31-mayo-2021 – Exercitium

Mayor producto con sumandos de la descomposición

PorJosé A. Alonso 31-mayo-202126-enero-2022

El enunciado del 4º problema para la IMO (Olimpiada Internacional de Matemáticas) de 1976 es

Calcular el mayor número que se puede obtener multiplicando los enteros positivos cuya suma es 1976.

Definir la función

   mayorProductoSumandos :: Integer -> Integer

1	mayorProductoSumandos :: Integer -> Integer

tal que (mayorProductoSumandos n) el mayor número que se puede obtener multiplicando los enteros positivos cuya suma es n. Por ejemplo,

   mayorProductoSumandos 5 == 6

1	mayorProductoSumandos 5 == 6

ya que los posibles listas de sumandos con suma 5 son

   [5], [2,3], [1,4], [1,2,2], [1,1,3], [1,1,1,2], [1,1,1,1,1]

1	[5], [2,3], [1,4], [1,2,2], [1,1,3], [1,1,1,2], [1,1,1,1,1]

sus productos son

   5,   6,     4,     4,       3,       2,         1

1	5, 6, 4, 4, 3, 2, 1

y el mayor de dichos productos es 6.

Otros ejemplos son

   mayorProductoSumandos 10   ==  36
   mayorProductoSumandos 100  ==  7412080755407364
   length (show (mayorProductoSumandos (10^8)))  ==  15904042

mayorProductoSumandos 10 == 36

mayorProductoSumandos 100 == 7412080755407364

length (show (mayorProductoSumandos (10^8))) == 15904042

Usando la función mayorProductoSumandos, calcular la respuesta al problema de la Olimpiada.

Soluciones

import Data.Numbers.Primes (primeFactors)
import Data.List (genericLength, group)
import Test.QuickCheck (Property, (==>), quickCheck)

-- 1ª solución
-- ===========

mayorProductoSumandos :: Integer -> Integer
mayorProductoSumandos n =
  maximum [product xs | xs <- sumandos n]

-- (sumandos n) es la lista de las descomposiciones de n
-- como suma de números naturales. Por ejemplo,
--    sumandos 3  ==  [[3],[1,2],[1,1,1],[2,1]]
sumandos :: Integer -> [[Integer]]
sumandos 1 = [[1]]
sumandos n =
  [n]: [n-x:ys | x <- [1..n-1], ys <- sumandos x, n-x <= head ys]

-- 2ª solución
-- ===========

mayorProductoSumandos2 :: Integer -> Integer
mayorProductoSumandos2 n
  | n < 5     = n
  | otherwise = maximum [(n-i) * mayorProductoSumandos2 i
                        | i <- [1..n-1]]

-- 3ª solución
-- ===========

-- Observando los siguientes cálculos
--    λ> [mayorProductoSumandos n | n <- [0..20]]
--    [0,1,2,3,4,6,9,12,18,27,36,54,81,108,162,243,324,486,729,972,1458]
--    λ> [mayorProductoSumandos n | n <- [0,3..20]]
--    [0,3,9,27,81,243,729]
--    λ> [mayorProductoSumandos n | n <- [1,4..20]]
--    [1,4,12,36,108,324,972]
--    λ> [mayorProductoSumandos n | n <- [2,5..20]]
--    [2,6,18,54,162,486,1458]

mayorProductoSumandos3 :: Integer -> Integer
mayorProductoSumandos3 n
  | n < 5     = n
  | otherwise = 3 * mayorProductoSumandos3 (n-3)

-- 4ª solución
-- ===========

-- (factorizacion n) es la descomposición de n en factores primos como
-- una lista de pares donde los primeros elementos son la base y los
-- segundo son los exponentes. Por ejemplo,
--    factorizacion 3000  ==  [(2,3),(3,1),(5,3)]
-- ya que 3000 = 2^3*3*5^3
factorizacion :: Integer -> [(Integer,Integer)]
factorizacion n =
  [(head xs,genericLength xs) | xs <- group (primeFactors n)]

-- Observando los siguientes cálculos
--    λ> [factorizacion (mayorProductoSumandos3 n) | n <- [3,6..20]]
--    [[(3,1)],[(3,2)],[(3,3)],[(3,4)],[(3,5)],[(3,6)]]
--    λ> [factorizacion (mayorProductoSumandos3 n) | n <- [4,7..20]]
--    [[(2,2)],[(2,2),(3,1)],[(2,2),(3,2)],[(2,2),(3,3)],[(2,2),(3,4)],[(2,2),(3,5)]]
--    λ> [factorizacion (mayorProductoSumandos3 n) | n <- [5,8..20]]
--    [[(2,1),(3,1)],[(2,1),(3,2)],[(2,1),(3,3)],[(2,1),(3,4)],[(2,1),(3,5)],[(2,1),(3,6)]]

mayorProductoSumandos4 :: Integer -> Integer
mayorProductoSumandos4 n
    | n < 5     = n
    | otherwise = case r of
                    0 -> 3^q
                    1 -> 4*3^(q-1)
                    2 -> 2*3^q
  where (q,r) = quotRem n 3

-- Comprobación de equivalencia
-- ============================

-- Para los primeros valores la propiedad es
prop_equivalencia1 :: Integer -> Bool
prop_equivalencia1 n =
  and [f k == mayorProductoSumandos4 k
      | k <- [0..n],
        f <- [mayorProductoSumandos,
              mayorProductoSumandos2,
              mayorProductoSumandos3]]

-- La comprobación es
--    λ> prop_equivalencia1 20
--    True

-- Para los grandes valores la propiedad es
prop_equivalencia2 :: Integer -> Property
prop_equivalencia2 n =
  n >= 0 ==>
  mayorProductoSumandos3 n == mayorProductoSumandos4 n

-- La comprobación es
--    λ> quickCheck prop_equivalencia2
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> mayorProductoSumandos 22
--    2916
--    (2.99 secs, 2,319,928,184 bytes)
--    λ> mayorProductoSumandos2 22
--    2916
--    (0.47 secs, 313,625,800 bytes)
--    λ> mayorProductoSumandos3 22
--    2916
--    (0.01 secs, 103,864 bytes)
--    λ> mayorProductoSumandos4 22
--    2916
--    (0.01 secs, 102,712 bytes)
--
--    λ> mayorProductoSumandos2 25
--    8748
--    (3.26 secs, 2,508,295,368 bytes)
--    λ> mayorProductoSumandos3 25
--    8748
--    (0.00 secs, 103,960 bytes)
--    λ> mayorProductoSumandos4 25
--    8748
--    (0.00 secs, 102,856 bytes)
--
--    λ> length (show (mayorProductoSumandos3 (10^6)))
--    159041
--    (9.83 secs, 11,400,807,392 bytes)
--    λ> length (show (mayorProductoSumandos4 (10^6)))
--    159041
--    (0.03 secs, 10,082,080 bytes)
--
--    λ> length (show (mayorProductoSumandos4 (10^8)))
--    15904042
--    (3.53 secs, 1,022,783,472 bytes)

-- Cálculo de la respuesta al problema
-- ===================================

-- El cálculo es
--    λ> mayorProductoSumandos4 1976
--    176528813092650631321824697527678863603414507360733532172646534742
--    374472004561447647833551576599071841268147340684692909561979543969
--    046876247215728742219795875277856143555895806750102055076974383708
--    360617266962123284615873951950033196388833843896325045289546019012
--    398784375461116652095995292235273337590912307103378
--    λ> factorizacion (mayorProductoSumandos4 1976)
--    [(2,1),(3,658)]
--    λ> mayorProductoSumandos3 1976 == 2*3^658
--    True

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

import Data.Numbers.Primes (primeFactors)

import Data.List (genericLength, group)

import Test.QuickCheck (Property, (==>), quickCheck)

-- 1ª solución

-- ===========

mayorProductoSumandos :: Integer -> Integer

mayorProductoSumandos n =

maximum [product xs | xs <- sumandos n]

-- (sumandos n) es la lista de las descomposiciones de n

-- como suma de números naturales. Por ejemplo,

-- sumandos 3 == [[3],[1,2],[1,1,1],[2,1]]

sumandos :: Integer -> [[Integer]]

sumandos 1 = [[1]]

sumandos n =

[n]: [n-x:ys | x <- [1..n-1], ys <- sumandos x, n-x <= head ys]

-- 2ª solución

-- ===========

mayorProductoSumandos2 :: Integer -> Integer

mayorProductoSumandos2 n

| n < 5 = n

| otherwise = maximum [(n-i) * mayorProductoSumandos2 i

| i <- [1..n-1]]

-- 3ª solución

-- ===========

-- Observando los siguientes cálculos

-- λ> [mayorProductoSumandos n | n <- [0..20]]

-- [0,1,2,3,4,6,9,12,18,27,36,54,81,108,162,243,324,486,729,972,1458]

-- λ> [mayorProductoSumandos n | n <- [0,3..20]]

-- [0,3,9,27,81,243,729]

-- λ> [mayorProductoSumandos n | n <- [1,4..20]]

-- [1,4,12,36,108,324,972]

-- λ> [mayorProductoSumandos n | n <- [2,5..20]]

-- [2,6,18,54,162,486,1458]

mayorProductoSumandos3 :: Integer -> Integer

mayorProductoSumandos3 n

| n < 5 = n

| otherwise = 3 * mayorProductoSumandos3 (n-3)

-- 4ª solución

-- ===========

-- (factorizacion n) es la descomposición de n en factores primos como

-- una lista de pares donde los primeros elementos son la base y los

-- segundo son los exponentes. Por ejemplo,

-- factorizacion 3000 == [(2,3),(3,1),(5,3)]

-- ya que 3000 = 2^3*3*5^3

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

factorizacion n =

[(head xs,genericLength xs) | xs <- group (primeFactors n)]

-- Observando los siguientes cálculos

-- λ> [factorizacion (mayorProductoSumandos3 n) | n <- [3,6..20]]

-- [[(3,1)],[(3,2)],[(3,3)],[(3,4)],[(3,5)],[(3,6)]]

-- λ> [factorizacion (mayorProductoSumandos3 n) | n <- [4,7..20]]

-- [[(2,2)],[(2,2),(3,1)],[(2,2),(3,2)],[(2,2),(3,3)],[(2,2),(3,4)],[(2,2),(3,5)]]

-- λ> [factorizacion (mayorProductoSumandos3 n) | n <- [5,8..20]]

-- [[(2,1),(3,1)],[(2,1),(3,2)],[(2,1),(3,3)],[(2,1),(3,4)],[(2,1),(3,5)],[(2,1),(3,6)]]

mayorProductoSumandos4 :: Integer -> Integer

mayorProductoSumandos4 n

| n < 5 = n

| otherwise = case r of

0 -> 3^q

1 -> 4*3^(q-1)

2 -> 2*3^q

where (q,r) = quotRem n 3

-- Comprobación de equivalencia

-- ============================

-- Para los primeros valores la propiedad es

prop_equivalencia1 :: Integer -> Bool

prop_equivalencia1 n =

and [f k == mayorProductoSumandos4 k

| k <- [0..n],

f <- [mayorProductoSumandos,

mayorProductoSumandos2,

mayorProductoSumandos3]]

-- La comprobación es

-- λ> prop_equivalencia1 20

-- True

-- Para los grandes valores la propiedad es

prop_equivalencia2 :: Integer -> Property

prop_equivalencia2 n =

n >= 0 ==>

mayorProductoSumandos3 n == mayorProductoSumandos4 n

-- La comprobación es

-- λ> quickCheck prop_equivalencia2

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> mayorProductoSumandos 22

-- 2916

-- (2.99 secs, 2,319,928,184 bytes)

-- λ> mayorProductoSumandos2 22

-- 2916

-- (0.47 secs, 313,625,800 bytes)

-- λ> mayorProductoSumandos3 22

-- 2916

-- (0.01 secs, 103,864 bytes)

-- λ> mayorProductoSumandos4 22

-- 2916

-- (0.01 secs, 102,712 bytes)

-- λ> mayorProductoSumandos2 25

-- 8748

-- (3.26 secs, 2,508,295,368 bytes)

-- λ> mayorProductoSumandos3 25

-- 8748

-- (0.00 secs, 103,960 bytes)

-- λ> mayorProductoSumandos4 25

-- 8748

-- (0.00 secs, 102,856 bytes)

-- λ> length (show (mayorProductoSumandos3 (10^6)))

-- 159041

-- (9.83 secs, 11,400,807,392 bytes)

-- λ> length (show (mayorProductoSumandos4 (10^6)))

-- 159041

-- (0.03 secs, 10,082,080 bytes)

-- λ> length (show (mayorProductoSumandos4 (10^8)))

-- 15904042

-- (3.53 secs, 1,022,783,472 bytes)

-- Cálculo de la respuesta al problema

-- ===================================

-- El cálculo es

-- λ> mayorProductoSumandos4 1976

-- 176528813092650631321824697527678863603414507360733532172646534742

-- 374472004561447647833551576599071841268147340684692909561979543969

-- 046876247215728742219795875277856143555895806750102055076974383708

-- 360617266962123284615873951950033196388833843896325045289546019012

-- 398784375461116652095995292235273337590912307103378

-- λ> factorizacion (mayorProductoSumandos4 1976)

-- [(2,1),(3,658)]

-- λ> mayorProductoSumandos3 1976 == 2*3^658

-- True

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>

Día: 31-mayo-2021

Mayor producto con sumandos de la descomposición

Soluciones

Nuevas soluciones

Entradas recientes

Buscar

Correo electrónico