Medio

Mínima suma borrando todas las ocurrencias de un dígito

PorJosé A. Alonso 15-febrero-202122-febrero-2021

Para la lista [23,12,77,82], las sumas obtenidas eliminando todas las ocurrencias de uno de sus dígitos son

+ Eliminando el 1: 23 +  2 + 77 + 82 = 184
+ Eliminando el 2:  3 + 1  + 77 + 8  =  89
+ Eliminando el 3: 2  + 12 + 77 + 82 = 173
+ Eliminando el 7: 23 + 12      + 82 = 117
+ Eliminando el 8: 23 + 12 + 77 +  2 = 114

+ Eliminando el 1: 23 + 2 + 77 + 82 = 184

+ Eliminando el 2: 3 + 1 + 77 + 8 = 89

+ Eliminando el 3: 2 + 12 + 77 + 82 = 173

+ Eliminando el 7: 23 + 12 + 82 = 117

+ Eliminando el 8: 23 + 12 + 77 + 2 = 114

El mínimo de las sumas es 89 (que se obtiene eliminando todas las ocurrencias del dígito 2).

Definir la función

   minimaSumaEliminandoDigito :: [Integer] -> Integer

1	minimaSumaEliminandoDigito :: [Integer] -> Integer

tal que (minimaSumaEliminandoDigito xs) es el mínimo de las sumas obtenidas eliminando todas las ocurrencias de uno de los dígitos de xs. Por ejemplo,

   minimaSumaEliminandoDigito [23,12,77,82]  ==  89
   minimaSumaEliminandoDigito [2312,7,4,82]  ==  50

1 2	minimaSumaEliminandoDigito [23,12,77,82] == 89 minimaSumaEliminandoDigito [2312,7,4,82] == 50

Soluciones

import Data.List ((\\), nub)

minimaSumaEliminandoDigito :: [Int] -> Int
minimaSumaEliminandoDigito xs =
  minimum [sumaSinDigito k xs | k <- digitosLista xs]

-- (digitosLista xs) es una lista, sin repeticiones, de los dígitos de
-- xs. Por ejemplo,
--    digitosLista [23,12,74,82]  ==  [2,3,1,7,4,8]
digitosLista :: [Int] -> [Int]
digitosLista = nub . concatMap digitos

-- (digitos x) es la lista de los dígitos de x. Por ejemplo,
--    digitos 3252  ==  [3,2,5,2]
digitos :: Int -> [Int]
digitos x = [read [c] | c <- show x]

-- (sumaSinDigito k xs) es la suma de los números de xs en los que se han
-- borrado todas las ocurrencias del dígito k. Por ejemplo,
--    sumaSinDigito 2 [23,12,22,82]  ==  12
sumaSinDigito :: Int -> [Int] -> Int
sumaSinDigito k xs = sum (listaSinDigito k xs)

-- (listaSinDigito k xs) es la lista de los números de xs en los que se han
-- borrado todas las ocurrencias del dígito k. Por ejemplo,
--    listaSinDigito 2 [23,12,22,82]  ==  [3,1,8]
listaSinDigito :: Int -> [Int] -> [Int]
listaSinDigito k xs =
  [read cs | x <- xs
           , let cs = filter (/=c) (show x)
           , not (null cs)]
  where [c] = show k

import Data.List ((\\), nub)

minimaSumaEliminandoDigito :: [Int] -> Int

minimaSumaEliminandoDigito xs =

minimum [sumaSinDigito k xs | k <- digitosLista xs]

-- (digitosLista xs) es una lista, sin repeticiones, de los dígitos de

-- xs. Por ejemplo,

-- digitosLista [23,12,74,82] == [2,3,1,7,4,8]

digitosLista :: [Int] -> [Int]

digitosLista = nub . concatMap digitos

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

-- digitos 3252 == [3,2,5,2]

digitos :: Int -> [Int]

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

-- (sumaSinDigito k xs) es la suma de los números de xs en los que se han

-- borrado todas las ocurrencias del dígito k. Por ejemplo,

