Menu Close

Día: 14 mayo, 2021

Números consecutivos con factorización con exponentes impares

El enunciado del problema B.5 de la Fase Local de la Olimpiada Matemática Española del 2006 es

Los números naturales 22, 23, y 24 tienen la siguiente propiedad: los exponentes de los factores primos de su descomposición son todos impares (22 = 2¹·11¹, 23 = 23¹, 24 = 2³·3¹)

¿Cuál es el mayor número de naturales consecutivos que pueden tener esa propiedad?. Razónese la contestación.

Definir la lista

   consecutivosExponentesImpares :: [[Integer]]

cuyos elementos sean las sucesiones maximales de números enteros positivos tales que los exponentes de los factores primos de su descomposición son todos impares. Por ejemplo,

   λ> take 7 consecutivosExponentesImpares
   [[1,2,3],[5,6,7,8],[10,11],[13,14,15],[17],[19],[21,22,23,24]]
   λ> consecutivosExponentesImpares !! (10^4)
   [43030,43031,43032,43033,43034,43035]

Usando la función consecutivosExponentesImpares conjeturar la respuesta a la pregunta del problema y comprobarla con QuickCheck.

Soluciones

import Data.List (group)
import Data.Numbers.Primes (primeFactors)
import Test.QuickCheck (Property, (==>), quickCheck)
 
-- 1ª solución
-- ===========
 
consecutivosExponentesImpares :: [[Integer]]
consecutivosExponentesImpares =
  consecutivosExponentesImparesDesde 1 :
  [consecutivosExponentesImparesDesde n | n <- [1..],
                                          not (exponentesImpares (n-1)),
                                          exponentesImpares n]
 
-- (consecutivosExponentesImparesDesde n) es la sucesión maximal de
-- números enteros positivos a partir de n tales que los exponentes de
-- los factores primos de su descomposición son todos impares. Por
-- ejemplo,
--    consecutivosExponentesImparesDesde 1  ==  [1,2,3]
--    consecutivosExponentesImparesDesde 4  ==  []
--    consecutivosExponentesImparesDesde 5  ==  [5,6,7,8]
consecutivosExponentesImparesDesde :: Integer -> [Integer]
consecutivosExponentesImparesDesde n
  | exponentesImpares n = n : consecutivosExponentesImparesDesde (n+1)
  | otherwise           = []
 
-- (exponentesImpares n) se verifica si los exponentes de los factores
-- primos de su descomposición son todos impares. Por ejemplo,
--    exponentesImpares 4  ==  False
--    exponentesImpares 6  ==  True
exponentesImpares :: Integer -> Bool
exponentesImpares n = all odd (exponentes n)
 
-- (exponentes n) es la lista de los exponentes de la factorización
-- prima de n. Por ejemplo,
--    exponentes 4  ==  [2]
--    exponentes 6  ==  [1,1]
--    exponentes 1200  ==  [4,1,2]
exponentes :: Integer -> [Int]
exponentes n = map length (group (primeFactors n))
 
-- 2ª solución
-- ===========
 
consecutivosExponentesImpares2 :: [[Integer]]
consecutivosExponentesImpares2 = aux 1
  where aux n | exponentesImpares n = xs : aux (1 + last xs)
              | otherwise           = aux (n+1)
          where xs = consecutivosExponentesImparesDesde n
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_consecutivosExponentesImpares :: Int -> Property
prop_consecutivosExponentesImpares n =
  n > 0 ==>
  consecutivosExponentesImpares !! n == consecutivosExponentesImpares2 !! n
 
-- La comprobación es
--    λ> quickCheck prop_consecutivosExponentesImpares
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> consecutivosExponentesImpares !! (5*10^4)
--    [214917,214918,214919,214920,214921,214922,214923]
--    (4.95 secs, 14,329,413,944 bytes)
--    λ> consecutivosExponentesImpares2 !! (5*10^4)
--    [214917,214918,214919,214920,214921,214922,214923]
--    (5.29 secs, 15,103,460,488 bytes)
 
-- Respuesta a la pregunta del problema
-- ====================================
 
-- A partir del siguiente cálculo
--    λ> maximum [length xs | xs <- take (10^4) consecutivosExponentesImpares]
--    7
-- se puede conjeturar que el mayor número de naturales consecutivos que pueden
-- tener la propiedad es 7. Por el cálculo, se sabe que es mayor o igual
-- que 7. Falta por comprobar que es menor o igual que 7; es decir,
prop_maximoConsecutivosExponentesImpares :: Int -> Property
prop_maximoConsecutivosExponentesImpares n =
  n >= 0 ==>
  length (consecutivosExponentesImpares !! n) <= 7
 
-- La comprobación es
--    λ> quickCheck prop_maximoConsecutivosExponentesImpares
--    +++ OK, passed 100 tests.

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>