Menu Close

Etiqueta: even

Último dígito no nulo del factorial

José A. Alonso, ,

El factorial de 7 es

   7! = 1 * 2 * 3 * 4 * 5 * 6 * 7 = 5040

por tanto, el último dígito no nulo del factorial de 7 es 4.

Definir la función

   ultimoNoNuloFactorial :: Integer -> Integer

tal que (ultimoNoNuloFactorial n) es el último dígito no nulo del factorial de n. Por ejemplo,

   ultimoNoNuloFactorial  7  == 4
   ultimoNoNuloFactorial 10  == 8
   ultimoNoNuloFactorial 12  == 6
   ultimoNoNuloFactorial 97  == 2
   ultimoNoNuloFactorial  0  == 1

Comprobar con QuickCheck que si n es mayor que 4, entonces el último dígito no nulo del factorial de n es par.

Soluciones

import Data.Char (digitToInt)
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
ultimoNoNuloFactorial :: Integer -> Integer
ultimoNoNuloFactorial = ultimoNoNulo . factorial
 
-- (factorial n) es el factorial de n. Por ejemplo,
--    factorial 7  ==  5040
factorial :: Integer -> Integer
factorial n = product [1..n]
 
-- (ultimoNoNulo n) es el último dígito no nulo de n. Por ejemplo,
--    ultimoNoNulo 5040  ==  4
ultimoNoNulo :: Integer -> Integer
ultimoNoNulo n | r /= 0    = r
               | otherwise = ultimoNoNulo q
  where (q,r) = n `quotRem` 10
 
-- 2ª solución
-- ===========
 
ultimoNoNuloFactorial2 :: Integer -> Integer
ultimoNoNuloFactorial2 = last . filter (/= 0) . digitos . factorial
 
digitos :: Integer -> [Integer]
digitos n = [read [x] | x <- show n]
 
-- 3ª solución
-- ===========
 
ultimoNoNuloFactorial3 :: Integer -> Integer
ultimoNoNuloFactorial3 = last . filter (/= 0) . digitos3 . factorial3
 
digitos3 :: Integer -> [Integer]
digitos3 = map (fromIntegral . digitToInt) . show
 
factorial3 :: Integer -> Integer
factorial3 = product . enumFromTo 1
 
-- 4ª solución
-- ===========
 
ultimoNoNulo4 :: Integer -> Integer
ultimoNoNulo4 n = read [head (dropWhile (=='0') (reverse (show n)))]
 
-- 5ª solución
-- ===========
 
ultimoNoNulo5 :: Integer -> Integer
ultimoNoNulo5 =
  read . return . head . dropWhile ('0' ==) . reverse . show
 
-- Propiedad
-- =========
 
-- La propiedad es
prop_ultimoNoNuloFactorial :: Integer -> Property
prop_ultimoNoNuloFactorial n = 
  n > 4 ==> even (ultimoNoNuloFactorial n)
 
-- La comprobación es
--    ghci> quickCheck prop_ultimoNoNuloFactorial
--    +++ OK, passed 100 tests.

Pensamiento

Busca el tu esencial,
que no está en ninguna parte
y en todas partes está.

Antonio Machado

Leer más →

La conjetura de Collatz

José A. Alonso, ,

La conjetura de Collatz, conocida también como conjetura 3n+1, fue enunciada por Lothar Collatz en 1937 y, hasta la fecha, no se ha resuelto.

La conjetura hace referencia a una propiedad de las sucesiones de Siracusa. La sucesión de Siracusa de un número entero positivo x es la sucesión cuyo primer término es x y el siguiente de un término se obtiene dividiéndolo entre 2, si es par o multiplicándolo por 3 y sumándole 1, si es impar. Por ejemplo, la sucesión de Siracusa de 12 es

   12, 6, 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, ....

La conjetura de Collatz afirma que para todo número entero positivo x, el 1 pertenece a la sucesión de Siracusa de x.

Definir las funciones

   siracusa        :: Integer -> [Integer]
   graficaSiracusa :: Int -> [Integer] -> IO ()

tales que

  • (siracusa x) es la sucesión de Siracusa de x. Por ejemplo,
     λ> take 20 (siracusa 12)
     [12,6,3,10,5,16,8,4,2,1,4,2,1,4,2,1,4,2,1,4]
     λ> take 20 (siracusa 22)
     [22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1,4,2,1,4]
  • (graficaSiracusa n xs) dibuja los n primeros términos de las sucesiones de Siracusas de los elementos de xs. Por ejemplo, (graficaSiracusa 100 [27]) dibuja

y (graficaSiracusa 150 [1..1000]) dibuja

Comprobar con QuickCheck la conjetura de Collatz.

Soluciones

import Test.QuickCheck
import Graphics.Gnuplot.Simple
 
-- 1ª definición de siracusa
-- =========================
 
siracusa :: Integer -> [Integer]
siracusa n | even n    = n : siracusa (n `div` 2)
           | otherwise = n : siracusa (3*n+1)
 
-- 2ª definición de siracusa
-- =========================
 
siracusa2 :: Integer -> [Integer]
siracusa2 = iterate siguiente 
  where siguiente x | even x    = x `div` 2
                    | otherwise = 3*x+1
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> siracusa 12 !! (10^6)
--    4
--    (0.55 secs, 362,791,008 bytes)
--    λ> siracusa 12 !! (2*10^6)
--    2
--    (1.05 secs, 725,456,376 bytes)
--    λ> siracusa2 12 !! (10^6)
--    4
--    (1.66 secs, 647,189,664 bytes)
--    λ> siracusa2 12 !! (2*10^6)
--    2
--    (3.11 secs, 1,294,286,792 bytes)
 
-- Definición de graficaSiracusa
-- =============================
 
graficaSiracusa :: Int -> [Integer] -> IO ()
graficaSiracusa n xs =
  plotLists [ Key Nothing
            , PNG "La_conjetura_de_Collatz.png"
            ]
            [take n (siracusa x) | x <- xs]
 
-- Comprobación de la conjetura
-- ============================
 
-- La conjetura es
conjeturaCollatz :: Positive Integer -> Bool
conjeturaCollatz (Positive n) =
  1 `elem` siracusa n
 
-- La comprobación es
--    λ> quickCheck conjeturaCollatz
--    +++ OK, passed 100 tests.

Pensamiento

Que el caminante es suma del camino …

Antonio Machado

Leer más →

Dígitos en las posiciones pares de cuadrados

José A. Alonso, ,

Definir las funciones

   digitosPosParesCuadrado    :: Integer -> ([Integer],Int)
   invDigitosPosParesCuadrado :: ([Integer],Int) -> [Integer]

tales que

  • (digitosPosParesCuadrado n) es el par formados por los dígitos de n² en la posiciones pares y por el número de dígitos de n². Por ejemplo, 
     digitosPosParesCuadrado 8     ==  ([6],2)
     digitosPosParesCuadrado 14    ==  ([1,6],3)
     digitosPosParesCuadrado 36    ==  ([1,9],4)
     digitosPosParesCuadrado 116   ==  ([1,4,6],5)
     digitosPosParesCuadrado 2019  ==  ([4,7,3,1],7)
  • (invDigitosPosParesCuadrado (xs,k)) es la lista de los números n tales que xs es la lista de los dígitos de n² en la posiciones pares y k es el número de dígitos de n². Por ejemplo,
     invDigitosPosParesCuadrado ([6],2)             ==  [8]
     invDigitosPosParesCuadrado ([1,6],3)           ==  [14]
     invDigitosPosParesCuadrado ([1,9],4)           ==  [36]
     invDigitosPosParesCuadrado ([1,4,6],5)         ==  [116,136]
     invDigitosPosParesCuadrado ([4,7,3,1],7)       ==  [2019,2139,2231]
     invDigitosPosParesCuadrado ([1,2],3)           ==  []
     invDigitosPosParesCuadrado ([1,2],4)           ==  [32,35,39]
     invDigitosPosParesCuadrado ([1,2,3,4,5,6],11)  ==  [115256,127334,135254]

Comprobar con QuickCheck que para todo entero positivo n se verifica que para todo entero positivo m, m pertenece a (invDigitosPosParesCuadrado (digitosPosParesCuadrado n)) si, y sólo si, (digitosPosParesCuadrado m) es igual a (digitosPosParesCuadrado n)

Soluciones

import Test.QuickCheck
 
-- Definición de digitosPosParesCuadrado
-- =====================================
 
digitosPosParesCuadrado :: Integer -> ([Integer],Int)
digitosPosParesCuadrado n =
  (digitosPosPares (n^2),length (show (n^2)))
 
-- (digitosPosPares n) es la lista de los dígitos de n en posiciones
-- pares. Por ejemplo,
--    digitosPosPares 24012019  ==  [2,0,2,1]
digitosPosPares :: Integer -> [Integer]
digitosPosPares n = elementosPosPares (digitos n)
 
-- (digitos n) es la lista de los dígitos de n. Por ejemplo,
--    digitos 325  ==  [3,2,5]
digitos :: Integer -> [Integer]
digitos n = [read [c] | c <- show n]
 