-- sumaSinDigito 2 [23,12,22,82] == 12

sumaSinDigito :: Int -> [Int] -> Int

sumaSinDigito k xs = sum (listaSinDigito k xs)

-- (listaSinDigito k xs) es la lista de los números de xs en los que se han

-- borrado todas las ocurrencias del dígito k. Por ejemplo,

-- listaSinDigito 2 [23,12,22,82] == [3,1,8]

listaSinDigito :: Int -> [Int] -> [Int]

listaSinDigito k xs =

[read cs | x <- xs

, let cs = filter (/=c) (show x)

, not (null cs)]

where [c] = show k

Nuevas soluciones

En los comentarios se pueden escribir nuevas soluciones.
El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

Descomposición de N en K sumandos pares distintos

PorJosé A. Alonso 12-febrero-202119-febrero-2021

Definir las funciones

   sumas  :: Integer -> Integer -> [[Integer]]
   esSuma :: Integer -> Integer -> Bool

1 2	sumas :: Integer -> Integer -> [[Integer]] esSuma :: Integer -> Integer -> Bool

tales que

(sumas n k) es la lista de las descomposiones de n en k sumandos pares y distintos. Por ejemplo,

     sumas 16 3  ==  [[2,4,10],[2,6,8]]
     sumas 18 4  ==  []

1 2	sumas 16 3 == [[2,4,10],[2,6,8]] sumas 18 4 == []

(esSuma n k) se verifica si n se puede escribir como suma de k sumandos pares y distintos. Por ejemplo,

     esSuma 16 3  ==  True
     esSuma 18 4  ==  False
     esSuma (10^5000) (10^7)  ==  True
     esSuma (11^5000) (10^7)  ==  False

esSuma 16 3 == True

esSuma 18 4 == False

esSuma (10^5000) (10^7) == True

esSuma (11^5000) (10^7) == False

Soluciones

import Test.QuickCheck

sumas :: Integer -> Integer -> [[Integer]]
sumas n k = sumasLista n k [2,4..n]

-- (sumasLista n k xs) es la lista de las descomposiciones de n como k
-- elementos de xs (cada uno una vez como máximo). Por ejemplo,
--    sumasLista 16 3 [2,4..15]  ==  [[2,4,10],[2,6,8]]
--    sumasLista 18 4 [2,4..15]  ==  []
sumasLista :: Integer -> Integer -> [Integer] -> [[Integer]]
sumasLista _ _ [] = []
sumasLista n 1 xs
  | n `elem` xs = [[n]]
  | otherwise   = []
sumasLista n k (x:xs)
  | x > n     = []
  | otherwise = [x:ys | ys <- sumasLista (n-x) (k-1) xs] ++
                sumasLista n k xs

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

esSuma :: Integer -> Integer -> Bool
esSuma n k = not (null (sumas n k))

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

-- Se observan las siguientes propiedades:
-- 1. Si n es impar, no se puede escribir como suma de pares.
-- 2. El menor número que se puede escribir como suma de k sumandos
--    impares distintos es 2 * sum [1..k] y su descomposición es
--    [2,4..2*k] (es decir, map (*2) [1..k]).
-- 3. Si n es un número par mayor o igual que (2 * sum [1..k])
--    entonces se puede escribir como suma de k sumandos pares distintos;
--    en efecto,
--       x = 2 + 4 + ··· + 2*(k-1) + (x - (2 + 4 + ··· + 2*(k-1))

esSuma2 :: Integer -> Integer -> Bool
esSuma2 n k
  | odd n               = False
  | 2 * sum [1..k] <= n = True
  | otherwise           = False

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

esSuma3 :: Integer -> Integer -> Bool
esSuma3 n k
  | odd n            = False
  | k * (k + 1) <= n = True
  | otherwise        = False

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

-- La propiedad es
prop_equiv_esSuma :: Integer -> Integer -> Property
prop_equiv_esSuma n k =
  n > 0 && k > 0 ==>
  all (== (esSuma3 n k)) [esSuma n k, esSuma2 n k]

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

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

-- La comparación es
--    λ> esSuma 200 20
--    False
--    (6.12 secs, 3,079,059,560 bytes)
--    λ> esSuma2 200 20
--    False
--    (0.00 secs, 102,800 bytes)
--    λ> esSuma3 200 20
--    False
--    (0.01 secs, 102,760 bytes)
--
--    λ> esSuma2 (10^5000) (10^7)
--    True
--    (2.55 secs, 1,612,412,664 bytes)
--    λ> esSuma3 (10^5000) (10^7)
--    True
--    (0.03 secs, 109,200 bytes)

import Test.QuickCheck

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

sumas n k = sumasLista n k [2,4..n]

-- (sumasLista n k xs) es la lista de las descomposiciones de n como k

-- elementos de xs (cada uno una vez como máximo). Por ejemplo,

-- sumasLista 16 3 [2,4..15] == [[2,4,10],[2,6,8]]

-- sumasLista 18 4 [2,4..15] == []

sumasLista :: Integer -> Integer -> [Integer] -> [[Integer]]

sumasLista _ _ [] = []

sumasLista n 1 xs

| n `elem` xs = [[n]]

| otherwise = []

sumasLista n k (x:xs)

| x > n = []

| otherwise = [x:ys | ys <- sumasLista (n-x) (k-1) xs] ++

sumasLista n k xs

-- 1ª definición de esSuma

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

esSuma :: Integer -> Integer -> Bool

esSuma n k = not (null (sumas n k))

-- 2ª definición de esSuma

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

-- Se observan las siguientes propiedades:

-- 1. Si n es impar, no se puede escribir como suma de pares.

-- 2. El menor número que se puede escribir como suma de k sumandos

-- impares distintos es 2 * sum [1..k] y su descomposición es

-- [2,4..2*k] (es decir, map (*2) [1..k]).

-- 3. Si n es un número par mayor o igual que (2 * sum [1..k])

-- entonces se puede escribir como suma de k sumandos pares distintos;

-- en efecto,

-- x = 2 + 4 + ··· + 2*(k-1) + (x - (2 + 4 + ··· + 2*(k-1))

esSuma2 :: Integer -> Integer -> Bool

esSuma2 n k

| odd n = False

| 2 * sum [1..k] <= n = True

| otherwise = False

-- 3ª definición de esSuma

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

esSuma3 :: Integer -> Integer -> Bool

esSuma3 n k

| odd n = False

| k * (k + 1) <= n = True

| otherwise = False

-- Comprobación de equivalencia

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

-- La propiedad es

prop_equiv_esSuma :: Integer -> Integer -> Property

prop_equiv_esSuma n k =

n > 0 && k > 0 ==>

all (== (esSuma3 n k)) [esSuma n k, esSuma2 n k]

-- La comprobación es

-- λ> quickCheck prop_equiv_esSuma

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> esSuma 200 20

-- False

-- (6.12 secs, 3,079,059,560 bytes)

-- λ> esSuma2 200 20

-- False

-- (0.00 secs, 102,800 bytes)

-- λ> esSuma3 200 20

-- False

-- (0.01 secs, 102,760 bytes)

-- λ> esSuma2 (10^5000) (10^7)

-- True

-- (2.55 secs, 1,612,412,664 bytes)

-- λ> esSuma3 (10^5000) (10^7)

-- True

-- (0.03 secs, 109,200 bytes)

Nuevas soluciones

En los comentarios se pueden escribir nuevas soluciones.
El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

Los números armónicos no son enteros

PorJosé A. Alonso 3-febrero-202110-febrero-2021

Los números armónicos son las sumas de los inversos de de los primeros números enteros positivos; es decir, el n-ésimo número armónico es

   H(n) = 1 + 1/2 + 1/3 + ··· + 1/n

1	H(n) = 1 + 1/2 + 1/3 + ··· + 1/n

Los primeros números armónicos son

   1, 3/2, 11/6, 25/12, 137/60, ..

1	1, 3/2, 11/6, 25/12, 137/60, ..

Definir, usando la librería de los números racionales (Data.Ratio), las funciones

   armonico  :: Integer -> Rational
   armonicos :: [Rational]
   esEntero  :: Rational -> Bool

armonico :: Integer -> Rational

armonicos :: [Rational]

esEntero :: Rational -> Bool

tales que

(armonico n) es el n-ésimo número armónico. Por ejemplo,

     armonico 2  ==    3 % 2
     armonico 3  ==   11 % 6
     armonico 4  ==   25 % 12
     armonico 5  ==  137 % 60

armonico 2 == 3 % 2

armonico 3 == 11 % 6

armonico 4 == 25 % 12

armonico 5 == 137 % 60

armonicos es la lista de los números armónicos. Por ejemplo,

     take 5 armonicos  ==  [1 % 1,3 % 2,11 % 6,25 % 12,137 % 60]

1	take 5 armonicos == [1 % 1,3 % 2,11 % 6,25 % 12,137 % 60]

(esEntero x) se verifica si x es un número entero. Por ejemplo,

     esEntero (1 % 7)           ==  False
     esEntero (1 % 7 + 20 % 7)  ==  True

1 2	esEntero (1 % 7) == False esEntero (1 % 7 + 20 % 7) == True

Comprobar con QuickCheck que

nigún número armónico, excepto el primero, es un número entero y
la diferencia de dos números armónicos distintos nunca es un número entero.

Nota: Este ejercicio está basado en el artículo Sums of consecutive reciprocals publicado por John D. Cook en su blog el 23 de enero de 2021.

Soluciones

import Data.List (genericIndex)
import Data.Ratio ((%), denominator)
import Test.QuickCheck (Property, (==>), quickCheck)

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

armonico  :: Integer -> Rational
armonico 1 = 1
armonico n = 1 % n + armonico (n-1)

armonicos :: [Rational]
armonicos = map armonico [1..]

esEntero  :: Rational -> Bool
esEntero x = denominator x == 1

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

armonicos2 :: [Rational]
armonicos2 = scanl1 (\ x y -> x + y) [1 % n | n <- [1..]]

armonico2  :: Integer -> Rational
armonico2 n = armonicos `genericIndex` n

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

-- La comparación es
--    λ> fromRational (armonicos !! (10^4))
--    9.787706026045383
--    (9.17 secs, 29,293,137,856 bytes)
--    λ> fromRational (armonicos2 !! (10^4))
--    9.787706026045383
--    (9.42 secs, 29,292,225,904 bytes)

-- Propiedades
-- ===========

-- La 1ª propiedad es
prop_armonicos :: Integer -> Property
prop_armonicos n =
  n > 1 ==>
  not (esEntero (armonico n))

-- La comprobación de la 1ª propiedad es
--    λ> quickCheck prop_armonicos
--    +++ OK, passed 100 tests.

-- La 2ª propiedad es
prop_armonicos2 :: Integer -> Integer -> Property
prop_armonicos2 n m =
  n > 0 && m > 0 && n /= m ==>
  not (esEntero (armonico n - armonico m))

-- La comprobación de la segunda propiedad es
--   λ> quickCheck prop_armonicos2
--   +++ OK, passed 100 tests.

import Data.List (genericIndex)

import Data.Ratio ((%), denominator)

import Test.QuickCheck (Property, (==>), quickCheck)

-- 1ª solución

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

armonico :: Integer -> Rational

armonico 1 = 1

armonico n = 1 % n + armonico (n-1)

armonicos :: [Rational]

armonicos = map armonico [1..]

esEntero :: Rational -> Bool

esEntero x = denominator x == 1

-- 2ª solución

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

armonicos2 :: [Rational]

armonicos2 = scanl1 (\ x y -> x + y) [1 % n | n <- [1..]]

armonico2 :: Integer -> Rational

armonico2 n = armonicos `genericIndex` n

-- Comparación de eficiencia

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

-- La comparación es

-- λ> fromRational (armonicos !! (10^4))

-- 9.787706026045383

-- (9.17 secs, 29,293,137,856 bytes)

-- λ> fromRational (armonicos2 !! (10^4))

-- 9.787706026045383

-- (9.42 secs, 29,292,225,904 bytes)

-- Propiedades

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

-- La 1ª propiedad es

prop_armonicos :: Integer -> Property

prop_armonicos n =

n > 1 ==>

not (esEntero (armonico n))

-- La comprobación de la 1ª propiedad es

-- λ> quickCheck prop_armonicos

-- +++ OK, passed 100 tests.

-- La 2ª propiedad es

prop_armonicos2 :: Integer -> Integer -> Property

prop_armonicos2 n m =

n > 0 && m > 0 && n /= m ==>

not (esEntero (armonico n - armonico m))

-- La comprobación de la segunda propiedad es

-- λ> quickCheck prop_armonicos2

-- +++ OK, passed 100 tests.

Nuevas soluciones

En los comentarios se pueden escribir nuevas soluciones.
El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

Partición por suma

PorJosé A. Alonso 2-febrero-20219-febrero-2021

Definir la función

   particion :: Int -> [Int] -> [[Int]]

1	particion :: Int -> [Int] -> [[Int]]

tal que (particion n xs) es la lista de los elementos de xs, en el mismo orden, agrupados en listas con sumas menores o iguales que n. Por ejemplo,

   particion 6 [1,1,1,3,2,2,2,1,2,2,3]   ==  [[1,1,1,3],[2,2,2],[1,2,2],[3]]
   particion 5 [1,1,1,3,2,2,2,1,2,2,3]   ==  [[1,1,1],[3,2],[2,2,1],[2,2],[3]]
   particion 4 [1,1,1,3,2,2,2,1,2,2,3]   ==  [[1,1,1],[3],[2,2],[2,1],[2,2],[3]]
   particion 3 [1,1,1,3,2,2,2,1,2,2,3]   ==  [[1,1,1],[3],[2],[2],[2,1],[2],[2],[3]]
   particion 2 [1,1,1,3,2,2,2,1,2,2,3]   ==  []

particion 6 [1,1,1,3,2,2,2,1,2,2,3] == [[1,1,1,3],[2,2,2],[1,2,2],[3]]

particion 5 [1,1,1,3,2,2,2,1,2,2,3] == [[1,1,1],[3,2],[2,2,1],[2,2],[3]]

particion 4 [1,1,1,3,2,2,2,1,2,2,3] == [[1,1,1],[3],[2,2],[2,1],[2,2],[3]]

particion 3 [1,1,1,3,2,2,2,1,2,2,3] == [[1,1,1],[3],[2],[2],[2,1],[2],[2],[3]]

particion 2 [1,1,1,3,2,2,2,1,2,2,3] == []

Soluciones

particion :: Int -> [Int] -> [[Int]]
particion n xs = reverse (map reverse (aux xs [[]]))
  where aux []     yss      = yss
        aux (x:xs) (ys:yss) | x > n           = []
                            | x + sum ys <= n = aux xs ((x:ys):yss)
                            | otherwise       = aux xs ([x]:ys:yss)

particion :: Int -> [Int] -> [[Int]]

particion n xs = reverse (map reverse (aux xs [[]]))

where aux [] yss = yss

aux (x:xs) (ys:yss) | x > n = []

| x + sum ys <= n = aux xs ((x:ys):yss)

| otherwise = aux xs ([x]:ys:yss)

Nuevas soluciones

En los comentarios se pueden escribir nuevas soluciones.
El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

Con algún nueve

PorJosé A. Alonso 1-febrero-20218-febrero-2021

Definir las funciones

   numerosConNueve :: [Integer]
   conNueve :: Integer -> Integer

1 2	numerosConNueve :: [Integer] conNueve :: Integer -> Integer

tales que

numerosConNueve es la lista de los números con algún dígito igual a 9. Por ejemplo,

     λ> take 20 numerosConNueve
     [9,19,29,39,49,59,69,79,89,90,91,92,93,94,95,96,97,98,99,109]

1 2	λ> take 20 numerosConNueve [9,19,29,39,49,59,69,79,89,90,91,92,93,94,95,96,97,98,99,109]

(conNueve n) es la cantidad de números enteros no negativos menores o iguales que n con algún dígito igual a 9. Por ejemplo,

     conNueve 1   ==  0
     conNueve 10  ==  1
     conNueve 90  ==  10
     length (show (conNueve (10^3)))      ==  3
     length (show (conNueve (10^30)))     ==  30
     length (show (conNueve (10^300)))    ==  300
     length (show (conNueve (10^3000)))   ==  3000
     length (show (conNueve (10^30000)))  ==  30000

conNueve 1 == 0

conNueve 10 == 1

conNueve 90 == 10

length (show (conNueve (10^3))) == 3

length (show (conNueve (10^30))) == 30

length (show (conNueve (10^300))) == 300

length (show (conNueve (10^3000))) == 3000

length (show (conNueve (10^30000))) == 30000

Soluciones

import Data.List (genericLength)
import Test.QuickCheck (Property, (==>), quickCheck)

numerosConNueve :: [Integer]
numerosConNueve = filter tieneNueve [9..]

-- (tieneNueve n) se verifica si algún dígito de n es igual a 9. Por
-- ejemplo,
--    tieneNueve 2919  ==  True
--    tieneNueve 2717  ==  False
tieneNueve :: Integer -> Bool
tieneNueve n = '9' `elem` show n

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

conNueve :: Integer -> Integer
conNueve n =
  genericLength (takeWhile (<= n) numerosConNueve)

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

conNueve2 :: Integer -> Integer
conNueve2 0 = 0
conNueve2 n
  | tieneNueve n = 1 + conNueve2 (n-1)
  | otherwise   = conNueve2 (n-1)

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

conNueve3 :: Integer -> Integer
conNueve3 n = n + 1 - sinNueve n

-- (sinNueve n) es la cantidad de números enteros no negativos menores
-- o iguales que n con ningún dígito igual a 9. Por ejemplo,
--    sinNueve 1   ==  2
--    sinNueve 9   ==  9
--    sinNueve 90  ==  81
sinNueve :: Integer -> Integer
sinNueve n = aux (digitos n)
  where aux []     = 0
        aux [9]    = 9
        aux [x]    = x+1
        aux (9:xs) = 9^(1 + length xs)
        aux (x:xs) = x*9^(length xs) + aux xs

-- (digitos n) es la lista de los dígitod de n. Por ejemplo,
--    digitos 2021  ==  [2,0,2,1]
digitos :: Integer -> [Integer]
digitos n = [read [c] | c <- show n]

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

conNueve4 :: Integer -> Integer
conNueve4 n = n + 1 - sinNueve2 n

sinNueve2 :: Integer -> Integer
sinNueve2 n = aux ds (length ds)
  where ds = digitos n
        aux []     _ = 0
        aux [9]    _ = 9
        aux [x]    _ = x+1
        aux (9:xs) m = 9^m
        aux (x:xs) m = x*9^(m-1) + aux xs (m-1)

-- Comprobacion de equivalencia
-- ============================

-- La propiedad es
prop_conNueve_equiv :: Integer -> Property
prop_conNueve_equiv n =
  n >= 0 ==>
  all (== (conNueve n))
      [conNueve2 n,
       conNueve3 n,
       conNueve4 n]

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

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

-- La comparación es
--    λ> conNueve (10^7)
--    5217031
--    (5.21 secs, 5,215,047,968 bytes)
--    λ> conNueve2 (10^7)
--    5217031
--    (8.25 secs, 5,651,944,872 bytes)
--    λ> conNueve3 (10^7)
--    5217031
--    (0.02 secs, 144,000 bytes)
--    λ> conNueve4 (10^7)
--    5217031
--    (0.02 secs, 145,904 bytes)
--
--    λ> length (show (conNueve3 (10^30000)))
--    30000
--    (3.24 secs, 776,076,072 bytes)
--    λ> length (show (conNueve4 (10^30000)))
--    30000
--    (2.00 secs, 786,452,856 bytes)

100

101

102

103

104

105

106

107

import Data.List (genericLength)

import Test.QuickCheck (Property, (==>), quickCheck)

numerosConNueve :: [Integer]

numerosConNueve = filter tieneNueve [9..]

-- (tieneNueve n) se verifica si algún dígito de n es igual a 9. Por

-- ejemplo,

-- tieneNueve 2919 == True

-- tieneNueve 2717 == False

tieneNueve :: Integer -> Bool

tieneNueve n = '9' `elem` show n

-- 1ª definición de conNueve

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

conNueve :: Integer -> Integer

conNueve n =

genericLength (takeWhile (<= n) numerosConNueve)

-- 2ª definición de conNueve

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

conNueve2 :: Integer -> Integer

conNueve2 0 = 0

conNueve2 n

| tieneNueve n = 1 + conNueve2 (n-1)

| otherwise = conNueve2 (n-1)

-- 3ª definición de conNueve

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

conNueve3 :: Integer -> Integer

conNueve3 n = n + 1 - sinNueve n

-- (sinNueve n) es la cantidad de números enteros no negativos menores

-- o iguales que n con ningún dígito igual a 9. Por ejemplo,

-- sinNueve 1 == 2

-- sinNueve 9 == 9

-- sinNueve 90 == 81

sinNueve :: Integer -> Integer

sinNueve n = aux (digitos n)

where aux [] = 0

aux [9] = 9

aux [x] = x+1

aux (9:xs) = 9^(1 + length xs)

aux (x:xs) = x*9^(length xs) + aux xs

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

-- digitos 2021 == [2,0,2,1]

digitos :: Integer -> [Integer]

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

-- 4ª definición de conNueve

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

conNueve4 :: Integer -> Integer

conNueve4 n = n + 1 - sinNueve2 n

sinNueve2 :: Integer -> Integer

sinNueve2 n = aux ds (length ds)

where ds = digitos n

aux [] _ = 0

aux [9] _ = 9

aux [x] _ = x+1

aux (9:xs) m = 9^m

aux (x:xs) m = x*9^(m-1) + aux xs (m-1)

-- Comprobacion de equivalencia

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

-- La propiedad es

prop_conNueve_equiv :: Integer -> Property

prop_conNueve_equiv n =

n >= 0 ==>

all (== (conNueve n))

[conNueve2 n,

conNueve3 n,

conNueve4 n]

-- La comprobación es

-- λ> quickCheck prop_conNueve_equiv

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> conNueve (10^7)

-- 5217031

-- (5.21 secs, 5,215,047,968 bytes)

-- λ> conNueve2 (10^7)

-- 5217031

-- (8.25 secs, 5,651,944,872 bytes)

-- λ> conNueve3 (10^7)

-- 5217031

-- (0.02 secs, 144,000 bytes)

-- λ> conNueve4 (10^7)

-- 5217031

-- (0.02 secs, 145,904 bytes)

-- λ> length (show (conNueve3 (10^30000)))

-- 30000

-- (3.24 secs, 776,076,072 bytes)

-- λ> length (show (conNueve4 (10^30000)))

-- 30000

-- (2.00 secs, 786,452,856 bytes)

Nuevas soluciones

En los comentarios se pueden escribir nuevas soluciones.
El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

Mínima suma borrando todas las ocurrencias de un dígito

Soluciones

Nuevas soluciones

Descomposición de N en K sumandos pares distintos

Soluciones

Nuevas soluciones

Los números armónicos no son enteros

Soluciones

Nuevas soluciones

Partición por suma

Soluciones

Nuevas soluciones

Con algún nueve

Soluciones

Nuevas soluciones

Entradas recientes

Buscar

Correo electrónico