Test.QuickCheck

Números de Munchausen

PorJosé A. Alonso 13-enero-202020-enero-2020

Un número de Munchausen es un número entero positivo tal que es igual a la suma de sus dígitos elevados a sí mismo. Por ejemplo, 3435 es un número de Munchausen ya que

   3³ + 4⁴ + 3³ + 5⁵ = 27 + 256 + 27 + 3125 = 3435

1	3³ + 4⁴ + 3³ + 5⁵ = 27 + 256 + 27 + 3125 = 3435

Definir la función

   esMunchausen :: Integer -> Bool

1	esMunchausen :: Integer -> Bool

tal que (esMunchausen n) se verifica si n es un número de Munchausen. Por ejemplo,

   esMunchausen 3435  ==  True
   esMunchausen 2020  ==  False

1 2	esMunchausen 3435 == True esMunchausen 2020 == False

Comprobar con QuickCheck que que los únicos números de Munchausen son 1 y 3435.

Nota 1: No usar la propiedad en la definición.

Nota 2: El ejercicio está basado en el artículo ¿Por qué 3435 es uno de mis números favoritos? de Miguel Ángel Morales en El Aleph.

Soluciones

import Test.QuickCheck

esMunchausen :: Integer -> Bool
esMunchausen n =
  n == sum [x^x | x <- digitos n]

-- (digitos n) es la lista de los dígitos de n. Por ejemplo,
--    digitos 3435  ==  [3,4,3,5]
digitos :: Integer -> [Integer]
digitos n = [read [c] | c <- show n]

-- La propiedad es
prop_Munchausen :: Integer -> Property
prop_Munchausen n =
  n > 0
  ==>
  esMunchausen n == elem n [1, 3435]

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

import Test.QuickCheck

esMunchausen :: Integer -> Bool

esMunchausen n =

n == sum [x^x | x <- digitos n]

-- (digitos n) es la lista de los dígitos de n. Por ejemplo,

-- digitos 3435 == [3,4,3,5]

digitos :: Integer -> [Integer]

digitos n = [read [c] | c <- show n]

-- La propiedad es

prop_Munchausen :: Integer -> Property

prop_Munchausen n =

n > 0

==>

esMunchausen n == elem n [1, 3435]

-- La comprobación es

-- λ> quickCheck prop_Munchausen

-- +++ OK, passed 100 tests.

Pensamiento

Escribiré en tu abanico:
te quiero para olvidarte,
para quererte te olvido.

Antonio Machado

Teorema de existencia de divisores

PorJosé A. Alonso 10-enero-20206-junio-2022

El teorema de existencia de divisores afirma que

En cualquier subconjunto de {1, 2, …, 2m} con al menos m+1 elementos existen números distintos a, b tales que a divide a b.

Un conjunto de números naturales xs es mayoritario si existe un m tal que la lista de xs es un subconjunto de {1,2,…,2m} con al menos m+1 elementos. Por ejemplo, {2,3,5,6} porque es un subconjunto de {1,2,…,6} con más de 3 elementos.

Definir las funciones

   divisoresMultiplos :: [Integer] -> [(Integer,Integer)]
   esMayoritario :: [Integer] -> Bool

1 2	divisoresMultiplos :: [Integer] -> [(Integer,Integer)] esMayoritario :: [Integer] -> Bool

tales que

(divisores xs) es la lista de pares de elementos distintos de (a,b) tales que a divide a b. Por ejemplo,

     divisoresMultiplos [2,3,5,6]  ==  [(2,6),(3,6)]
     divisoresMultiplos [2,3,5]    ==  []
     divisoresMultiplos [4..8]     ==  [(4,8)]

divisoresMultiplos [2,3,5,6] == [(2,6),(3,6)]

divisoresMultiplos [2,3,5] == []

divisoresMultiplos [4..8] == [(4,8)]

(esMayoritario xs) se verifica xs es mayoritario. Por ejemplo,

     esMayoritario [2,3,5,6]  ==  True
     esMayoritario [2,3,5]    ==  False

1 2	esMayoritario [2,3,5,6] == True esMayoritario [2,3,5] == False

Comprobar con QuickCheck el teorema de existencia de divisores; es decir, en cualquier conjunto mayoritario existen números distintos a, b tales que a divide a b. Para la comprobación se puede usar el siguiente generador de conjuntos mayoritarios

   mayoritario :: Gen [Integer]
   mayoritario = do
     m' <- arbitrary
     let m = 1 + abs m'
     xs' <- sublistOf [1..2*m] `suchThat` (\ys -> genericLength ys > m)
     return xs'

mayoritario :: Gen [Integer]

mayoritario = do

m' <- arbitrary

let m = 1 + abs m'

xs' <- sublistOf [1..2*m] `suchThat` (\ys -> genericLength ys > m)

return xs'

con lo que la propiedad que hay que comprobar con QuickCheck es

   teorema_de_existencia_de_divisores :: Property
   teorema_de_existencia_de_divisores =
     forAll mayoritario (not . null . divisoresMultiplos)

teorema_de_existencia_de_divisores :: Property

teorema_de_existencia_de_divisores =

forAll mayoritario (not . null . divisoresMultiplos)

Soluciones

import Data.List (genericLength)
import Test.QuickCheck

divisoresMultiplos :: [Integer] -> [(Integer,Integer)]
divisoresMultiplos xs =
  [(x,y) | x <- xs
         , y <- xs
         , y /= x
         , y `mod` x == 0]

esMayoritario :: [Integer] -> Bool
esMayoritario xs =
  not (null xs) && length xs > ceiling (n / 2) 
  where n = fromIntegral (maximum xs)

-- Comprobación del teorema
-- ========================

-- La propiedad es
teorema_de_existencia_de_divisores :: Property
teorema_de_existencia_de_divisores =
  forAll mayoritario (not . null . divisoresMultiplos)

-- mayoritario es un generador de conjuntos mayoritarios. Por ejemplo, 
--    λ> sample mayoritario
--    [1,2]
--    [2,5,7,8]
--    [1,2,8,10,14]
--    [3,8,11,12,13,15,18,19,22,23,25,26]
--    [1,3,4,6]
--    [3,6,9,11,12,14,17,19]
mayoritario :: Gen [Integer]
mayoritario = do
  m' <- arbitrary
  let m = 1 + abs m'
  xs' <- sublistOf [1..2*m] `suchThat` (\ys -> genericLength ys > m)
  return xs'

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

import Data.List (genericLength)

import Test.QuickCheck

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

divisoresMultiplos xs =

[(x,y) | x <- xs

, y <- xs

, y /= x

, y `mod` x == 0]

esMayoritario :: [Integer] -> Bool

esMayoritario xs =

not (null xs) && length xs > ceiling (n / 2)

where n = fromIntegral (maximum xs)

-- Comprobación del teorema

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

-- La propiedad es

teorema_de_existencia_de_divisores :: Property

teorema_de_existencia_de_divisores =

forAll mayoritario (not . null . divisoresMultiplos)

-- mayoritario es un generador de conjuntos mayoritarios. Por ejemplo,

-- λ> sample mayoritario

-- [1,2]

-- [2,5,7,8]

-- [1,2,8,10,14]

-- [3,8,11,12,13,15,18,19,22,23,25,26]

-- [1,3,4,6]

-- [3,6,9,11,12,14,17,19]

mayoritario :: Gen [Integer]

mayoritario = do

m' <- arbitrary

let m = 1 + abs m'

xs' <- sublistOf [1..2*m] `suchThat` (\ys -> genericLength ys > m)

return xs'

-- La comprobación es

-- λ> quickCheck teorema_de_existencia_de_divisores

-- +++ OK, passed 100 tests.

Pensamiento

Guiomar, Guiomar,
mírame en ti castigado:
reo de haberte creado,
ya no te puedo olvidar.

Antonio Machado

Teorema de Hilbert-Waring

PorJosé A. Alonso 9-enero-202016-enero-2020

El problema de Waring, propuesto por Edward Waring consiste en déterminar si, para cada número entero k mayor que 1, existe un número n tal que todo entero positivo se puede escribir como una suma de k-potencias de números positivos con n sumandos como máximo.

La respuesta afirmativa al problema, aportada por David Hilbert, se conoce como el teorema de Hilbert-Waring. Su enunciado es

Para cada número entero k, con k ≥ 2, existe un entero positivo g(k) tal que todo entero positivo se puede expresar como una suma de a lo más g(k) k-ésimas potencias.

Definir las funciones

   descomposiciones :: Integer -> Integer -> Integer -> [[Integer]]
   orden :: Integer -> Integer -> Integer

1 2	descomposiciones :: Integer -> Integer -> Integer -> [[Integer]] orden :: Integer -> Integer -> Integer

tales que

(descomposiciones x k n) es la lista de descomposiciones de x como suma de n potencias con exponente k de números enteros positivos.

     descomposiciones 9   2 1  ==  [[9]]
     descomposiciones 9   3 1  ==  []
     descomposiciones 9   3 2  ==  [[1,8]]
     descomposiciones 9   4 9  ==  [[1,1,1,1,1,1,1,1,1]]
     descomposiciones 25  2 2  ==  [[9,16]]
     descomposiciones 133 2 3  ==  [[8,125]]
     descomposiciones 38  3 2  ==  [[1,1,36],[4,9,25]]

descomposiciones 9 2 1 == [[9]]

descomposiciones 9 3 1 == []

descomposiciones 9 3 2 == [[1,8]]

descomposiciones 9 4 9 == [[1,1,1,1,1,1,1,1,1]]

descomposiciones 25 2 2 == [[9,16]]

descomposiciones 133 2 3 == [[8,125]]

descomposiciones 38 3 2 == [[1,1,36],[4,9,25]]

(orden x k) es el menor número de sumandos necesario para expresar x como suma de k-ésimas potencias. Por ejemplo,

     orden 9  2  ==  1
     orden 9  3  ==  2
     orden 9  4  ==  9
     orden 10 2  ==  2
     orden 10 3  ==  3
     orden 10 4  ==  10
     [maximum [orden x k | x <- [1..1000]] | k <- [1..6]] == [1,4,9,19,37,73]

orden 9 2 == 1

orden 9 3 == 2

orden 9 4 == 9

orden 10 2 == 2

orden 10 3 == 3

orden 10 4 == 10

[maximum [orden x k | x <- [1..1000]] | k <- [1..6]] == [1,4,9,19,37,73]

Comprobar el teorema de Hilbert-Waring para k hasta 7; es decir, para todo número x positivo se verifica que

   orden x 2 <= 4   
   orden x 3 <= 9   
   orden x 4 <= 19  
   orden x 5 <= 37  
   orden x 6 <= 73  
   orden x 7 <= 143

orden x 2 <= 4

orden x 3 <= 9

orden x 4 <= 19

orden x 5 <= 37

orden x 6 <= 73

orden x 7 <= 143

y, en general,

   orden x k <= 2^k + floor ((3/2)^k) - 2

1	orden x k <= 2^k + floor ((3/2)^k) - 2

Soluciones

import Test.QuickCheck

descomposiciones :: Integer -> Integer -> Integer -> [[Integer]]
descomposiciones x k n =
  sumas x (takeWhile (<= x) (potencias k)) n

-- (potencias n) es la lista de las potencias de n
--    take 7 (potencias 2)  ==  [1,4,9,16,25,36,49]
--    take 7 (potencias 3)  ==  [1,8,27,64,125,216,343]
potencias :: Integer -> [Integer]
potencias n = map (^n) [1..]

