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

PorJosé A. Alonso 27-abril-20214-mayo-2021

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

1	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

1	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

1 2	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]

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

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>

3 Comentarios

termino :: Integer -> Integer
termino 1 = 1
termino n | even n    = termino (div n 2)
          | otherwise = termino (div n 2) +1

maximoG :: Integer -> Integer 
maximoG m = maximum [termino n | n<-[1..m]]

valores :: Integer -> Integer
valores m =  genericLength $takeWhile (==n) $ dropWhile (/=n) $sort (map (termino) [1..m])
              where n = maximoG m

--    λ>map (termino) [1..30] == 
--    [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]
--    (0.00 secs, 135,328 bytes)

--    λ> maximoG 30 == 4
--    (0.02 secs, 98,328 bytes)

--    λ> maximoG 2002 == 10
--    (0.05 secs, 6,726,488 bytes)

--    λ> valores 2002 == 5
--    (0.05 secs, 8,419,104 bytes)

termino :: Integer -> Integer

termino 1 = 1

termino n | even n = termino (div n 2)

| otherwise = termino (div n 2) +1

maximoG :: Integer -> Integer

maximoG m = maximum [termino n | n<-[1..m]]

valores :: Integer -> Integer

valores m = genericLength $takeWhile (==n) $ dropWhile (/=n) $sort (map (termino) [1..m])

where n = maximoG m

-- λ>map (termino) [1..30] ==

-- [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]

-- (0.00 secs, 135,328 bytes)

-- λ> maximoG 30 == 4

-- (0.02 secs, 98,328 bytes)

-- λ> maximoG 2002 == 10

-- (0.05 secs, 6,726,488 bytes)

-- λ> valores 2002 == 5

-- (0.05 secs, 8,419,104 bytes)

Responder

-- 1ª Definición de g:
-- ==================

g1 :: Integer -> Integer
g1 1 = 1
g1 n | even n = g1 (div n 2)
     | otherwise = g1 (n-1) + 1

-- 2ª Definición de g:
-- ==================

-- Se observa que el comportamiento de la sucesión g es similar a la forma en
-- la que pasamos los números enteros a binario. En concreto, se tiene que
-- g n = x, donde x es el número de unos que aparecen en la representación
-- binaria de n.

g2 :: Integer -> Integer
g2 = sum . int2bin

int2bin :: Integer -> [Integer]
int2bin 1 = [1]
int2bin n = mod n 2 : int2bin (div n 2)

-- A partir de esta definición, más eficiente, vamos a calcular el valor máximo
-- de g(n) y el número de valores que satisface g(n) = M.
--    λ> maximum [g2 n | n <- [1..2002]]
--    10
--    λ> length [n | n <- [1..2002], g2 n == 10]
--    5
-- 
-- Es más, la idea de la representación binaria nos permite saber qué números
-- en particular satisfacen que g(n) = 10. Estos números son los 5 más pequeños
-- posibles cuya representación binaria tiene 10 unos: 1023, 1535, 1791, 1919 y
-- 1983 (calculados con la función bin2int).

bin2int :: [Integer] -> Integer
bin2int [] = 0
bin2int (x:xs) = x + 2 * bin2int xs

-- Definición de maximoG:
-- =====================

-- Basándonos en la idea anterior, maximoG n es el exponente de la potencia de
-- 2 más cercana por debajo al número n.

maximoG :: Integer -> Integer
maximoG n = head [x | x <- [0..], 2^x > n] - 1

-- Para optimizar esta función, voy a necesitar emplear funciones auxiliares
-- más eficientes que en su día se subieron como solución a otros ejercicios,
-- esta vez adaptadas al problema actual.

maximoGOpt :: Integer -> Integer
maximoGOpt 1 = 0
maximoGOpt n = busqueda (cotas (2^) n)
  where busqueda (a,b) | a+1 == b  = a
                       | n < 2^m  = busqueda (a,m)
                       | otherwise = busqueda (m,b)
                           where m = (a+b) `div`  2

cotas :: (Integer -> Integer) -> Integer -> (Integer, Integer)
cotas f n | n <= f 0  = (-1,0)
          | otherwise = (b `div` 2, b)
              where b = until done (*2) 1
                    done b = n < f b

-- Equivalencia de las definiciones:
-- ================================

prop :: Integer -> Bool
prop n = maximoG m == maximoGOpt m
  where m = abs n + 1

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

-- Comparación de eficiencia:
-- =========================
--
-- λ> maximoG (10^(10^4))
-- 33219
-- (0.50 secs, 339,338,720 bytes)
-- λ> maximoGOpt (10^(10^4))
-- 33219
-- (0.01 secs, 413,728 bytes)
--
-- λ> maximoGOpt (10^(10^5))
-- 332192
-- (0.06 secs, 2,695,672 bytes)

