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

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

λ> 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.

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>

-- Definición:
-- ==========

consecutivosExponentesImpares :: [[Integer]]
consecutivosExponentesImpares = [1,2,3] : aux listaAlgunPar
  where aux (x:y:xs)
          | null zs   = aux (y:xs)
          | otherwise = zs : aux (y:xs)
              where zs = [x+1..y-1]

-- listaAlgunPar es la lista de los enteros positivos con algún exponente par
-- en su factorización prima. Por ejemplo,
--    λ> take 20 listaAlgunPar
--    [4,9,12,16,18,20,25,28,36,44,45,48,49,50,52,60,63,64,68,72]

listaAlgunPar :: [Integer]
listaAlgunPar = filter p [1..]
  where p x = any even [n | n <- map length (group (primeFactors x))]

-- Solución del problema:
-- =====================

-- Vamos a conjeturar la respuesta para los primeros 10000 términos de la lista
-- de listas. El cálculo es el siguiente:
--    λ> maximum [length xs | xs <- take 10000 consecutivosExponentesImpares]
--    7
--    (0.58 secs, 1,378,631,016 bytes)

-- Definición:

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

consecutivosExponentesImpares :: [[Integer]]

consecutivosExponentesImpares = [1,2,3] : aux listaAlgunPar

where aux (x:y:xs)

| null zs = aux (y:xs)

| otherwise = zs : aux (y:xs)

where zs = [x+1..y-1]

-- listaAlgunPar es la lista de los enteros positivos con algún exponente par

-- en su factorización prima. Por ejemplo,

-- λ> take 20 listaAlgunPar

-- [4,9,12,16,18,20,25,28,36,44,45,48,49,50,52,60,63,64,68,72]

listaAlgunPar :: [Integer]

listaAlgunPar = filter p [1..]

where p x = any even [n | n <- map length (group (primeFactors x))]

-- Solución del problema:

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

-- Vamos a conjeturar la respuesta para los primeros 10000 términos de la lista

-- de listas. El cálculo es el siguiente:

-- λ> maximum [length xs | xs <- take 10000 consecutivosExponentesImpares]

-- 7

-- (0.58 secs, 1,378,631,016 bytes)

Responder

Números consecutivos con factorización con exponentes impares

Soluciones

Nuevas soluciones

Un comentario

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Nuevas soluciones

Se puede imprimir o compartir con

Un comentario

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico