read – Página 2 – Exercitium

Números somirp

PorJosé A. Alonso 10-enero-201819-febrero-2018

Un número omirp es un número primo que forma un primo distinto al invertir el orden de sus dígitos.

Definir las funciones

  esOmirp            :: Integer -> Bool
  omirps             :: [Integer]
  nOmirpsIntermedios :: Int -> Int

esOmirp :: Integer -> Bool

omirps :: [Integer]

nOmirpsIntermedios :: Int -> Int

tales que

(esOmirp n) se verifica si n es un número omirp. Por ejemplo,

     esOmirp 13      ==  True
     esOmirp 11      ==  False
     esOmirp 112207  ==  True

esOmirp 13 == True

esOmirp 11 == False

esOmirp 112207 == True

omirps es la lista de los números omirps. Por ejemplo,

     take 15 omirps  ==  [13,17,31,37,71,73,79,97,107,113]
     omirps !! 2000  ==  112207

1 2	take 15 omirps == [13,17,31,37,71,73,79,97,107,113] omirps !! 2000 == 112207

(nOmirpsIntermedios n) es la cantidad de números omirps entre el n-ésimo número omirp y el obtenido al invertir el orden de sus dígitos. Por ejemplo,

     nOmirpsIntermedios 2000  ==  4750

1	nOmirpsIntermedios 2000 == 4750

Nota: Este ejercicio ha sido propuesto por Ángel Ruiz Campos.

Soluciones

import Data.Numbers.Primes (isPrime,primes)

esOmirp :: Integer -> Bool
esOmirp n = n /= rn && isPrime rn
  where rn = read . reverse . show $ n

omirps :: [Integer]
omirps = filter esOmirp primes

nOmirpsIntermedios :: Int -> Int
nOmirpsIntermedios n =
  length
  . filter esOmirp
  . takeWhile (< rx)
  . dropWhile (<= x) $ primes
  where x  = omirps !! n
        rx = read . reverse . show $ x

import Data.Numbers.Primes (isPrime,primes)

esOmirp :: Integer -> Bool

esOmirp n = n /= rn && isPrime rn

where rn = read . reverse . show $ n

omirps :: [Integer]

omirps = filter esOmirp primes

nOmirpsIntermedios :: Int -> Int

nOmirpsIntermedios n =

length

. filter esOmirp

. takeWhile (< rx)

. dropWhile (<= x) $ primes

where x = omirps !! n

rx = read . reverse . show $ x

De hexadecimal a decimal

PorJosé A. Alonso 1-enero-201819-febrero-2018

El sistema hexadecimal es el sistema de numeración posicional que tiene como base el 16.

En principio, dado que el sistema usual de numeración es de base decimal y, por ello, sólo se dispone de diez dígitos, se adoptó la convención de usar las seis primeras letras del alfabeto latino para suplir los dígitos que nos faltan. El conjunto de símbolos es el siguiente: {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}. En ocasiones se emplean letras minúsculas en lugar de mayúsculas. Se debe notar que A = 10, B = 11, C = 12, D = 13, E = 14 y F = 15.

Como en cualquier sistema de numeración posicional, el valor numérico de cada dígito es alterado dependiendo de su posición en la cadena de dígitos, quedando multiplicado por una cierta potencia de la base del sistema, que en este caso es 16. Por ejemplo, el valor decimal del número hexadecimal 3E0A es

     3×16^3 + E×16^2 + 0×16^1 + A×16^0
   = 3×4096 + 14×256 + 0×16   + 10×1
   = 15882

3×16^3 + E×16^2 + 0×16^1 + A×16^0

= 3×4096 + 14×256 + 0×16 + 10×1

= 15882

Definir la función

   hexAdec :: String -> Int

1	hexAdec :: String -> Int

tal que (hexAdec cs) es el valor decimal del número hexadecimal representado meiante la cadena cs. Por ejemplo,

   hexAdec "3E0A"   == 15882
   hexAdec "ABCDEF" == 11259375
   hexAdec "FEDCBA" == 16702650

hexAdec "3E0A" == 15882

hexAdec "ABCDEF" == 11259375

hexAdec "FEDCBA" == 16702650

Soluciones