-- (elementosPosPares xs) es la lista de los elementos de xs en
-- posiciones pares. Por ejemplo,
--    elementosPosPares [3,2,5,7,6,4]  ==  [3,5,6]
elementosPosPares :: [a] -> [a]
elementosPosPares []       = []
elementosPosPares [x]      = [x]
elementosPosPares (x:_:zs) = x : elementosPosPares zs
 
-- 1ª definición de invDigitosPosParesCuadrado
-- ========================================
 
invDigitosPosParesCuadrado :: ([Integer],Int) -> [Integer]
invDigitosPosParesCuadrado (xs, a) =
  [x | x <- [ceiling (sqrt 10^(a-1))..ceiling (sqrt 10^a)]
     , digitosPosParesCuadrado x == (xs,a)]
 
-- 2ª definición de invDigitosPosParesCuadrado
-- ========================================
 
invDigitosPosParesCuadrado2 :: ([Integer],Int) -> [Integer]
invDigitosPosParesCuadrado2 x =
  [n | n <- [a..b], digitosPosParesCuadrado n == x]
  where a = floor (sqrt (fromIntegral (completaNum x 0)))
        b = ceiling (sqrt (fromIntegral (completaNum x 9)))
 
-- (completaNum (xs,k) n) es el número cuyos dígitos en las posiciones
-- pares son los de xs y los de las posiciones impares son iguales a n
-- (se supone que k es igual al doble de la longitud de xs o un
-- menos). Por ejemplo, 
--    completaNum ([1,3,8],5) 4  ==  14348
--    completaNum ([1,3,8],6) 4  ==  143484
completaNum :: ([Integer],Int) -> Integer -> Integer
completaNum x n = digitosAnumero (completa x n)
 
-- (completa (xs,k) n) es la lista cuyos elementos en las posiciones
-- pares son los de xs y los de las posiciones impares son iguales a n
-- (se supone que k es igual al doble de la longitud de xs o un
-- menos). Por ejemplo, 
--    completa ([1,3,8],5) 4  ==  [1,4,3,4,8]
--    completa ([1,3,8],6) 4  ==  [1,4,3,4,8,4]
completa :: ([Integer],Int) -> Integer -> [Integer]
completa (xs,k) n
  | even k    = ys
  | otherwise = init ys
  where ys = concat [[x,n] | x <- xs]
 
-- (digitosAnumero ds) es el número cuyos dígitos son ds. Por ejemplo,
--    digitosAnumero [2,0,1,9]  ==  2019
digitosAnumero :: [Integer] -> Integer
digitosAnumero = read . concatMap show
 
-- Comparación de eficiencia
-- =========================
 
--    λ> invDigitosPosParesCuadrado ([1,2,1,5,7,4,9],13)
--    [1106393,1234567,1314597]
--    (7.55 secs, 13,764,850,536 bytes)
--    λ> invDigitosPosParesCuadrado2 ([1,2,1,5,7,4,9],13)
--    [1106393,1234567,1314597]
--    (1.96 secs, 3,780,368,816 bytes)
 
-- Comprobación de la propiedad
-- ============================
 
-- La propiedad es  
prop_digitosPosParesCuadrado :: Positive Integer -> Positive Integer -> Bool
prop_digitosPosParesCuadrado (Positive n) (Positive m) =
  (digitosPosParesCuadrado m == x)
  == (m `elem` invDigitosPosParesCuadrado x)
  where x = digitosPosParesCuadrado n
 
-- La comprobación es
--    λ> quickCheck prop_digitosPosParesCuadrado
--    +++ OK, passed 100 tests.

Pensamiento

¡Ojos que a la luz se abrieron
un día para, después,
ciegos tornar a la tierra,
hartos de mirar sin ver.

Antonio Machado

Leer más →

El 2019 es malvado

José A. Alonso, ,

Un número malvado es un número natural cuya expresión en base 2 contiene un número par de unos. Por ejemplo, 6 es malvado porque su expresión en base 2 es 110 que tiene dos unos.

Definir las funciones

   esMalvado       :: Integer -> Bool
   malvados        :: [Integer]
   posicionMalvada :: Integer -> Maybe Int