-- 1ª Definición de g:

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

g1 :: Integer -> Integer

g1 1 = 1

g1 n | even n = g1 (div n 2)

| otherwise = g1 (n-1) + 1

-- 2ª Definición de g:

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

-- Se observa que el comportamiento de la sucesión g es similar a la forma en

-- la que pasamos los números enteros a binario. En concreto, se tiene que

-- g n = x, donde x es el número de unos que aparecen en la representación

-- binaria de n.

g2 :: Integer -> Integer

g2 = sum . int2bin

int2bin :: Integer -> [Integer]

int2bin 1 = [1]

int2bin n = mod n 2 : int2bin (div n 2)

-- A partir de esta definición, más eficiente, vamos a calcular el valor máximo

-- de g(n) y el número de valores que satisface g(n) = M.

-- λ> maximum [g2 n | n <- [1..2002]]

-- 10

-- λ> length [n | n <- [1..2002], g2 n == 10]

-- 5

-- Es más, la idea de la representación binaria nos permite saber qué números

-- en particular satisfacen que g(n) = 10. Estos números son los 5 más pequeños

-- posibles cuya representación binaria tiene 10 unos: 1023, 1535, 1791, 1919 y

-- 1983 (calculados con la función bin2int).

bin2int :: [Integer] -> Integer

bin2int [] = 0

bin2int (x:xs) = x + 2 * bin2int xs

-- Definición de maximoG:

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

-- Basándonos en la idea anterior, maximoG n es el exponente de la potencia de

-- 2 más cercana por debajo al número n.

maximoG :: Integer -> Integer

maximoG n = head [x | x <- [0..], 2^x > n] - 1

-- Para optimizar esta función, voy a necesitar emplear funciones auxiliares

-- más eficientes que en su día se subieron como solución a otros ejercicios,

-- esta vez adaptadas al problema actual.

maximoGOpt :: Integer -> Integer

maximoGOpt 1 = 0

maximoGOpt n = busqueda (cotas (2^) n)

where busqueda (a,b) | a+1 == b = a

| n < 2^m = busqueda (a,m)

| otherwise = busqueda (m,b)

where m = (a+b) `div` 2

cotas :: (Integer -> Integer) -> Integer -> (Integer, Integer)

cotas f n | n <= f 0 = (-1,0)

| otherwise = (b `div` 2, b)

where b = until done (*2) 1

done b = n < f b

-- Equivalencia de las definiciones:

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

prop :: Integer -> Bool

prop n = maximoG m == maximoGOpt m

where m = abs n + 1

-- La comprobación es:

-- λ> quickCheck prop

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia:

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

-- λ> maximoG (10^(10^4))

-- 33219

-- (0.50 secs, 339,338,720 bytes)

-- λ> maximoGOpt (10^(10^4))

-- 33219

-- (0.01 secs, 413,728 bytes)

-- λ> maximoGOpt (10^(10^5))

-- 332192

-- (0.06 secs, 2,695,672 bytes)

Responder

g :: Integer -> Integer
g 1 = 1
g n | mod n 2 == 0 = g (div n 2)
    | otherwise = g (div n 2) + 1

maximoG :: Integer -> Integer
maximoG n = last (sort [g m | m <- [1..n]])

enmax :: Integer -> [Integer]
enmax n = [m | m <- [1..] , g m == n]

maximos :: Integer -> [Integer]
maximos n = takeWhile (<n) (enmax (maximoG n))

{--Así, el valor máximo M es:
maximoG 2002
10
(0.05 secs, 7,102,256 bytes);

y los valores de n que satisfacen g(n)=M son:
maximos 2002
[1023,1535,1791,1919,1983]
(0.26 secs, 12,852,960 bytes)--}

g :: Integer -> Integer

g 1 = 1

g n | mod n 2 == 0 = g (div n 2)

| otherwise = g (div n 2) + 1

maximoG :: Integer -> Integer

maximoG n = last (sort [g m | m <- [1..n]])

enmax :: Integer -> [Integer]

enmax n = [m | m <- [1..] , g m == n]

maximos :: Integer -> [Integer]

maximos n = takeWhile (<n) (enmax (maximoG n))

{--Así, el valor máximo M es:

maximoG 2002

(0.05 secs, 7,102,256 bytes);

y los valores de n que satisfacen g(n)=M son:

maximos 2002

[1023,1535,1791,1919,1983]

(0.26 secs, 12,852,960 bytes)--}

Responder

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

Soluciones

Nuevas soluciones

3 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Nuevas soluciones

Se puede imprimir o compartir con

3 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico