quotRem

Biparticiones de un número

PorJosé A. Alonso 9-noviembre-201716-noviembre-2017

Definir la función

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

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

tal que (biparticiones n) es la lista de pares de números formados por las primeras cifras de n y las restantes. Por ejemplo,

   biparticiones  2025  ==  [(202,5),(20,25),(2,25)]
   biparticiones 10000  ==  [(1000,0),(100,0),(10,0),(1,0)]

1 2	biparticiones 2025 == [(202,5),(20,25),(2,25)] biparticiones 10000 == [(1000,0),(100,0),(10,0),(1,0)]

Soluciones

import Test.QuickCheck

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

biparticiones1 :: Integer -> [(Integer,Integer)]
biparticiones1 x = [(read y, read z) | (y,z) <- biparticionesL1 xs]
  where xs = show x

-- (biparticionesL1 xs) es la lista de los pares formados por los
-- prefijos no vacío de xs y su resto. Por ejemplo,
--    biparticionesL1 "2025" == [("2","025"),("20","25"),("202","5")]
biparticionesL1 :: [a] -> [([a],[a])]
biparticionesL1 xs = [splitAt k xs | k <- [1..length xs - 1]]

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

biparticiones2 :: Integer -> [(Integer,Integer)]
biparticiones2 x = [(read y, read z) | (y,z) <- biparticionesL2 xs]
  where xs = show x

-- (biparticionesL2 xs) es la lista de los pares formados por los
-- prefijos no vacío de xs y su resto. Por ejemplo,
--    biparticionesL2 "2025" == [("2","025"),("20","25"),("202","5")]
biparticionesL2 :: [a] -> [([a],[a])]
biparticionesL2 xs =
  takeWhile (not . null . snd) [splitAt n xs | n <- [1..]]

-- 3ª solución
-- ===========

biparticiones3 :: Integer -> [(Integer,Integer)]
biparticiones3 a =
  takeWhile ((>0) . fst) [divMod a (10^n) | n <- [1..]] 

-- 4ª solución
-- ===========

biparticiones4 :: Integer -> [(Integer,Integer)]
biparticiones4 n =
  [quotRem n (10^x) | x <- [1..length (show n) -1]]

-- 5ª solución
-- ===========

biparticiones5 :: Integer -> [(Integer,Integer)]
biparticiones5 n =
  takeWhile (/= (0,n)) [divMod n (10^x) | x <- [1..]]

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

--    λ> numero n = (read (replicate n '2')) :: Integer
--    (0.00 secs, 0 bytes)
--    λ> length (biparticiones1 (numero 10000))
--    9999
--    (0.03 secs, 10,753,192 bytes)
--    λ> length (biparticiones2 (numero 10000))
--    9999
--    (1.89 secs, 6,410,513,136 bytes)
--    λ> length (biparticiones3 (numero 10000))
--    9999
--    (0.54 secs, 152,777,680 bytes)
--    λ> length (biparticiones4 (numero 10000))
--    9999
--    (0.01 secs, 7,382,816 bytes)
--    λ> length (biparticiones5 (numero 10000))
--    9999
--    (2.11 secs, 152,131,136 bytes)
--    
--    λ> length (biparticiones1 (numero (10^7)))
--    9999999
--    (14.23 secs, 10,401,100,848 bytes)
--    λ> length (biparticiones4 (numero (10^7)))
--    9999999
--    (11.43 secs, 7,361,097,856 bytes)

import Test.QuickCheck

-- 1ª solución

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

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

biparticiones1 x = [(read y, read z) | (y,z) <- biparticionesL1 xs]

where xs = show x

-- (biparticionesL1 xs) es la lista de los pares formados por los

-- prefijos no vacío de xs y su resto. Por ejemplo,

-- biparticionesL1 "2025" == [("2","025"),("20","25"),("202","5")]

biparticionesL1 :: [a] -> [([a],[a])]

biparticionesL1 xs = [splitAt k xs | k <- [1..length xs - 1]]

-- 2ª solución

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

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

biparticiones2 x = [(read y, read z) | (y,z) <- biparticionesL2 xs]

where xs = show x

-- (biparticionesL2 xs) es la lista de los pares formados por los

-- prefijos no vacío de xs y su resto. Por ejemplo,

-- biparticionesL2 "2025" == [("2","025"),("20","25"),("202","5")]

biparticionesL2 :: [a] -> [([a],[a])]

biparticionesL2 xs =

takeWhile (not . null . snd) [splitAt n xs | n <- [1..]]

-- 3ª solución

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

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

biparticiones3 a =

takeWhile ((>0) . fst) [divMod a (10^n) | n <- [1..]]

-- 4ª solución

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

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

biparticiones4 n =

[quotRem n (10^x) | x <- [1..length (show n) -1]]

-- 5ª solución

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

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

biparticiones5 n =

takeWhile (/= (0,n)) [divMod n (10^x) | x <- [1..]]

-- Comparación de eficiencia

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

-- λ> numero n = (read (replicate n '2')) :: Integer

-- (0.00 secs, 0 bytes)