-- (sumas n ys x) es la lista de las descomposiciones de x como
-- sumas de n sumandos de la lista creciente ys. Por ejemplo,
--    sumas 3 [1,2] 2  ==  [[1,2]]
--    sumas 4 [1,2] 2  ==  [[2,2]]
--    sumas 5 [1,2] 2  ==  []
--    sumas 5 [1,2] 3  ==  [[1,2,2]]
--    sumas 6 [1,2] 3  ==  [[2,2,2]]
--    sumas 6 [1,2,5] 2  ==  [[1,5]]
sumas :: Integer -> [Integer] -> Integer -> [[Integer]]
sumas _ [] _                   = []
sumas x ys 1     | x `elem` ys = [[x]]
                 | otherwise   = []
sumas x (y:ys) n | y > x       = []
                 | otherwise   = map (y:) (sumas (x-y) (y:ys) (n-1)) ++
                                 sumas x ys n

orden :: Integer -> Integer -> Integer
orden x k = head [n | n <- [1..]
                    , not (null (descomposiciones x k n))]

-- El teorema es                                 
teorema_Hilbert_Waring :: Integer -> Integer -> Property
teorema_Hilbert_Waring x k =
  x > 0 && k >= 2
  ==>
  orden x 2 <= 4   &&
  orden x 3 <= 9   &&
  orden x 4 <= 19  &&
  orden x 5 <= 37  &&
  orden x 6 <= 73  &&
  orden x 7 <= 143 &&
  orden x k <= 2^k + floor ((3/2)^k) - 2

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

import Test.QuickCheck

descomposiciones :: Integer -> Integer -> Integer -> [[Integer]]

descomposiciones x k n =

sumas x (takeWhile (<= x) (potencias k)) n

-- (potencias n) es la lista de las potencias de n

-- take 7 (potencias 2) == [1,4,9,16,25,36,49]

-- take 7 (potencias 3) == [1,8,27,64,125,216,343]

potencias :: Integer -> [Integer]

potencias n = map (^n) [1..]

-- (sumas n ys x) es la lista de las descomposiciones de x como

-- sumas de n sumandos de la lista creciente ys. Por ejemplo,

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

-- sumas 4 [1,2] 2 == [[2,2]]

-- sumas 5 [1,2] 2 == []

-- sumas 5 [1,2] 3 == [[1,2,2]]

-- sumas 6 [1,2] 3 == [[2,2,2]]

-- sumas 6 [1,2,5] 2 == [[1,5]]

sumas :: Integer -> [Integer] -> Integer -> [[Integer]]

sumas _ [] _ = []

sumas x ys 1 | x `elem` ys = [[x]]

| otherwise = []

sumas x (y:ys) n | y > x = []

| otherwise = map (y:) (sumas (x-y) (y:ys) (n-1)) ++

sumas x ys n

orden :: Integer -> Integer -> Integer

orden x k = head [n | n <- [1..]

, not (null (descomposiciones x k n))]

-- El teorema es

teorema_Hilbert_Waring :: Integer -> Integer -> Property

teorema_Hilbert_Waring x k =

x > 0 && k >= 2

==>

orden x 2 <= 4 &&

orden x 3 <= 9 &&

orden x 4 <= 19 &&

orden x 5 <= 37 &&

orden x 6 <= 73 &&

orden x 7 <= 143 &&

orden x k <= 2^k + floor ((3/2)^k) - 2

-- La comprobación es

-- λ> quickCheck teorema_Hilbert_Waring

-- +++ OK, passed 100 tests.

Referencia

Basado en Hilbert-Waring theorem de ProofWiki.

Pensamiento

¡Y en la tersa arena,
cerca de la mar,
tu carne rosa y morena,
súbitamente Guiomar!

Antonio Machado

Enteros como sumas de tres coprimos.

