Menu Close

Día: 27 abril, 2021

Máximos de una función recursiva (OME2002 P3)

El enunciado del problema 5 de la OME (Olimpiada Matemática Española) del 2002 es

La función g se define sobre los números naturales y satisface las condiciones:

  • g(1) = 1
  • g(2n) = g(n)
  • g(2n + 1) = g(2n) + 1

Sea n un número natural tal que 1 ≤ n ≤ 2002. Calcula el valor máximo M de g(n). Calcula también cuántos valores de n satisfacen g(n) = M.

Los valores de la función g para n de 1 a 30 son

   1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4

Definir la función

   maximoG :: Integer -> Integer

tal que (maximoG m) es el máximo de los valores de g(n) para n en {1, 2,…, m}. Por ejemplo,

   maximoG 30           ==  4
   maximoG (10^(10^5))  ==  332192

Usando la función maximoG, calcular los valores pedidos en el problema.

Soluciones

import Data.List (genericLength, genericTake, group)
import Test.QuickCheck (Property, (==>), quickCheck)
 
-- 1ª solución
-- ===========
 
maximoG :: Integer -> Integer
maximoG m = maximum (genericTake m sucesionG)
 
-- sucesionG es la lista de los valores de g. Por ejemplo,
--    λ> take 30 sucesionG
--    [1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4]
sucesionG :: [Integer]
sucesionG = map g [1..]
 
-- (g n) es el valor de g(n).
g :: Integer -> Integer
g 1 = 1
g n | even n    = g (n `div` 2)
    | otherwise = g (n `div` 2) + 1
 
-- 2ª solución
-- ===========
 
-- Observando los siguientes cálculos
--   λ> map maximoG [1..40]
--   [1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5]
--   λ> take 10 (map length (group (map maximoG [1..])))
--   [2,4,8,16,32,64,128,256,512,1024]
 
maximoG2 :: Integer -> Integer
maximoG2 m = head [x | x <- [1..], m + 1 < 2^x] - 1
 
-- 3ª solución
-- ===========
 
maximoG3 :: Integer -> Integer
maximoG3 m = genericLength (takeWhile (<m+2) potenciasDeDos) - 1
 
-- potenciasDeDos es la lista de las potencias de dos. Por ejemplo,
--    take 10 potenciasDeDos  ==  [1,2,4,8,16,32,64,128,256,512]
potenciasDeDos :: [Integer]
potenciasDeDos = iterate (*2) 1
 
-- 4ª solución
-- ===========
 
maximoG4 :: Integer -> Integer
maximoG4 m = floor (logBase 2 (fromIntegral (m+1)))
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_maximoG :: Integer -> Property
prop_maximoG m =
  m > 0 ==>
  all (== (maximoG m))
      [ maximoG2 m,
        maximoG3 m,
        maximoG4 m]
 
-- La comprobación es
--    λ> quickCheck prop_maximoG
--    +++ OK, passed 100 tests.
 
-- Nota: Aunque QuickCheck no ha encontrado ningún contraejemplo, la
-- definición maximoG4 que usa números decimales falla para números muy
-- grandes. Por ejemplo,
--    λ> maximoG4 (10^308)
--    1023
--    λ> maximoG4 (10^309)
--    1797693134862315907729305190789024733617976978942306572734300...
--    λ> maximoG3 (10^308)
--    1023
--    λ> maximoG3 (10^309)
--    1026
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> maximoG (10^6)
--    19
--    (8.80 secs, 6,015,772,760 bytes)
--    λ> maximoG2 (10^6)
--    19
--    (0.02 secs, 106,752 bytes)
--    λ> maximoG3 (10^6)
--    19
--    (0.02 secs, 102,592 bytes)
--    λ> maximoG4 (10^6)
--    19
--    (0.01 secs, 98,464 bytes)
--
--    λ> maximoG2 (10^308)
--    1023
--    (0.03 secs, 3,266,096 bytes)
--    λ> maximoG3 (10^308)
--    1023
--    (0.02 secs, 266,856 bytes)
--    λ> maximoG4 (10^308)
--    1023
--    (0.02 secs, 103,176 bytes)
--
--    λ> maximoG2 (10^16789)
--    55771
--    (1.70 secs, 1,201,022,600 bytes)
--    λ> maximoG3 (10^16789)
--    55771
--    (0.24 secs, 214,872,864 bytes)
 
-- Cálculos del problema
-- =====================
 
-- El máximo se calcula como sigue:
--    λ> maximum (take 2002 sucesionG)
--    10
-- Por tanto, el máximo es 10.
 
-- Los valores de n tales que g(n) es el máximo se calcula como sigue:
--    λ> [n | n <- [1..2002], g n == 10]
--    [1023,1535,1791,1919,1983]

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>