-- λ> length (biparticiones1 (numero 10000))

-- 9999

-- (0.03 secs, 10,753,192 bytes)

-- λ> length (biparticiones2 (numero 10000))

-- 9999

-- (1.89 secs, 6,410,513,136 bytes)

-- λ> length (biparticiones3 (numero 10000))

-- 9999

-- (0.54 secs, 152,777,680 bytes)

-- λ> length (biparticiones4 (numero 10000))

-- 9999

-- (0.01 secs, 7,382,816 bytes)

-- λ> length (biparticiones5 (numero 10000))

-- 9999

-- (2.11 secs, 152,131,136 bytes)

-- λ> length (biparticiones1 (numero (10^7)))

-- 9999999

-- (14.23 secs, 10,401,100,848 bytes)

-- λ> length (biparticiones4 (numero (10^7)))

-- 9999999

-- (11.43 secs, 7,361,097,856 bytes)

Sin ceros finales

PorJosé A. Alonso 6-diciembre-201613-diciembre-2016

Definir la función

   sinCerosFinales :: Int -> Int

1	sinCerosFinales :: Int -> Int

tal que (sinCerosFinales n) es el número obtenido eliminando los ceros finales de n. Por ejemplo,

   sinCerosFinales 104050     == 10405
   sinCerosFinales 960000     == 96
   sinCerosFinales 100050     == 10005
   sinCerosFinales (-10050)   == -1005
   sinCerosFinales 12         == 12
   sinCerosFinales 0          == 0

sinCerosFinales 104050 == 10405

sinCerosFinales 960000 == 96

sinCerosFinales 100050 == 10005

sinCerosFinales (-10050) == -1005

sinCerosFinales 12 == 12

sinCerosFinales 0 == 0

Comprobar con QuickCheck que, para cualquier número entero n,

   sinCerosFinales (sinCerosFinales n) == sinCerosFinales n

1	sinCerosFinales (sinCerosFinales n) == sinCerosFinales n

Soluciones

import Test.QuickCheck

-- 1ª solución
sinCerosFinales :: Int -> Int
sinCerosFinales 0 = 0
sinCerosFinales n
  | r /= 0    = n
  | otherwise = sinCerosFinales q  
  where (q,r) = quotRem n 10

-- 2ª solución
sinCerosFinales2 :: Int -> Int
sinCerosFinales2 0 = 0
sinCerosFinales2 n =
  read (reverse (dropWhile (=='0') (reverse (show n))))

-- 3ª solución
sinCerosFinales3 :: Int -> Int
sinCerosFinales3 0 = 0
sinCerosFinales3 n =
  (read . reverse . dropWhile (== '0') . reverse . show) n

-- 4ª solución
sinCerosFinales4 :: Int -> Int
sinCerosFinales4 0 = 0
sinCerosFinales4 n =
  read . reverse . dropWhile (== '0') . reverse . show $ n

-- La propiedad es
prop_sinCerosFinales :: Int -> Bool
prop_sinCerosFinales n =
  sinCerosFinales (sinCerosFinales n) == sinCerosFinales n

-- 5ª solución
sinCerosFinales5 :: Int -> Int
sinCerosFinales5 0 = 0
sinCerosFinales5 n = until (\x -> mod x 10 /= 0) (`div` 10) n

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

import Test.QuickCheck

-- 1ª solución

sinCerosFinales :: Int -> Int

sinCerosFinales 0 = 0

sinCerosFinales n

| r /= 0 = n

| otherwise = sinCerosFinales q

where (q,r) = quotRem n 10

-- 2ª solución

sinCerosFinales2 :: Int -> Int

sinCerosFinales2 0 = 0

sinCerosFinales2 n =

read (reverse (dropWhile (=='0') (reverse (show n))))

-- 3ª solución

sinCerosFinales3 :: Int -> Int

sinCerosFinales3 0 = 0

sinCerosFinales3 n =

(read . reverse . dropWhile (== '0') . reverse . show) n

-- 4ª solución

sinCerosFinales4 :: Int -> Int

sinCerosFinales4 0 = 0

sinCerosFinales4 n =

read . reverse . dropWhile (== '0') . reverse . show $ n

-- La propiedad es

prop_sinCerosFinales :: Int -> Bool

prop_sinCerosFinales n =

sinCerosFinales (sinCerosFinales n) == sinCerosFinales n

-- 5ª solución

sinCerosFinales5 :: Int -> Int

sinCerosFinales5 0 = 0

sinCerosFinales5 n = until (\x -> mod x 10 /= 0) (`div` 10) n

-- La comprobación es

-- λ> quickCheck prop_sinCerosFinales

-- +++ OK, passed 100 tests.

Persistencia multiplicativa de un número

PorJosé A. Alonso 14-noviembre-201621-noviembre-2016

La persistencia multiplicativa de un número es la cantidad de pasos requeridos para reducirlo a una cifra multiplicando sus dígitos. Por ejemplo, la persistencia de 39 es 3 porque 3×9 = 27, 2×7 = 14 y 1×4 = 4.

Definir las funciones

   persistencia     :: Integer -> Integer
   menorPersistente :: Integer -> Integer

1 2	persistencia :: Integer -> Integer menorPersistente :: Integer -> Integer

tales que

(persistencia x) es la persistencia de x. Por ejemplo,

     persistencia 39                             ==   3
     persistencia 2677889                        ==   8
     persistencia 26888999                       ==   9
     persistencia 3778888999                     ==  10
     persistencia 277777788888899                ==  11
     persistencia 77777733332222222222222222222  ==  11

persistencia 39 == 3

persistencia 2677889 == 8

persistencia 26888999 == 9

persistencia 3778888999 == 10

persistencia 277777788888899 == 11

persistencia 77777733332222222222222222222 == 11

(menorPersistente n) es el menor número con persistencia n. Por ejemplo,

     menorPersistente 0  ==  1
     menorPersistente 1  ==  10
     menorPersistente 2  ==  25
     menorPersistente 3  ==  39
     menorPersistente 4  ==  77
     menorPersistente 5  ==  679
     menorPersistente 6  ==  6788
     menorPersistente 7  ==  68889

menorPersistente 0 == 1

menorPersistente 1 == 10

menorPersistente 2 == 25

menorPersistente 3 == 39

menorPersistente 4 == 77

menorPersistente 5 == 679

menorPersistente 6 == 6788

menorPersistente 7 == 68889

Comprobar con QuickCheck si todos los números menores que 10^233 tienen una persistencia multiplicativa menor o igual que 11.

Nota: Este ejercicio ha sido propuesto por Marcos Giráldez.

Soluciones

import Test.QuickCheck

persistencia :: Integer -> Integer
persistencia x
  | x < 10    = 0
  | otherwise = 1 + persistencia (productoDigitos x)

productoDigitos :: Integer -> Integer
productoDigitos x 
  | x < 10    = x
  | otherwise = r * productoDigitos y
  where (y,r) = quotRem x 10

menorPersistente :: Integer -> Integer
menorPersistente n =
  head [x | x <- [1..]
          , persistencia x == n]

-- La propiedad es
prop_persistencia :: Integer -> Property
prop_persistencia x =
  x <= y ==> persistencia x <= 11
  where y = 10^233

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

import Test.QuickCheck

persistencia :: Integer -> Integer

persistencia x

| x < 10 = 0

| otherwise = 1 + persistencia (productoDigitos x)

productoDigitos :: Integer -> Integer

productoDigitos x

| x < 10 = x

| otherwise = r * productoDigitos y

where (y,r) = quotRem x 10

menorPersistente :: Integer -> Integer

menorPersistente n =

head [x | x <- [1..]

, persistencia x == n]

-- La propiedad es

prop_persistencia :: Integer -> Property

prop_persistencia x =

x <= y ==> persistencia x <= 11

where y = 10^233

-- La comprobación es

-- λ> quickCheck prop_persistencia

-- +++ OK, passed 100 tests.

Referencias

Persistencia multiplicativa y el número 77777733332222222222222222222 por M. Macho
Multiplicative persistence por Eric W. Weisstein en MathWorld.
Sucesión A003001 de la OEIS.

Inverso multiplicativo modular

PorJosé A. Alonso 6-abril-201626-marzo-2022

El inverso multiplicativo modular de un entero n módulo p es el número m, entre 1 y p-1, tal que

   mn = 1 (mod p)

1	mn = 1 (mod p)

Por ejemplo, el inverso multiplicativo de 2 módulo 5 es 3, ya que 1 <= 3 <= 4 y 2×3 = 1 (mod 5).

El inverso multipicativo de n módulo p existe si y sólo si n y p son coprimos; es decir, si mcd(n,p) = 1.

Definir la función

   invMod :: Integer -> Integer -> Maybe Integer

1	invMod :: Integer -> Integer -> Maybe Integer

tal que (invMod n p) es justo el inverso multiplicativo de n módulo p, si existe y Nothing en caso contrario. Por ejemplo,

   λ> invMod 2 5
   Just 3
   λ> invMod 2 6
   Nothing
   λ> [(x,invMod x 5) | x <- [0..4]]
   [(0,Nothing),(1,Just 1),(2,Just 3),(3,Just 2),(4,Just 4)]
   λ> [(x,invMod x 6) | x <- [0..5]]
   [(0,Nothing),(1,Just 1),(2,Nothing),(3,Nothing),(4,Nothing),(5,Just 5)]
   λ> let n = 10^7 in invMod (10^n) (1+10^n) == Just (10^n)
   True

λ> invMod 2 5

Just 3

λ> invMod 2 6

Nothing

λ> [(x,invMod x 5) | x <- [0..4]]

[(0,Nothing),(1,Just 1),(2,Just 3),(3,Just 2),(4,Just 4)]

λ> [(x,invMod x 6) | x <- [0..5]]

[(0,Nothing),(1,Just 1),(2,Nothing),(3,Nothing),(4,Nothing),(5,Just 5)]

λ> let n = 10^7 in invMod (10^n) (1+10^n) == Just (10^n)

True

Soluciones

-- 1ª definición
-- =============

invMod1 :: Integer -> Integer -> Maybe Integer
invMod1 n p | gcd n p == 1 = Just (head [m | m <- [1..p-1], m*n `mod` p == 1])
            | otherwise    = Nothing

-- 2ª definición
-- =============

invMod2 :: Integer -> Integer -> Maybe Integer
invMod2 n p | m /= 1    = Nothing
            | x < 0     = Just (x + p)
            | otherwise = Just x
    where (x,_,m) = mcdExt n p

-- [Algoritmo extendido de Euclides]
-- (mcd a b) es la terna (x,y,g) tal que g es el máximo común divisor
-- de a y b y se cumple que ax + by = g. Por ejemplo,
--    mcdExt  2  5  ==  (-2,1,1)
--    mcdExt  2  6  ==  ( 1,0,2)
--    mcdExt 12 15  ==  (-1,1,3)
mcdExt :: Integer -> Integer -> (Integer,Integer,Integer)
mcdExt a 0 = (1, 0, a)
mcdExt a b = (t, s - q * t, g)
  where (q, r)    = a `quotRem` b
        (s, t, g) = mcdExt b r

-- 3ª definición
-- =============

invMod3 :: Integer -> Integer -> Maybe Integer
invMod3 n p | gcd n p == 1 = Just (aux n p)
            | otherwise    = Nothing
  where aux 1 p = 1
        aux n p = (x * p + 1) `div` n
          where x = n - aux (p `mod` n) n                    

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

--    λ> invMod1 (10^7) (1+10^7)
--    Just 10000000
--    (5.05 secs, 2,872,350,896 bytes)
--    λ> invMod2 (10^7) (1+10^7)
--    Just 10000000
--    (0.00 secs, 0 bytes)
--    λ> invMod3 (10^7) (1+10^7)
--    Just 10000000
--    (0.00 secs, 0 bytes)
--    
--    λ> let n = 10^7 in invMod2 (10^n) (1+10^n) == Just (10^n)
--    True
--    (0.88 secs, 55,728,120 bytes)
--    λ> let n = 10^7 in invMod3 (10^n) (1+10^n) == Just (10^n)
--    True
--    (1.99 secs, 80,644,352 bytes)

-- 1ª definición

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

invMod1 :: Integer -> Integer -> Maybe Integer

invMod1 n p | gcd n p == 1 = Just (head [m | m <- [1..p-1], m*n `mod` p == 1])

| otherwise = Nothing

-- 2ª definición

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

invMod2 :: Integer -> Integer -> Maybe Integer

invMod2 n p | m /= 1 = Nothing

| x < 0 = Just (x + p)

| otherwise = Just x

where (x,_,m) = mcdExt n p

-- [Algoritmo extendido de Euclides]

-- (mcd a b) es la terna (x,y,g) tal que g es el máximo común divisor

-- de a y b y se cumple que ax + by = g. Por ejemplo,

-- mcdExt 2 5 == (-2,1,1)

-- mcdExt 2 6 == ( 1,0,2)

-- mcdExt 12 15 == (-1,1,3)

mcdExt :: Integer -> Integer -> (Integer,Integer,Integer)

mcdExt a 0 = (1, 0, a)

mcdExt a b = (t, s - q * t, g)

where (q, r) = a `quotRem` b

(s, t, g) = mcdExt b r

-- 3ª definición

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

invMod3 :: Integer -> Integer -> Maybe Integer

invMod3 n p | gcd n p == 1 = Just (aux n p)

| otherwise = Nothing

where aux 1 p = 1

aux n p = (x * p + 1) `div` n

where x = n - aux (p `mod` n) n

-- Comparación de eficiencia

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

-- λ> invMod1 (10^7) (1+10^7)

-- Just 10000000

-- (5.05 secs, 2,872,350,896 bytes)

-- λ> invMod2 (10^7) (1+10^7)

-- Just 10000000

-- (0.00 secs, 0 bytes)

-- λ> invMod3 (10^7) (1+10^7)

-- Just 10000000

-- (0.00 secs, 0 bytes)

-- λ> let n = 10^7 in invMod2 (10^n) (1+10^n) == Just (10^n)

-- True

-- (0.88 secs, 55,728,120 bytes)

-- λ> let n = 10^7 in invMod3 (10^n) (1+10^n) == Just (10^n)

-- True

-- (1.99 secs, 80,644,352 bytes)

Solución en Maxima

invMod (n,p) := block ([r],
  r : inv_mod (n,p),
  if integerp (r)
  then Just (r)
  else Nothing)$

invMod (n,p) := block ([r],

r : inv_mod (n,p),

if integerp (r)

then Just (r)

else Nothing)$

La evaluación de los ejemplos es