tales que

  • (esMalvado n) se verifica si n es un número malvado. Por ejemplo,
     esMalvado 6              ==  True
     esMalvado 7              ==  False
     esMalvado 2019           ==  True
     esMalvado (10^70000)     ==  True
     esMalvado (10^(3*10^7))  ==  True
  • malvados es la sucesión de los números malvados. Por ejemplo,
     λ> take 20 malvados
     [0,3,5,6,9,10,12,15,17,18,20,23,24,27,29,30,33,34,36,39]
     malvados !! 1009    ==  2019
     malvados !! 10      ==  20
     malvados !! (10^2)  ==  201
     malvados !! (10^3)  ==  2000
     malvados !! (10^4)  ==  20001
     malvados !! (10^5)  ==  200000
     malvados !! (10^6)  ==  2000001
  • (posicionMalvada n) es justo la posición de n en la sucesión de números malvados, si n es malvado o Nothing, en caso contrario. Por ejemplo,
     posicionMalvada 6        ==  Just 3
     posicionMalvada 2019     ==  Just 1009
     posicionMalvada 2018     ==  Nothing
     posicionMalvada 2000001  ==  Just 1000000
     posicionMalvada (10^7)   ==  Just 5000000

Soluciones

import Data.List (genericLength, elemIndex)
import Data.Bits (popCount)
 
-- 1ª definición de esMalvado
-- ==========================
 
esMalvado :: Integer -> Bool
esMalvado n = even (numeroUnosBin n)
 
-- Sin argumentos
esMalvado' :: Integer -> Bool
esMalvado' = even . numeroUnosBin
 
-- (numeroUnosBin n) es el número de unos de la representación binaria
-- del número decimal n. Por ejemplo,
--   numeroUnosBin 11  ==  3
--   numeroUnosBin 12  ==  2
numeroUnosBin :: Integer -> Integer
numeroUnosBin n  = genericLength (filter (== 1) (binario n))
 
-- Sin argumentos
numeroUnosBin' :: Integer -> Integer
numeroUnosBin' = genericLength . filter (== 1) . binario
 
-- (binario n) es el número binario correspondiente al número decimal n.
-- Por ejemplo, 
--   binario 11  ==  [1,1,0,1]
--   binario 12  ==  [0,0,1,1]
binario :: Integer -> [Integer]
binario n | n < 2     = [n]
          | otherwise = n `mod` 2 : binario (n `div` 2)
 
-- 2ª definición de esMalvado
-- ==========================
 
esMalvado2 :: Integer -> Bool
esMalvado2 n = even (numeroUnosBin n)
 
-- (numeroIntBin n) es el número de unos que contiene la representación
-- binaria del número decimal n. Por ejemplo,
--   numeroIntBin 11  ==  3
--   numeroIntBin 12  ==  2
numeroIntBin :: Integer -> Integer
numeroIntBin n | n < 2     = n
               | otherwise = n `mod` 2 + numeroIntBin (n `div` 2)
 
-- 3ª definición de esMalvado
-- ==========================
 
esMalvado3 :: Integer -> Bool
esMalvado3 n = even (popCount n)
 
-- Sin argumentos
esMalvado3' :: Integer -> Bool
esMalvado3' = even . popCount 
 
-- Comparación de eficiencia
-- =========================
 
--    λ> esMalvado (10^30000)
--    True
--    (1.79 secs, 664,627,936 bytes)
--    λ> esMalvado2 (10^30000)
--    True
--    (1.79 secs, 664,626,992 bytes)
--    λ> esMalvado3 (10^30000)
--    True
--    (0.03 secs, 141,432 bytes)
--    
--    λ> esMalvado (10^40000)
--    False
--    (2.95 secs, 1,162,091,464 bytes)
--    λ> esMalvado2 (10^40000)
--    False
--    (2.96 secs, 1,162,091,096 bytes)
--    λ> esMalvado3 (10^40000)
--    False
--    (0.04 secs, 155,248 bytes)
 
-- 1ª definición de malvados
-- =========================
 
malvados :: [Integer]
malvados = [n | n <- [0..], esMalvado3 n]
 
-- 2ª definición de malvados
-- =========================
 
malvados2 :: [Integer]
malvados2 = filter esMalvado3 [0..]
 
-- 1ª definición de posicionMalvada
-- ================================
 
posicionMalvada :: Integer -> Maybe Int
posicionMalvada n
  | y == n    = Just (length xs)
  | otherwise = Nothing
  where (xs,(y:_)) = span (<n) malvados
 
-- 2ª definición de posicionMalvada
posicionMalvada2 :: Integer -> Maybe Int
posicionMalvada2 n
  | esMalvado n = elemIndex n malvados
  | otherwise        = Nothing

Pensamiento

… Yo os enseño, o pretendo enseñaros a que dudéis de todo: de lo
humano y de lo divino, sin excluir vuestra propia existencia.

Antonio Machado

Leer más →

Tablas de operaciones binarias

José A. Alonso, ,