PorJosé A. Alonso 8-enero-202015-enero-2020

Dos números enteros son coprimos (o primos entre sí) si no tienen ningún factor primo en común. Por ejemplo, 4 y 15 son coprimos.

Una terna coprima es una terna (a,b,c) tal que

a y b son coprimos,
a y c son coprimos y
b y c son coprimos.

Por ejemplo, (3,4,5) es una terna coprima.

Definir la función

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

1	sumas3coprimos :: Integer -> [(Integer,Integer,Integer)]

tal que (sumas3coprimos n) es la lista de las ternas coprimas cuya suma es n. Por ejemplo,

   sumas3coprimos 10  ==  [(2,3,5)]
   sumas3coprimos 11  ==  []
   sumas3coprimos 12  ==  [(2,3,7),(3,4,5)]
   length (sumas3coprimos 4000)  ==  546146

sumas3coprimos 10 == [(2,3,5)]

sumas3coprimos 11 == []

sumas3coprimos 12 == [(2,3,7),(3,4,5)]

length (sumas3coprimos 4000) == 546146

Comprobar con QuickCheck que todo número entero mayor que 17 se puede escribir como suma de alguna terna coprima; es decir, para todo entero n, (sumas3coprimos2 (18 + abs n)) tiene algún elemento.

Soluciones

import Test.QuickCheck

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

sumas3coprimos :: Integer -> [(Integer,Integer,Integer)]
sumas3coprimos n =
  [(a,b,c) | a <- [2..n]
           , b <- [a+1..n]
           , c <- [b+1..n]
           , a + b + c == n
           , gcd a b == 1
           , gcd a c == 1
           , gcd b c == 1]

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

sumas3coprimos2 :: Integer -> [(Integer,Integer,Integer)]
sumas3coprimos2 n =
  [(a,b,c) | a <- [2..n `div` 3]
           , b <- [a+1..(n - a) `div` 2]
           , gcd a b == 1
           , let c = n - a - b  
           , gcd a c == 1
           , gcd b c == 1]

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

-- La propiedad de equivalencia es
prop_sumas3coprimos_equiv :: Integer -> Property
prop_sumas3coprimos_equiv n =
  n > 0 ==> sumas3coprimos n == sumas3coprimos2 n

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

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

--    λ> length (sumas3coprimos 400)
--    5345
--    (4.16 secs, 2,894,799,744 bytes)
--    λ> length (sumas3coprimos2 400)
--    5345
--    (0.06 secs, 16,565,136 bytes)

-- Propiedad
-- =========

-- La propiedad
prop_sumas3coprimos :: Integer -> Bool
prop_sumas3coprimos n =
  not (null (sumas3coprimos2 (18 + abs n)))

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

import Test.QuickCheck

-- 1ª solución

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

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

sumas3coprimos n =

[(a,b,c) | a <- [2..n]

, b <- [a+1..n]

, c <- [b+1..n]

, a + b + c == n

, gcd a b == 1

, gcd a c == 1

, gcd b c == 1]

-- 2ª solución

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

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

sumas3coprimos2 n =

[(a,b,c) | a <- [2..n `div` 3]

, b <- [a+1..(n - a) `div` 2]

, gcd a b == 1

, let c = n - a - b

, gcd a c == 1

, gcd b c == 1]

-- Equivalencia de las definiciones

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

-- La propiedad de equivalencia es

prop_sumas3coprimos_equiv :: Integer -> Property

prop_sumas3coprimos_equiv n =

n > 0 ==> sumas3coprimos n == sumas3coprimos2 n

-- La comprobación es

-- λ> quickCheck prop_sumas3coprimos_equiv

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- λ> length (sumas3coprimos 400)

-- 5345

-- (4.16 secs, 2,894,799,744 bytes)

-- λ> length (sumas3coprimos2 400)

-- 5345

-- (0.06 secs, 16,565,136 bytes)

-- Propiedad

-- =========