(%i2) invMod (2,5);
(%o2) Just(3)
(%i3) invMod (2,6);
(%o3) Nothing
(%i4) makelist([x,invMod(x,5)],x,0,4);
(%o4) [[0,Nothing],[1,Just(1)],[2,Just(3)],[3,Just(2)],[4,Just(4)]]
(%i5) makelist([x,invMod(x,6)],x,0,5);
(%o5) [[0,Nothing],[1,Just(1)],[2,Nothing],[3,Nothing],[4,Nothing],[5,Just(5)]]
(%i6) (n : 10^7, is (invMod (10^n,1+10^n) = Just (10^n)));
(%o6) true

(%i2) invMod (2,5);

(%o2) Just(3)

(%i3) invMod (2,6);

(%o3) Nothing

(%i4) makelist([x,invMod(x,5)],x,0,4);

(%o4) [[0,Nothing],[1,Just(1)],[2,Just(3)],[3,Just(2)],[4,Just(4)]]

(%i5) makelist([x,invMod(x,6)],x,0,5);

(%o5) [[0,Nothing],[1,Just(1)],[2,Nothing],[3,Nothing],[4,Nothing],[5,Just(5)]]

(%i6) (n : 10^7, is (invMod (10^n,1+10^n) = Just (10^n)));

(%o6) true

Referencia

Calculating multiplicative inverses in modular arithmetic

Representación decimal de números racionales

PorJosé A. Alonso 1-abril-20168-abril-2016

Los números decimales se representan por ternas, donde el primer elemento es la parte entera, el segundo es el anteperíodo y el tercero es el período. Por ejemplo,

    6/2  = 3                  se representa por (3,[],[])
    1/2  = 0.5                se representa por (0,[5],[])
    1/3  = 0.333333...        se representa por (0,[],[3])  
   23/14 = 1.6428571428571... se representa por (1,[6],[4,2,8,5,7,1])

6/2 = 3 se representa por (3,[],[])

1/2 = 0.5 se representa por (0,[5],[])

1/3 = 0.333333... se representa por (0,[],[3])

23/14 = 1.6428571428571... se representa por (1,[6],[4,2,8,5,7,1])

Su tipo es

   type Decimal = (Integer,[Integer],[Integer])

1	type Decimal = (Integer,[Integer],[Integer])

Los números racionales se representan por un par de enteros, donde el primer elemento es el numerador y el segundo el denominador. Por ejemplo, el número 2/3 se representa por (2,3). Su tipo es

   type Racional = (Integer,Integer)

1	type Racional = (Integer,Integer)

Definir las funciones

   decimal  :: Racional -> Decimal
   racional :: Decimal -> Racional

1 2	decimal :: Racional -> Decimal racional :: Decimal -> Racional

tales que

(decimal r) es la representación decimal del número racional r. Por ejemplo,

        decimal (1,4)    ==  (0,[2,5],[])
        decimal (1,3)    ==  (0,[],[3])
        decimal (23,14)  ==  (1,[6],[4,2,8,5,7,1])

decimal (1,4) == (0,[2,5],[])

decimal (1,3) == (0,[],[3])

decimal (23,14) == (1,[6],[4,2,8,5,7,1])

(racional d) es el número racional cuya representación decimal es d. Por ejemplo,

        racional (0,[2,5],[])           ==  (1,4)
        racional (0,[],[3])             ==  (1,3)
        racional (1,[6],[4,2,8,5,7,1])  ==  (23,14)

racional (0,[2,5],[]) == (1,4)

racional (0,[],[3]) == (1,3)

racional (1,[6],[4,2,8,5,7,1]) == (23,14)

Con la función decimal se puede calcular los períodos de los números racionales. Por ejemplo,

   ghci> let (_,_,p) = decimal (23,14) in concatMap show p
   "428571"
   ghci> let (_,_,p) = decimal (1,47) in concatMap show p
   "0212765957446808510638297872340425531914893617"
   ghci> let (_,_,p) = decimal (1,541) in length (concatMap show p)
   540

ghci> let (_,_,p) = decimal (23,14) in concatMap show p

"428571"

ghci> let (_,_,p) = decimal (1,47) in concatMap show p

"0212765957446808510638297872340425531914893617"

ghci> let (_,_,p) = decimal (1,541) in length (concatMap show p)

540

Comprobar con QuickCheck si las funciones decimal y racional son inversas.

Soluciones

-- ---------------------------------------------------------------------
-- § Librerías auxiliares                                             --
-- ---------------------------------------------------------------------

import Data.List
import Test.QuickCheck

-- ---------------------------------------------------------------------
-- § Tipos                                                            --
-- ---------------------------------------------------------------------

-- Un número racional se representa por un par de enteros, donde el
-- primer elemento es el numerador y el segundo el denominador.
type Racional = (Integer,Integer)

-- Un número decimal es una terna donde el primer elemento es la parte
-- entera, el segundo es el anteperíodo y el tercero es el período.
type Decimal = (Integer,[Integer],[Integer])

-- ---------------------------------------------------------------------
-- § De racional a decimal                                            --
-- ---------------------------------------------------------------------

-- (mayorExponente a x) es el mayor n tal que a^n divide a x. Por ejemplo,
--    mayorExponente 2 40  ==  3
--    mayorExponente 5 40  ==  1
--    mayorExponente 5 41  ==  0
mayorExponente :: Integer -> Integer -> Integer
mayorExponente a x = head [n | n <- [1..], mod x (a^n) /= 0] - 1

-- (longitudAnteperiodo n) es la longitud del anteperíodo de 1/n (y de
-- cualquier fracción irreducible de denominador n). Por ejemplo, 
--    longitudAnteperiodo 2   ==  1
--    longitudAnteperiodo 3   ==  0
--    longitudAnteperiodo 14  ==  1
longitudAnteperiodo :: Integer -> Integer
longitudAnteperiodo n = max (mayorExponente 2 n) (mayorExponente 5 n)

-- (longitudPeriodo n) es la longitud del período de 1/n (y de
-- cualquier fracción irreducible de denominador n). Por ejemplo, 
--    longitudPeriodo 2  ==  0
--    longitudPeriodo 3  ==  1
--    longitudPeriodo 7  ==  6
longitudPeriodo :: Integer -> Integer
longitudPeriodo n
    | m == 1    = 0 
    | otherwise = head [k | k <- [1..], (10^k) `mod` m == 1]
    where m = n `div` (2^(mayorExponente 2 n) * 5^(mayorExponente 5 n))

-- (expansionDec (x,y)) es la expansión decimal de x/y. Por ejemplo, 
--    take 10 (expansionDec (1,4))    ==  [0,2,5]
--    take 10 (expansionDec (1,7))    ==  [0,1,4,2,8,5,7,1,4,2]
--    take 12 (expansionDec (90,7))   ==  [12,8,5,7,1,4,2,8,5,7,1,4]
--    take 12 (expansionDec (23,14))  ==  [1,6,4,2,8,5,7,1,4,2,8,5]
expansionDec :: Racional -> [Integer]
expansionDec (x,y) 
    | r == 0    = [q] 
    | otherwise = q : expansionDec (r*10,y)
    where (q,r) = quotRem x y

-- (parteEntera (a,b)) es la parte entera de a/b. Por ejemplo,
--    parteEntera (125,3)  ==  41
parteEntera :: Racional -> Integer
parteEntera (a,b) = a `div` b

-- (antePeriodo (a,b)) es el anteperíodo de a/b; es decir, la lista de
-- cifras que se encuentran entre la parte entera y el primer período de
-- a/b. Por ejemplo,
--    antePeriodo (23,14)  ==  [6]
--    antePeriodo (1,5)    ==  [2]
antePeriodo :: Racional -> [Integer]
antePeriodo (a,b) = genericTake s (tail xs)
    where xs = expansionDec (a,b)
          s  = longitudAnteperiodo b

-- (periodo (a,b)) es el período de a/b; es decir, la lista de cifras que
-- se encuentran entre la parte entera y el primer período de a/b. Por
-- ejemplo, 
--    periodo (1,3)                   ==  [3]
--    periodo (1,5)                   ==  []
--    periodo (1,7)                   ==  [1,4,2,8,5,7]
--    periodo (23,14)                 ==  [4,2,8,5,7,1]
--    concatMap show $ periodo (1,29) == "0344827586206896551724137931"
periodo :: Racional -> [Integer]
periodo (a,b) = genericTake t (genericDrop (1+s) xs)
    where xs = expansionDec (a,b)
          s  = longitudAnteperiodo b
          t  = longitudPeriodo b

-- (reducido (a,b)) es la forma reducida del número racional a/b. Por
-- ejemplo, 
--    reducido (40,80)  ==  (1,2)
reducido :: Racional -> Racional
reducido (a,b) = (a `div` m, b `div` m) 
    where m = gcd a b

-- (decimal (x,y)) es la forma decimal de x/y; es decir, la terna
-- formada por la parte entera, la parte decimal pura y la parte decimal
-- periódica. Por ejemplo, 
--    decimal (1,4)    ==  (0,[2,5],[])
--    decimal (1,3)    ==  (0,[],[3])
--    decimal (23,14)  ==  (1,[6],[4,2,8,5,7,1])
decimal :: Racional -> Decimal
decimal (a,b) = (parteEntera r, antePeriodo r, periodo r)
    where r = reducido (a,b)

-- ---------------------------------------------------------------------
-- § De decimal a racional                                            --
-- ---------------------------------------------------------------------

-- (digitosAnumero xs) es el número correspondiente a la lista de
-- dígitos xs. Por ejemplo,
--    digitosAnumero [3,2,5]  ==  325
digitosAnumero :: [Integer] -> Integer
digitosAnumero = foldl (\a y -> 10*a+y) 0

-- 2ª definición de digitosAnumero (por comprensión)
digitosAnumero2 :: [Integer] -> Integer
digitosAnumero2 xs = sum [x*(10^i) | (x,i) <- zip xs [n-1,n-2..0]]
    where n = length xs

-- (racional (x,ys,zs)) es el número racional cuya representación
-- decimal es (x,ys,zs). Por ejemplo,
--    racional (0,[2,5],[])           ==  (1,4)
--    racional (0,[],[3])             ==  (1,3)
--    racional (1,[6],[4,2,8,5,7,1])  ==  (23,14)
racional :: Decimal -> Racional
racional (x,ys,[]) = reducido (a,b) where
    a = digitosAnumero (x:ys)
    b = 10^(length ys)