Para representar las operaciones binarias en un conjunto finito A con n elementos se pueden numerar sus elementos desde el 0 al n-1. Entonces cada operación binaria en A se puede ver como una lista de listas xss tal que el valor de aplicar la operación a los elementos i y j es el j-ésimo elemento del i-ésimo elemento de xss. Por ejemplo, si A = {0,1,2} entonces las tabla de la suma y de la resta módulo 3 en A son

   0 1 2    0 2 1
   1 2 0    1 0 2
   2 0 1    2 1 0
   Suma     Resta

Definir las funciones

   tablaOperacion :: (Int -> Int -> Int) -> Int -> [[Int]]
   tablaSuma      :: Int -> [[Int]]
   tablaResta     :: Int -> [[Int]]
   tablaProducto  :: Int -> [[Int]]

tales que

  • (tablaOperacion f n) es la tabla de la operación f módulo n en [0..n-1]. Por ejemplo, 
     tablaOperacion (+) 3  ==  [[0,1,2],[1,2,0],[2,0,1]]
     tablaOperacion (-) 3  ==  [[0,2,1],[1,0,2],[2,1,0]]
     tablaOperacion (-) 4  ==  [[0,3,2,1],[1,0,3,2],[2,1,0,3],[3,2,1,0]]
     tablaOperacion (\x y -> abs (x-y)) 3  ==  [[0,1,2],[1,0,1],[2,1,0]]
  • (tablaSuma n) es la tabla de la suma módulo n en [0..n-1]. Por ejemplo,
     tablaSuma 3  ==  [[0,1,2],[1,2,0],[2,0,1]]
     tablaSuma 4  ==  [[0,1,2,3],[1,2,3,0],[2,3,0,1],[3,0,1,2]]
  • (tablaResta n) es la tabla de la resta módulo n en [0..n-1]. Por ejemplo,
     tablaResta 3  ==  [[0,2,1],[1,0,2],[2,1,0]]
     tablaResta 4  ==  [[0,3,2,1],[1,0,3,2],[2,1,0,3],[3,2,1,0]]
  • (tablaProducto n) es la tabla del producto módulo n en [0..n-1]. Por ejemplo,
     tablaProducto 3  ==  [[0,0,0],[0,1,2],[0,2,1]]
     tablaProducto 4  ==  [[0,0,0,0],[0,1,2,3],[0,2,0,2],[0,3,2,1]]

Comprobar con QuickCheck, si parato entero positivo n de verificar las siguientes propiedades:

  • La suma, módulo n, de todos los números de (tablaSuma n) es 0.
  • La suma, módulo n, de todos los números de (tablaResta n) es 0.
  • La suma, módulo n, de todos los números de (tablaProducto n) es n/2 si n es el doble de un número impar y es 0, en caso contrario.

Soluciones

import Test.QuickCheck
 
tablaOperacion :: (Int -> Int -> Int) -> Int -> [[Int]]
tablaOperacion f n =
  [[f i j `mod` n | j <- [0..n-1]] | i <- [0..n-1]]
 
tablaSuma :: Int -> [[Int]]
tablaSuma = tablaOperacion (+)
 
tablaResta :: Int -> [[Int]]
tablaResta = tablaOperacion (-)
 
tablaProducto :: Int -> [[Int]]
tablaProducto = tablaOperacion (*)
 
-- (sumaTabla xss) es la suma, módulo n, de los elementos de la tabla de
-- operación xss (donde n es el número de elementos de xss). Por
-- ejemplo, 
--    sumaTabla [[0,2,1],[1,1,2],[2,1,0]]  ==  1
sumaTabla :: [[Int]] -> Int
sumaTabla = sum . concat
 
-- La propiedad de la tabla de la suma es
prop_tablaSuma :: (Positive Int) -> Bool
prop_tablaSuma (Positive n) =
  sumaTabla (tablaSuma n) == 0
 
-- La comprobación es
--    λ> quickCheck prop_tablaSuma
--    +++ OK, passed 100 tests.
 
-- La propiedad de la tabla de la resta es
prop_tablaResta :: (Positive Int) -> Bool
prop_tablaResta (Positive n) =
  sumaTabla (tablaResta n) == 0
 
-- La comprobación es
--    λ> quickCheck prop_tablaResta
--    +++ OK, passed 100 tests.
 
-- La propiedad de la tabla del producto es
prop_tablaProducto :: (Positive Int) -> Bool
prop_tablaProducto (Positive n)
  | even n && odd (n `div` 2) = suma == n `div` 2
  | otherwise                 = suma == 0
  where suma = sumaTabla (tablaProducto n)

Pensamiento

¿Tu verdad? No, la Verdad,
y ven conmigo a buscarla.
La tuya guárdatela.

Antonio Machado

Leer más →