import Data.Char (digitToInt)
import Numeric(readHex)
import Data.List (foldl')

-- 1ª solución
hexAdec1 :: String -> Int
hexAdec1 s =
  sum (zipWith (*) (map digitToInt (reverse s)) (iterate (*16) 1))

-- 2ª solución
hexAdec2 :: String -> Int
hexAdec2 = foldl' (\acc x -> acc * 16 + digitToInt x) 0

-- 3ª solución
hexAdec3 :: String -> Int
hexAdec3 = read . ("0x" ++)

-- 4ª solución
hexAdec4 :: String -> Int
hexAdec4 = fst . head . readHex

import Data.Char (digitToInt)

import Numeric(readHex)

import Data.List (foldl')

-- 1ª solución

hexAdec1 :: String -> Int

hexAdec1 s =

sum (zipWith (*) (map digitToInt (reverse s)) (iterate (*16) 1))

-- 2ª solución

hexAdec2 :: String -> Int

hexAdec2 = foldl' (\acc x -> acc * 16 + digitToInt x) 0

-- 3ª solución

hexAdec3 :: String -> Int

hexAdec3 = read . ("0x" ++)

-- 4ª solución

hexAdec4 :: String -> Int

hexAdec4 = fst . head . readHex

Rotaciones divisibles por 8

PorJosé A. Alonso 22-diciembre-201719-febrero-2018

Las rotaciones de 928160 son 928160, 281609, 816092, 160928, 609281 y 92816 de las que 3 son divisibles por 8 (928160, 160928 y 92816).

Definir la función

   nRotacionesDivisiblesPor8 :: Integer -> Int

1	nRotacionesDivisiblesPor8 :: Integer -> Int

tal que (nRotacionesDivisiblesPor8 x) es el número de rotaciones de x divisibles por 8. Por ejemplo,

   nRotacionesDivisiblesPor8 928160       ==  3
   nRotacionesDivisiblesPor8 43262488612  ==  4
   nRotacionesDivisiblesPor8 (read (take (10^4) (cycle "248")))  ==  6666

nRotacionesDivisiblesPor8 928160 == 3

nRotacionesDivisiblesPor8 43262488612 == 4

nRotacionesDivisiblesPor8 (read (take (10^4) (cycle "248"))) == 6666

Soluciones

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

nRotacionesDivisiblesPor8 :: Integer -> Int
nRotacionesDivisiblesPor8 x =
  length [y | y <- rotaciones x
            , y `mod` 8 == 0]

--    rotaciones 1234  ==  [1234,2341,3412,4123]
rotaciones :: Integer -> [Integer]
rotaciones x = [read ys | ys <- rotacionesLista xs]
  where xs = show x

--    rotacionesLista "abcd"  ==  ["abcd","bcda","cdab","dabc"]
rotacionesLista :: [a] -> [[a]]
rotacionesLista xs =
  [zs ++ ys | k <- [0 .. length xs - 1]
            , let (ys,zs) = splitAt k xs] 

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

nRotacionesDivisiblesPor8b :: Integer -> Int
nRotacionesDivisiblesPor8b x =
  length [y | y <- tresDigitosConsecutivos x
            , y `mod` 8 == 0]

--    tresDigitosConsecutivos 1234  ==  [123,234,341,412]
tresDigitosConsecutivos :: Integer -> [Integer]
tresDigitosConsecutivos x =
  [read (take 3 ys) | ys <- rotacionesLista (show x)]

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

--    λ> nRotacionesDivisiblesPor8 (read (take (3*10^3) (cycle "248")))
--    2000
--    (3.59 secs, 4,449,162,144 bytes)
--    λ> nRotacionesDivisiblesPor8b (read (take (3*10^3) (cycle "248")))
--    2000
--    (0.48 secs, 593,670,656 bytes)

-- 1ª definición

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

nRotacionesDivisiblesPor8 :: Integer -> Int

nRotacionesDivisiblesPor8 x =

length [y | y <- rotaciones x

, y `mod` 8 == 0]

-- rotaciones 1234 == [1234,2341,3412,4123]

rotaciones :: Integer -> [Integer]

rotaciones x = [read ys | ys <- rotacionesLista xs]

where xs = show x

-- rotacionesLista "abcd" == ["abcd","bcda","cdab","dabc"]

rotacionesLista :: [a] -> [[a]]

rotacionesLista xs =

[zs ++ ys | k <- [0 .. length xs - 1]

, let (ys,zs) = splitAt k xs]

-- 2ª definición

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

nRotacionesDivisiblesPor8b :: Integer -> Int

nRotacionesDivisiblesPor8b x =

length [y | y <- tresDigitosConsecutivos x

, y `mod` 8 == 0]

-- tresDigitosConsecutivos 1234 == [123,234,341,412]

tresDigitosConsecutivos :: Integer -> [Integer]

tresDigitosConsecutivos x =

[read (take 3 ys) | ys <- rotacionesLista (show x)]

-- Comparación de eficiencia

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

-- λ> nRotacionesDivisiblesPor8 (read (take (3*10^3) (cycle "248")))

-- 2000

-- (3.59 secs, 4,449,162,144 bytes)

-- λ> nRotacionesDivisiblesPor8b (read (take (3*10^3) (cycle "248")))

-- 2000

-- (0.48 secs, 593,670,656 bytes)

Máximo de las rotaciones restringidas

PorJosé A. Alonso 6-diciembre-201713-diciembre-2017

Rotar un número a la iquierda significa pasar su primer dígito al final. Por ejemplo, rotando a la izquierda el 56789 se obtiene 67895.

Las rotaciones restringidas del número 56789 se obtienen como se indica a continución:

Se inicia con el propio número: 56789
El anterior se rota a la izquierda y se obtiene el 67895.
Del anterior se fija el primer dígito y se rota a la iquierda los otros. Se obtiene 68957.
Del anterior se fijan los 2 primeros dígito y se rota a la iquierda los otros. Se obtiene 68579.
Del anterior se fijan los 3 primeros dígito y se rota a la iquierda los otros. Se obtiene 68597.

El proceso ha terminado ya que conservando los cuatro primeros queda sólo un dígito que al girar es él mismo. Por tanto, la sucesión de las rotaciones restringidas de 56789 es

   56789 -> 67895 -> 68957 -> 68579 -> 68597

1	56789 -> 67895 -> 68957 -> 68579 -> 68597

y su mayor elemento es 68957.

Definir la función

   maxRotaciones :: Integer -> Integer

1	maxRotaciones :: Integer -> Integer

tal que (maxRotaciones n) es el máximo de las rotaciones restringidas del número n. Por ejemplo,

   maxRotaciones 56789       ==  68957
   maxRotaciones 1347902468  ==  3790246814
   maxRotaciones 6           ==  6
   maxRotaciones 2017        ==  2017

maxRotaciones 56789 == 68957

maxRotaciones 1347902468 == 3790246814

maxRotaciones 6 == 6

maxRotaciones 2017 == 2017

Soluciones

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

maxRotaciones :: Integer -> Integer
maxRotaciones = read . aux . show
  where aux n@[_]        = n
        aux n@(x1:x2:xs) = max n (x2:aux (xs ++ [x1]))

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

maxRotaciones2 :: Integer -> Integer
maxRotaciones2 n
  | n < 10    = n
  | otherwise = maximum [ read (us ++ vs)
                        | (us,vs) <- take m (iterate siguiente ("",xs)) ]
  where xs = show n
        m  = length xs

-- siguiente ("","56789")  ==  ("6","7895")
-- siguiente ("6","7895")  ==  ("68","957")
-- siguiente ("68","957")  ==  ("685","79")
-- siguiente ("685","79")  ==  ("6859","7")
-- siguiente ("6859","7")  ==  ("6859","7")
siguiente :: (String,String) -> (String,String)
siguiente (xs,a:b:ys) = (xs ++ [b], ys ++ [a])
siguiente (xs,[a])    = (xs,[a])

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

maxRotaciones3 :: Integer -> Integer
maxRotaciones3 = read . aux . show
  where aux (x:y:xs) | x > y     = x : y : xs
                     | otherwise = y : (aux $ xs ++ [x])
        aux [x]                  = [x]
        aux _                    = []

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

--    λ> length (show (maxRotaciones (n (5*10^3))))
--    5001
--    (2.74 secs, 802,282,616 bytes)
--    λ> length (show (maxRotaciones2 (n (5*10^3))))
--    5001
--    (18.23 secs, 12,375,579,216 bytes)
--    λ> length (show (maxRotaciones3 (n (5*10^3))))
--    5001
--    (0.67 secs, 729,155,056 bytes)

-- 1ª solución

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

maxRotaciones :: Integer -> Integer

maxRotaciones = read . aux . show

where aux n@[_] = n

aux n@(x1:x2:xs) = max n (x2:aux (xs ++ [x1]))

-- 2ª solución

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

maxRotaciones2 :: Integer -> Integer

maxRotaciones2 n

| n < 10 = n

| otherwise = maximum [ read (us ++ vs)

| (us,vs) <- take m (iterate siguiente ("",xs)) ]

where xs = show n

m = length xs

-- siguiente ("","56789") == ("6","7895")

-- siguiente ("6","7895") == ("68","957")

-- siguiente ("68","957") == ("685","79")

-- siguiente ("685","79") == ("6859","7")

-- siguiente ("6859","7") == ("6859","7")

siguiente :: (String,String) -> (String,String)

siguiente (xs,a:b:ys) = (xs ++ [b], ys ++ [a])

siguiente (xs,[a]) = (xs,[a])

-- 3ª solución

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

maxRotaciones3 :: Integer -> Integer

maxRotaciones3 = read . aux . show

where aux (x:y:xs) | x > y = x : y : xs

| otherwise = y : (aux $ xs ++ [x])

aux [x] = [x]

aux _ = []

-- Comparación de eficiencia

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

-- λ> length (show (maxRotaciones (n (5*10^3))))

-- 5001

-- (2.74 secs, 802,282,616 bytes)

-- λ> length (show (maxRotaciones2 (n (5*10^3))))

-- 5001

-- (18.23 secs, 12,375,579,216 bytes)

-- λ> length (show (maxRotaciones3 (n (5*10^3))))

-- 5001

-- (0.67 secs, 729,155,056 bytes)

Menor x tal que los x múltiplos de n contienen todos los dígitos

PorJosé A. Alonso 28-noviembre-20178-diciembre-2017

Definir la función

   menorX :: Integer -> Integer

1	menorX :: Integer -> Integer

tal que (menorX n) es el menor x tal que entre los x primeros múltiplos de n (es decir, entre n, 2×n, 3×n, … y x×n) contienen todos los dígitos al menos una vez. Por ejemplo, (menorX 92) es 6 ya que

   92                                    contiene  [2,9]
   92 y 92×2                             contienen [1,2,4,8,9]
   92,  92×2 y 92×3                      contienen [1,2,4,6,7,8,9]
   92,  92×2,  92×3 y 92×4               contienen [1,2,3,4,6,7,8,9]
   92,  92×2,  92×3,  92×4 y 92×5        contienen [0,1,2,3,4,6,7,8,9]
   92,  92×2,  92×3,  92×4,  92×5 y 92×6 contienen [0,1,2,3,4,5,6,7,8,9]

92 contiene [2,9]

92 y 92×2 contienen [1,2,4,8,9]

92, 92×2 y 92×3 contienen [1,2,4,6,7,8,9]

92, 92×2, 92×3 y 92×4 contienen [1,2,3,4,6,7,8,9]

92, 92×2, 92×3, 92×4 y 92×5 contienen [0,1,2,3,4,6,7,8,9]

92, 92×2, 92×3, 92×4, 92×5 y 92×6 contienen [0,1,2,3,4,5,6,7,8,9]

Otros ejemplos

   menorX 92          ==  6
   menorX 2967        ==  3
   menorX 266         ==  4
   menorX 18          ==  5
   menorX 2           ==  45
   menorX 125         ==  72
   menorX 1234567890  ==  1
   maximum [menorX n | n <- [1..3000]]  ==  72
   minimum [menorX n | n <- [1..3000]]  ==  3

menorX 92 == 6

menorX 2967 == 3

menorX 266 == 4

menorX 18 == 5

menorX 2 == 45

menorX 125 == 72

menorX 1234567890 == 1

maximum [menorX n | n <- [1..3000]] == 72

minimum [menorX n | n <- [1..3000]] == 3

Soluciones

import Data.List ((\\))

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

menorX :: Integer -> Integer
menorX n =
  head [x | x <- [1..]
          , [0..9] `contenido` digitosMultiplos n x]

contenido :: Eq a => [a] -> [a] -> Bool
contenido xs ys =
  all (`elem` ys) xs

digitosMultiplos :: Integer -> Integer -> [Integer]
digitosMultiplos n x =
  concatMap digitos [n,2*n..x*n]

digitos :: Integer -> [Integer]
digitos n =
  [read [c] | c <- show n]

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

menorX2 :: Integer -> Integer
menorX2 n = aux [] 0
  where aux xs x
          | [0..9] `contenido` xs = x
          | otherwise             = aux (digitos (n*(x+1)) ++ xs) (x+1)

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

menorX3 :: Integer -> Integer
menorX3 n = aux ['0'..'9'] 0
  where aux xs x
          | null xs   = x
          | otherwise = aux (xs \\ show (n*(x+1))) (x+1)

-- 4ª definición
-- =============

menorX4 :: Integer -> Integer
menorX4 n = aux "0123456789" 1 n
  where aux xs x nx | null ys   = x
                    | otherwise = aux ys (1+x) (nx+n)
          where ys = xs \\ show nx

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

--    λ> maximum [menorX n | n <- [1..6000]]
--    72
--    (2.04 secs, 3,737,579,888 bytes)
--    λ> maximum [menorX2 n | n <- [1..6000]]
--    72
--    (0.52 secs, 818,602,736 bytes)
--    λ> maximum [menorX3 n | n <- [1..6000]]
--    72
--    (0.10 secs, 67,090,800 bytes)
--    λ> maximum [menorX3 n | n <- [1..6000]]
--    72
--    (0.08 secs, 67,090,800 bytes)
--    
--    λ> maximum [menorX3 n | n <- [1..10^5]]
--    72
--    (0.81 secs, 1,044,781,216 bytes)
--    λ> maximum [menorX4 n | n <- [1..10^5]]
--    72
--    (0.71 secs, 1,009,113,304 bytes)

import Data.List ((\\))

-- 1ª definición

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

menorX :: Integer -> Integer

menorX n =

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

, [0..9] `contenido` digitosMultiplos n x]

contenido :: Eq a => [a] -> [a] -> Bool

contenido xs ys =

all (`elem` ys) xs

digitosMultiplos :: Integer -> Integer -> [Integer]

digitosMultiplos n x =

concatMap digitos [n,2*n..x*n]

digitos :: Integer -> [Integer]

digitos n =

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

-- 2ª definición

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

menorX2 :: Integer -> Integer

menorX2 n = aux [] 0

where aux xs x

| [0..9] `contenido` xs = x

| otherwise = aux (digitos (n*(x+1)) ++ xs) (x+1)

-- 3ª definición

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

menorX3 :: Integer -> Integer

menorX3 n = aux ['0'..'9'] 0

where aux xs x

| null xs = x

| otherwise = aux (xs \\ show (n*(x+1))) (x+1)

-- 4ª definición

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

menorX4 :: Integer -> Integer

menorX4 n = aux "0123456789" 1 n

where aux xs x nx | null ys = x

| otherwise = aux ys (1+x) (nx+n)

where ys = xs \\ show nx

-- Comparación de eficiencia

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

-- λ> maximum [menorX n | n <- [1..6000]]

-- 72

-- (2.04 secs, 3,737,579,888 bytes)

-- λ> maximum [menorX2 n | n <- [1..6000]]

-- 72

-- (0.52 secs, 818,602,736 bytes)

-- λ> maximum [menorX3 n | n <- [1..6000]]

-- 72

-- (0.10 secs, 67,090,800 bytes)

-- λ> maximum [menorX3 n | n <- [1..6000]]

-- 72

-- (0.08 secs, 67,090,800 bytes)

-- λ> maximum [menorX3 n | n <- [1..10^5]]

-- 72

-- (0.81 secs, 1,044,781,216 bytes)

-- λ> maximum [menorX4 n | n <- [1..10^5]]

-- 72

-- (0.71 secs, 1,009,113,304 bytes)

Sucesión contadora

PorJosé A. Alonso 22-noviembre-201726-marzo-2022

Definir las siguientes funciones

   numeroContado           :: Integer -> Integer
   contadora               :: Integer -> [Integer]
   lugarPuntoFijoContadora :: Integer -> Integer -> Maybe Integer

numeroContado :: Integer -> Integer

contadora :: Integer -> [Integer]

lugarPuntoFijoContadora :: Integer -> Integer -> Maybe Integer

tales que

(numeroContado n) es el número obtenido al contar las repeticiones de cada una de las cifras de n. Por ejemplo,

     numeroContado 1                 == 11
     numeroContado 114213            == 31121314
     numeroContado 1111111111111111  == 161
     numeroContado 555555555500      == 20105

numeroContado 1 == 11

numeroContado 114213 == 31121314

numeroContado 1111111111111111 == 161

numeroContado 555555555500 == 20105

(contadora n) es la sucesión cuyo primer elemento es n y los restantes se obtienen contando el número anterior de la sucesión. Por ejemplo,

     λ> take 14 (contadora 1)
     [1,11,21,1112,3112,211213,312213,212223,114213,31121314,41122314,
      31221324,21322314,21322314]
     λ> take 14 (contadora 5)
     [5,15,1115,3115,211315,31121315,41122315,3122131415,4122231415,
      3132132415,3122331415,3122331415,3122331415,3122331415]

λ> take 14 (contadora 1)

[1,11,21,1112,3112,211213,312213,212223,114213,31121314,41122314,

31221324,21322314,21322314]

λ> take 14 (contadora 5)

[5,15,1115,3115,211315,31121315,41122315,3122131415,4122231415,

3132132415,3122331415,3122331415,3122331415,3122331415]

(lugarPuntoFijoContadora n k) es el menor i <= k tal que son iguales los elementos en las posiciones i e i+1 de la sucesión contadora que cominza con n. Por ejemplo,

      λ> lugarPuntoFijoContadora 1 100
      Just 12
      λ> contadora 1 !! 11
      31221324
      λ> contadora 1 !! 12
      21322314
      λ> contadora 1 !! 13
      21322314
      λ> lugarPuntoFijoContadora 1 10
      Nothing
      λ> lugarPuntoFijoContadora 5 20
      Just 10
      λ> lugarPuntoFijoContadora 40 200
      Nothing

λ> lugarPuntoFijoContadora 1 100

Just 12

λ> contadora 1 !! 11

31221324

λ> contadora 1 !! 12

21322314

λ> contadora 1 !! 13

21322314

λ> lugarPuntoFijoContadora 1 10

Nothing

λ> lugarPuntoFijoContadora 5 20

Just 10

λ> lugarPuntoFijoContadora 40 200

Nothing

Nota: Este ejercicio ha sido propuesto por Ángel Ruiz.

Soluciones

import Data.List ( genericLength
                 , genericTake
                 , group
                 , nub
                 , sort
                 )

-- Definición de numeroContado
numeroContado :: Integer -> Integer
numeroContado n =
  (read . concat . map concat) [[(show . length) m,nub m]
                               | m <- (group . sort . show) n]

-- 1ª definición de contadora
contadora :: Integer -> [Integer]
contadora n = n : map numeroContado (contadora n)

-- 2ª definición de contadora
contadora2 :: Integer ->  [Integer]
contadora2 = iterate numeroContado 

-- Definición de lugarPuntoFijoContadora
lugarPuntoFijoContadora :: Integer -> Integer -> Maybe Integer
lugarPuntoFijoContadora n k
  | m == k-1  = Nothing
  | otherwise = Just m
  where xs = genericTake k (contadora n)
        ds = zipWith (-) xs (tail xs)
        m  = genericLength (takeWhile (/=0) ds)

import Data.List ( genericLength

, genericTake

, group

, nub

, sort

)

-- Definición de numeroContado

numeroContado :: Integer -> Integer

numeroContado n =

(read . concat . map concat) [[(show . length) m,nub m]

| m <- (group . sort . show) n]

-- 1ª definición de contadora

contadora :: Integer -> [Integer]

contadora n = n : map numeroContado (contadora n)

-- 2ª definición de contadora

contadora2 :: Integer -> [Integer]

contadora2 = iterate numeroContado

-- Definición de lugarPuntoFijoContadora

lugarPuntoFijoContadora :: Integer -> Integer -> Maybe Integer

lugarPuntoFijoContadora n k

| m == k-1 = Nothing

| otherwise = Just m

where xs = genericTake k (contadora n)

ds = zipWith (-) xs (tail xs)

m = genericLength (takeWhile (/=0) ds)

Cadenas de sumas de factoriales de los dígitos

PorJosé A. Alonso 17-noviembre-201725-noviembre-2017

Dado un número n se considera la sucesión cuyo primer término es n y los restantes se obtienen sumando los factoriales de los dígitos del anterior. Por ejemplo, la sucesión que empieza en 69 es

         69
     363600  (porque 6! + 9! = 363600)  
       1454  (porque 3! + 6! + 3! + 6! + 0! + 0! = 1454)
        169  (porque 1! + 4! + 5! + 4! = 169)
     363601  (porque 1! + 6! + 9! = 363601)
       1454  (porque 3! + 6! + 3! + 6! + 0! + 1! = 1454)
     ......

363600 (porque 6! + 9! = 363600)

1454 (porque 3! + 6! + 3! + 6! + 0! + 0! = 1454)

169 (porque 1! + 4! + 5! + 4! = 169)

363601 (porque 1! + 6! + 9! = 363601)

1454 (porque 3! + 6! + 3! + 6! + 0! + 1! = 1454)

......

La cadena correspondiente a un número n son los términos de la sucesión que empieza en n hasta la primera repetición de un elemento en la sucesión. Por ejemplo, la cadena de 69 es

   [69,363600,1454,169,363601,1454]

1	[69,363600,1454,169,363601,1454]

Consta de una parte no periódica ([69,363600]) y de una periódica ([1454,169,363601]).

Definir las funciones

   cadena  :: Integer -> [Integer]
   periodo :: Integer -> [Integer]

1 2	cadena :: Integer -> [Integer] periodo :: Integer -> [Integer]

tales que

(cadena n es la cadena correspondiente al número n. Por ejemplo,

      cadena 69    ==  [69,363600,1454,169,363601,1454]
      cadena 145   ==  [145,145]
      cadena 78    ==  [78,45360,871,45361,871]
      cadena 569   ==  [569,363720,5775,10320,11,2,2]
      cadena 3888  ==  [3888,120966,364324,782,45362,872,45362]
      maximum [length (cadena n) | n <- [1..5000]]  ==  61
      length (cadena 1479)                          ==  61

cadena 69 == [69,363600,1454,169,363601,1454]

cadena 145 == [145,145]

cadena 78 == [78,45360,871,45361,871]

cadena 569 == [569,363720,5775,10320,11,2,2]

cadena 3888 == [3888,120966,364324,782,45362,872,45362]

maximum [length (cadena n) | n <- [1..5000]] == 61

length (cadena 1479) == 61

(periodo n) es la parte periódica de la cadena de n. Por ejemplo,

      periodo 69    ==  [169,363601,1454]
      periodo 145   ==  [145]
      periodo 78    ==  [45361,871]
      periodo 569   ==  [2]
      periodo 3888  ==  [872,45362]
      maximum [length (periodo n) | n <- [1..5000]]  ==  3
      length (periodo 1479)                          ==  3

periodo 69 == [169,363601,1454]

periodo 145 == [145]

periodo 78 == [45361,871]

periodo 569 == [2]

periodo 3888 == [872,45362]

maximum [length (periodo n) | n <- [1..5000]] == 3

length (periodo 1479) == 3

Soluciones

-- Definición de cadena
-- ====================

cadena :: Integer -> [Integer]
cadena n = reverse (extension [n])

extension :: [Integer] -> [Integer]
extension (n:ns)
  | m `elem` (n:ns) = m : n : ns
  | otherwise       = extension (m : n : ns)
  where m = siguiente n

siguiente :: Integer -> Integer
siguiente n =
  sum [factorial d | d <- digitos n]

factorial :: Integer -> Integer
factorial n =
  product [1..n]

digitos :: Integer -> [Integer]
digitos n =
  [read [c] | c <- show n]

-- Definición de periodo
-- =====================

periodo :: Integer -> [Integer]
periodo n =
  reverse (x : takeWhile (/= x) xs)
  where (x:xs) = reverse (cadena n)

-- Definición de cadena

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

cadena :: Integer -> [Integer]

cadena n = reverse (extension [n])

extension :: [Integer] -> [Integer]

extension (n:ns)

| m `elem` (n:ns) = m : n : ns

| otherwise = extension (m : n : ns)

where m = siguiente n

siguiente :: Integer -> Integer

siguiente n =

sum [factorial d | d <- digitos n]

factorial :: Integer -> Integer

factorial n =

product [1..n]

digitos :: Integer -> [Integer]

digitos n =

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

-- Definición de periodo

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

periodo :: Integer -> [Integer]

periodo n =

reverse (x : takeWhile (/= x) xs)

where (x:xs) = reverse (cadena n)

Números dígito potenciales

PorJosé A. Alonso 15-noviembre-201725-noviembre-2017

Un número entero x es dígito potencial de orden n si x es la suma de los dígitos de x elevados a n. Por ejemplo,

153 es un dígito potencial de orden 3 ya que 153 = 1^3+5^3+3^3
4150 es un dígito potencial de orden 5 ya que 4150 = 4^5+1^5+5^5+0^5

Un número x es dígito auto potencial si es un dígito potencial de orden n, donde n es el número de dígitos de n. Por ejemplo, 153 es un número dígito auto potencial.

Definir las funciones

   digitosPotencialesOrden :: Integer -> [Integer]
   digitosAutoPotenciales  :: [Integer]

1 2	digitosPotencialesOrden :: Integer -> [Integer] digitosAutoPotenciales :: [Integer]

tales que

(digitosPotencialesOrden n) es la lista de los números dígito potenciales de orden n. Por ejemplo,

     take 6 (digitosPotencialesOrden 3)  ==  [0,1,153,370,371,407]
     take 5 (digitosPotencialesOrden 4)  ==  [0,1,1634,8208,9474]
     take 8 (digitosPotencialesOrden 5)  ==  [0,1,4150,4151,54748,92727,93084,194979]
     take 3 (digitosPotencialesOrden 6)  ==  [0,1,548834]

take 6 (digitosPotencialesOrden 3) == [0,1,153,370,371,407]

take 5 (digitosPotencialesOrden 4) == [0,1,1634,8208,9474]

take 8 (digitosPotencialesOrden 5) == [0,1,4150,4151,54748,92727,93084,194979]

take 3 (digitosPotencialesOrden 6) == [0,1,548834]

digitosAutoPotenciales es la lista de los números dígito auto potenciales. Por ejemplo,

     λ> take 20 digitosAutoPotenciales
     [0,1,2,3,4,5,6,7,8,9,153,370,371,407,1634,8208,9474,54748,92727,93084]

1 2	λ> take 20 digitosAutoPotenciales [0,1,2,3,4,5,6,7,8,9,153,370,371,407,1634,8208,9474,54748,92727,93084]

Soluciones

import Data.List (genericLength)
import Data.Char (digitToInt)

-- 1ª definición de digitosPotencialesOrden
-- ========================================

digitosPotencialesOrden :: Integer -> [Integer]
digitosPotencialesOrden n =
  [x | x <- [0..]
     , esDigitoPotencialOrden n x]

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

digitos :: Integer -> [Integer]
digitos x = [read [d] | d <- show x] 

-- 2ª definición de digitosPotencialesOrden
-- ========================================

digitosPotencialesOrden2 :: Integer -> [Integer]
digitosPotencialesOrden2 n =
  filter (esDigitoPotencialOrden2 n) [0..]

esDigitoPotencialOrden2 :: Integer -> Integer -> Bool
esDigitoPotencialOrden2 n x =
  x == sum (map (^n) (digitos2 x))

digitos2 :: Integer -> [Integer]
digitos2 = map (toInteger . digitToInt) . show

-- 3ª definición de digitosPotencialesOrden
-- ========================================

--    digitosPotencialesOrden3 3  ==  [0,1,153,370,371,407]
--    digitosPotencialesOrden3 4  ==  [0,1,1634,8208,9474]
digitosPotencialesOrden3 :: Integer -> [Integer]
digitosPotencialesOrden3 n =
  filter (esDigitoPotencialOrden2 n) [0..10^d-1]
  where d = maximoNDigitosPotencialesOrden n 

-- (maximoNDigitosPotencialesOrden n) es el máximo número de dígitos de
-- los números dígitos potenciales de orden d. Por ejemplo,
--    maximoNDigitosPotencialesOrden 3  ==  5
--    maximoNDigitosPotencialesOrden 5  ==  7
maximoNDigitosPotencialesOrden :: Integer -> Integer
maximoNDigitosPotencialesOrden n =
  head (dropWhile (\d -> d*9^n >= 10^(d-1)) [1..])

-- 1ª definición de esDigitoAutoPotencial
-- ======================================

esDigitoAutoPotencial :: Integer -> Bool
esDigitoAutoPotencial x =
  esDigitoPotencialOrden (genericLength (show x)) x

digitosAutoPotenciales :: [Integer]
digitosAutoPotenciales =
  filter esDigitoAutoPotencial [0..]

-- 2ª definición de esDigitoAutoPotencial
-- ======================================

digitosAutoPotenciales2 :: [Integer]
digitosAutoPotenciales2 =
  0: concat [[x | x <- [10^k..10^(k+1)-1], esDigitoPotencialOrden (k+1) x]
            | k <- [0..]]

import Data.List (genericLength)

import Data.Char (digitToInt)

-- 1ª definición de digitosPotencialesOrden

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

digitosPotencialesOrden :: Integer -> [Integer]

digitosPotencialesOrden n =

[x | x <- [0..]

, esDigitoPotencialOrden n x]

esDigitoPotencialOrden :: Integer -> Integer -> Bool

esDigitoPotencialOrden n x =

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

digitos :: Integer -> [Integer]

digitos x = [read [d] | d <- show x]

-- 2ª definición de digitosPotencialesOrden

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

digitosPotencialesOrden2 :: Integer -> [Integer]

digitosPotencialesOrden2 n =

filter (esDigitoPotencialOrden2 n) [0..]

esDigitoPotencialOrden2 :: Integer -> Integer -> Bool

esDigitoPotencialOrden2 n x =

x == sum (map (^n) (digitos2 x))

digitos2 :: Integer -> [Integer]

digitos2 = map (toInteger . digitToInt) . show

-- 3ª definición de digitosPotencialesOrden

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

-- digitosPotencialesOrden3 3 == [0,1,153,370,371,407]

-- digitosPotencialesOrden3 4 == [0,1,1634,8208,9474]

digitosPotencialesOrden3 :: Integer -> [Integer]

digitosPotencialesOrden3 n =

filter (esDigitoPotencialOrden2 n) [0..10^d-1]

where d = maximoNDigitosPotencialesOrden n

-- (maximoNDigitosPotencialesOrden n) es el máximo número de dígitos de

-- los números dígitos potenciales de orden d. Por ejemplo,

-- maximoNDigitosPotencialesOrden 3 == 5

-- maximoNDigitosPotencialesOrden 5 == 7

maximoNDigitosPotencialesOrden :: Integer -> Integer

maximoNDigitosPotencialesOrden n =

head (dropWhile (\d -> d*9^n >= 10^(d-1)) [1..])

-- 1ª definición de esDigitoAutoPotencial

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

esDigitoAutoPotencial :: Integer -> Bool

esDigitoAutoPotencial x =

esDigitoPotencialOrden (genericLength (show x)) x

digitosAutoPotenciales :: [Integer]

digitosAutoPotenciales =

filter esDigitoAutoPotencial [0..]

-- 2ª definición de esDigitoAutoPotencial

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

digitosAutoPotenciales2 :: [Integer]

digitosAutoPotenciales2 =

0: concat [[x | x <- [10^k..10^(k+1)-1], esDigitoPotencialOrden (k+1) x]

| k <- [0..]]

Mayor número equidigital

PorJosé A. Alonso 14-noviembre-201721-noviembre-2017

Definir la función

   mayorEquidigital :: Integer -> Integer

1	mayorEquidigital :: Integer -> Integer

tal que (mayorEquidigital x) es el mayor número que se puede contruir con los dígitos de x. Por ejemplo,

   mayorEquidigital 13112017  ==  73211110
   mayorEquidigital2 (2^100)  ==  9987776666655443322222211000000

1 2	mayorEquidigital 13112017 == 73211110 mayorEquidigital2 (2^100) == 9987776666655443322222211000000

Soluciones

import Data.List (sort, permutations)

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

mayorEquidigital1 :: Integer -> Integer
mayorEquidigital1 =
  maximum . equidigitales

-- (equidigitales x) es la lista de los números que se pueden contruir
-- con los dígitos de x. Por ejemplo, 
--    equidigitales 325  ==  [325,235,523,253,532,352]
equidigitales :: Integer -> [Integer]
equidigitales x =
  [read ys | ys <- permutations ds]
  where ds = show x

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

mayorEquidigital2 :: Integer -> Integer
mayorEquidigital2 = read . reverse . sort . show 

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

--    λ> mayorEquidigital1 (2^30)
--    8774432110
--    (11.77 secs, 26,334,106,664 bytes)
--    λ> mayorEquidigital2 (2^30)
--    8774432110
--    (0.00 secs, 156,800 bytes)

import Data.List (sort, permutations)

-- 1ª solución

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

mayorEquidigital1 :: Integer -> Integer

mayorEquidigital1 =

maximum . equidigitales

-- (equidigitales x) es la lista de los números que se pueden contruir

-- con los dígitos de x. Por ejemplo,

-- equidigitales 325 == [325,235,523,253,532,352]

equidigitales :: Integer -> [Integer]

equidigitales x =

[read ys | ys <- permutations ds]

where ds = show x

-- 2ª solución

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

mayorEquidigital2 :: Integer -> Integer

mayorEquidigital2 = read . reverse . sort . show

-- Comparación de eficiencia

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

-- λ> mayorEquidigital1 (2^30)

-- 8774432110

-- (11.77 secs, 26,334,106,664 bytes)

-- λ> mayorEquidigital2 (2^30)

-- 8774432110

-- (0.00 secs, 156,800 bytes)

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)

Subnúmeros pares

PorJosé A. Alonso 18-abril-201725-abril-2017

Los subnúmeros de un número x son los números que se pueden formar con dígitos de x en posiciones consecutivas. Por ejemplo, el número 254 tiene 6 subnúmeros: 2, 5, 4, 25, 54 y 254.

Definir las funciones

   subnumeros       :: Integer -> [Integer]
   nSubnumerosPares :: Integer -> Integer

1 2	subnumeros :: Integer -> [Integer] nSubnumerosPares :: Integer -> Integer

tales que

(subnumerosPares x) es la lista de los subnúmeros pares de x. Por ejemplo,

     subnumerosPares 254   ==  [2,254,54,4]
     subnumerosPares 154   ==  [154,54,4]
     subnumerosPares 15    ==  []

subnumerosPares 254 == [2,254,54,4]

subnumerosPares 154 == [154,54,4]

subnumerosPares 15 == []

(nSubnumerosPares x) es la cantidad de subnúmeros pares de x. Por ejemplo,

     nSubnumerosPares 254   ==  4
     nSubnumerosPares2 (4^(10^6))  ==  90625258498

1 2	nSubnumerosPares 254 == 4 nSubnumerosPares2 (4^(10^6)) == 90625258498

Soluciones

import Data.List ( genericLength
                 , inits
                 , tails
                 )

subnumerosPares :: Integer -> [Integer]
subnumerosPares n =
  filter even (subnumeros n)

-- (subnumeros n) es la lista de los subnúmeros de n. Por ejemplo,
--    subnumeros 254  ==  [2,25,5,254,54,4]
subnumeros :: Integer -> [Integer]
subnumeros n =
  [read x | x <- sublistas (show n)]

-- (sublistas xs) es la lista de las sublistas de xs. Por ejemplo, 
--    sublistas "abc"  ==  ["a","ab","b","abc","bc","c"]
sublistas :: [a] -> [[a]]
sublistas xs =
  concat [init (tails ys) | ys <- tail (inits xs)]

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

nSubnumerosPares :: Integer -> Integer
nSubnumerosPares =
  genericLength . subnumerosPares

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

nSubnumerosPares2 :: Integer -> Integer
nSubnumerosPares2 =
  sum . posicionesDigitosPares 

-- (posicionesDigitosPares x) es la lista de las posiciones de los
-- dígitos pares de x. Por ejemplo,
--    posicionesDigitosPares 254  ==  [1,3]
posicionesDigitosPares :: Integer -> [Integer]
posicionesDigitosPares x =
  [n | (n,y) <- zip [1..] (show x)
     , y `elem` "02468"]

-- Comparación de eficiencia
--    λ> nSubnumerosPares (2^(10^3))
--    22934
--    (2.83 secs, 3,413,414,872 bytes)
--    λ> nSubnumerosPares2 (2^(10^3))
--    22934
--    (0.01 secs, 0 bytes)

import Data.List ( genericLength

, inits

, tails

)

subnumerosPares :: Integer -> [Integer]

subnumerosPares n =

filter even (subnumeros n)

-- (subnumeros n) es la lista de los subnúmeros de n. Por ejemplo,

-- subnumeros 254 == [2,25,5,254,54,4]

subnumeros :: Integer -> [Integer]

subnumeros n =

[read x | x <- sublistas (show n)]

-- (sublistas xs) es la lista de las sublistas de xs. Por ejemplo,

-- sublistas "abc" == ["a","ab","b","abc","bc","c"]

sublistas :: [a] -> [[a]]

sublistas xs =

concat [init (tails ys) | ys <- tail (inits xs)]

-- 1ª definición

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

nSubnumerosPares :: Integer -> Integer

nSubnumerosPares =

genericLength . subnumerosPares

-- 2ª definición

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

nSubnumerosPares2 :: Integer -> Integer

nSubnumerosPares2 =

sum . posicionesDigitosPares

-- (posicionesDigitosPares x) es la lista de las posiciones de los

-- dígitos pares de x. Por ejemplo,

-- posicionesDigitosPares 254 == [1,3]

posicionesDigitosPares :: Integer -> [Integer]

posicionesDigitosPares x =

[n | (n,y) <- zip [1..] (show x)

, y `elem` "02468"]

-- Comparación de eficiencia

-- λ> nSubnumerosPares (2^(10^3))

-- 22934

-- (2.83 secs, 3,413,414,872 bytes)

-- λ> nSubnumerosPares2 (2^(10^3))

-- 22934

-- (0.01 secs, 0 bytes)

Rotaciones divisibles por 4

PorJosé A. Alonso 3-abril-201710-abril-2017

Las rotaciones de 928160 son 928160, 281609, 816092, 160928, 609281 y 92816. De las cuales, las divisibles por 4 son 928160, 816092, 160928 y 92816.

Definir la función

   nRotacionesDivisibles :: Integer -> Int

1	nRotacionesDivisibles :: Integer -> Int

tal que (nRotacionesDivisibles n) es el número de rotaciones del número n divisibles por 4. Por ejemplo,

   nRotacionesDivisibles 928160          ==  4
   nRotacionesDivisibles 44              ==  2
   nRotacionesDivisibles (1234^50000)    ==  38684
   nRotacionesDivisibles (1234^300000)   ==  231853

nRotacionesDivisibles 928160 == 4

nRotacionesDivisibles 44 == 2

nRotacionesDivisibles (1234^50000) == 38684

nRotacionesDivisibles (1234^300000) == 231853

Soluciones

import Data.Char (digitToInt)

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

nRotacionesDivisibles :: Integer -> Int
nRotacionesDivisibles n =
  length [x | x <- rotacionesNumero n, x `mod` 4 == 0]


-- (rotacionesNumero) es la lista de la rotaciones del número n. Por
-- ejemplo,
--    rotacionesNumero 235  ==  [235,352,523]
rotacionesNumero :: Integer -> [Integer]
rotacionesNumero = map read . rotaciones . show

-- (rotaciones xs) es la lista de las rotaciones obtenidas desplazando
-- el primer elemento xs al final. Por ejemplo,
--    rotaciones [2,3,5]  ==  [[2,3,5],[3,5,2],[5,2,3]]
rotaciones :: [a] -> [[a]]
rotaciones xs = take (length xs) (iterate rota xs)

-- (rota xs) es la lista añadiendo el primer elemento de xs al
-- final. Por ejemplo, 
--    rota [3,2,5,7]  ==  [2,5,7,3]
rota :: [a] -> [a]
rota (x:xs) = xs ++ [x]

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

nRotacionesDivisibles2 :: Integer -> Int
nRotacionesDivisibles2 n = 
  length [x | x <- pares n, x `mod` 4 == 0]

-- (pares n) es la lista de pares de elementos consecutivos, incluyendo
-- el último con el primero. Por ejemplo,
--    pares 928160  ==  [9,92,28,81,16,60]
pares :: Integer -> [Int]
pares n =
  read [last ns,head ns] : [read [a,b] | (a,b) <- zip ns (tail ns)]
  where ns = show n

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

nRotacionesDivisibles3 :: Integer -> Int
nRotacionesDivisibles3 n =
  ( length
  . filter (0 ==)
  . map (`mod` 4)
  . zipWith (\x y -> 2*x + y) d
  . tail
  . (++[i])) d
  where
    d@(i:dn) = (map digitToInt . show) n

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

--    λ> nRotacionesDivisibles (123^1500)
--    803
--    (8.15 secs, 7,109,852,800 bytes)
--    λ> nRotacionesDivisibles2 (123^1500)
--    803
--    (0.05 secs, 0 bytes)
--    λ> nRotacionesDivisibles3 (123^1500)
--    803
--    (0.02 secs, 0 bytes)
--
--    λ> nRotacionesDivisibles2 (1234^50000)
--    38684
--    (2.24 secs, 1,160,467,472 bytes)
--    λ> nRotacionesDivisibles3 (1234^50000)
--    38684
--    (0.31 secs, 68,252,040 bytes)

import Data.Char (digitToInt)

-- 1ª definición

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

nRotacionesDivisibles :: Integer -> Int

nRotacionesDivisibles n =

length [x | x <- rotacionesNumero n, x `mod` 4 == 0]

-- (rotacionesNumero) es la lista de la rotaciones del número n. Por

-- ejemplo,

-- rotacionesNumero 235 == [235,352,523]

rotacionesNumero :: Integer -> [Integer]

rotacionesNumero = map read . rotaciones . show

-- (rotaciones xs) es la lista de las rotaciones obtenidas desplazando

-- el primer elemento xs al final. Por ejemplo,

-- rotaciones [2,3,5] == [[2,3,5],[3,5,2],[5,2,3]]

rotaciones :: [a] -> [[a]]

rotaciones xs = take (length xs) (iterate rota xs)

-- (rota xs) es la lista añadiendo el primer elemento de xs al

-- final. Por ejemplo,

-- rota [3,2,5,7] == [2,5,7,3]

rota :: [a] -> [a]

rota (x:xs) = xs ++ [x]

-- 2ª definición

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

nRotacionesDivisibles2 :: Integer -> Int

nRotacionesDivisibles2 n =

length [x | x <- pares n, x `mod` 4 == 0]

-- (pares n) es la lista de pares de elementos consecutivos, incluyendo

-- el último con el primero. Por ejemplo,

-- pares 928160 == [9,92,28,81,16,60]

pares :: Integer -> [Int]

pares n =

read [last ns,head ns] : [read [a,b] | (a,b) <- zip ns (tail ns)]

where ns = show n

-- 3ª definición

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

nRotacionesDivisibles3 :: Integer -> Int

nRotacionesDivisibles3 n =

( length

. filter (0 ==)

. map (`mod` 4)

. zipWith (\x y -> 2*x + y) d

. tail

. (++[i])) d

where

d@(i:dn) = (map digitToInt . show) n

-- Comparación de eficiencia

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

-- λ> nRotacionesDivisibles (123^1500)

-- 803

-- (8.15 secs, 7,109,852,800 bytes)

-- λ> nRotacionesDivisibles2 (123^1500)

-- 803

-- (0.05 secs, 0 bytes)

-- λ> nRotacionesDivisibles3 (123^1500)

-- 803

-- (0.02 secs, 0 bytes)

-- λ> nRotacionesDivisibles2 (1234^50000)

-- 38684

-- (2.24 secs, 1,160,467,472 bytes)

-- λ> nRotacionesDivisibles3 (1234^50000)

-- 38684

-- (0.31 secs, 68,252,040 bytes)

Distribución de diferencias de dígitos consecutivos de pi

PorJosé A. Alonso 14-marzo-201725-abril-2021

La distribución de las diferencias de los dígitos consecutivos para los 18 primeros dígitos de pi se calcula como sigue: los primeros 18 dígitos de pi son

   3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3

1	3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3

Las diferencias de sus elementos consecutivos es

   2, -3, 3, -4, -4, 7, -4, 1, 2, -2, -3, -1, 2, -2, 6, 1, -1

1	2, -3, 3, -4, -4, 7, -4, 1, 2, -2, -3, -1, 2, -2, 6, 1, -1

y la distribución de sus frecuencias en el intervalo [-9,9] es

   0, 0, 0, 0, 0, 3, 2, 2, 2, 0, 2, 3, 1, 0, 0, 1, 1, 0, 0

1	0, 0, 0, 0, 0, 3, 2, 2, 2, 0, 2, 3, 1, 0, 0, 1, 1, 0, 0

es decir, el desde el -9 a -5 no aparecen, el -4 aparece 3 veces, el -2 aparece 2 veces y así sucesivamente.

Definir las funciones

   distribucionDDCpi :: Int -> [Int]
   graficas :: [Int] -> FilePath -> IO ()

1 2	distribucionDDCpi :: Int -> [Int] graficas :: [Int] -> FilePath -> IO ()

tales que

(distribucionDDCpi n) es la distribución de las diferencias de los dígitos consecutivos para los primeros n dígitos de pi. Por ejemplo,

   λ> distribucionDDCpi 18
   [0,0,0,0,0,3,2,2,2,0,2,3,1,0,0,1,1,0,0]
   λ> distribucionDDCpi 100
   [1,2,1,7,7,7,6,5,8,6,7,14,4,9,3,6,4,1,0]
   λ> distribucionDDCpi 200
   [3,6,2,13,14,12,11,12,15,17,15,19,11,17,8,13,9,2,0]
   λ> distribucionDDCpi 1000
   [16,25,23,44,57,61,55,75,92,98,80,88,64,65,42,54,39,14,8]
   λ> distribucionDDCpi 5000
   [67,99,130,196,245,314,361,391,453,468,447,407,377,304,242,221,134,97,47]

λ> distribucionDDCpi 18

[0,0,0,0,0,3,2,2,2,0,2,3,1,0,0,1,1,0,0]

λ> distribucionDDCpi 100

[1,2,1,7,7,7,6,5,8,6,7,14,4,9,3,6,4,1,0]

λ> distribucionDDCpi 200

[3,6,2,13,14,12,11,12,15,17,15,19,11,17,8,13,9,2,0]

λ> distribucionDDCpi 1000

[16,25,23,44,57,61,55,75,92,98,80,88,64,65,42,54,39,14,8]

λ> distribucionDDCpi 5000

[67,99,130,196,245,314,361,391,453,468,447,407,377,304,242,221,134,97,47]

(graficas ns f) dibuja en el fichero f las gráficas de las distribuciones de las diferencias de los dígitos consecutivos para los primeros n dígitos de pi, para n en ns. Por ejemplo, al evaluar (graficas [100,250..4000] «distribucionDDCpi.png» se escribe en el fichero «distribucionDDCpi.png» la siguiente gráfica

Nota: Se puede usar la librería Data.Number.CReal.

Soluciones

import Data.Number.CReal
import Graphics.Gnuplot.Simple
import Data.Array

--    λ> digitosPi 18
--    [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3]
digitosPi :: Int -> [Int]
digitosPi n = init [read [c] | c <- (x:xs)]
  where (x:_:xs) = showCReal n pi

--    λ> diferenciasConsecutivos (digitosPi 18)
--    [2,-3,3,-4,-4,7,-4,1,2,-2,-3,-1,2,-2,6,1,-1]
diferenciasConsecutivos :: Num a => [a] -> [a]
diferenciasConsecutivos xs =
  zipWith (-) xs (tail xs)

distribucionDDCpi :: Int -> [Int]
distribucionDDCpi =
  distribucion . diferenciasConsecutivos . digitosPi
  where distribucion xs =
          elems (accumArray (+) 0 (-9,9) (zip xs (repeat 1)))

graficas :: [Int] -> FilePath -> IO ()
graficas ns f = 
  plotLists [Key Nothing, PNG f]
            [puntos n | n <- ns]
  where puntos :: Int -> [(Int,Int)]
        puntos n = zip [-9..9] (distribucionDDCpi n)

import Data.Number.CReal

import Graphics.Gnuplot.Simple

import Data.Array

-- λ> digitosPi 18

-- [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3]

digitosPi :: Int -> [Int]

digitosPi n = init [read [c] | c <- (x:xs)]

where (x:_:xs) = showCReal n pi

-- λ> diferenciasConsecutivos (digitosPi 18)

-- [2,-3,3,-4,-4,7,-4,1,2,-2,-3,-1,2,-2,6,1,-1]

diferenciasConsecutivos :: Num a => [a] -> [a]

diferenciasConsecutivos xs =

zipWith (-) xs (tail xs)

distribucionDDCpi :: Int -> [Int]

distribucionDDCpi =

distribucion . diferenciasConsecutivos . digitosPi

where distribucion xs =

elems (accumArray (+) 0 (-9,9) (zip xs (repeat 1)))

graficas :: [Int] -> FilePath -> IO ()

graficas ns f =

plotLists [Key Nothing, PNG f]

[puntos n | n <- ns]

where puntos :: Int -> [(Int,Int)]

puntos n = zip [-9..9] (distribucionDDCpi n)

Contando en la arena

PorJosé A. Alonso 2-marzo-20179-marzo-2017

El problema de ayer de ¡Acepta el reto! fue Contando en la arena cuyo enunciado es el siguiente:

Es ampliamente conocido que escribimos los números utilizando base 10, en la que expresamos las cantidades utilizando 10 dígitos distintos (0…9). El valor de cada uno de ellos depende de la posición que ocupe dentro del número, pues cada dígito se multiplica por una potencia de 10 distinta según cuál sea esa posición.

La descomposición, por ejemplo, del número 1.234 es: 1.234 = 1×10^3 + 2×10^2 + 3×10^1 + 4×10^0

Otra base muy conocida es la base 2 al ser la utilizada por los dispositivos electrónicos. En ella sólo hay dos dígitos distintos (0 y 1), que se ven multiplicados por potencias de 2.

Mucho antes de que llegaran la base 2, la base 10 e incluso los números romanos, los primeros seres humanos contaban haciendo surcos en la arena, muescas en un trozo de madera o colocando palos en línea. Estaban, sin saberlo, usando base 1. En ella sólo hay un símbolo y cada dígito es multiplicado por una potencia de 1. Dado que 1^n = 1 el resultado es que todos los dígitos tienen el mismo peso.

Definir la función

   transformaAbase1 :: FilePath -> FilePath -> IO ()

1	transformaAbase1 :: FilePath -> FilePath -> IO ()

tal que al evaluar (transformaAbase1 f1 f2) lee el contenido del fichero f1 (que estará compuesto por distintos números mayores que 0, cada uno en una línea) y escribe en el fichero f2 una línea con la representación en base 1 de cada uno de los números de f1 excepto el 0 final. Por ejemplo, si el contenido de «Entrada.txt» es

al evaluar (transformaAbase1 «Entrada.txt» «Salida.txt») el contenido de «Salida.txt» debe de ser

1
1111
111111

1111

111111

Soluciones

transformaAbase1 :: FilePath -> FilePath -> IO ()
transformaAbase1 f1 f2 = do
  cs <- readFile f1
  writeFile f2 (transformaAbase1Aux cs)

-- (transformaAbase1Aux cs) es la cadena obtenida transformando a base 1
-- cada uno de los números de cs. Por ejemplo,
--    λ> transformaAbase1Aux "1\n4\n6\n0\n" 
--    "1\n1111\n111111\n"
transformaAbase1Aux :: String -> String
transformaAbase1Aux cs =
  unlines (map (show . enBase1) (numeros cs))

-- (numeros cs) es la lista de los números de cs, excepto el último. Por
-- ejemplo, 
--    numeros "1\n4\n6\n0\n"  ==  [1,4,6]
numeros :: String -> [Integer]
numeros cs  =
  init (map read (lines cs))

-- (enBsase1 x) es la representación de x en base 1. Por ejemplo,
--    enBase1 4  ==  1111
enBase1 :: Integer -> Integer
enBase1 x = (10^x - 1) `div` 9

transformaAbase1 :: FilePath -> FilePath -> IO ()

transformaAbase1 f1 f2 = do

cs <- readFile f1

writeFile f2 (transformaAbase1Aux cs)

-- (transformaAbase1Aux cs) es la cadena obtenida transformando a base 1

-- cada uno de los números de cs. Por ejemplo,

-- λ> transformaAbase1Aux "1\n4\n6\n0\n"

-- "1\n1111\n111111\n"

transformaAbase1Aux :: String -> String

transformaAbase1Aux cs =

unlines (map (show . enBase1) (numeros cs))

-- (numeros cs) es la lista de los números de cs, excepto el último. Por

-- ejemplo,

-- numeros "1\n4\n6\n0\n" == [1,4,6]

numeros :: String -> [Integer]

numeros cs =

init (map read (lines cs))

-- (enBsase1 x) es la representación de x en base 1. Por ejemplo,

-- enBase1 4 == 1111

enBase1 :: Integer -> Integer

enBase1 x = (10^x - 1) `div` 9

Máximo común divisor de x e y veces n

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

Definir las funciones

   repite :: Int -> Integer -> Integer
   mcdR   :: Integer -> Int -> Int -> Integer

1 2	repite :: Int -> Integer -> Integer mcdR :: Integer -> Int -> Int -> Integer

tales que

(repite x n) es el número obtenido repitiendo x veces el número n. Por ejemplo.

     repite 3 123  ==  123123123

1	repite 3 123 == 123123123

(mcdR n x y) es el máximo común divisor de los números obtenidos repitiendo x veces e y veces el número n. Por ejemplo.

     mcdR 123 2 3                     ==  123
     mcdR 4 4 6                       ==  44
     mcdR 2017 (10^1000) (2+10^1000)  ==  20172017

mcdR 123 2 3 == 123

mcdR 4 4 6 == 44

mcdR 2017 (10^1000) (2+10^1000) == 20172017

Soluciones

import Test.QuickCheck

repite :: Int -> Integer -> Integer
repite x n =
  read (concat (replicate x (show n)))

-- 1ª definición
mcdR :: Integer -> Int -> Int -> Integer
mcdR n x y =
  gcd (repite x n) (repite y n)

-- 2ª definición
mcdR2 :: Integer -> Int -> Int -> Integer
mcdR2 n x y =
  repite (gcd x y) n

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_equivalencia :: (Positive Integer) -> (Positive Int) -> (Positive Int)
                     -> Bool
prop_equivalencia (Positive n) (Positive x) (Positive y) =
  mcdR n x y == mcdR2 n x y

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

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

--    λ> mcdR 2017 (10^6) (2+10^6)
--    20172017
--    (18.92 secs, 6,012,285,224 bytes)
--    λ> mcdR2 2017 (10^6) (2+10^6)
--    20172017
--    (0.01 secs, 0 bytes)

import Test.QuickCheck

repite :: Int -> Integer -> Integer

repite x n =

read (concat (replicate x (show n)))

-- 1ª definición

mcdR :: Integer -> Int -> Int -> Integer

mcdR n x y =

gcd (repite x n) (repite y n)

-- 2ª definición

mcdR2 :: Integer -> Int -> Int -> Integer

mcdR2 n x y =

repite (gcd x y) n

-- Comprobación de equivalencia

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

-- La propiedad es

prop_equivalencia :: (Positive Integer) -> (Positive Int) -> (Positive Int)

-> Bool

prop_equivalencia (Positive n) (Positive x) (Positive y) =

mcdR n x y == mcdR2 n x y

-- La comprobación es

-- λ> quickCheck prop_equivalencia

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- λ> mcdR 2017 (10^6) (2+10^6)

-- 20172017

-- (18.92 secs, 6,012,285,224 bytes)

-- λ> mcdR2 2017 (10^6) (2+10^6)

-- 20172017

-- (0.01 secs, 0 bytes)

La sucesión «Mira y di»

PorJosé A. Alonso 24-enero-201731-enero-2017

La sucesión «Mira y di» (en inglés, Look-and-Say) es una sucesión de números naturales en donde cada término se obtiene agrupando las cifras iguales del anterior y recitándolas. Por ejemplo, si x(0) = 1 se lee como «un uno» y por tanto x(1) = 11. Análogamente,

   x(1) = 11     ("dos unos                          --> "21")
   x(2) = 21     ("un dos un uno                     --> "1211")
   x(3) = 1211   ("un uno un dos dos unos            --> "111221")
   x(4) = 111221 ("tres unos dos doses un uno        --> "312211")
   x(5) = 312211 ("un tres un uno dos doses dos unos --> "13112221")

x(1) = 11 ("dos unos --> "21")

x(2) = 21 ("un dos un uno --> "1211")

x(3) = 1211 ("un uno un dos dos unos --> "111221")

x(4) = 111221 ("tres unos dos doses un uno --> "312211")

x(5) = 312211 ("un tres un uno dos doses dos unos --> "13112221")

Definir la función

  sucMiraYDi :: Integer -> [Integer]

1	sucMiraYDi :: Integer -> [Integer]

tal que (sucMiraYDi n) es la sucesión «Mira y di» cuyo primer término es n. Por ejemplo,

   λ> take 9 (sucMiraYdi 1)
   [1,11,21,1211,111221,312211,13112221,1113213211,31131211131221]
   λ> take 5 (sucMiraYdi 2017)
   [2017,12101117,111211103117,31123110132117,1321121321101113122117]
   λ> take 7 (sucMiraYDi 22)
   [22,22,22,22,22,22,22]
   λ> (sucMiraYDi 1) !! 11
   3113112221232112111312211312113211
   λ> (sucMiraYDi 1) !! 12
   1321132132111213122112311311222113111221131221

λ> take 9 (sucMiraYdi 1)

[1,11,21,1211,111221,312211,13112221,1113213211,31131211131221]

λ> take 5 (sucMiraYdi 2017)

[2017,12101117,111211103117,31123110132117,1321121321101113122117]

λ> take 7 (sucMiraYDi 22)

[22,22,22,22,22,22,22]

λ> (sucMiraYDi 1) !! 11

3113112221232112111312211312113211

λ> (sucMiraYDi 1) !! 12

1321132132111213122112311311222113111221131221

Independientemente del término inicial x(0) elegido (con la única salvedad del 22), la sucesión diverge y la razón entre el número de cifras de x(n) y el de x(n-1) tiende a un valor fijo que es la constante de Conway λ ≈ 1.303577269. Por ejemplo, para x(0) = 1, las razones son

   2, 1, 2, 1.5, 1, 1.3333333333333333, 1.25, 1.4, 1.4285714285714286, 1.3

1	2, 1, 2, 1.5, 1, 1.3333333333333333, 1.25, 1.4, 1.4285714285714286, 1.3

Definir la función

   aproximacionConway :: Integer -> Double -> Int

1	aproximacionConway :: Integer -> Double -> Int

tal que (aproximacionConway n e) es el menor k tal que la diferencia entre la constante de Conway y la razón entre el número de cifras de x(k) x(k-1) es, en valor absoluto, menor que e. Por ejemplo,

   aproximacionConway 1 0.3     ==  3
   aproximacionConway 1 0.1     ==  5
   aproximacionConway 1 0.01    ==  9
   aproximacionConway 1 0.001   ==  24
   aproximacionConway 1 0.0001  ==  43
   aproximacionConway 2 0.0001  ==  47

aproximacionConway 1 0.3 == 3

aproximacionConway 1 0.1 == 5

aproximacionConway 1 0.01 == 9

aproximacionConway 1 0.001 == 24

aproximacionConway 1 0.0001 == 43

aproximacionConway 2 0.0001 == 47

Nota: Este ejercicio ha sido propuesto por Elías Guisado.

Soluciones

import Data.List (genericLength, group)

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

sucMiraYdi :: Integer -> [Integer]
sucMiraYdi = iterate di

-- (di x) es el número correspondiente a la lectura de x. Por ejemplo.
--    di 1       ==  11
--    di 11      ==  21
--    di 21      ==  1211
--    di 1211    ==  111221
--    di 111221  ==  312211
--    di 312211  ==  13112221
di :: Integer -> Integer
di = read . concatMap aux . group . show
  where aux s = show (length s) ++ [head s]

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

sucMiraYdi2 :: Integer -> [Integer]
sucMiraYdi2 = iterate (read . concatMap aux . group . show)
  where aux s = show (length s) ++ [head s]

-- Constante de Conway
-- ===================

aproximacionConway :: Integer -> Double -> Int
aproximacionConway n e =
  length (takeWhile aux (razonesMiraYdi n))
  where aux x = abs (x - constanteConway) > e 

constanteConway :: Double
constanteConway = 1.303577269

-- (razonesMiraYdi n) es la sucesión de las razones entre de cada
-- elemento de la sucesión "Mira y di" con elemento inicial n y su
-- anterior. Por ejemplo,
--    λ> take 10 (razonesMiraYdi 1)
--    [2.0,1.0,2.0,1.5,1.0,1.3333333333333333,1.25,1.4,1.4285714285714286,1.3]
--    λ> take 7 (razonesMiraYdi 10)
--    [2.0,1.0,1.5,1.6666666666666667,1.2,1.1666666666666667,1.5714285714285714]
razonesMiraYdi :: Integer -> [Double]
razonesMiraYdi n =
  zipWith (/) (tail xs) xs
  where xs = map (genericLength . show) (sucMiraYdi n)

import Data.List (genericLength, group)

-- 1ª solución

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

sucMiraYdi :: Integer -> [Integer]

sucMiraYdi = iterate di

-- (di x) es el número correspondiente a la lectura de x. Por ejemplo.

-- di 1 == 11

-- di 11 == 21

-- di 21 == 1211

-- di 1211 == 111221

-- di 111221 == 312211

-- di 312211 == 13112221

di :: Integer -> Integer

di = read . concatMap aux . group . show

where aux s = show (length s) ++ [head s]

-- 2ª solución

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

sucMiraYdi2 :: Integer -> [Integer]

sucMiraYdi2 = iterate (read . concatMap aux . group . show)

where aux s = show (length s) ++ [head s]

-- Constante de Conway

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

aproximacionConway :: Integer -> Double -> Int

aproximacionConway n e =

length (takeWhile aux (razonesMiraYdi n))

where aux x = abs (x - constanteConway) > e

constanteConway :: Double

constanteConway = 1.303577269

-- (razonesMiraYdi n) es la sucesión de las razones entre de cada

-- elemento de la sucesión "Mira y di" con elemento inicial n y su

-- anterior. Por ejemplo,

-- λ> take 10 (razonesMiraYdi 1)

-- [2.0,1.0,2.0,1.5,1.0,1.3333333333333333,1.25,1.4,1.4285714285714286,1.3]

-- λ> take 7 (razonesMiraYdi 10)

-- [2.0,1.0,1.5,1.6666666666666667,1.2,1.1666666666666667,1.5714285714285714]

razonesMiraYdi :: Integer -> [Double]

razonesMiraYdi n =

zipWith (/) (tail xs) xs

where xs = map (genericLength . show) (sucMiraYdi n)

Notación polaca inversa

PorJosé A. Alonso 20-enero-201727-enero-2017

La notación polaca inversa (en inglés, Reverse Polish Notation, o RPN), es una forma alternativa de escribir expresiones matemáticas. Por ejemplo, la expresión "20 - (4 + 3) * 2" en RPN es "20 4 3 + 2 * -".

Para evaluar una expresión en RPN, usamos una lista auxiliar (inicialmente vacía) y recorremos la expresión de izquierda a derecha. Cada vez que encontramos un número, lo añadimos a la lista auxiliar. Cuando encontramos un operador, retiramos los dos números que hay al principio de la pila, utilizamos el operador con ellos y los quitamos de la lista y le añadimos el resultado. Cuando alcancemos el final de la expresión, debemos tener un solo número en la lista auxiliar si la expresión estaba bien formada, y éste representa el resultado de la expresión. Por ejemplo, la evaluación de RPN "20 4 3 + 2 * -" es la siguiente

   ""                 []
   "20"               [20]
   "20 4"             [4, 20]
   "20 4 3"           [3, 4, 20]
   "20 4 3 +"         [7, 20]
   "20 4 3 + 2"       [2, 7, 20]
   "20 4 3 + 2 *"     [14, 20]
   "20 4 3 + 2 * -"   [6]

"" []

"20" [20]

"20 4" [4, 20]

"20 4 3" [3, 4, 20]

"20 4 3 +" [7, 20]

"20 4 3 + 2" [2, 7, 20]

"20 4 3 + 2 *" [14, 20]

"20 4 3 + 2 * -" [6]

Definir la función

   valor :: String -> Float

1	valor :: String -> Float

tal que (valor cs) es el valor de la expresión RPN cs. Por ejemplo,

   valor "4"               ==  4.0
   valor "4 3 +"           ==  7.0
   valor "4 3 + 2 *"       ==  14.0
   valor "20 4 3 + 2 * -"  ==  6.0
   valor "3 7 + 2 /"       ==  5.0

valor "4" == 4.0

valor "4 3 +" == 7.0

valor "4 3 + 2 *" == 14.0

valor "20 4 3 + 2 * -" == 6.0

valor "3 7 + 2 /" == 5.0

Soluciones

valor :: String -> Float
valor = head . foldl aux [] . words
  where aux (x:y:ys) "+" = (x + y) : ys
        aux (x:y:ys) "-" = (y - x) : ys
        aux (x:y:ys) "*" = (x * y) : ys
        aux (x:y:ys) "/" = (y / x) : ys
        aux xs cs        = read cs : xs

valor :: String -> Float

valor = head . foldl aux [] . words

where aux (x:y:ys) "+" = (x + y) : ys

aux (x:y:ys) "-" = (y - x) : ys

aux (x:y:ys) "*" = (x * y) : ys

aux (x:y:ys) "/" = (y / x) : ys

aux xs cs = read cs : xs

La conjetura de Rodolfo

PorJosé A. Alonso 19-enero-201726-enero-2017

El pasado 1 de enero, Claudio Meller publicó el artículo La conjetura de Rodolfo que afirma que

Todos los números naturales se pueden números pueden expresarse como la suma de un capicúa y un capicúa especial (siendo los capicúas especiales los números que al quitarles los ceros finales son capicúas; por ejemplo, 32300, 50500 y 78987).

Definir las funciones

   descomposiciones               :: Integer -> [(Integer, Integer)]
   contraejemplosConjeturaRodolfo :: [Integer]

1 2	descomposiciones :: Integer -> [(Integer, Integer)] contraejemplosConjeturaRodolfo :: [Integer]

tales que

(descomposiciones x) es la lista de las descomposiciones de x como la suma de un capicúa y un capicúa especial. Por ejemplo,

     descomposiciones 1980  ==  [(99,1881),(979,1001)]
     descomposiciones 2016  ==  [(575,1441),(606,1410)]
     descomposiciones 1971  ==  [(161,1810),(1771,200),(1881,90)]

descomposiciones 1980 == [(99,1881),(979,1001)]

descomposiciones 2016 == [(575,1441),(606,1410)]

descomposiciones 1971 == [(161,1810),(1771,200),(1881,90)]

contraejemplosConjeturaRodolfo es la lista de contraejemplos de la conjetura de Rodolfo; es decir, de los números que no pueden expresarse com la suma de un capicúa y un capicúa especial. Por ejemplo,

     λ> take 12 contraejemplosConjeturaRodolfo
     [1200,1220,1240,1250,1260,1270,1280,1290,1300,1330,1350,1360]
     λ> take 12 (dropWhile (< 2000) contraejemplosConjeturaRodolfo)
     [3020,3240,3350,3460,3570,3680,3920,4030,4250,4360,4470,4580]

λ> take 12 contraejemplosConjeturaRodolfo

[1200,1220,1240,1250,1260,1270,1280,1290,1300,1330,1350,1360]

λ> take 12 (dropWhile (< 2000) contraejemplosConjeturaRodolfo)

[3020,3240,3350,3460,3570,3680,3920,4030,4250,4360,4470,4580]

Soluciones

import Data.List (nub)

descomposiciones :: Integer -> [(Integer, Integer)]
descomposiciones x =
  reducida [(y,z) | y <- takeWhile (<= x) capicuas
                  , let z = x - y
                  , esCapicuaG z]

-- capicuas es la sucesión de los números capicúas. Por ejemplo,
--    λ> take 45 capicuas
--    [0,1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,101,111,121,131,
--     141,151,161,171,181,191,202,212,222,232,242,252,262,272,282,292,
--     303,313,323,333,343,353]
-- Se usará la 2ª definición del ejercicio "Sucesión de capicúas".
capicuas :: [Integer]
capicuas = capicuasImpares `mezcla` capicuasPares

-- capicuasPares es la sucesión del cero y las capicúas con un número
-- par de dígitos. Por ejemplo,  
--    λ> take 17 capicuasPares
--    [0,11,22,33,44,55,66,77,88,99,1001,1111,1221,1331,1441,1551,1661]
capicuasPares :: [Integer]
capicuasPares =
  [read (ns ++ reverse ns) | n <- [0..]
                           , let ns = show n]   

-- capicuasImpares es la sucesión de las capicúas con un número
-- impar de dígitos a partir de 1. Por ejemplo,  
--    λ> take 20 capicuasImpares
--    [1,2,3,4,5,6,7,8,9,101,111,121,131,141,151,161,171,181,191,202]
capicuasImpares :: [Integer]
capicuasImpares =
  [1..9] ++ [read (ns ++ [z] ++ reverse ns)
            | n <- [1..]
            , let ns = show n
            , z <- "0123456789"]   

-- (mezcla xs ys) es la lista ordenada obtenida mezclando las dos listas
-- ordenadas xs e ys, suponiendo que ambas son infinitas y con elementos
-- distintos. Por ejemplo,
--    take 10 (mezcla [2,12..] [5,15..])  ==  [2,5,12,15,22,25,32,35,42,45]
--    take 10 (mezcla [2,22..] [5,15..])  ==  [2,5,15,22,25,35,42,45,55,62]
mezcla :: Ord a => [a] -> [a] -> [a]
mezcla us@(x:xs) vs@(y:ys)
  | x < y     = x : mezcla xs vs
  | otherwise = y : mezcla us ys

-- (esCapicua x) se verifica si x es capicúa. Por ejemplo,
--    esCapicua 353   ==  True
--    esCapicua 3553  ==  True
--    esCapicua 3535  ==  False
esCapicua :: Integer -> Bool
esCapicua x =
  xs == reverse xs
  where xs = show x

esCapicuaG :: Integer -> Bool
esCapicuaG x =
  x == 0 || esCapicua (sinCerosFinales x)

--    sinCerosFinales 3405000  ==  3405
sinCerosFinales :: Integer -> Integer
sinCerosFinales x =
  read (reverse (dropWhile (== '0') (reverse (show x))))

reducida :: [(Integer, Integer)] -> [(Integer, Integer)]
reducida ps =
  nub [(x,y) | (x,y) <- ps
             , x <= y]

--    λ> take 12 contraejemplosConjeturaRodolfo
--    [1200,1220,1240,1250,1260,1270,1280,1290,1300,1330,1350,1360]
--    λ> take 12 (dropWhile (< 2000) contraejemplosConjeturaRodolfo)
--    [3020,3240,3350,3460,3570,3680,3920,4030,4250,4360,4470,4580]
contraejemplosConjeturaRodolfo :: [Integer]
contraejemplosConjeturaRodolfo =
  [x | x <- [0..]
  , null (descomposiciones x)]

import Data.List (nub)

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

descomposiciones x =

reducida [(y,z) | y <- takeWhile (<= x) capicuas

, let z = x - y

, esCapicuaG z]

-- capicuas es la sucesión de los números capicúas. Por ejemplo,

-- λ> take 45 capicuas

-- [0,1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,101,111,121,131,

-- 141,151,161,171,181,191,202,212,222,232,242,252,262,272,282,292,

-- 303,313,323,333,343,353]

-- Se usará la 2ª definición del ejercicio "Sucesión de capicúas".

capicuas :: [Integer]

capicuas = capicuasImpares `mezcla` capicuasPares

-- capicuasPares es la sucesión del cero y las capicúas con un número

-- par de dígitos. Por ejemplo,

-- λ> take 17 capicuasPares

-- [0,11,22,33,44,55,66,77,88,99,1001,1111,1221,1331,1441,1551,1661]

capicuasPares :: [Integer]

capicuasPares =

[read (ns ++ reverse ns) | n <- [0..]

, let ns = show n]

-- capicuasImpares es la sucesión de las capicúas con un número

-- impar de dígitos a partir de 1. Por ejemplo,

-- λ> take 20 capicuasImpares

-- [1,2,3,4,5,6,7,8,9,101,111,121,131,141,151,161,171,181,191,202]

capicuasImpares :: [Integer]

capicuasImpares =

[1..9] ++ [read (ns ++ [z] ++ reverse ns)

| n <- [1..]

, let ns = show n

, z <- "0123456789"]

-- (mezcla xs ys) es la lista ordenada obtenida mezclando las dos listas

-- ordenadas xs e ys, suponiendo que ambas son infinitas y con elementos

-- distintos. Por ejemplo,

-- take 10 (mezcla [2,12..] [5,15..]) == [2,5,12,15,22,25,32,35,42,45]

-- take 10 (mezcla [2,22..] [5,15..]) == [2,5,15,22,25,35,42,45,55,62]

mezcla :: Ord a => [a] -> [a] -> [a]

mezcla us@(x:xs) vs@(y:ys)

| x < y = x : mezcla xs vs

| otherwise = y : mezcla us ys

-- (esCapicua x) se verifica si x es capicúa. Por ejemplo,

-- esCapicua 353 == True

-- esCapicua 3553 == True

-- esCapicua 3535 == False

esCapicua :: Integer -> Bool

esCapicua x =

xs == reverse xs

where xs = show x

esCapicuaG :: Integer -> Bool

esCapicuaG x =

x == 0 || esCapicua (sinCerosFinales x)

-- sinCerosFinales 3405000 == 3405

sinCerosFinales :: Integer -> Integer

sinCerosFinales x =

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

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

reducida ps =

nub [(x,y) | (x,y) <- ps

, x <= y]

-- λ> take 12 contraejemplosConjeturaRodolfo

-- [1200,1220,1240,1250,1260,1270,1280,1290,1300,1330,1350,1360]

-- λ> take 12 (dropWhile (< 2000) contraejemplosConjeturaRodolfo)

-- [3020,3240,3350,3460,3570,3680,3920,4030,4250,4360,4470,4580]

contraejemplosConjeturaRodolfo :: [Integer]

contraejemplosConjeturaRodolfo =

[x | x <- [0..]

, null (descomposiciones x)]

Sumas de dos capicúas

PorJosé A. Alonso 17-enero-201724-enero-2017

Definir las funciones

   sumas2Capicuas  :: Integer -> [(Integer, Integer)]
   noSuma2Capicuas :: [Integer]

1 2	sumas2Capicuas :: Integer -> [(Integer, Integer)] noSuma2Capicuas :: [Integer]

tales que

(sumas2Capicuas x) es la lista de las descomposiciones de x como suma de dos capicúas (con el primer sumando menor o igual que el segundo). Por ejemplo,

      sumas2Capicuas 17  == [(6,11),(8,9)]
      sumas2Capicuas 187 == [(6,181),(66,121),(88,99)]
      sumas2Capicuas 165 == [(4,161),(44,121),(66,99),(77,88)]
      sumas2Capicuas 382 == [(9,373),(191,191)]
      sumas2Capicuas 151 == [(0,151)]
      sumas2Capicuas 201 == []

sumas2Capicuas 17 == [(6,11),(8,9)]

sumas2Capicuas 187 == [(6,181),(66,121),(88,99)]

sumas2Capicuas 165 == [(4,161),(44,121),(66,99),(77,88)]

sumas2Capicuas 382 == [(9,373),(191,191)]

sumas2Capicuas 151 == [(0,151)]

sumas2Capicuas 201 == []

noSuma2Capicuas es la sucesión de los números que no se pueden escribir como suma de dos capicúas. Por ejemplo,

      λ> take 15 noSuma2Capicuas
      [21,32,43,54,65,76,87,98,201,1031,1041,1042,1051,1052,1053]
      λ> noSuma2Capicuas !! 3000
      19941

λ> take 15 noSuma2Capicuas

[21,32,43,54,65,76,87,98,201,1031,1041,1042,1051,1052,1053]

λ> noSuma2Capicuas !! 3000

19941

Soluciones

sumas2Capicuas :: Integer -> [(Integer, Integer)]
sumas2Capicuas x =
  [(y,z) | y <- takeWhile (<= (x `div` 2)) capicuas
         , let z = x - y
         , esCapicua z]

-- capicuas es la sucesión de los números capicúas. Por ejemplo,
--    λ> take 45 capicuas
--    [0,1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,101,111,121,131,
--     141,151,161,171,181,191,202,212,222,232,242,252,262,272,282,292,
--     303,313,323,333,343,353]
-- Se usará la 2ª definición del ejercicio "Sucesión de capicúas".
capicuas :: [Integer]
capicuas = capicuasImpares `mezcla` capicuasPares

-- capicuasPares es la sucesión del cero y las capicúas con un número
-- par de dígitos. Por ejemplo,  
--    λ> take 17 capicuasPares
--    [0,11,22,33,44,55,66,77,88,99,1001,1111,1221,1331,1441,1551,1661]
capicuasPares :: [Integer]
capicuasPares =
  [read (ns ++ reverse ns) | n <- [0..]
                           , let ns = show n]   

-- capicuasImpares es la sucesión de las capicúas con un número
-- impar de dígitos a partir de 1. Por ejemplo,  
--    λ> take 20 capicuasImpares
--    [1,2,3,4,5,6,7,8,9,101,111,121,131,141,151,161,171,181,191,202]
capicuasImpares :: [Integer]
capicuasImpares =
  [1..9] ++ [read (ns ++ [z] ++ reverse ns)
            | n <- [1..]
            , let ns = show n
            , z <- "0123456789"]   

-- (mezcla xs ys) es la lista ordenada obtenida mezclando las dos listas
-- ordenadas xs e ys, suponiendo que ambas son infinitas y con elementos
-- distintos. Por ejemplo,
--    take 10 (mezcla [2,12..] [5,15..])  ==  [2,5,12,15,22,25,32,35,42,45]
--    take 10 (mezcla [2,22..] [5,15..])  ==  [2,5,15,22,25,35,42,45,55,62]
mezcla :: Ord a => [a] -> [a] -> [a]
mezcla us@(x:xs) vs@(y:ys)
  | x < y     = x : mezcla xs vs
  | otherwise = y : mezcla us ys

-- (esCapicua x) se verifica si x es capicúa. Por ejemplo,
--    esCapicua 353   ==  True
--    esCapicua 3553  ==  True
--    esCapicua 3535  ==  False
esCapicua :: Integer -> Bool
esCapicua x =
  xs == reverse xs
  where xs = show x

noSuma2Capicuas :: [Integer]
noSuma2Capicuas =
  [x | x <- [0..]
     , null (sumas2Capicuas x)]

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

sumas2Capicuas x =

[(y,z) | y <- takeWhile (<= (x `div` 2)) capicuas

, let z = x - y

, esCapicua z]

-- capicuas es la sucesión de los números capicúas. Por ejemplo,

-- λ> take 45 capicuas

-- [0,1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,101,111,121,131,

-- 141,151,161,171,181,191,202,212,222,232,242,252,262,272,282,292,

-- 303,313,323,333,343,353]

-- Se usará la 2ª definición del ejercicio "Sucesión de capicúas".

capicuas :: [Integer]

capicuas = capicuasImpares `mezcla` capicuasPares

-- capicuasPares es la sucesión del cero y las capicúas con un número

-- par de dígitos. Por ejemplo,

-- λ> take 17 capicuasPares

-- [0,11,22,33,44,55,66,77,88,99,1001,1111,1221,1331,1441,1551,1661]

capicuasPares :: [Integer]

capicuasPares =

[read (ns ++ reverse ns) | n <- [0..]

, let ns = show n]

-- capicuasImpares es la sucesión de las capicúas con un número

-- impar de dígitos a partir de 1. Por ejemplo,

-- λ> take 20 capicuasImpares

-- [1,2,3,4,5,6,7,8,9,101,111,121,131,141,151,161,171,181,191,202]

capicuasImpares :: [Integer]

capicuasImpares =

[1..9] ++ [read (ns ++ [z] ++ reverse ns)

| n <- [1..]

, let ns = show n

, z <- "0123456789"]

-- (mezcla xs ys) es la lista ordenada obtenida mezclando las dos listas

-- ordenadas xs e ys, suponiendo que ambas son infinitas y con elementos

-- distintos. Por ejemplo,

-- take 10 (mezcla [2,12..] [5,15..]) == [2,5,12,15,22,25,32,35,42,45]

-- take 10 (mezcla [2,22..] [5,15..]) == [2,5,15,22,25,35,42,45,55,62]

mezcla :: Ord a => [a] -> [a] -> [a]

mezcla us@(x:xs) vs@(y:ys)

| x < y = x : mezcla xs vs

| otherwise = y : mezcla us ys

-- (esCapicua x) se verifica si x es capicúa. Por ejemplo,

-- esCapicua 353 == True

-- esCapicua 3553 == True

-- esCapicua 3535 == False

esCapicua :: Integer -> Bool

esCapicua x =

xs == reverse xs

where xs = show x

noSuma2Capicuas :: [Integer]

noSuma2Capicuas =

[x | x <- [0..]

, null (sumas2Capicuas x)]

Sumas de tres capicúas

PorJosé A. Alonso 12-enero-201719-enero-2017

Definir la función

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

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

tales que (sumas3Capicuas x) es la lista de las descomposiciones de x como suma de tres capicúas (con los sumandos no decrecientes). Por ejemplo,

   sumas3Capicuas 0  ==  [(0,0,0)]
   sumas3Capicuas 1  ==  [(0,0,1)]
   sumas3Capicuas 2  ==  [(0,0,2),(0,1,1)]
   sumas3Capicuas 3  ==  [(0,0,3),(0,1,2),(1,1,1)]
   sumas3Capicuas 4  ==  [(0,0,4),(0,1,3),(0,2,2),(1,1,2)]
   length (sumas3Capicuas 17)      ==  17
   length (sumas3Capicuas 2017)    ==  47
   length (sumas3Capicuas 999999)  ==  15266

sumas3Capicuas 0 == [(0,0,0)]

sumas3Capicuas 1 == [(0,0,1)]

sumas3Capicuas 2 == [(0,0,2),(0,1,1)]

sumas3Capicuas 3 == [(0,0,3),(0,1,2),(1,1,1)]

sumas3Capicuas 4 == [(0,0,4),(0,1,3),(0,2,2),(1,1,2)]

length (sumas3Capicuas 17) == 17

length (sumas3Capicuas 2017) == 47

length (sumas3Capicuas 999999) == 15266

Comprobar con QuickCheck que todo número natural se puede escribir como suma de tres capicúas.

Soluciones

import Test.QuickCheck

sumas3Capicuas :: Integer -> [(Integer, Integer, Integer)]
sumas3Capicuas x =
  [(a,b,c) | a <- as
           , b <- dropWhile (< a) as
           , let c = x - a - b
           , b <= c 
           , esCapicua c]
  where as = takeWhile (<= x) capicuas

-- capicuas es la sucesión de los números capicúas. Por ejemplo,
--    λ> take 45 capicuas
--    [0,1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,101,111,121,131,
--     141,151,161,171,181,191,202,212,222,232,242,252,262,272,282,292,
--     303,313,323,333,343,353]
-- Se usará la 2ª definición del ejercicio "Sucesión de capicúas".
capicuas :: [Integer]
capicuas = capicuasImpares `mezcla` capicuasPares

-- capicuasPares es la sucesión del cero y las capicúas con un número
-- par de dígitos. Por ejemplo,  
--    λ> take 17 capicuasPares
--    [0,11,22,33,44,55,66,77,88,99,1001,1111,1221,1331,1441,1551,1661]
capicuasPares :: [Integer]
capicuasPares =
  [read (ns ++ reverse ns) | n <- [0..]
                           , let ns = show n]   

-- capicuasImpares es la sucesión de las capicúas con un número
-- impar de dígitos a partir de 1. Por ejemplo,  
--    λ> take 20 capicuasImpares
--    [1,2,3,4,5,6,7,8,9,101,111,121,131,141,151,161,171,181,191,202]
capicuasImpares :: [Integer]
capicuasImpares =
  [1..9] ++ [read (ns ++ [z] ++ reverse ns)
            | n <- [1..]
            , let ns = show n
            , z <- "0123456789"]   

-- (mezcla xs ys) es la lista ordenada obtenida mezclando las dos listas
-- ordenadas xs e ys, suponiendo que ambas son infinitas y con elementos
-- distintos. Por ejemplo,
--    take 10 (mezcla [2,12..] [5,15..])  ==  [2,5,12,15,22,25,32,35,42,45]
--    take 10 (mezcla [2,22..] [5,15..])  ==  [2,5,15,22,25,35,42,45,55,62]
mezcla :: Ord a => [a] -> [a] -> [a]
mezcla us@(x:xs) vs@(y:ys)
  | x < y     = x : mezcla xs vs
  | otherwise = y : mezcla us ys

-- (esCapicua x) se verifica si x es capicúa. Por ejemplo,
--    esCapicua 353   ==  True
--    esCapicua 3553  ==  True
--    esCapicua 3535  ==  False
esCapicua :: Integer -> Bool
esCapicua x =
  xs == reverse xs
  where xs = show x

-- La propiedad es
prop_sumas3Capicuas :: Integer -> Property
prop_sumas3Capicuas x =
  x >= 0 ==> not (null (sumas3Capicuas x))

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

import Test.QuickCheck

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

sumas3Capicuas x =

[(a,b,c) | a <- as

, b <- dropWhile (< a) as

, let c = x - a - b

, b <= c

, esCapicua c]

where as = takeWhile (<= x) capicuas

-- capicuas es la sucesión de los números capicúas. Por ejemplo,

-- λ> take 45 capicuas

-- [0,1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,101,111,121,131,

-- 141,151,161,171,181,191,202,212,222,232,242,252,262,272,282,292,

-- 303,313,323,333,343,353]

-- Se usará la 2ª definición del ejercicio "Sucesión de capicúas".

capicuas :: [Integer]

capicuas = capicuasImpares `mezcla` capicuasPares

-- capicuasPares es la sucesión del cero y las capicúas con un número

-- par de dígitos. Por ejemplo,

-- λ> take 17 capicuasPares

-- [0,11,22,33,44,55,66,77,88,99,1001,1111,1221,1331,1441,1551,1661]

capicuasPares :: [Integer]

capicuasPares =

[read (ns ++ reverse ns) | n <- [0..]

, let ns = show n]

-- capicuasImpares es la sucesión de las capicúas con un número

-- impar de dígitos a partir de 1. Por ejemplo,

-- λ> take 20 capicuasImpares

-- [1,2,3,4,5,6,7,8,9,101,111,121,131,141,151,161,171,181,191,202]

capicuasImpares :: [Integer]

capicuasImpares =

[1..9] ++ [read (ns ++ [z] ++ reverse ns)

| n <- [1..]

, let ns = show n

, z <- "0123456789"]

-- (mezcla xs ys) es la lista ordenada obtenida mezclando las dos listas

-- ordenadas xs e ys, suponiendo que ambas son infinitas y con elementos

-- distintos. Por ejemplo,

-- take 10 (mezcla [2,12..] [5,15..]) == [2,5,12,15,22,25,32,35,42,45]

-- take 10 (mezcla [2,22..] [5,15..]) == [2,5,15,22,25,35,42,45,55,62]

mezcla :: Ord a => [a] -> [a] -> [a]

mezcla us@(x:xs) vs@(y:ys)

| x < y = x : mezcla xs vs

| otherwise = y : mezcla us ys

-- (esCapicua x) se verifica si x es capicúa. Por ejemplo,

-- esCapicua 353 == True

-- esCapicua 3553 == True

-- esCapicua 3535 == False

esCapicua :: Integer -> Bool

esCapicua x =

xs == reverse xs

where xs = show x

-- La propiedad es

prop_sumas3Capicuas :: Integer -> Property

prop_sumas3Capicuas x =

x >= 0 ==> not (null (sumas3Capicuas x))

-- La comprobación es

-- λ> quickCheck prop_sumas3Capicuas

-- +++ OK, passed 100 tests.

Sucesión de capicúas

PorJosé A. Alonso 11-enero-201718-enero-2017

Definir las funciones

   capicuas        :: [Integer] 
   posicionCapicua :: Integer -> Integer

1 2	capicuas :: [Integer] posicionCapicua :: Integer -> Integer

tales que

capicuas es la sucesión de los números capicúas. Por ejemplo,

   λ> take 45 capicuas
   [0,1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,101,111,121,131,
    141,151,161,171,181,191,202,212,222,232,242,252,262,272,282,292,
    303,313,323,333,343,353]
   λ> capicuas !! (10^5)  
   900010009

λ> take 45 capicuas

[0,1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,101,111,121,131,

141,151,161,171,181,191,202,212,222,232,242,252,262,272,282,292,

303,313,323,333,343,353]

λ> capicuas !! (10^5)

900010009

(posicionCapicua x) es la posición del número capicúa x en la sucesión de los capicúas. Por ejemplo,

   λ> posicionCapicua 353
   44
   λ> posicionCapicua 900010009
   100000
   λ> let xs = show (123^30)
   λ> posicionCapicua (read (xs ++ reverse xs))
   1497912859868342793044999075260564303046944727069807798026337448
   λ> posicionCapicua (read (xs ++ "7" ++ reverse xs))
   5979128598683427930449990752605643030469447270698077980263374496

λ> posicionCapicua 353

λ> posicionCapicua 900010009

100000

λ> let xs = show (123^30)

λ> posicionCapicua (read (xs ++ reverse xs))

1497912859868342793044999075260564303046944727069807798026337448

λ> posicionCapicua (read (xs ++ "7" ++ reverse xs))

5979128598683427930449990752605643030469447270698077980263374496

Soluciones

import Data.List (genericLength)

-- 1ª definición de capicuas
-- =========================

capicuas1 :: [Integer]
capicuas1 = [n | n <- [0..]
               , esCapicua n]

-- (esCapicua x) se verifica si x es capicúa. Por ejemplo,
--    esCapicua 353   ==  True
--    esCapicua 3553  ==  True
--    esCapicua 3535  ==  False
esCapicua :: Integer -> Bool
esCapicua x =
  xs == reverse xs
  where xs = show x


-- 2ª definición de capicuas
-- =========================

capicuas2 :: [Integer]
capicuas2 = capicuasImpares `mezcla` capicuasPares

-- capicuasPares es la sucesión del cero y las capicúas con un número
-- par de dígitos. Por ejemplo,  
--    λ> take 17 capicuasPares
--    [0,11,22,33,44,55,66,77,88,99,1001,1111,1221,1331,1441,1551,1661]
capicuasPares :: [Integer]
capicuasPares =
  [read (ns ++ reverse ns) | n <- [0..]
                           , let ns = show n]   

-- capicuasImpares es la sucesión de las capicúas con un número
-- impar de dígitos a partir de 1. Por ejemplo,  
--    λ> take 20 capicuasImpares
--    [1,2,3,4,5,6,7,8,9,101,111,121,131,141,151,161,171,181,191,202]
capicuasImpares :: [Integer]
capicuasImpares =
  [1..9] ++ [read (ns ++ [z] ++ reverse ns)
            | n <- [1..]
            , let ns = show n
            , z <- "0123456789"]   

-- (mezcla xs ys) es la lista ordenada obtenida mezclando las dos listas
-- ordenadas xs e ys, suponiendo que ambas son infinitas y con elementos
-- distintos. Por ejemplo,
--    take 10 (mezcla [2,12..] [5,15..])  ==  [2,5,12,15,22,25,32,35,42,45]
--    take 10 (mezcla [2,22..] [5,15..])  ==  [2,5,15,22,25,35,42,45,55,62]
mezcla :: Ord a => [a] -> [a] -> [a]
mezcla us@(x:xs) vs@(y:ys)
  | x < y     = x : mezcla xs vs
  | otherwise = y : mezcla us ys

-- 3ª definición de capicuas
-- =========================

capicuas3 :: [Integer]
capicuas3 = iterate sigCapicua 0

-- (sigCapicua x) es el capicúa siguiente del número x. Por ejemplo,
--    sigCapicua 12321           == 12421
--    sigCapicua 1298921         == 1299921
--    sigCapicua 999             == 1001
--    sigCapicua 9999            == 10001
--    sigCapicua 898             == 909
--    sigCapicua 123456777654321 == 123456787654321
sigCapicua :: Integer -> Integer
sigCapicua n = read cs
    where l  = length (show (n+1))
          k  = l `div` 2
          xs = show ((n `div` (10^k)) + 1) 
          cs = xs ++ drop (l `rem` 2) (reverse xs)

-- 4ª definición de capicuas
-- =========================

capicuas4 :: [Integer]
capicuas4 =
  concatMap generaCapicuas4 [1..]

generaCapicuas4 :: Integer -> [Integer]
generaCapicuas4 1 = [0..9]
generaCapicuas4 n
  | even n    = [read (xs ++ reverse xs)
                | xs <- map show [10^(m-1)..10^m-1]]
  | otherwise = [read (xs ++ (y : reverse xs))
                | xs <- map show [10^(m-1)..10^m-1]
                , y <- "0123456789"]
  where m = n `div` 2

-- 5ª definición de capicuas
-- =========================

capicuas5 :: [Integer]
capicuas5 = 0 : aux 1
  where aux n =    [read (show x ++ tail (reverse (show x)))
                   | x <- [10^(n-1)..10^n-1]]
                ++ [read (show x ++ reverse (show x))
                   | x <- [10^(n-1)..10^n-1]]
                ++ aux (n+1)

-- 6ª definición de capicuas
-- =========================

capicuas6 :: [Integer]
capicuas6 = 0 : map read (capicuas6Aux [1..9])
 
capicuas6Aux :: [Integer] -> [String]
capicuas6Aux xs =  map duplica1 ys
                ++ map duplica2 ys
                ++ capicuas6Aux [head xs * 10 .. last xs * 10 + 9]
  where
    ys          = map show xs
    duplica1 cs = cs ++ tail (reverse cs)
    duplica2 cs = cs ++ reverse cs

-- 7ª definición de capicuas
-- =========================

capicuas7 :: [Integer]
capicuas7 = 0 : map read (capicuas7Aux [1..9])
 
capicuas7Aux :: [Integer] -> [String]
capicuas7Aux xs =  map duplica1 ys
                ++ map duplica2 ys
                ++ capicuas7Aux [head xs * 10 .. last xs * 10 + 9]
  where
    ys       = map show xs
    duplica1 = (++) <$> id <*> tail . reverse
    duplica2 = (++) <$> id <*> reverse

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

--    λ> capicuas1 !! 2000
--    1001001
--    (2.25 secs, 598,879,552 bytes)
--    λ> capicuas2 !! 2000
--    1001001
--    (0.05 secs, 28,630,552 bytes)
--    λ> capicuas3 !! 2000
--    1001001
--    (0.06 secs, 14,721,360 bytes)
--    λ> capicuas4 !! 2000
--    1001001
--    (0.01 secs, 0 bytes)
--    λ> capicuas5 !! 2000
--    1001001
--    (0.01 secs, 0 bytes)
--    λ> capicuas6 !! 2000
--    1001001
--    (0.01 secs, 0 bytes)
--    λ> capicuas7 !! 2000
--    1001001
--    (0.01 secs, 0 bytes)
--    
--    λ> capicuas2 !! (10^5)
--    900010009
--    (2.03 secs, 1,190,503,952 bytes)
--    λ> capicuas3 !! (10^5)
--    900010009
--    (5.12 secs, 1,408,876,328 bytes)
--    λ> capicuas4 !! (10^5)
--    900010009
--    (0.21 secs, 8,249,296 bytes)
--    λ> capicuas5 !! (10^5)
--    900010009
--    (0.10 secs, 31,134,176 bytes)
--    λ> capicuas6 !! (10^5)
--    900010009
--    (0.14 secs, 55,211,272 bytes)
--    λ> capicuas7 !! (10^5)
--    900010009
--    (0.03 secs, 0 bytes)

-- 1ª definición de posicionCapicua
posicionCapicua1 :: Integer -> Integer
posicionCapicua1 x =
  genericLength (takeWhile (< x) capicuas7)

-- 2ª definición
posicionCapicua2 :: Integer -> Integer
posicionCapicua2 x
  | even n    = read ('1' : take (n `div` 2) xs) - 1
  | otherwise = read (show (1 + read [y]) ++ take (n `div` 2) ys) - 1
  where xs@(y:ys) = show x
        n         = genericLength xs

-- Comparación de eficiencia
--    λ> posicionCapicua1 (10^9 - 1)
--    109998
--    (1.98 secs, 1,112,991,520 bytes)
--    λ> posicionCapicua2 (10^9 - 1)
--    109998
--    (0.01 secs, 0 bytes)

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

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

import Data.List (genericLength)

-- 1ª definición de capicuas

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

capicuas1 :: [Integer]

capicuas1 = [n | n <- [0..]

, esCapicua n]

-- (esCapicua x) se verifica si x es capicúa. Por ejemplo,

-- esCapicua 353 == True

-- esCapicua 3553 == True

-- esCapicua 3535 == False

esCapicua :: Integer -> Bool

esCapicua x =

xs == reverse xs

where xs = show x

-- 2ª definición de capicuas

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

capicuas2 :: [Integer]

capicuas2 = capicuasImpares `mezcla` capicuasPares

-- capicuasPares es la sucesión del cero y las capicúas con un número

-- par de dígitos. Por ejemplo,

-- λ> take 17 capicuasPares

-- [0,11,22,33,44,55,66,77,88,99,1001,1111,1221,1331,1441,1551,1661]

capicuasPares :: [Integer]

capicuasPares =

[read (ns ++ reverse ns) | n <- [0..]

, let ns = show n]

-- capicuasImpares es la sucesión de las capicúas con un número

-- impar de dígitos a partir de 1. Por ejemplo,

-- λ> take 20 capicuasImpares

-- [1,2,3,4,5,6,7,8,9,101,111,121,131,141,151,161,171,181,191,202]

capicuasImpares :: [Integer]

capicuasImpares =

[1..9] ++ [read (ns ++ [z] ++ reverse ns)

| n <- [1..]

, let ns = show n

, z <- "0123456789"]

-- (mezcla xs ys) es la lista ordenada obtenida mezclando las dos listas

-- ordenadas xs e ys, suponiendo que ambas son infinitas y con elementos

-- distintos. Por ejemplo,

-- take 10 (mezcla [2,12..] [5,15..]) == [2,5,12,15,22,25,32,35,42,45]

-- take 10 (mezcla [2,22..] [5,15..]) == [2,5,15,22,25,35,42,45,55,62]

mezcla :: Ord a => [a] -> [a] -> [a]

mezcla us@(x:xs) vs@(y:ys)

| x < y = x : mezcla xs vs

| otherwise = y : mezcla us ys

-- 3ª definición de capicuas

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

capicuas3 :: [Integer]

capicuas3 = iterate sigCapicua 0

-- (sigCapicua x) es el capicúa siguiente del número x. Por ejemplo,

-- sigCapicua 12321 == 12421

-- sigCapicua 1298921 == 1299921

-- sigCapicua 999 == 1001

-- sigCapicua 9999 == 10001

-- sigCapicua 898 == 909

-- sigCapicua 123456777654321 == 123456787654321

sigCapicua :: Integer -> Integer

sigCapicua n = read cs

where l = length (show (n+1))

k = l `div` 2

xs = show ((n `div` (10^k)) + 1)

cs = xs ++ drop (l `rem` 2) (reverse xs)

-- 4ª definición de capicuas

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

capicuas4 :: [Integer]

capicuas4 =

concatMap generaCapicuas4 [1..]

generaCapicuas4 :: Integer -> [Integer]

generaCapicuas4 1 = [0..9]

generaCapicuas4 n

| even n = [read (xs ++ reverse xs)

| xs <- map show [10^(m-1)..10^m-1]]

| otherwise = [read (xs ++ (y : reverse xs))

| xs <- map show [10^(m-1)..10^m-1]

, y <- "0123456789"]

where m = n `div` 2

-- 5ª definición de capicuas

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

capicuas5 :: [Integer]

capicuas5 = 0 : aux 1

where aux n = [read (show x ++ tail (reverse (show x)))

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

++ [read (show x ++ reverse (show x))

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

++ aux (n+1)

-- 6ª definición de capicuas

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

capicuas6 :: [Integer]

capicuas6 = 0 : map read (capicuas6Aux [1..9])

capicuas6Aux :: [Integer] -> [String]

capicuas6Aux xs = map duplica1 ys

++ map duplica2 ys

++ capicuas6Aux [head xs * 10 .. last xs * 10 + 9]

where

ys = map show xs

duplica1 cs = cs ++ tail (reverse cs)

duplica2 cs = cs ++ reverse cs

-- 7ª definición de capicuas

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

capicuas7 :: [Integer]

capicuas7 = 0 : map read (capicuas7Aux [1..9])

capicuas7Aux :: [Integer] -> [String]

capicuas7Aux xs = map duplica1 ys

++ map duplica2 ys

++ capicuas7Aux [head xs * 10 .. last xs * 10 + 9]

where

ys = map show xs

duplica1 = (++) <$> id <*> tail . reverse

duplica2 = (++) <$> id <*> reverse

-- Comparación de eficiencia

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

-- λ> capicuas1 !! 2000

-- 1001001

-- (2.25 secs, 598,879,552 bytes)

-- λ> capicuas2 !! 2000

-- 1001001

-- (0.05 secs, 28,630,552 bytes)

-- λ> capicuas3 !! 2000

-- 1001001

-- (0.06 secs, 14,721,360 bytes)

-- λ> capicuas4 !! 2000

-- 1001001

-- (0.01 secs, 0 bytes)

-- λ> capicuas5 !! 2000

-- 1001001

-- (0.01 secs, 0 bytes)

-- λ> capicuas6 !! 2000

-- 1001001

-- (0.01 secs, 0 bytes)

-- λ> capicuas7 !! 2000

-- 1001001

-- (0.01 secs, 0 bytes)

-- λ> capicuas2 !! (10^5)

-- 900010009

-- (2.03 secs, 1,190,503,952 bytes)

-- λ> capicuas3 !! (10^5)

-- 900010009

-- (5.12 secs, 1,408,876,328 bytes)

-- λ> capicuas4 !! (10^5)

-- 900010009

-- (0.21 secs, 8,249,296 bytes)

-- λ> capicuas5 !! (10^5)

-- 900010009

-- (0.10 secs, 31,134,176 bytes)

-- λ> capicuas6 !! (10^5)

-- 900010009

-- (0.14 secs, 55,211,272 bytes)

-- λ> capicuas7 !! (10^5)

-- 900010009

-- (0.03 secs, 0 bytes)

-- 1ª definición de posicionCapicua

posicionCapicua1 :: Integer -> Integer

posicionCapicua1 x =

genericLength (takeWhile (< x) capicuas7)

-- 2ª definición

posicionCapicua2 :: Integer -> Integer

posicionCapicua2 x

| even n = read ('1' : take (n `div` 2) xs) - 1

| otherwise = read (show (1 + read [y]) ++ take (n `div` 2) ys) - 1

where xs@(y:ys) = show x

n = genericLength xs

-- Comparación de eficiencia

-- λ> posicionCapicua1 (10^9 - 1)

-- 109998

-- (1.98 secs, 1,112,991,520 bytes)

-- λ> posicionCapicua2 (10^9 - 1)

-- 109998

-- (0.01 secs, 0 bytes)

Números dorados

PorJosé A. Alonso 6-enero-201713-enero-2017

Los dígitos del número 2375 se pueden separar en dos grupos de igual tamaño ([7,2] y [5,3]) tales que para los correspondientes números (72 y 53) se verifique que la diferencia de sus cuadrados sea el número original (es decir, 72^2 – 53^2 = 2375).

Un número x es dorado si sus dígitos se pueden separar en dos grupos de igual tamaño tales que para los correspondientes números (a y b) se verifique que la diferencia de sus cuadrados sea el número original (es decir, b^2 – a^2 = x).

Definir la función

   esDorado :: Integer -> Bool

1	esDorado :: Integer -> Bool

tales que (esDorado x) se verifica si x es un número dorado. Por
ejemplo,

   λ> esDorado 2375
   True
   λ> take 5 [x | x <- [1..], esDorado x]
   [48,1023,1404,2325,2375]

λ> esDorado 2375

True

λ> take 5 [x | x <- [1..], esDorado x]

[48,1023,1404,2325,2375]

Soluciones

import Data.List (permutations)

esDorado :: Integer -> Bool
esDorado x =
  even (length (show x)) &&
  or [b^2 - a^2 == x | (a,b) <- particionesNumero x]

-- (particiones xs) es la lista de las formas de dividir xs en dos
-- partes de igual longitud (se supone que xs tiene un número par de
-- elementos). Por ejemplo,
--    λ> particiones "abcd"
--    [("ab","cd"),("ba","cd"),("cb","ad"),("bc","ad"),("ca","bd"),
--     ("ac","bd"),("dc","ba"),("cd","ba"),("cb","da"),("db","ca"),
--     ("bd","ca"),("bc","da"),("da","bc"),("ad","bc"),("ab","dc"),
--     ("db","ac"),("bd","ac"),("ba","dc"),("da","cb"),("ad","cb"),
--     ("ac","db"),("dc","ab"),("cd","ab"),("ca","db")]
particiones :: [a] -> [([a],[a])]
particiones xs =
  [splitAt m ys | ys <- permutations xs]
  where m = length xs `div` 2

-- (particionesNumero n) es la lista de las formas de dividir n en dos
-- partes de igual longitud (se supone que n tiene un número par de
-- dígitos). Por ejemplo,
--    λ> particionesNumero 1234
--    [(12,34),(21,34),(32,14),(23,14),(31,24),(13,24),(43,21),(34,21),
--     (32,41),(42,31),(24,31),(23,41),(41,23),(14,23),(12,43),(42,13),
--     (24,13),(21,43),(41,32),(14,32),(13,42),(43,12),(34,12),(31,42)]
particionesNumero :: Integer -> [(Integer,Integer)]
particionesNumero n =
  [(read xs,read ys) | (xs,ys) <- particiones (show n)]

import Data.List (permutations)

esDorado :: Integer -> Bool

esDorado x =

even (length (show x)) &&

or [b^2 - a^2 == x | (a,b) <- particionesNumero x]

-- (particiones xs) es la lista de las formas de dividir xs en dos

-- partes de igual longitud (se supone que xs tiene un número par de

-- elementos). Por ejemplo,

-- λ> particiones "abcd"

-- [("ab","cd"),("ba","cd"),("cb","ad"),("bc","ad"),("ca","bd"),

-- ("ac","bd"),("dc","ba"),("cd","ba"),("cb","da"),("db","ca"),

-- ("bd","ca"),("bc","da"),("da","bc"),("ad","bc"),("ab","dc"),

-- ("db","ac"),("bd","ac"),("ba","dc"),("da","cb"),("ad","cb"),

-- ("ac","db"),("dc","ab"),("cd","ab"),("ca","db")]

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

particiones xs =

[splitAt m ys | ys <- permutations xs]

where m = length xs `div` 2

-- (particionesNumero n) es la lista de las formas de dividir n en dos

-- partes de igual longitud (se supone que n tiene un número par de

-- dígitos). Por ejemplo,

-- λ> particionesNumero 1234

-- [(12,34),(21,34),(32,14),(23,14),(31,24),(13,24),(43,21),(34,21),

-- (32,41),(42,31),(24,31),(23,41),(41,23),(14,23),(12,43),(42,13),

-- (24,13),(21,43),(41,32),(14,32),(13,42),(43,12),(34,12),(31,42)]

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

particionesNumero n =

[(read xs,read ys) | (xs,ys) <- particiones (show n)]

Sucesión de cuadrados reducidos

PorJosé A. Alonso 5-enero-201712-enero-2017

La sucesión de cuadrados de orden n definida a partir de un número x se forma iniciándola en x y, para cada término z el siguiente es el número formado por los n primeros dígitos del cuadrado de z. Por ejemplo, para n = 4 y x = 1111, el primer término de la sucesión es 1111, el segundo es 1234 (ya que 1111^2 = 1234321) y el tercero es 1522 (ya que 1234^2 = 1522756).

Definir la función

   sucCuadrados :: Int -> Integer -> [Integer]

1	sucCuadrados :: Int -> Integer -> [Integer]

tal que (sucCuadrados n x) es la sucesión de cuadrados de orden n definida a partir de x. Por ejemplo,

   λ> take 10 (sucCuadrados 4 1111)
   [1111,1234,1522,2316,5363,2876,8271,6840,4678,2188]
   λ> take 10 (sucCuadrados 3 457)
   [457,208,432,186,345,119,141,198,392,153]
   λ> take 20 (sucCuadrados 2 55)
   [55,30,90,81,65,42,17,28,78,60,36,12,14,19,36,12,14,19,36,12]

λ> take 10 (sucCuadrados 4 1111)

[1111,1234,1522,2316,5363,2876,8271,6840,4678,2188]

λ> take 10 (sucCuadrados 3 457)

[457,208,432,186,345,119,141,198,392,153]

λ> take 20 (sucCuadrados 2 55)

[55,30,90,81,65,42,17,28,78,60,36,12,14,19,36,12,14,19,36,12]

Soluciones

sucCuadrados :: Int -> Integer -> [Integer]
sucCuadrados n x = iterate (siguiente n) x

siguiente :: Int -> Integer -> Integer
siguiente n x = read (take n (show (x^2)))

sucCuadrados :: Int -> Integer -> [Integer]

sucCuadrados n x = iterate (siguiente n) x

siguiente :: Int -> Integer -> Integer

siguiente n x = read (take n (show (x^2)))

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.

Representación binaria de los números de Carol

PorJosé A. Alonso 28-noviembre-20165-diciembre-2016

Un número de Carol es un número entero de la forma $4^n-2^{n+1}-1$ o, equivalentemente, $(2^n-1)^2-2$ . Los primeros números de Carol son -1, 7, 47, 223, 959, 3967, 16127, 65023, 261119, 1046527.

Definir las funciones

   carol        :: Integer -> Integer
   carolBinario :: Integer -> Integer

1 2	carol :: Integer -> Integer carolBinario :: Integer -> Integer

tales que

(carol n) es el n-ésimo número de Carol. Por ejemplo,

     carol  3  ==  47
     carol  4  ==  223
     carol 25  ==  1125899839733759

carol 3 == 47

carol 4 == 223

carol 25 == 1125899839733759

(carolBinario n) es la representación binaria del n-ésimo número de Carol. Por ejemplo,

     carolBinario 3  ==  101111
     carolBinario 4  ==  11011111
     carolBinario 5  ==  1110111111

carolBinario 3 == 101111

carolBinario 4 == 11011111

carolBinario 5 == 1110111111

Comprobar con QuickCheck que, para n > 2, la representación binaria del n-ésimo número de Carol es el número formado por n-2 veces el dígito 1, seguido por un 0 y a continuación n+1 veces el dígito 1.

Soluciones

import Test.QuickCheck

carol :: Integer -> Integer
carol n = x^2 - 2
  where x = 2^n - 1

carolBinario :: Integer -> Integer
carolBinario = binario . carol

-- (binario x) es el número binario correspondiente al número decimal
-- x. Por ejemplo, 
--    binario 223  ==  11011111
binario :: Integer -> Integer 
binario = digitosAnumero . reverse . int2bin

-- (int2bin x) es el número binario (representado como la lista
-- invertida de sus dígitos) correspondiente al número decimal
-- x. Por ejemplo, 
--    int2bin 223  ==  [1,1,1,1,1,0,1,1]
int2bin :: Integer -> [Integer]
int2bin n | n < 2     = [n]
          | otherwise = n `mod` 2 : int2bin (n `div` 2)

-- (digitosAnumero xs) es el número cuya lista de dígitos es xs. Por
-- ejemplo,  
--    digitosAnumero [3,2,5]  ==  325
digitosAnumero :: [Integer] -> Integer
digitosAnumero xs =
  read (concatMap show xs)

-- En la definición anterior se pueden eliminar el argumento
digitosAnumero2 :: [Integer] -> Integer
digitosAnumero2 = read . (concatMap show)

-- La propiedad es
prop_carol :: Integer -> Property
prop_carol n =
  n > 2 ==> carolBinario n == carolBinario2 n
  where
    carolBinario2 n =
      digitosAnumero ((replicate (m-2) 1) ++ [0] ++ (replicate (m+1) 1))
      where m = fromIntegral n

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

import Test.QuickCheck

carol :: Integer -> Integer

carol n = x^2 - 2

where x = 2^n - 1

carolBinario :: Integer -> Integer

carolBinario = binario . carol

-- (binario x) es el número binario correspondiente al número decimal

-- x. Por ejemplo,

-- binario 223 == 11011111

binario :: Integer -> Integer

binario = digitosAnumero . reverse . int2bin

-- (int2bin x) es el número binario (representado como la lista

-- invertida de sus dígitos) correspondiente al número decimal

-- x. Por ejemplo,

-- int2bin 223 == [1,1,1,1,1,0,1,1]

int2bin :: Integer -> [Integer]

int2bin n | n < 2 = [n]

| otherwise = n `mod` 2 : int2bin (n `div` 2)

-- (digitosAnumero xs) es el número cuya lista de dígitos es xs. Por

-- ejemplo,

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

digitosAnumero :: [Integer] -> Integer

digitosAnumero xs =

read (concatMap show xs)

-- En la definición anterior se pueden eliminar el argumento

digitosAnumero2 :: [Integer] -> Integer

digitosAnumero2 = read . (concatMap show)

-- La propiedad es

prop_carol :: Integer -> Property

prop_carol n =

n > 2 ==> carolBinario n == carolBinario2 n

where

carolBinario2 n =

digitosAnumero ((replicate (m-2) 1) ++ [0] ++ (replicate (m+1) 1))

where m = fromIntegral n

-- La comprobación es

-- λ> quickCheck prop_carol

-- +++ OK, passed 100 tests.

Referencias

Carol number por Shashank Mishra en GeeksforGeeks.
Carol number en la Wikipedia.

Números de Dudeney

PorJosé A. Alonso 18-noviembre-201625-noviembre-2016

La semana pasada, Pepe Muñoz Santonja publicó en su blog Algo más que números el artículo Números de Dudeney en la base OEIS

Un número de Dudeney es un número entero n tal que el cubo de la suma de sus dígitos es igual a n. Por ejemplo, 512 es un número de Dudeney ya que (5+1+2)^3 = 8^3 = 512.

Se puede generalizar variando el exponente: Un número de Dudeney de orden k es un número entero n tal que la potencia k-ésima de la suma de sus dígitos es igual a n. Por ejemplo, 2401 es un número de Dudeney de orden 4 ya que (2+4+0+1)^4 = 7^4 = 2401.

Definir la función

   numerosDudeney :: Integer -> [Integer]

1	numerosDudeney :: Integer -> [Integer]

tal que (numerosDudeney k) es la lista de los números de Dudeney oe orden k. Por ejemplo,

   take 6 (numerosDudeney 3)  == [1,512,4913,5832,17576,19683]
   take 6 (numerosDudeney 4)  == [1,2401,234256,390625,614656,1679616]
   take 2 (numerosDudeney 20) == [1,1215766545905692880100000000000000000000]

take 6 (numerosDudeney 3) == [1,512,4913,5832,17576,19683]

take 6 (numerosDudeney 4) == [1,2401,234256,390625,614656,1679616]

take 2 (numerosDudeney 20) == [1,1215766545905692880100000000000000000000]

Comprobar con QuickCheck que 19683 es el mayor número de Dudeney de orden 3.

Soluciones

import Test.QuickCheck

numerosDudeney :: Integer -> [Integer]
numerosDudeney k =
  [n^k | n <- [1..]
       , esDudeney k (n^k)]

esDudeney :: Integer -> Integer -> Bool
esDudeney k n =
  (sum (digitos n)) ^ k == n

digitos :: Integer -> [Integer]
digitos n = [read [d] | d <- show n]

-- La propiedad es
prop_Dudeney :: Integer -> Property
prop_Dudeney n =
  n > 0 ==> not (esDudeney 3 (19683 + n))
  
-- La comprobación es
--    λ> quickCheck prop_Dudeney
--    +++ OK, passed 100 tests.

import Test.QuickCheck

numerosDudeney :: Integer -> [Integer]

numerosDudeney k =

[n^k | n <- [1..]

, esDudeney k (n^k)]

esDudeney :: Integer -> Integer -> Bool

esDudeney k n =

(sum (digitos n)) ^ k == n

digitos :: Integer -> [Integer]

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

-- La propiedad es

prop_Dudeney :: Integer -> Property

prop_Dudeney n =

n > 0 ==> not (esDudeney 3 (19683 + n))

-- La comprobación es

-- λ> quickCheck prop_Dudeney

-- +++ OK, passed 100 tests.

Números poderosos

PorJosé A. Alonso 17-noviembre-201624-noviembre-2016

Un número es poderoso si es igual a la suma de sus dígitos elevados a sus respectivas posiciones. Por ejemplo, los números 89, 135 y 1306 son poderosos ya que

     89 = 8^1 + 9^2
    135 = 1^1 + 3^2 + 5^3.
   1306 = 1^1 + 3^2 + 0^3 + 6^4

89 = 8^1 + 9^2

135 = 1^1 + 3^2 + 5^3.

1306 = 1^1 + 3^2 + 0^3 + 6^4

Definir la función

   esPoderoso :: Integer -> Bool

1	esPoderoso :: Integer -> Bool

tal que (esPoderoso n) se verifica si n es poderoso. Por ejemplo,

   λ> esPoderoso 135
   True
   λ> esPoderoso 80
   False
   λ> esPoderoso 89
   True
   λ> esPoderoso 12157692622039623539
   True
   λ> [n | n <- [10..30000], esPoderoso n]
   [89,135,175,518,598,1306,1676,2427]

λ> esPoderoso 135

True

λ> esPoderoso 80

False

λ> esPoderoso 89

True

λ> esPoderoso 12157692622039623539

True

λ> [n | n <- [10..30000], esPoderoso n]

[89,135,175,518,598,1306,1676,2427]

Comprobar con QuickCheck que 12157692622039623539 es el mayor número poderoso.

Soluciones

import Test.QuickCheck

esPoderoso :: Integer -> Bool
esPoderoso n =
  sum (zipWith (^) (digitos n) [1..]) == n

digitos :: Integer -> [Integer]
digitos n =
  [read [d] | d <- show n]

-- La propiedad es
prop_poderosos :: Integer -> Property
prop_poderosos n =
  n > 0 ==> not (esPoderoso (12157692622039623539 + n))

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

import Test.QuickCheck

esPoderoso :: Integer -> Bool

esPoderoso n =

sum (zipWith (^) (digitos n) [1..]) == n

digitos :: Integer -> [Integer]

digitos n =

[read [d] | d <- show n]

-- La propiedad es

prop_poderosos :: Integer -> Property

prop_poderosos n =

n > 0 ==> not (esPoderoso (12157692622039623539 + n))

-- La comprobación es

-- λ> quickCheck prop_poderosos

-- +++ OK, passed 100 tests.

Primos de Kamenetsky

PorJosé A. Alonso 4-noviembre-201611-noviembre-2016

Un número primo se dice que es un primo de Kamenetsky si al anteponerlo cualquier dígito se obtiene un número compuesto. Por ejemplo, el 5 es un primo de Kamenetsky ya que 15, 25, 35, 45, 55, 65, 75, 85 y 95 son compuestos. También lo es 149 ya que 1149, 2149, 3149, 4149, 5149, 6149, 7149, 8149 y 9149 son compuestos.

Definir la sucesión

   primosKamenetsky :: [Integer]

1	primosKamenetsky :: [Integer]

tal que sus elementos son los números primos de Kamenetsky. Por ejemplo,

   take 5 primosKamenetsky  ==  [2,5,149,401,509]

1	take 5 primosKamenetsky == [2,5,149,401,509]

Soluciones

import Data.Numbers.Primes (isPrime, primes)

primosKamenetsky :: [Integer]
primosKamenetsky =
  [x | x <- primes
     , esKamenetsky x] 

esKamenetsky :: Integer -> Bool
esKamenetsky x =
  all (not . isPrime) [read (d:xs) | d <- "123456789"]
  where xs = show x

import Data.Numbers.Primes (isPrime, primes)

primosKamenetsky :: [Integer]

primosKamenetsky =

[x | x <- primes

, esKamenetsky x]

esKamenetsky :: Integer -> Bool

esKamenetsky x =

all (not . isPrime) [read (d:xs) | d <- "123456789"]

where xs = show x

Referencias

Sucesión A155762 de la OEIS.
Anteponer un dígito a un primo en «Números y algo más».

Números de Harshad hereditarios

PorJosé A. Alonso 3-noviembre-201610-noviembre-2016

Un número de Harshad es un entero divisible entre la suma de sus dígitos. Por ejemplo, 201 es un número de Harshad porque es divisible por 3 (la suma de sus dígitos). Cuando se elimina el último dígito de 201 se obtiene 20 que también es un número de Harshad. Cuando se elimina el último dígito de 20 se obtiene 2 que también es un número de Harshad. Los números como el 201 que son de Harshad y que los números obtenidos eliminando sus últimos dígitos siguen siendo de Harshad se llaman números de Harshad hereditarios por la derecha. Definir la función

   numeroHHD :: Int -> Bool

1	numeroHHD :: Int -> Bool

tal que (numeroHHD n) se verifica si n es un número de Harshad hereditario por la derecha. Por ejemplo,

   numeroHHD 201  ==  True
   numeroHHD 140  ==  False
   numeroHHD 1104 ==  False

numeroHHD 201 == True

numeroHHD 140 == False

numeroHHD 1104 == False

Calcular el mayor número de Harshad hereditario por la derecha con tres dígitos.

Soluciones

-- (numeroH n) se verifica si n es un número de Harshad.
--    numeroH 201  ==  True
numeroH :: Int -> Bool
numeroH n = rem n (sum (digitos n)) == 0

-- (digitos n) es la lista de los dígitos de n. Por ejemplo,
--    digitos 201  ==  [2,0,1]
digitos :: Int -> [Int]
digitos n = [read [d] | d <- show n]

numeroHHD :: Int -> Bool 
numeroHHD n | n < 10    = True
            | otherwise = numeroH n && numeroHHD (div n 10) 

-- El cálculo es
--    ghci> head [n | n <- [999,998..100], numeroHHD n]
--    902

-- (numeroH n) se verifica si n es un número de Harshad.

-- numeroH 201 == True

numeroH :: Int -> Bool

numeroH n = rem n (sum (digitos n)) == 0

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

-- digitos 201 == [2,0,1]

digitos :: Int -> [Int]

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

numeroHHD :: Int -> Bool

numeroHHD n | n < 10 = True

| otherwise = numeroH n && numeroHHD (div n 10)

-- El cálculo es

-- ghci> head [n | n <- [999,998..100], numeroHHD n]

-- 902

Conjuntos de primos emparejables

PorJosé A. Alonso 9-mayo-201625-abril-2021

Un conjunto de primos emparejables es un conjunto S de números primos tales que al concatenar cualquier par de elementos de S se obtiene un número primo. Por ejemplo, {3, 7, 109, 673} es un conjunto de primos emparejables ya que sus elementos son primos y las concatenaciones de sus parejas son 37, 3109, 3673, 73, 7109, 7673, 1093, 1097, 109673, 6733, 6737 y 673109 son primos.

Definir la función

   emparejables :: Integer -> Integer -> [[Integer]]

1	emparejables :: Integer -> Integer -> [[Integer]]

tal que (emparejables n m) es el conjunto de los conjuntos emparejables de n elementos menores que n. Por ejemplo,

   take 5 (emparejables 2   10)  ==  [[3,7]]
   take 5 (emparejables 3   10)  ==  []
   take 5 (emparejables 2  100)  ==  [[3,7],[3,11],[3,17],[3,31],[3,37]]
   take 5 (emparejables 3  100)  ==  [[3,37,67],[7,19,97]]
   take 5 (emparejables 4  100)  ==  []
   take 5 (emparejables 4 1000)  ==  [[3,7,109,673],[23,311,677,827]]

take 5 (emparejables 2 10) == [[3,7]]

take 5 (emparejables 3 10) == []

take 5 (emparejables 2 100) == [[3,7],[3,11],[3,17],[3,31],[3,37]]

take 5 (emparejables 3 100) == [[3,37,67],[7,19,97]]

take 5 (emparejables 4 100) == []

take 5 (emparejables 4 1000) == [[3,7,109,673],[23,311,677,827]]

Soluciones

import Data.Numbers.Primes (primes, isPrime)
import Data.List (nub, sort)
import qualified Data.Set as S

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

emparejables :: Integer -> Integer -> [[Integer]]
emparejables 0 _ = [[]]
emparejables n m = 
    nub [sort (x:xs) | x <- takeWhile (<=m) primes,
                       xs <- xss,
                       all (x `emparejable`) xs]
    where xss = emparejables (n-1) m

emparejable :: Integer -> Integer -> Bool
emparejable x y =
    isPrime (concatenacion x y) &&
    isPrime (concatenacion y x)

concatenacion :: Integer -> Integer -> Integer
concatenacion x y =
    read (show x ++ show y)

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

emparejables2 :: Integer -> Integer -> [[Integer]]
emparejables2 n m = map reverse (aux n m)
    where aux 1 m = [[x] | x <- takeWhile (<=m) primes]
          aux n m = 
              [p:ys | ys@(x:xs) <- xss,
                      p <- dropWhile (<x) ps,
                      all (p `emparejable`) ys]
              where ps  = takeWhile (<=m) primes
                    xss = aux (n-1) m

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

emparejables3 :: Integer -> Integer -> [[Integer]]
emparejables3 n m = map S.toList (aux n m)
    where aux 1 m = [S.singleton x | x <- takeWhile (<=m) primes]
          aux n m = [S.insert x xs | x <- takeWhile (<=m) primes,
                                     xs <- xss,
                                     all (x `emparejable`) xs]
              where xss = aux (n-1) m

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

emparejables4 :: Integer -> Integer -> [[Integer]]
emparejables4 n m = map S.toList (aux n m)
    where aux 1 m = [S.singleton x | x <- takeWhile (<=m) primes]
          aux n m = 
              [S.insert p ys | ys <- xss,
                               let (x,xs) = S.deleteFindMax ys,
                               p <- dropWhile (<x) ps,
                               all (p `emparejable`) ys]
              where ps  = takeWhile (<=m) primes
                    xss = aux (n-1) m

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

--    λ> head (emparejables 4 1000)
--    [3,7,109,673]
--    (20.36 secs, 11,781,891,120 bytes)
--    
--    λ> head (emparejables2 4 1000)
--    [3,7,109,673]
--    (0.02 secs, 0 bytes)
--    
--    λ> head (emparejables3 4 1000)
--    [3,7,109,673]
--    (38.04 secs, 21,542,334,024 bytes)
--    
--    λ> head (emparejables4 4 1000)
--    [3,7,109,673]
--    (0.03 secs, 0 bytes)

import Data.Numbers.Primes (primes, isPrime)

import Data.List (nub, sort)

import qualified Data.Set as S

-- 1ª definición

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

emparejables :: Integer -> Integer -> [[Integer]]

emparejables 0 _ = [[]]

emparejables n m =

nub [sort (x:xs) | x <- takeWhile (<=m) primes,

xs <- xss,

all (x `emparejable`) xs]

where xss = emparejables (n-1) m

emparejable :: Integer -> Integer -> Bool

emparejable x y =

isPrime (concatenacion x y) &&

isPrime (concatenacion y x)

concatenacion :: Integer -> Integer -> Integer

concatenacion x y =

read (show x ++ show y)

-- 2ª definición

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

emparejables2 :: Integer -> Integer -> [[Integer]]

emparejables2 n m = map reverse (aux n m)

where aux 1 m = [[x] | x <- takeWhile (<=m) primes]

aux n m =

[p:ys | ys@(x:xs) <- xss,

p <- dropWhile (<x) ps,

all (p `emparejable`) ys]

where ps = takeWhile (<=m) primes

xss = aux (n-1) m

-- 3ª definición

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

emparejables3 :: Integer -> Integer -> [[Integer]]

emparejables3 n m = map S.toList (aux n m)

where aux 1 m = [S.singleton x | x <- takeWhile (<=m) primes]

aux n m = [S.insert x xs | x <- takeWhile (<=m) primes,

xs <- xss,

all (x `emparejable`) xs]

where xss = aux (n-1) m

-- 2ª definición

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

emparejables4 :: Integer -> Integer -> [[Integer]]

emparejables4 n m = map S.toList (aux n m)

where aux 1 m = [S.singleton x | x <- takeWhile (<=m) primes]

aux n m =

[S.insert p ys | ys <- xss,

let (x,xs) = S.deleteFindMax ys,

p <- dropWhile (<x) ps,

all (p `emparejable`) ys]

where ps = takeWhile (<=m) primes

xss = aux (n-1) m

-- Comparación de eficiencia

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

-- λ> head (emparejables 4 1000)

-- [3,7,109,673]

-- (20.36 secs, 11,781,891,120 bytes)

-- λ> head (emparejables2 4 1000)

-- [3,7,109,673]

-- (0.02 secs, 0 bytes)

-- λ> head (emparejables3 4 1000)

-- [3,7,109,673]

-- (38.04 secs, 21,542,334,024 bytes)

-- λ> head (emparejables4 4 1000)

-- [3,7,109,673]

-- (0.03 secs, 0 bytes)

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Referencias

Soluciones

Soluciones

Soluciones

Referencias

Soluciones

Soluciones

Entradas recientes

Buscar

Correo electrónico