racional (x,ys,zs) = reducido (a,b) where 
    a = digitosAnumero (x:ys++zs) - digitosAnumero (x:ys)
    b = digitosAnumero (replicate (length zs) 9 ++ replicate (length ys) 0)

-- ---------------------------------------------------------------------
-- § Propiedades                                                      --
-- ---------------------------------------------------------------------

-- La 1ª propiedad es
prop_RacionalDecimal :: Racional -> Property
prop_RacionalDecimal (a,b) =
    a >= 0 && b > 0  ==>
    racional (decimal (a,b)) == reducido (a,b)

-- La comprobación es 
--    ghci> quickCheck prop_RacionalDecimal
--    +++ OK, passed 100 tests.

-- En lugar de reducido se puede usar un generador de números racionales
numeroRacional :: Gen Racional
numeroRacional = do a <- arbitrary
                    b <- arbitrary
                    return (reducido (abs a, 1+ abs b))

-- La propiedad es
prop_RacionalDecimal2 :: Property
prop_RacionalDecimal2 =
    forAll numeroRacional
           (\(a,b) -> racional (decimal (a,b)) == (a,b))

-- La comprobación es
--   ghci> quickCheck prop_RacionalDecimal2
--   +++ OK, passed 100 tests.

-- Para la 2ª propiedad se define un generador de números decimales
numeroDecimal :: Gen Decimal
numeroDecimal = do a <- arbitrary
                   b <- arbitrary
                   return (decimal (abs a, 1+ abs b))

-- La 2ª propiedad es
prop_DecimalRacional :: Property
prop_DecimalRacional =
    forAll numeroDecimal 
           (\(x,ys,zs) -> decimal (racional (x,ys,zs)) == (x,ys,zs))

-- La comprobación es
--   ghci> quickCheck prop_DecimalRacional
--   +++ OK, passed 100 tests.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

-- ---------------------------------------------------------------------

-- § Librerías auxiliares --

-- ---------------------------------------------------------------------

import Data.List

import Test.QuickCheck

-- ---------------------------------------------------------------------

-- § Tipos --

-- ---------------------------------------------------------------------

-- Un número racional se representa por un par de enteros, donde el

-- primer elemento es el numerador y el segundo el denominador.

type Racional = (Integer,Integer)

-- Un número decimal es una terna donde el primer elemento es la parte

-- entera, el segundo es el anteperíodo y el tercero es el período.

type Decimal = (Integer,[Integer],[Integer])

-- ---------------------------------------------------------------------

-- § De racional a decimal --

-- ---------------------------------------------------------------------

-- (mayorExponente a x) es el mayor n tal que a^n divide a x. Por ejemplo,

-- mayorExponente 2 40 == 3

-- mayorExponente 5 40 == 1

-- mayorExponente 5 41 == 0

mayorExponente :: Integer -> Integer -> Integer

mayorExponente a x = head [n | n <- [1..], mod x (a^n) /= 0] - 1

-- (longitudAnteperiodo n) es la longitud del anteperíodo de 1/n (y de

-- cualquier fracción irreducible de denominador n). Por ejemplo,

-- longitudAnteperiodo 2 == 1

-- longitudAnteperiodo 3 == 0

-- longitudAnteperiodo 14 == 1

longitudAnteperiodo :: Integer -> Integer

longitudAnteperiodo n = max (mayorExponente 2 n) (mayorExponente 5 n)

-- (longitudPeriodo n) es la longitud del período de 1/n (y de

-- cualquier fracción irreducible de denominador n). Por ejemplo,

-- longitudPeriodo 2 == 0

-- longitudPeriodo 3 == 1

-- longitudPeriodo 7 == 6

longitudPeriodo :: Integer -> Integer

longitudPeriodo n

| m == 1 = 0

| otherwise = head [k | k <- [1..], (10^k) `mod` m == 1]

where m = n `div` (2^(mayorExponente 2 n) * 5^(mayorExponente 5 n))

-- (expansionDec (x,y)) es la expansión decimal de x/y. Por ejemplo,

-- take 10 (expansionDec (1,4)) == [0,2,5]

-- take 10 (expansionDec (1,7)) == [0,1,4,2,8,5,7,1,4,2]

-- take 12 (expansionDec (90,7)) == [12,8,5,7,1,4,2,8,5,7,1,4]

-- take 12 (expansionDec (23,14)) == [1,6,4,2,8,5,7,1,4,2,8,5]

expansionDec :: Racional -> [Integer]

expansionDec (x,y)

| r == 0 = [q]

| otherwise = q : expansionDec (r*10,y)

where (q,r) = quotRem x y

-- (parteEntera (a,b)) es la parte entera de a/b. Por ejemplo,

-- parteEntera (125,3) == 41

parteEntera :: Racional -> Integer

parteEntera (a,b) = a `div` b

-- (antePeriodo (a,b)) es el anteperíodo de a/b; es decir, la lista de