-- La propiedad

prop_sumas3coprimos :: Integer -> Bool

prop_sumas3coprimos n =

not (null (sumas3coprimos2 (18 + abs n)))

-- La comprobación es

-- λ> quickCheck prop_sumas3coprimos

-- +++ OK, passed 100 tests.

Referencias

Basado en Integers as sum of three pairwise coprime integers de ProofWiki.

Pensamiento

Todo amor es fantasía;
él inventa el año, el día,
la hora y su melodía;
inventa el amante y, más
la amada. No prueba nada,
contra el amor, que la amada
no haya existido jamás.

Antonio Machado

La mayor potencia de dos no es divisor

PorJosé A. Alonso 7-enero-202014-enero-2020

Para cada número entero positivo n, se define el conjunto

   S(n) = {1, 2, 3, ..., n}

1	S(n) = {1, 2, 3, ..., n}

de los números desde el 1 hasta n.

Definir la función

   mayorPotenciaDeDosEnS :: Integer -> Integer

1	mayorPotenciaDeDosEnS :: Integer -> Integer

tal que (mayorPotenciaDeDosEnS n) es la mayor potencia de 2 en S(n). Por ejemplo,

   mayorPotenciaDeDosEnS 3  ==  2
   mayorPotenciaDeDosEnS 4  ==  4

1 2	mayorPotenciaDeDosEnS 3 == 2 mayorPotenciaDeDosEnS 4 == 4

Comprobar con QuickCheck que la mayor potencia de 2 en S(n) no divide a ningún otro elemento de S(n).

Soluciones

import Data.List (delete)
import Test.QuickCheck

mayorPotenciaDeDosEnS :: Integer -> Integer
mayorPotenciaDeDosEnS n =
  last (takeWhile (<=n) potenciasDeDos)

-- potenciasDeDos es la lista de las potencias de 2. Por ejemplo,
--    take 5 potenciasDeDos  ==  [1,2,4,8,16]
potenciasDeDos :: [Integer]
potenciasDeDos = iterate (*2) 1

-- La propiedad es
prop_mayorPotenciaDeDosEnS :: Integer -> Property
prop_mayorPotenciaDeDosEnS n =
  n > 0 ==> all (x `noDivide`) (delete x [1..n])
  where x = mayorPotenciaDeDosEnS n
        x `noDivide` y = y `mod` x /= 0

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

import Data.List (delete)

import Test.QuickCheck

mayorPotenciaDeDosEnS :: Integer -> Integer

mayorPotenciaDeDosEnS n =

last (takeWhile (<=n) potenciasDeDos)

-- potenciasDeDos es la lista de las potencias de 2. Por ejemplo,

-- take 5 potenciasDeDos == [1,2,4,8,16]

potenciasDeDos :: [Integer]

potenciasDeDos = iterate (*2) 1

-- La propiedad es

prop_mayorPotenciaDeDosEnS :: Integer -> Property

prop_mayorPotenciaDeDosEnS n =

n > 0 ==> all (x `noDivide`) (delete x [1..n])

where x = mayorPotenciaDeDosEnS n

x `noDivide` y = y `mod` x /= 0

-- La comprobación es

-- λ> quickCheck prop_mayorPotenciaDeDosEnS

-- +++ OK, passed 100 tests.

Referencia

Basado en Greatest power of two not divisor de ProofWiki.

Pensamiento

¡Sólo tu figura,
como una centella blanca,
en mi noche oscura.

Antonio Machado

Números de Munchausen

Soluciones

Pensamiento

Teorema de existencia de divisores

Soluciones

Pensamiento

Teorema de Hilbert-Waring

Soluciones

Referencia

Pensamiento

Enteros como sumas de tres coprimos.

Soluciones

Referencias

Pensamiento

La mayor potencia de dos no es divisor

Soluciones

Referencia

Pensamiento

Entradas recientes

Buscar

Correo electrónico