-- cifras que se encuentran entre la parte entera y el primer período de

-- a/b. Por ejemplo,

-- antePeriodo (23,14) == [6]

-- antePeriodo (1,5) == [2]

antePeriodo :: Racional -> [Integer]

antePeriodo (a,b) = genericTake s (tail xs)

where xs = expansionDec (a,b)

s = longitudAnteperiodo b

-- (periodo (a,b)) es el período de a/b; es decir, la lista de cifras que

-- se encuentran entre la parte entera y el primer período de a/b. Por

-- ejemplo,

-- periodo (1,3) == [3]

-- periodo (1,5) == []

-- periodo (1,7) == [1,4,2,8,5,7]

-- periodo (23,14) == [4,2,8,5,7,1]

-- concatMap show $ periodo (1,29) == "0344827586206896551724137931"

periodo :: Racional -> [Integer]

periodo (a,b) = genericTake t (genericDrop (1+s) xs)

where xs = expansionDec (a,b)

s = longitudAnteperiodo b

t = longitudPeriodo b

-- (reducido (a,b)) es la forma reducida del número racional a/b. Por

-- ejemplo,

-- reducido (40,80) == (1,2)

reducido :: Racional -> Racional

reducido (a,b) = (a `div` m, b `div` m)

where m = gcd a b

-- (decimal (x,y)) es la forma decimal de x/y; es decir, la terna

-- formada por la parte entera, la parte decimal pura y la parte decimal

-- periódica. Por ejemplo,

-- decimal (1,4) == (0,[2,5],[])

-- decimal (1,3) == (0,[],[3])

-- decimal (23,14) == (1,[6],[4,2,8,5,7,1])

decimal :: Racional -> Decimal

decimal (a,b) = (parteEntera r, antePeriodo r, periodo r)

where r = reducido (a,b)

-- ---------------------------------------------------------------------

-- § De decimal a racional --

-- ---------------------------------------------------------------------

-- (digitosAnumero xs) es el número correspondiente a la lista de

-- dígitos xs. Por ejemplo,

-- digitosAnumero [3,2,5] == 325

digitosAnumero :: [Integer] -> Integer

digitosAnumero = foldl (\a y -> 10*a+y) 0

-- 2ª definición de digitosAnumero (por comprensión)

digitosAnumero2 :: [Integer] -> Integer

digitosAnumero2 xs = sum [x*(10^i) | (x,i) <- zip xs [n-1,n-2..0]]

where n = length xs

-- (racional (x,ys,zs)) es el número racional cuya representación

-- decimal es (x,ys,zs). Por ejemplo,

-- racional (0,[2,5],[]) == (1,4)

-- racional (0,[],[3]) == (1,3)

-- racional (1,[6],[4,2,8,5,7,1]) == (23,14)

racional :: Decimal -> Racional

racional (x,ys,[]) = reducido (a,b) where

a = digitosAnumero (x:ys)

b = 10^(length ys)

racional (x,ys,zs) = reducido (a,b) where

a = digitosAnumero (x:ys++zs) - digitosAnumero (x:ys)

b = digitosAnumero (replicate (length zs) 9 ++ replicate (length ys) 0)

-- ---------------------------------------------------------------------

-- § Propiedades --

-- ---------------------------------------------------------------------

-- La 1ª propiedad es

prop_RacionalDecimal :: Racional -> Property

prop_RacionalDecimal (a,b) =

a >= 0 && b > 0 ==>

racional (decimal (a,b)) == reducido (a,b)

-- La comprobación es

-- ghci> quickCheck prop_RacionalDecimal

-- +++ OK, passed 100 tests.

-- En lugar de reducido se puede usar un generador de números racionales

numeroRacional :: Gen Racional

numeroRacional = do a <- arbitrary

b <- arbitrary

return (reducido (abs a, 1+ abs b))

-- La propiedad es

prop_RacionalDecimal2 :: Property

prop_RacionalDecimal2 =

forAll numeroRacional

(\(a,b) -> racional (decimal (a,b)) == (a,b))

-- La comprobación es

-- ghci> quickCheck prop_RacionalDecimal2

-- +++ OK, passed 100 tests.

-- Para la 2ª propiedad se define un generador de números decimales

numeroDecimal :: Gen Decimal

numeroDecimal = do a <- arbitrary

b <- arbitrary

return (decimal (abs a, 1+ abs b))

-- La 2ª propiedad es

prop_DecimalRacional :: Property

prop_DecimalRacional =

forAll numeroDecimal

(\(x,ys,zs) -> decimal (racional (x,ys,zs)) == (x,ys,zs))

-- La comprobación es

-- ghci> quickCheck prop_DecimalRacional

-- +++ OK, passed 100 tests.

Biparticiones de un número

Soluciones

Sin ceros finales

Soluciones

Persistencia multiplicativa de un número

Soluciones

Referencias

Inverso multiplicativo modular

Soluciones

Solución en Maxima

Referencia

Representación decimal de números racionales

Soluciones

Entradas recientes

Buscar

Correo electrónico